Include nonpositive counts and exhausted input explicitly:
take :: Int -> [a] -> [a]
take n _      | n <= 0 = []
take _ []             = []
take n (x:xs)         = x : take (n-1) xs

drop :: Int -> [a] -> [a]
drop n xs     | n <= 0 = xs
drop _ []             = []
drop n (_:xs)         = drop (n-1) xs
The tests on the count precede inspection of the input list. Thus take 0 undefined = [], while drop 0 undefined = undefined, exactly as these list prefix and list suffix operations require. No element value is inspected merely to traverse the spine.[ref]
A shared recursion computes both components:
split :: Int -> [a] -> ([a],[a])
split n xs | n <= 0 = ([],xs)
split _ []         = ([],[])
split n (x:xs)     = (x:ys,zs)
  where (ys,zs) = split (n-1) xs
For a defined count and a spine with available constructors before termination, each of take and drop makes recursive calls, whereas split makes that many once. The number of recursive calls is halved. The irrefutable pattern in the local pair binding also avoids evaluating the recursive pair merely to expose the first output element.
On proper lazy lists this has the intended two component values. There is a small bottom value distinction outside that domain: the displayed single-pass definition must inspect a positive-count input spine before returning its outer pair, whereas the literal expression (take n xs, drop n xs) exposes the pair constructor even if xs is undefined. The algorithmic answer concerns the two components and the stated call count; it need not silently claim equality under a test that observes this outer constructor alone.
For the paper's leaf-labelled binary tree, the combining operation receives the results of the two subtrees, and the other argument handles a leaf:
foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f g (One x)   = f x
foldTree f g (Two l r) = g (foldTree f g l) (foldTree f g r)
Its constructor equation is foldTree One Two = id. More generally, a function h satisfying h (One x) = f x and h (Two l r) = g (h l) (h r) equals foldTree f g on finite trees, by structural induction. This is the tree fold specialized to a datatype with labels only at leaves, rather than at internal nodes.
Both versions preserve left-to-right leaf order:
flatten :: Tree a -> [a]
flatten (One x)   = [x]
flatten (Two l r) = flatten l ++ flatten r

flattenFold :: Tree a -> [a]
flattenFold = foldTree (\x -> [x]) (++)
The tree fold replaces each leaf by a singleton list and each internal node by list concatenation. The defining equations of flattenFold are consequently those of flatten, proving their equality by structural induction.
Let be the number of leaves; the total number of nodes is . List concatenation copies its left operand. For a tree whose left subtree contains leaves at each successive internal node, these copied lengths are . Their sum is , so the worst-case running time is .
A difference list representation avoids copying prefixes:
flattenFast :: Tree a -> [a]
flattenFast t = go t []
  where
    go (One x)   acc = x:acc
    go (Two l r) acc = go l (go r acc)
The recursion invariant is go t acc = flatten t ++ acc. The leaf case is immediate; the internal-node case uses associativity of list concatenation. Each node is visited once and each leaf contributes one output constructor, giving running time when the result is fully consumed. This is linear flattening of a binary tree and does not assume balance.
The necessary domain is a finite, nonempty list: the datatype has no representation of an empty leaf sequence, and the supplied size-based balance condition does not specify an infinite-size construction.
build :: [a] -> Tree a
build []  = error "build: empty input"
build [x] = One x
build xs  = Two (build ys) (build zs)
  where
    (ys,zs) = split (length xs `div` 2) xs
For length , the two nonempty pieces have and elements. Their sizes differ by at most one, and both are shorter than the input. Induction therefore proves termination and the required leaf-balanced binary tree property at every node. The same induction, using ys ++ zs = xs, proves flatten (build xs) = xs. This straightforward implementation takes running time; computing the length repeatedly is acceptable here because no faster construction was requested.
Use the input list as the seed of the tree unfold:
buildUnfold :: [a] -> Tree a
buildUnfold = unfold step
  where
    step []  = error "build: empty input"
    step [x] = Left x
    step xs  = Right (split (length xs `div` 2) xs)
On a singleton seed, unfold produces the same leaf as build; on a longer finite seed, it recursively builds the same two pieces. Induction on input length proves buildUnfold = build on finite nonempty inputs. The empty-input qualification remains essential: a tree unfold cannot supply a missing empty-tree constructor.

Ancestors (10)

  1. Functional programming, design and analysis of algorithms
  2. 2019
  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