ocaml 嵌套列表中的递归

Question

我是 Ocaml 新手，正在编写代码来替换嵌套 Ocaml 列表中的元素。我的代码如下：

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

我的替换函数（它将嵌套列表中所有出现的元素 a 替换为 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

类型的函数

'a -> 'a -> 'a sexp -> 'a sexp

来代替吗？它会读到

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

进行操作的函数，您可以轻松定义

subst_list

类型的函数

'a -> 'a -> 'a sexp list -> 'a sexp list

：

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

---

更好的是从替换中抽象出来，并具有更普遍适用的

map

类型的函数

('a -> 'b) -> 'a sexp -> 'b sexp

，用于执行

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

然后用

subst

和

map

来定义

subst_list

，就像以前一样，用

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

注意：此处使用 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

类型的元素，您现在可以将其与列表的其余部分结合使用。

Answer 3

看起来你的函数

subst

应该返回

'a sexp list

类型的内容。这就是第一个和第二个匹配案例返回的内容。

在第三个匹配的情况下，那么，你的返回值为：

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

由于您的函数返回

'a sexp list

，因此这种类型没有多大意义。列表头的类型为

'a sexp list

，列表尾部的类型为 'a sexp list 的

also

。很难想出任何具有这种结构的列表。我认为你想要的是列表的头部是

'a sexp

类型。

如果您希望列表的头部为

'a sexp

类型，则需要某种方法将事物列表打包为单个“

a sexp

”。如果这还不够提示，请查看您的

L

构造函数。这正是它的作用。