# Difference between revisions of "99 questions/Solutions/7"

From HaskellWiki

< 99 questions | Solutions

Markstoehr (talk | contribs) |
Markstoehr (talk | contribs) |
||

Line 26: | Line 26: | ||

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

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

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

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

## Revision as of 23:27, 25 December 2011

(**) 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
```

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]).