Use the source's constructor order: left subtree, root value, right subtree.A tree fold replaces the two constructors by an algebra on already folded children. A tree unfold expands a seed either into the empty tree or into a root value and two new seeds. The definitions themselves work on arbitrary binary trees; preserving the binary search tree ordering requires the supplied algebra or seed expansion to respect its bounds.
data Tree a = Tree (Tree a) a (Tree a) | Empty
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree node empty Empty = empty
foldTree node empty (Tree l x r) =
node (foldTree node empty l) x (foldTree node empty r)
unfoldTree :: (s -> Maybe (s,a,s)) -> s -> Tree a
unfoldTree next seed = case next seed of
Nothing -> Empty
Just (ls,x,rs) ->
Tree (unfoldTree next ls) x (unfoldTree next rs)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.Choose the middle element as the root:The input is a finite, strictly ascending list, as required for distinct elements of a set. The two child lengths differ by at most one. Applying the same argument recursively gives a balanced binary tree of logarithmic height. All values on each side retain their original order, proving the binary search tree property. With linked lists, the repeated splitting gives time; it does not repeatedly insert values into a skewed tree.
build :: [a] -> Tree a
build [] = Empty
build xs = Tree (build ls) x (build rs)
where
(ls,x:rs) = splitAt (length xs `div` 2) xsUse the remaining ascending list itself as the seed:The empty seed produces
buildUnfold :: [a] -> Tree a
buildUnfold = unfoldTree split
where
split [] = Nothing
split xs =
let (ls,x:rs) = splitAt (length xs `div` 2) xs
in Just (ls,x,rs)Empty. Every nonempty seed produces exactly the midpoint and two child seeds used by build. Thus the defining equations agree, and structural induction on the finite input proves buildUnfold xs = build xs. The balance and ordering arguments carry over unchanged.Fold into a membership predicate:At an empty tree the predicate is always false. At a nonempty binary search tree, an unequal query can occur only in the indicated child, while equality finds the root. This proves correctness inductively. Under lazy evaluation, the unused folded child is not demanded; lookup follows one root-to-leaf route and takes comparisons in a tree of height . Defining the predicate by a fold does not require visiting both subtrees for each query.
find :: Ord a => Tree a -> a -> Bool
find = foldTree node (const False)
where
node left x right q = case compare q x of
LT -> left q
EQ -> True
GT -> right qInsert down the unique search route, leaving equal elements unchanged:The binary search tree ordering determines the only child in which a missing query can belong. The recursive call preserves that child's ordering bounds, and the other child is shared. Thus the output represents the original set with
insert :: Ord a => a -> Tree a -> Tree a
insert q Empty = Tree Empty q Empty
insert q t@(Tree l x r) = case compare q x of
LT -> Tree (insert q l) x r
EQ -> t
GT -> Tree l x (insert q r)q added, with duplicates suppressed. Its time complexity and newly allocated route length are ; it makes no balancing guarantee.A tree fold can compute insertion while retaining the unchanged children by carrying a pair. The following fold-derived implementation preserves the lazy evaluation behaviour of part (f):The invariant of the folded pair is
insertViaFold :: Ord a => a -> Tree a -> Tree a
insertViaFold q t = snd (foldTree node base t)
where
base = (Empty, Tree Empty q Empty)
node ~(l,li) x ~(r,ri) = (original,updated)
where
original = Tree l x r
updated = case compare q x of
LT -> Tree li x r
EQ -> original
GT -> Tree l x ri(original subtree, subtree with q inserted). The empty case establishes it. At a node, the first components reconstruct the original tree, and the second components supply whichever child insertion is needed. The irrefutable pair patterns ~(l,li) and ~(r,ri) avoid demanding an unused child's fold. Induction on finite approximations therefore proves equivalence even for partial trees, and only the selected search route needs insertion work.There is a distinction if “written as a fold” is required to mean a direct same-result-type expression Here
insert q = foldTree node base, with no richer result and final projection. On finite fully defined binary search trees, such an expression is possible by undoing insertion of a new extreme key in the child that should remain unchanged. For completeness, a literal direct fold on that finite, fully defined domain is:eraseFresh :: Ord a => a -> Tree a -> Tree a
eraseFresh _ Empty = Empty
eraseFresh q (Tree l x r) = case compare q x of
LT -> Tree (eraseFresh q l) x r
EQ -> Empty
GT -> Tree l x (eraseFresh q r)
insertDirectFold :: Ord a => a -> Tree a -> Tree a
insertDirectFold q = foldTree node (Tree Empty q Empty)
where
node left x right = case compare q x of
LT -> Tree left x (eraseFresh q right)
EQ -> Tree (eraseFresh q left) x (eraseFresh q right)
GT -> Tree (eraseFresh q left) x righteraseFresh is used only to undo a newly inserted extreme key, which is a leaf; it is not a general deletion operation. The binary search tree bound at each root guarantees exactly that precondition on every child being restored.On all partial Haskell trees, however, a direct expression with result type
Tree a cannot implement part (f).For that obstruction, fix Both can be completed to valid right subtrees of a root labelled
q = 0, and consider the two right subtreesr1 = Tree Empty undefined Empty
r2 = Tree Empty undefined (Tree Empty 3 Empty)1. Yet insert 0 r1 and insert 0 r2 are both bottom, because insertion must compare 0 with their undefined root label. A direct fold equal to insertion would therefore receive the same folded left value, root 1, and bottom folded right value on both larger trees Tree Empty 1 r1 and Tree Empty 1 r2. It must return the same result. Part (f) instead preserves r1 or r2, which are distinguishable by inspecting their right-child constructors without inspecting the undefined labels. This proves the direct-fold obstruction. The pair-valued implementation avoids losing that information and states precisely which sense of fold implementation is being used. Articles by others on the same topic
There are currently no matching articles.