以ml爲單位的循環誤差

Question

我試圖運行一個函數subst（tr，v1，v2），它返回一個新的ntree，其中v1的所有值都被v2替換爲輸出樹。

datatype 'a ntree = leaf of 'a | node of 'a ntree list; 

fun map(f, []) = [] | map(f,x::t)=f(x) :: map(f,t); 

fun subst(leaf(d), v1, v2) = if d=v1 then v2 else d 
    | subst(node(q), v1, v2) = let fun w(k) = 
    if k=v1 then subst(v2, v1, v2) else subst(k, v1, v2) 
    in map(w, q) 
    end; 

但我得到一個循環錯誤b/c我的rhs of子句不同意w /函數結果類型。我的表達是「」 Z名單，我的結果類型是「」 Z

Answer 1

你忘了重新包裝的subst的結果與相應的ntree構造，因此，類型系統試圖等同的d類型與一個列表。此外，由於您將函數w映射到一個ntrees列表（即，k是一個ntree，並且您無法將它與v1進行比較），因此您的函數w沒有太大意義。

一般提示：如果您有奇怪的類型錯誤，您一開始無法理解它，通常可以通過添加類型註釋縮小它們的範圍，例如，函數參數或結果。

下面的代碼應該工作（未經測試）：

fun subst(leaf d, v1, v2) = leaf(if d = v1 then v2 else d) 
    | subst(node q, v1, v2) = node(map(fn k => subst(k, v1, v2), q)) 

隨着討好，並使用標準map功能適量，它可以更簡單：

fun subst v1 v2 (leaf d) = leaf(if d = v1 then v2 else d) 
    | subst v1 v2 (node q) = node(map (subst v1 v2) q) 

而且，如文體上，最好是利用構造函數（Leaf和Node），以便將它們與模式中的變量區分開來。