類型的錯誤編譯

時，我不明白爲什麼下面的代碼不會編譯：類型的錯誤編譯

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

來源

2012-02-17 David Kramf

Tikhon已經解釋了這個問題，所以讓我試着給出解決方案。除非我錯誤地認爲，通過將'comb'的最後一個等式改爲'comb（x：xs）= concatMap（遍歷x）（comb xs）'或'comb（x：xs）= comb xs >> =遍歷x'。 – 2012-02-17 23:57:50

的問題是，comb必須返回[[a]]類型的值。 traverse返回[[a]]類型的值，因此將其映射到另一個列表中會產生[[[a]]]，其嵌套級別太高。

讓我們看看map。它有一個類型map :: (x -> y) -> [x] -> [y]。 traverse x有一個類型[a] -> [[a]]。現在我們需要將這兩者結合起來。爲此，我們將x用[a]和y替換爲[[a]]，得到([a] -> [[a]]) -> [[a]] -> [[[a]]]。這清楚地顯示了映射的結果traverse必須具有至少三級嵌套。

如果你看看你的例子，這就是你實際得到的。對於comb，你只需要一個兩級的深度。

您的示例在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不兼容，並不是它本身是非法的。

來源

2012-02-17 22:57:33

那麼爲什麼我可以在Perlude（？）上在線運行表達式。請查看我的問題的底部。謝謝 – 2012-02-17 23:29:04

在'Main'處，你傳遞''['a]''類型的'map'，並返回一些類型爲[[[[a]]]的東西。在'comb'的最後一行，你正在傳入（根據'comb'的類型定義）某種類型的[[a]]'，所以你將返回某種類型的[[[[a]] ]'，這成爲'comb'的結果。然而，'comb'的結果應該是'[[a]]'，而不是'[[[a]]]'。 – pat 2012-02-17 23:41:04

類型的錯誤編譯

回答

相關問題