Haskell Tree to List - preorder traversal

Question

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]

Answer 1

Use pattern matching

preorder (Leaf n) = [n]
preorder (Node n a b) = n:(preorder a) ++ (preorder b)

Answer 2

You could aim to a more general solution and make your data type an instance of Foldable. There is a very similar example at hackage, but that implements a post-order visit. 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)

With this, you'll be able to use every function that works on Foldable types, like elem, foldr, foldr, sum, minimum, maximum and such (see here for reference).

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