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

Question

Я новичок в 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 

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

Моя подпись типа гласит, что вторым параметром intersperse является список списков . Поэтому, когда я сопоставляю шаблон с "s (x: y: xs)", x и y становятся списками . И все же я рассматривал x и y как элементы, а не списки.

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

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

Answer 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] должен быть идентифицированным с, что будет означать, что список является бесконечно вложенным. Это недопустимо (и в любом случае не то, что вы имеете в виду).

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

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

Answer 2

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

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

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'

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

Answer 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"]

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

Answer 4

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

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

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