在ocaml嵌套列表中遞歸

Question

我是Ocaml的新手，並且正在編寫代碼來替換嵌套的Ocaml列表中的元素。我的代碼如下：

type 'a sexp = S of 'a | L of 'a sexp list 

我的替代函數（它替換元件的所有出現的b在嵌套列表）如下：

let rec subst a b list = match list with 
    | [] -> list 
    | S s :: t -> if s = a then (S b) :: (subst a b t) else (S s) :: (subst a b t) 
    | L l :: t -> (subst a b l) :: (subst a b t) 

儘管多次嘗試（近6小時） ，我一直無法編譯此代碼..請幫助！

Answer 1

我可以建議先寫一個類型的函數subst而不是？它會讀

let subst x y sexp = 
    let rec visit = function 
    | S z -> S (if z = x then y else z) 
    | L sexps -> L (List.map visit sexps) 
    in 
    visit sexp 

，可以說是很好的地道捕獲遞歸在一個sexp的想法。

現在，爲了獲得一個函數，在列表中進行操作，而不是單一的sexp S，你可以很容易地定義'a -> 'a -> 'a sexp list -> 'a sexp list類型的函數subst_list：

let subst_list x y sexps = List.map (subst x y) sexps 

---

甚至更​​好的是抽象的替代路程，具有更普遍適用('a -> 'b) -> 'a sexp -> 'b sexp類型的函數map用於執行sexp S結構保留映射：

let map f sexp = 
    let rec visit = function 
    | S x -> S (f x) 
    | L sexps -> L (List.map visit sexps) 
    in 
    visit sexp 

然後在map和subst_list，如前所述來定義subst，在subst術語：

let subst x y sexp = map (fun z -> if z = x then y else z) sexp 
let subst_list x y sexps = List.map (subst x y) sexps 

Answer 2

它看起來像你的功能subst應該返回'a sexp list類型的東西。這就是第一場和第二場比賽的情況。

在第三場比賽的情況下，那麼，你的返回值：

(subst a b l) :: (subst a b t) 

因爲你的函數返回'a sexp list，這種類型不會使有很大的意義。該列表的頭是'a sexp list類型，列表的尾部是也是類型'a sexp list。想出具有這種結構的列表是非常困難的。我想你想要的是名單的頭是'a sexp類型。

如果您希望列表頭部的類型爲'a sexp，您需要某種方法將一系列事物打包成單個'a sexp。如果這不足以提示，請查看您的L構造函數。這正是它所做的。

Answer 3

注意：在這裏使用F＃編譯器;這臺計算機上沒有OCaml編譯器。

您subst函數的最後一行有一個錯誤：它應該是如下：

| L l :: t -> L (subst a b l) :: (subst a b t) 

所以完整的代碼應該是這樣的：

type 'a Sexp = 
    | S of 'a 
    | L of 'a Sexp list 

let rec subst (a) (b) (lst : 'a Sexp list) = 
    match lst with 
    | [] -> lst 
    | S s :: t -> if s = a then (S b) :: (subst a b t) else (S s) :: (subst a b t) 
    | L l :: t -> L (subst a b l) :: (subst a b t) 

let test() = 
    let (lst : int Sexp list) = [S 1; L [S 2; L [S 3]; S 4]; S 5] 
    let a = 2 
    let b = 3 
    subst a b lst 

的test()輸出是

[S 1; L [S 3; L [S 3]; S 4]; S 5] 

原因是你的功能subst返回'a Sexp list。如果您從最後一行省略L構造函數，那麼subst a b l的類型爲'a Sexp list，您試圖對'a Sexp list類型的另一個列表進行反省。這不起作用。

也不是這樣你的意圖，因爲你想與'a Sexp list類型的實體，這意味着你必須利弊'a Sexp型與'a Sexp list類型的列表中的元素來結束。通過指定L構造函數，您正在創建'a Sexp list類型的元素，現在可以將其與列表的其餘部分一起使用。