by Graham on March 6, 2009.
Tagged as: Lunches.
I 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)