[解決済み] なぜこのHaskellコードは "infinite type "エラーを発生させるのでしょうか？

質問

私はHaskellの初心者で、意味をなさない"cannot construct infinite type"エラーに直面しています。

実際、それ以上に、このエラーが何を意味するのかさえ、良い説明を見つけることができませんでしたので、もしあなたが私の基本的な質問を超えて、"infinite type" エラーを説明していただけるなら、私は本当に感謝します。

これがそのコードです。

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における"Infinite type"エラーを処理するための一般的なガイドラインです。

修正されたコード

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

何が問題だったのか。

私の型署名では、挟み込む2番目のパラメータは リストのリスト . したがって、"s (x:y:xs)" に対してパターンマッチを行うと、xとyは次のようになります。 リスト . それなのに、私はxとyをリストではなく、要素として扱っていたのです。

infinite type"エラーに対処するためのガイドラインです。

ほとんどの場合、このエラーが発生したときは、扱っているさまざまな変数の型を忘れてしまっていて、ある変数を、その型とは別の型であるかのように使おうとしているのです。すべてのものがどのような型であるか、どのように使用しているかを注意深く観察することで、たいていの場合、問題が明らかになります。

どのように解決するのですか？

問題は最後の節にあり、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