A tree fold first folds every child rose tree, then supplies the resulting list and the current label to the combining function:The label type
foldRTree :: (a -> [b] -> b) -> RTree a -> b
foldRTree f (Node x children) =
f x (map (foldRTree f) children)a and result type b are independent, so the polymorphic type needs no class constraint. With f x ys = x + sum ys, every label is counted exactly once; the illustrated labels sum to 28.The printed source gives the signature
exampleRTree but binds exampleRTRee, with different capitalization. They are different Haskell names; the demonstration requires using one spelling consistently. This typo does not affect the tree fold definition.Compute either the common depth of the leaves of a rooted tree, or failure when the depths differ. A tree fold can return a A leaf has depth zero. An internal vertex has equally deep leaves exactly when every child rose tree is perfect and their returned depths agree; adding one accounts for the edge to each child. This proves the stated meaning of the result by structural induction. In particular, unary branching is allowed, and a single leaf is perfect.
Maybe Integer: Just h means that the rose tree is a perfect rose tree with all leaves at depth relative to its root; Nothing means it is not perfect.perfect :: RTree a -> Bool
perfect t =
case foldRTree step t of
Nothing -> False
Just _ -> True
where
step :: a -> [Maybe Integer] -> Maybe Integer
step _ [] = Just 0
step _ (Nothing : _) = Nothing
step _ (Just h : hs)
| all (== Just h) hs = Just (h + 1)
| otherwise = Nothingperfect returns precisely the required Boolean. Its time complexity is linear in the number of vertices, assuming unit-cost depth arithmetic; labels are never compared or evaluated.Use For a nonempty forest, write its first rose tree as Thus the recursive Haskell definition isThe nested call supplies the continuation of the preorder traversal as a suffix. Each label is emitted once, without repeated list concatenation of an already flattened subtree. For a finite forest, constructing its entire contribution takes linear time in its number of vertices, without traversing the supplied suffix
concat [] = [], concat (ys:yss) = ys ++ concat yss, the corresponding equations for map, associativity of list concatenation, and (r:ys) ++ zs = r:(ys ++ zs). For an empty forest,flatten2 [] xs
= concat (map flatten []) ++ xs
= [] ++ xs
= xsNode r children:flatten2 (Node r children : trees) xs
= (flatten (Node r children) ++ concat (map flatten trees)) ++ xs
= (r : concat (map flatten children))
++ (concat (map flatten trees) ++ xs)
= r : (concat (map flatten children) ++ flatten2 trees xs)
= r : flatten2 children (flatten2 trees xs)flatten2 :: [RTree a] -> [a] -> [a]
flatten2 [] xs = xs
flatten2 (Node r children : trees) xs =
r : flatten2 children (flatten2 trees xs)xs.Measure the work of producing the entire output list, with constant-cost labels. Count height in levels, so a leaf has height one and . A perfect ternary tree with levels hasvertices. This is the finite geometric series formula, used without a new proof.
The three recursive calls cost . Ordinary
concat = foldr (++) [] copies each immediate child result once, and each result has elements. Consequently the nonrecursive work is , givingUnroll this recurrence relation. At level , the cost is , and there are internal levels, followed by leaves. ThereforeFor this is conventionally written ; in terms of total size it is . The extra height factor comes from copying labels at successive ancestors, even under lazy evaluation when the whole output is demanded. Merely producing its first constructor is a different cost question. If height instead counts edges, the source's height means levels; shifting the index by one leaves the boxed asymptotic bound unchanged. Part (c)'s suffix-passing implementation avoids this repeated copying. Articles by others on the same topic
There are currently no matching articles.