Ошибка «Не удается создать бесконечный тип» в Haskell

Question

Я хотел бы знать, почему Хаскелл принимает это

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

но не приму это:

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

жалуется, что

[1 из 1] Compiling Main (abc.hs, интерпретированный)

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)

Я могу понять, что он говорит, я просто не могу понять, почему первый в порядке, а второй нет!

РЕДАКТИРОВАТЬ: Ах, конечно, у меня также есть

perms [] = [[]]

вверху.

Спасибо

Answer 1

В первом выражении у вас есть x:y, что означает, что если x :: a, то y :: [a].В x : perms y, если x :: a, то это должно быть perms y :: [a], но perms y :: [[a]] (список перестановок).Typechecker пытается объединить [a] и [[a]] и завершается неудачей.

Answer 2

У меня болит мозг, и я не эксперт, но я думаю:

В

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

perms (takeOut i xs) - список списков. x ограничен каждым элементом этого списка. Perms вызывается из списка в целом, поэтому perms - это функция, принимающая список вещей.

В

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

(takeOut i xs) является списком, и для каждого элемента этого списка x ограничен в разрешении этого элемента. Perms вызывается для каждого элемента списка, поэтому perms - это функция, принимающая вещи.

Только первый случай является внутренне непротиворечивым, и проверщик типов любит вас.

Answer 3

В понимании списка x <- ys связывает x с каждым элементом в ys. По сути, вы пытаетесь преобразовать:

[ f foo | foo <- bar ]

В

[ f bar ]

Фраза

y <- perms (takeOut i xs)

Означает "для каждой перестановки y из takeOut i xs". Таким образом, [ x:y | ... ] добавляет x к каждой перестановке.

Соответственно фраза

y <- takeOut i xs

Означает "для каждого элемента y из takeOut i xs". Таким образом, [ x:perms y | ... ] пытается найти все перестановки элемента y (даже не список), а затем добавляет x к этому списку перестановок. Перестановки чего-либо - это список списков, поэтому x должен быть списком для этого, а это не так. Так что, в принципе, второй не имеет смысла.

Я понимаю, почему тебя сбросили. Просто запомните, <- - это не то же самое, что let, это означает для каждого .