型エラー

Question

をコンパイルするときに次のコードはコンパイルされませんなぜ私は理解していない：

append :: [a] -> [a] -> [a] 
append xs ys = foldr (:) ys xs 

traverse :: a -> [a] -> [[a]] 
traverse x [] = [[x]] 
traverse x (y:ys) = append [(x:y:ys)] (map (y:) (traverse x ys)) 

comb :: [a] -> [[a]] 
comb [] = [[]] 
comb (x:[]) = [[x]] 
comb (x:y:[]) = [[x,y],[y,x]] 
comb (x:xs) = map (traverse x) (comb xs) 

それは次のエラーを生成します。

pr27.hs:13:20: 
Couldn't match type `a' with `[a]' 
`a' is a rigid type variable bound by 
the type signature for comb :: [a] -> [[a]] at pr27.hs:10:1 
Expected type: [a] -> [a] 
Actual type: [a] -> [[a]] 
In the return type of a call of `traverse' 
In the first argument of `map', namely `(traverse x)' 
Failed, modules loaded: none 

しかし、ときに私はちょうどtraverseをロードし、それを使用します上記と同様の表現で、私は望みの結果を得る。どうしたの？

Main> map (traverse 3) [[1,2],[2,1]] 
    [[[3,1,2],[1,3,2],[1,2,3]],[[3,2,1],[2,3,1],[2,1,3]]] 

Answer 1

問題はcombがタイプ[[a]]の値を返すことがあるということです。 traverseはタイプ[[a]]の値を返します。したがって、別のリストにマッピングすると[[[a]]]が生成されますが、ネストのレベルが高すぎます。

mapを見てみましょう。タイプはmap :: (x -> y) -> [x] -> [y]です。 traverse xのタイプは[a] -> [[a]]です。今度は、2つを組み合わせる必要があります。これを行うには、xを[a]とyと置き換えて[[a]]と置き換え、([a] -> [[a]]) -> [[a]] -> [[[a]]]とします。これはマッピングtraverseの結果が少なくとも3つの入れ子レベルを持たなければならないことを明確に示している。

あなたの例を見ると、これは実際に得られるものです。 combについては、1つの2つのレベルの深さだけが必要です。

あなたの例がGHCiで働いた理由は、式がのいずれかのタイプを持つことができるからです。 map (traverse 3) [[1,2], [2,1]]の表現は完全に正当です。ただし、数字のリストのリストであるタイプNum a => [[[a]]]があります。 （試してみてください：:t map (traverse 3) [[1,2], [2,3]]）ただし、combのタイプは[a] -> [[a]]です。つまり、結果はリストのリストでなければならず、リストのリストのリストでなければなりません。したがって、map (traverse 3)はcombと互換性がなく、それ自体では違法ではありません。