## Saturday, 22 November 2008

### my thought process for breadth first numbering

`data Tree a = Leaf a | Branch a (Tree a) (Tree a) deriving Showi 0 = Leaf 0i n = Branch 0 (i (n-1)) (i (n-1))identity (Leaf i) = Leaf iidentity (Branch i left right) = Branch i (identity left) (identity right)depth current (Leaf _) = Leaf currentdepth current (Branch _ left right) = Branch current (depth (current + 1) left) (depth (current + 1) right)depth' current (Leaf i) = Leaf idepth' current (Branch i left right) = Branch i left' right' where left' = depth' (current + 1) left       right' = depth' (current + 1) rightdepth'' 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 rightdepth''' 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' rightwith = (,)unfold step current = case step current of Nothing -> current ; Just next -> unfold step nextbreadth 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)))`