Typecheck weirdness со списками списков

Question

Я не профессионал Haskell. Сегодня у меня был несколько странный опыт работы с системой типов сегодня. Вторая строка этого приведет к ошибке типа. Проблема заключается в maxdiag (as:bs:cs:ds) бит второй линии:

maxdiag ((a:as):(b:bs):(c:cs):(d:ds):xs) len = 
    maximum [a*(bs !! 0)*(cs !! 1)*(ds !! 2), maxdiag (as:bs:cs:ds) (len-1)] 

Он терпит неудачу со следующей ошибкой:

Occurs check: cannot construct the infinite type: a0 = [a0] 
Expected type: [[a0]] 
    Actual type: [a0] 
In the second argument of `(:)', namely `ds' 
In the second argument of `(:)', namely `cs : ds' 

Когда я изменить обижая часть второй линии maxdiag (as:bs:cs:ds:xs), так что он читает

maxdiag ((a:as):(b:bs):(c:cs):(d:ds):xs) len = 
    maximum [a*(bs !! 0)*(cs !! 1)*(ds !! 2), maxdiag (as:bs:cs:ds:xs) (len-1)] 

... тогда нет ошибки. Аналогично, если я заменил его на maxdiag (as:bs:cs:(ds:xs)), он будет успешным. Мои вопросы:

1. Что означает эта ошибка?
2. Почему это произошло?
3. Почему эти две, казалось бы, разные вещи исправить?

Answer 1

Важно помнить, что (:) имеет тип a -> [a] -> [a], поэтому его первый аргумент является элементом, а второй аргумент представляет собой список с этим типом элемента. Если сами элементы являются списками, это становится [a] -> [[a]] -> [[a]].

В вашем примере, as, bs, cs и ds все имеют тип [a], в то время как xs имеет тип [[a]], поэтому cs:ds ошибка во время ds:xs хорошо набирается.

Причина для этого конкретного сообщения об ошибке в том, что при попытке использовать (:) на две вещи одного и того же типа b, единственный способ, который будет работать, если b был тот же тип [b], но это было бы бесконечным тип, который не разрешен.

Для другого вопроса, оператор (:) является правоассоциативным, так as:bs:cs:ds:xs таким же, как as:(bs:(cs:(ds:xs))), а также as:bs:cs:(ds:xs).

Answer 2

Ошибка:

A.hs:2:63: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    Expected type: [[a0]] 
     Actual type: [a0] 
    In the second argument of `(:)', namely `ds' 
    In the second argument of `(:)', namely `cs : ds' 

означает, что у вас есть рекурсивное ограничение на типе, который является незаконным. То есть ваш тип a должен быть как a, так и [a].

«Техническое название для the type checking algorithm», выполняемое на данном этапе. «Встречная проверка» предотвращает построение бесконечно рекурсивных типов.

По моему опыту, в случае сбоя проверка со списком ошибок означает, что вы смешиваете (:) и (++). То есть вы иногда используете значение как элемент списка, а иногда и как список. В этом случае используется (:) в выражении as:bs:cs:ds. Возможно, вы имели в виду что-то вроде:

[as,bs,cs,ds]++xs 

Обратите внимание, что ваш код является довольно сложным - он делает много предположений о количестве и форме элементов в списке, которые очень маловероятно, чтобы быть правдой во все времена. Я бы очень боялся этого кода. Было бы гораздо безопаснее:

• использование сопоставления с образцом, чтобы исключить другие случаи (например, пустые списки, недостающие элементы)
• заменить индексацию (!!) с сопоставлением с образцом.

и думать о том, как вы можете упростить свой алгоритм.