Question: **Problem 7** *from 99 Haskell problems*

*Flatten a nested list structure*

This is my solution:

```hs
data NestedList a = Elem a | List [NestedList a]

myFlatten :: NestedList a -> [a]
myFlatten (Elem x) = [x]
myFlatten (List (x:xs)) = x : concatMap myFlatten xs

```

However, I would like to understand...Why does the compiler say:

> 
> Occurs check: cannot construct the infinite type: a ~ NestedList a
> 
> 
> 

> 
> Expected type: [NestedList a]
> Actual type: [a]
> 
> 
>

Answer: 
Let's examine this part of the code, only:

```
myFlatten :: NestedList a -> [a]
myFlatten (List (x:xs)) = x : ...

```

Inside `List` we have `x:xs`, and by definition of `List` we find `(x:xs) :: [NestedList a]`. Hence:

```
x :: NestedList a
xs :: [NestedList a]

```

The returned value is `x : ...` and that is a list of the type of `x`, which is `NestedList a`. Hence, the return type is `[NestedList a]`.

However, the signature of `myFlatten` says that the return type is `[a]`. This is possible only if `[a] = [NestedList a]`, i.e. only if `a = NestedList a`, but that's impossible, hence the type error.
With `List (x:xs)`, both `x` and `xs` are `NestedList a`s, not `a`s, you thus should use `concatMap` over the entire list, with:

```
myFlatten :: NestedList a -> [a]
myFlatten (Elem x) = [x]
myFlatten (List **xs**) = concatMap myFlatten **xs**
```

To avoid wrapping and unwrapping in singleton lists, you can work with a tail that you recursively pass to the list, with:

```
myFlatten :: NestedList a -> [a]
myFlatten = (`go` [])
    where go (Elem x) = (x :)
          go (List xs) = flip (foldr go) xs

```