# 99 questions/Solutions/7

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

The swerve (Talk | contribs) |
|||

(4 intermediate revisions by 2 users not shown) | |||

Line 7: | Line 7: | ||

flatten (Elem x) = [x] | flatten (Elem x) = [x] | ||

flatten (List x) = concatMap flatten x | flatten (List x) = concatMap flatten x | ||

+ | </haskell> | ||

+ | or without concatMap | ||

+ | <haskell> | ||

+ | flatten :: NestedList a -> [a] | ||

+ | flatten (Elem a ) = [a] | ||

+ | flatten (List (x:xs)) = flatten x ++ flatten (List xs) | ||

+ | flatten (List []) = [] | ||

+ | </haskell> | ||

+ | <haskell> | ||

+ | flatten2 :: NestedList a -> [a] | ||

+ | flatten2 a = flt' a [] | ||

+ | where flt' (Elem x) xs = x:xs | ||

+ | flt' (List (x:ls)) xs = flt' x (flt' (List ls) xs) | ||

+ | flt' (List []) xs = xs | ||

+ | </haskell> | ||

+ | or with foldr | ||

+ | <haskell> | ||

+ | flatten3 :: NestedList a -> [a] | ||

+ | flatten3 (Elem x ) = [x] | ||

+ | flatten3 (List xs) = foldr (++) [] $ map flatten3 xs | ||

+ | </haskell> | ||

+ | |||

+ | or with an accumulator function: | ||

+ | <haskell> | ||

+ | flatten4 = reverse . rec [] | ||

+ | where | ||

+ | rec acc (List []) = acc | ||

+ | rec acc (Elem x) = x:acc | ||

+ | rec acc (List (x:xs)) = rec (rec acc x) (List xs) | ||

</haskell> | </haskell> | ||

## Revision as of 06:22, 2 April 2014

(**) Flatten a nested list structure.

data NestedList a = Elem a | List [NestedList a] flatten :: NestedList a -> [a] flatten (Elem x) = [x] flatten (List x) = concatMap flatten x

or without concatMap

flatten :: NestedList a -> [a] flatten (Elem a ) = [a] flatten (List (x:xs)) = flatten x ++ flatten (List xs) flatten (List []) = []

flatten2 :: NestedList a -> [a] flatten2 a = flt' a [] where flt' (Elem x) xs = x:xs flt' (List (x:ls)) xs = flt' x (flt' (List ls) xs) flt' (List []) xs = xs

or with foldr

flatten3 :: NestedList a -> [a] flatten3 (Elem x ) = [x] flatten3 (List xs) = foldr (++) [] $ map flatten3 xs

or with an accumulator function:

flatten4 = reverse . rec [] where rec acc (List []) = acc rec acc (Elem x) = x:acc rec acc (List (x:xs)) = rec (rec acc x) (List xs)

We have to define a new data type, because lists in Haskell are homogeneous. [1, [2, [3, 4], 5]] is a type error. Therefore, we must have a way of representing a list that may (or may not) be nested.

Our NestedList datatype is either a single element of some type (Elem a), or a list of NestedLists of the same type. (List [NestedList a]).