"Cannot create infinite type" error in Haskell

Question

I'd like to know why Haskell accepts this

perms xs = [ x:y | i <- [0..(length xs - 1)], x <- [xs!!i], y <- perms (takeOut i xs)]

but won't accept that:

perms xs = [ x:(perms y) | i <- [0..(length xs - 1)], x <- [xs!!i], y <- (takeOut i xs)]

It complains that

[1 of 1] Compiling Main ( abc.hs, interpreted )

Occurs check: cannot construct the infinite type: t = [t]
  Expected type: t -> [t]
  Inferred type: [t] -> [[a]]
In the second argument of `(:)', namely `(perms y)'
In the expression: x : (perms y)

I can understand what it says, I just cannot is on why the first one is OK and the second one is not!

EDIT: Ah, of course I also have

perms [] = [[]]

at the top.

Thanks

Answer 1

In the first expression you have x:y which means, that if x :: a then y :: [a]. In x : perms y if x :: a then it must be that perms y :: [a], but perms y :: [[a]] (list of permutations). Typechecker tries to unify [a] and [[a]] and fails.

Answer 2

My brain hurts and I'm not an expert, but I think:

In

perms xs = [ x:y | i <- [0..(length xs - 1)], x <- [xs!!i], y <- perms (takeOut i xs)]

perms (takeOut i xs) is a list of lists. x is consed onto each element of that list. Perms is invoked on the list as a whole, so perms is a function taking list-of-thing.

In

perms xs = [ x:(perms y) | i <- [0..(length xs - 1)], x <- [xs!!i], y <- (takeOut i xs)]

(takeOut i xs) is a list, and for each element of that list x is consed onto perms of that element. Perms is invoked on each element of the list, so perms is a function taking thing.

Only the former case is internally consistent, and the typechecker loves you.