[Haskell-cafe] flatten a nested list

[Donald Bruce Stewart]

pphetra:
> 
> I would like to write a program that can do something like this.
>  
> ;; lisp syntax
> * (my-flatten '(1 (2 (3 4) 5)))
> (1 2 3 4 5)
> 
> I end up like this.
> 
> data Store a = E a | S [Store a]
>              deriving (Show)
> 
> flat :: [Store a] -> [a]
> flat [] = []
> flat ((E x):xs) = [x] ++ flat xs
> flat ((S x):xs) = flat x ++ flat xs
> 
> so
> *Main> flat [E 1, S[E 2, S[E 3, E 4], E 5]]
> [1,2,3,4,5]
> 
> Compare to a Lisp solution, It 's not looking good.
> Any suggestion.



Since this data type:

> data Store a = E a | S [Store a]
>              deriving (Show)

Is isomorphic to the normal Data.Tree type anyway, so we'll use that:

> data Tree a = N a [Tree a]
>   deriving Show

to define a new tree:

> tree = N 1 [N 2 [N 3 [], N 4 []], N 5 []]

Now we can flatten by folding:

> flatten t = go t []
>   where go (N x ts) xs = x : foldr go xs ts

So we can flatten our test tree:

> list = flatten tree

Even run it:

> main = print (flatten tree)

Or in GHCi:

*Main> flatten tree
[1,2,3,4,5]

Based on Data.Tree in the base library.

-- Don