CODEWITHSUNDEEP
haskelltreetree-traversal
Gravy
Gravy

Reputation: 12465

Haskell Tree to List - preorder traversal

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]

Upvotes: 4

Views: 5208

Answers (3)

Gravy
Gravy

Reputation: 12465

Ok, sorry about the late reply, but I got this working as follows:

preorder(Leaf n) = [n]
preorder(Node n treeL treeR) = [n] ++ preorder treeL ++ preorder treeR'code'

This however does not work for me still

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

Upvotes: 2

Riccardo T.
Riccardo T.

Reputation: 8937

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

Upvotes: 5

Philip JF
Philip JF

Reputation: 28539

Use pattern matching

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

Upvotes: 3

Related Questions