Почему этот код Haskell создает ошибку "бесконечного типа"?

Я новичок в Haskell и сталкиваюсь с ошибкой "не могу построить бесконечный тип", о которой я не могу понять.

Фактически, кроме того, я не смог найти хорошее объяснение того, что означает эта ошибка, поэтому, если бы вы могли выйти за рамки моего основного вопроса и объяснить ошибку "бесконечного типа" , я бы очень признателен.

Здесь код:

intersperse :: a -> [[a]] -> [a]

-- intersperse '*' ["foo","bar","baz","quux"] 
--  should produce the following:
--  "foo*bar*baz*quux"

-- intersperse -99 [ [1,2,3],[4,5,6],[7,8,9]]
--  should produce the following:
--  [1,2,3,-99,4,5,6,-99,7,8,9]

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:y:xs) = x:s:y:intersperse s xs

И вот ошибка, пытающаяся загрузить его в интерпретатор:

Prelude> :load ./chapter.3.ending.real.world.haskell.exercises.hs
[1 of 1] Compiling Main (chapter.3.ending.real.world.haskell.exercises.hs, interpreted )

chapter.3.ending.real.world.haskell.exercises.hs:147:0:
Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `intersperse'
Failed, modules loaded: none.

Спасибо.

Вот некоторые исправленные код и общее руководство для устранения ошибки "бесконечного типа" в Haskell:

Исправленный код

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) =  x ++ s:intersperse s xs

В чем проблема:

В моей сигнатуре типа указано, что вторым параметром для пересечения является список списков. Поэтому, когда я pattern сопоставлен с "s (x: y: xs)", x и y стали списками. И все же я рассматривал x и y как элементы, а не списки.

Руководство по устранению ошибки "бесконечного типа" :

В большинстве случаев, когда вы получаете эту ошибку, вы забыли типы различных переменных, с которыми имеете дело, и вы попытались использовать переменную, как если бы это был какой-то другой тип, чем тот, который есть. Посмотрите внимательно на то, что тип все по сравнению с тем, как вы его используете, и это обычно обнаруживает проблему.

Ответ 1

Проблема заключается в последнем пункте, где вы рассматриваете x и y как элементы, тогда как они являются списками. Это будет работать:

intersperse _ [] = []
intersperse _ [x] = x 
intersperse s (x:y:xs) = x ++ [s] ++ y ++ intersperse s xs

Ошибка бесконечного типа возникает, потому что оператор: имеет тип a → [a] → [a], а вы рассматриваете его как [a] → a → [a], что означает, что [a] быть отождествлен с a, что означало бы, что a - бесконечно вложенный список. Это не допустимо (а не то, что вы имеете в виду, так или иначе).

Изменить: есть еще одна ошибка в приведенном выше коде. Это должно быть:

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) = x ++ [s] ++ intersperse s xs

Ответ 2

Часто добавление явного определения типа может сделать сообщение об ошибке типа компилятора более разумным. Но в этом случае явное типирование делает сообщение об ошибке компилятора хуже.

Посмотрите, что произойдет, когда я дам ghc угадать тип interperse:

Occurs check: cannot construct the infinite type: a = [a]
  Expected type: [a] -> [[a]] -> [[a]]
  Inferred type: [a] -> [[a]] -> [a]
In the second argument of `(:)', namely `intersperse s xs'
In the second argument of `(:)', namely `y : intersperse s xs'

Это явно указывает на ошибку в коде. Используя эту технику, вам не нужно смотреть на все и думать о типах, как это предлагали другие.

Ответ 3

Возможно, я ошибаюсь, но, похоже, вы пытаетесь решить более сложную проблему. Ваша версия intersperse не просто пересекает значение с массивом, но также выравнивает его на один уровень.

Модуль List в Haskell на самом деле обеспечивает функцию интерполяции. Он вводит значение, заданное между каждым элементом в списке. Например:

intersperse 11 [1, 3, 5, 7, 9] = [1, 11, 3, 11, 5, 11, 7, 11, 9]
intersperse "*" ["foo","bar","baz","quux"] = ["foo", "*", "bar", "*", "baz", "*", "quux"]

Я предполагаю, что это то, что вы хотите сделать, потому что это то, что мой профессор хотел, чтобы мы делали, когда я изучал Haskell. Я мог бы, конечно, быть полностью вне.

Ответ 4

Также я нашел этот, который объясняет значение ошибки.

Каждый раз, когда интерпретатор/компилятор дает мне эту ошибку, потому что я использую некоторый тип-параметризованный кортеж как формальный параметр. Все работает корректно с помощью удаления определения типа функции, которое содержит переменные типа.

Я все еще не могу понять, как их исправить и сохранить определение типа функции.