Haskell Tree to List - preorder traversal

Questions

Given the following tree structure in Haskell:

data Tree = Leaf Int | Node Int Tree Tree deriving Show

How can I get Haskell to return a list of the data in pre-order?

e.g. given a tree:

Node 1 (Leaf 2) (Leaf 3)

return something like:

preorder = [1,2,3]

Answers

You could aim to a more general solution and make your data type an instance of Foldable. http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html If you want to support pre-order visits you will have to write something like this:

import qualified Data.Foldable as F

data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving Show

instance F.Foldable Tree where
    foldr f z (Leaf x) = f x z
    foldr f z (Node k l r) = f k (F.foldr f (F.foldr f z r) l)

http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html#g:6 http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html#g:6

In particular, the list you are searching for can be obtain with toList. Here are some examples of what you could write by having that instance declaration:

*Main> let t = Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5)
*Main> F.toList t
[1,2,3,4,5]
*Main> F.foldl (a x -> a ++ [x]) [] t
[1,2,3,4,5]
*Main> F.foldr (x a -> a ++ [x]) [] t
[5,4,3,2,1]
*Main> F.sum t
15
*Main> F.elem 3 t
True
*Main> F.elem 12 t
False

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/9492109/haskell-tree-to-list-preorder-traversal

Related