[Haskell-cafe] flatten a nested list

[Stefan O'Rear]

On Thu, Dec 28, 2006 at 11:56:58PM -0800, pphetra wrote:
> 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]

Since this problem is fundimentally tied to Lisp's dynamic
typing, it is no suprise it can be done very easily using
Haskell's support for dynamic typing:

> import Data.Typeable

> data D = forall a. Typeable a => D a  deriving(Typeable)

> flat :: D -> [D]
> flat (D x) = maybe [D x] (>>= flat) (cast x)

To use: map (\ (D x) -> cast x) flat (D [D 1, D [D 2, D 3], D 4]) :: [Maybe Integer]

The 'D' defines an existantial type, which can hold a value
of any type subject to the Typeable constraint.

Typeable allows the typesafe cast function, which returns
Nothing if the types were different.

maybe and >>= are prelude functions used to make the definition
shorter; without them:

> flat (D x) = case (cast x) of Just xs -> concatMap flat xs
>                               Nothing -> [D x]