Flatten a nested list structure using concatMap gives error

Question

Problem 7 from 99 Haskell problems

Flatten a nested list structure

This is my solution:

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 1

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.

Answer 2

With List (x:xs), both x and xs are NestedList as, not as, 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