The test consumes a state and returns Bool; the output function maps a state to an element; and the transition preserves the state type. Hence the most general polymorphic type signature is
unfold :: (s -> Bool) -> (s -> a) -> (s -> s) -> s -> [a]
Equivalently, . The state and emitted element can have unrelated types. A list unfold produces the next element from the current state, then advances to a new state.
Generate the successive states using the Haskell iterate function, keep those before the stopping test becomes true using the Haskell takeWhile function, then map the output function:
unfoldU :: (s -> Bool) -> (s -> a) -> (s -> s) -> s -> [a]
unfoldU p f g = map f . takeWhile (not . p) . iterate g
The missing expression is therefore . On states , the first state satisfying p is excluded, just as in the recursive list unfold. If no state satisfies p, the result is an infinite lazy list, provided each demanded test, output and transition terminates.
For a rose tree, fold each child recursively, retaining their order, and supply the resulting list with the current label to the combining function:
foldRTree :: (a -> [b] -> b) -> RTree a -> b
foldRTree f (Node x ts) = f x (map (foldRTree f) ts)
The defining tree fold equation is . A leaf passes [] as the list of child results; an internal node passes one result per child. Thus the combining function controls both cases without a separate leaf constructor.
Emit the root label, then concatenate the depth-first traversals of the child rose trees in order:
dft :: RTree a -> [a]
dft (Node x ts) = x : concatMap dft ts
This is preorder traversal:
(1)
The Haskell concatMap function preserves child order and finishes each child subtree before moving to the next. A leaf yields its singleton label; the source example yields [1,2,3,4,5,6,7].
The child results supplied by the tree fold are already their depth-first traversals. Prepend the current label to their list concatenation:
dftF :: RTree a -> [a]
dftF = foldRTree visit
  where
    visit :: a -> [[a]] -> [a]
    visit x childLists = x : concat childLists
Thus . Substituting the equation for the tree fold gives exactly the recursive preorder traversal equation from part (i), proving equality by structural induction on a finite rose tree.
A list unfold needs an explicit state describing the unvisited work. Use a list of pending rose trees, with the next tree first. Emit that tree's root label, and replace it by its children followed by the remaining pending trees:
dftU :: RTree a -> [a]
dftU t = unfold null label advance [t]
  where
    label :: [RTree a] -> a
    label (Node x _ : _) = x

    advance :: [RTree a] -> [RTree a]
    advance (Node _ children : rest) = children ++ rest
The boxed state transition is , with output . The stopping test prevents either helper from being applied to [].
The loop invariant is that concatenating the depth-first traversals of the pending trees gives exactly the unproduced output. Removing the next root emits its first label; replacing that tree by its children preserves the remainder of that preorder traversal. Adding children at the front realizes an explicit-stack depth-first tree traversal; placing them at the end would give a different visiting order. The first states for the source example have roots [1], [2,5,6], [3,4,5,6], [4,5,6], [5,6], [6], [7], [].

Ancestors (10)

  1. Functional programming, design and analysis of algorithms
  2. 2014
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version