Saturday 22 November 2008

my thought process for breadth first numbering


data Tree a = Leaf a | Branch a (Tree a) (Tree a) deriving Show

i 0 = Leaf 0
i n = Branch 0 (i (n-1)) (i (n-1))


identity (Leaf i) = Leaf i
identity (Branch i left right) = Branch i (identity left) (identity right)


depth current (Leaf _) = Leaf current
depth current (Branch _ left right) = Branch current (depth (current + 1) left) (depth (current + 1) right)


depth' current (Leaf i) = Leaf i
depth' current (Branch i left right) = Branch i left' right'
where left' = depth' (current + 1) left
right' = depth' (current + 1) right


depth'' current target (Leaf i) = Leaf (if current == target then i+1 else i)
depth'' current target (Branch i left right) = Branch (if current == target then i+1 else i) left' right'
where left' = depth'' (current + 1) target left
right' = depth'' (current + 1) target right


depth''' current target delta (Leaf i) = Leaf (if current == target then i+delta else i) `with` (if current == target then delta+1 else delta)
depth''' current target delta (Branch i left right) = Branch (if current == target then i+delta else i) left' right' `with` delta''
where (left',delta') = depth''' (current + 1) target (if current == target then delta+1 else delta) left
(right',delta'') = depth''' (current + 1) target delta' right

with = (,)


unfold step current = case step current of Nothing -> current ; Just next -> unfold step next


breadth tree = case unfold step (0,0,tree) of (_,_,tree) -> tree
where step (depth, delta, tree) = case depth''' 0 depth delta tree of
(tree, delta') -> if delta == delta' then Nothing else Just (depth + 1, delta', tree)

-- > breadth (i 3)
-- Branch 0 (Branch 1 (Branch 3 (Leaf 7)
-- (Leaf 8))
-- (Branch 4 (Leaf 9)
-- (Leaf 10)))
-- (Branch 2 (Branch 5 (Leaf 11)
-- (Leaf 12))
-- (Branch 6 (Leaf 13)
-- (Leaf 14)))

No comments: