Haskell FlatMap

Question

I am a beginner interested in Haskell, and I have been trying to implement the flatmap (>>=) on my own to better understand it. Currently I have

flatmap :: (t -> a) -> [t] -> [a]  
flatmap _ [] = []  
flatmap f (x:xs) = f x : flatmap f xs  

which implements the "map" part but not the "flat".
Most of the modifications I make result in the disheartening and fairly informationless

Occurs check: cannot construct the infinite type: a = [a]  
    When generalising the type(s) for `flatmap' 

error.

What am I missing?

Answer 1

An error like this happens when the type signature you specify does not match the actual type of the function. Since you didn't show the code that causes the error, I have to guess, but I presume you changed it to something like this:

flatmap _ [] = []  
flatmap f (x:xs) = f x ++ flatmap f xs

Which as it happens, is perfectly correct. However if you forgot to also change the type signature the following will happen:

The type checker sees that you use ++ on the results of f x and flatmap f xs. Since ++ works on two lists of the same type, the type checker now knows that both expressions have to evaluate to lists of the same type. Now the typechecker also knows that flatmap f xs will return a result of type [a], so f x also has to have type [a]. However in the type signature it says that f has type t -> a, so f x has to have type a. This leads the type checker to conclude that [a] = a which is a contradiction and leads to the error message you see.

If you change the type signature to flatmap :: (t -> [a]) -> [t] -> [a] (or remove it), it will work.