"Cannot create infinite type" error in Haskell

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 <- (ta开发者_如何学PythonkeOut 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

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.

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.

In a list comprehension, x <- ys binds x to each element in ys. Essentially, you are trying to transform:

[ f foo | foo <- bar ]

Into

[ f bar ]

The phrase

y <- perms (takeOut i xs)

Means "for each permutation y of takeOut i xs". So the [ x:y | ... ] prepends x to each permutation.

Correspondingly, the phrase

y <- takeOut i xs

Means "for each element y of takeOut i xs". So the [ x:perms y | ... ] is attempting to find all permutations of the element y (not even a list), and then prepend x to that list of permutations. The permutations of something is a list of lists, so x must be a list to do this, which it is not. So, basically, the second one makes no sense.

I can see why you would be thrown off. Just remember, <- isn't the same as let, it means for each.