In executable Haskell, the algebraic data type declaration uses data, rather than the printed type. A leaf of a rooted tree contributes False; a fork contributes True followed by its left and right subtrees in that order.
data Tree = Leaf | Fork Tree Tree

preorder :: Tree -> [Bool]
preorder Leaf       = [False]
preorder (Fork l r) = True : (preorder l ++ preorder r)
This is a preorder traversal of a full binary tree, including the leaves. Structural induction proves correctness: the leaf of a rooted tree case has precisely one output, and the fork case concatenates the correct preorder traversals of its two subtrees after its own marker.
An equivalent version avoids repeatedly copying the left list through list concatenation:
preorder t = walk t []
  where
    walk Leaf rest       = False : rest
    walk (Fork l r) rest = True : walk l (walk r rest)
Its strengthening is walk t rest = preorder t ++ rest. Each vertex constructs one list cell, so this version has linear time complexity. The concise result is
(1)

Ancestors (12)

  1. a
  2. 1
  3. Imperative programming
  4. 2015
  5. Past exam of the year 1 of the computer science course of the University of Oxford
  6. Year 1 of the computer science course of the University of Oxford
  7. Computer science course of the University of Oxford
  8. Undergraduate course of the University of Oxford
  9. Course of the University of Oxford
  10. University of Oxford
  11. List of universities
  12. 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