The direct tree fold for an inorder traversal isBy structural induction, the child lists are ascending; the binary search tree property places every left value below the root and every right value above it. The displayed list concatenation therefore gives an ascending list containing every stored value exactly once.
flattenFold :: Tree a -> [a]
flattenFold = foldTree (\ls x rs -> ls ++ (x:rs)) []For a version with linear time complexity on every tree shape, use an accumulator:This also has a higher-order tree fold expression using difference lists:Its folded value is a function that prepends the inorder traversal to a supplied tail. The accumulator invariant is
flatten :: Tree a -> [a]
flatten t = onto t []
where
onto Empty zs = zs
onto (Tree l x r) zs = onto l (x : onto r zs)flattenLinear :: Tree a -> [a]
flattenLinear t =
foldTree (\l x r -> l . (x:) . r) id t []onto t zs = flattenFold t ++ zs. Each node contributes one constructor, giving time to consume the output. By contrast, the direct list-valued fold can take on a left-skewed tree because ++ repeatedly copies left traversals. Articles by others on the same topic
There are currently no matching articles.