## Breadth first labelling

March 6th, 2009 by GrahamI talked about Jones and Gibbons’ breadth first labelling algorithm, which uses cyclic programming:

-- Binary trees with labels in the nodes: data Tree a = Leaf | Node (Tree a) a (Tree a) -- Breadth first labelling function that works by taking a -- stream comprising the first label for each level as an -- additional argument, and returning a stream comprising -- the next label for each level as an additional result: label' :: Tree a -> [Int] -> (Tree Int, [Int]) label' Leaf ns = (Leaf, ns) label' (Node l x r) (n:ns) = (Node l' n r', n+1 : ns'') where (l',ns') = label' l ns (r',ns'') = label' r ns' -- The desired stream of labels itself can then be constructed -- by feeding the result stream back as the argument stream: label :: Tree a -> Tree Int label t = t' where (t',ns) = label' t (1:ns)

Various related topics were then discussed, including Banach’s fixed point theorem (Thorsten), the construction of final co-algebras (Thorsten), and a queue-based algorithm due to Okasaki (Nisse)

March 16th, 2009 at 6:23 am

– Here’s a way to get rid of the spooky semantics of this

– program:

–

– model it as an interactive program, feed it with a 1 and

– then copy it’s output to it’s input.

data Tree a = Leaf | Node (Tree a) a (Tree a)

type OI a = ([Int],[Int]) -> (a ,[Int],[Int])

returnOI :: a -> OI a

returnOI a = \(i,o) -> (a,i,o)

bindOI :: OI a -> (a -> OI b) -> OI b

c `bindOI` f = \(i,o”) -> let

(a,i’,o) = c (i,o’)

(b,i”,o’) = f a (i’,o”)

in

(b,i”,o)

readOI :: OI Int

readOI = \(n:i,o) -> (n,i,o)

writeOI :: Int -> OI ()

writeOI n = \(i,o) -> ((),i,n:o)

label’ :: Tree a -> OI (Tree Int)

label’ Leaf = returnOI Leaf

label’ (Node l _ r) = readOI `bindOI` \n ->

writeOI (n+1) `bindOI` \_ ->

label’ l `bindOI` \l’ ->

label’ r `bindOI` \r’ ->

returnOI (Node l’ n r’)

unsafePerformOI :: OI a -> a

unsafePerformOI k = a

where

(a,o,i) = k (1:i,o)

label :: Tree a -> Tree Int

label t = unsafePerformOI (label’ t)

April 14th, 2009 at 8:38 pm

@Sebastian: that was a very interesting attempt, I had to try it myself! Unfortunately you did not implement breadth-first renumbering.