1

I have an certain binary tree like below.

     (1)
    /   \
  (2)   (3)
 /  \
(4) (5)

And want to produce new list to store this tree data using recursive function in left-right order.

I created the binary tree first and trying to store the data in a list. But have no idea how to store them in a list

data Tree a = Node a (Tree a) (Tree a) | Empty
tree :: Tree a -> [a]
tree Empty = 0
tree (Node x l r) = ?????????

So, expected output is [4, 2, 5, 1, 3].

Micha Wiedenmann
  • 19,979
  • 21
  • 92
  • 137
Hume
  • 93
  • 7

2 Answers2

6

You can turn on the DeriveFoldable feature, and let Haskell do the work for you:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Node (Tree a) a (Tree a) | Empty deriving Foldable

Since you want to use infix notation, we thus swap a and Tree a as parameter here.

We can then use the toList function from Data.Foldable:

Prelude> import Data.Foldable
Prelude Data.Foldable> toList (Node (Node Empty 1 Empty) 4 (Node (Node Empty 2 Empty) 5 Empty))
[1,4,2,5]

You do not only can convert the tree to a list, but you can use the functions that work on a foldable Foldable, for example:

Prelude Data.Foldable> sum (Node (Node Empty 4 Empty) 2 (Node Empty 5 Empty))
11
Prelude Data.Foldable> product (Node (Node Empty 4 Empty) 2 (Node Empty 5 Empty))
40
Prelude Data.Foldable> length (Node (Node Empty 4 Empty) 2 (Node Empty 5 Empty))
3
Prelude Data.Foldable> minimum (Node (Node Empty 4 Empty) 2 (Node Empty 5 Empty))
2
Prelude Data.Foldable> maximum (Node (Node Empty 4 Empty) 2 (Node Empty 5 Empty))
5
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
4

It's done recursively:

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

tree :: Tree a -> [a]

-- Bottom of the tree, nothing to see here
tree Empty = []

-- Append left subtree, self and right subtree
tree (Node x l r) = (tree l) ++ [x] ++ (tree r) 

-- prints [4, 2, 5, 1, 3]
main =
    let t1 = Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty)
        t2 = (Node 3 Empty Empty)
        t = Node 1 t1 t2
    in print $ tree t
bereal
  • 32,519
  • 6
  • 58
  • 104
  • @Hume thank you, though it's far from the [truly best one](https://stackoverflow.com/a/11227902/770830). – bereal Aug 23 '19 at 07:44
  • 1
    I don't understand why this is downvoted? This is a good solution that works properly. – Willem Van Onsem Aug 23 '19 at 12:10
  • @WillemVanOnsem perhaps people prefer genericity of your solution, which I tend to agree with. There is a case for both, though. – bereal Aug 23 '19 at 12:24
  • @bereal: well I think both demonstrate something different: your solution demonstrates what is how to do this. The `deriving Foldable` just automates it. But it is always a good idea to still understand what is going on, and for what cases the implementation will render inefficient, etc. – Willem Van Onsem Aug 23 '19 at 12:36