«
»

Breadth first labelling

March 6th, 2009 by Graham

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)

This entry was posted on Friday, March 6th, 2009 at 2:32 pm and is filed under Lunches. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Breadth first labelling”

  1. Sebastian Hanowski Says:
    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)

  2. Leon Smith Says:
    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.

Leave a Reply