0

我是 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 个小时），我还是无法编译这段代码。请帮忙！

4

3 回答 3

3

我可以建议先写一个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。

现在，要获得一个对列表而不是单个sexps 进行操作的函数，您可以轻松定义一个subst_listtype的函数'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来执行sexps 的结构保留映射：

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
于 2013-06-05T20:27:22.670 回答
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从最后一行省略构造函数，则 thensubst a b l是 type 'a Sexp list，您正试图将其与另一个 type 列表相结合'a Sexp list。这不起作用。

这也不是您的意图，因为您希望最终得到一个 type 的实体'a Sexp list，这意味着您必须将 type 的元素与 type'a Sexp的列表结合起来'a Sexp list。通过指定L构造函数，您正在创建一个 type 的元素'a Sexp list，您现在可以将其与列表的其余部分结合使用。

于 2013-06-05T19:07:52.710 回答
1

看起来你的函数subst应该返回 type 的东西'a sexp list。这就是第一个和第二个匹配案例返回的内容。

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

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

由于您的函数返回'a sexp list，因此这种类型没有多大意义。列表的头部是 type 'a sexp list，列表的尾部也是type 'a sexp list。很难想出任何具有这种结构的列表。我认为你想要的是列表的头部是 type 'a sexp。

如果您希望列表的头部是类型'a sexp，则需要某种方式将事物列表打包成单个 ' a sexp。如果这还不够提示，请查看您的L构造函数。这正是它的作用。

于 2013-06-05T18:38:50.963 回答