ocaml - 在 Ocaml 中展平列表的代码错误

Question

大家好，我想在 Ocaml 中展平一个列表。我是新手，如果我的错误是愚蠢的，请原谅我

例如，如果输入是 [[1];[2;3];[4]] 我应该以 [1;2;3;4] 结束。

我试图使用的想法如下
使用 accumaltor = [] 从右侧遍历列表(使用 fold_right)
伪代码如下

func flatten(list,  accumalator) 
  For each item from right to left in list 
     If Item is a scalar then n :: accumalator
     Else fi Item is a list of form head :: tail then
               head :: flatten (tail, accumalator).

我认为理论上该算法是正确的，但如果您不同意，请告诉我。

现在到我的 OCaml 代码来实现这个算法

let rec flatten acc x =
    match x with 
           n -> n :: acc
        | [x] -> x :: acc
        | head :: remainder -> 
            head :: ( my_flat acc remainder ) 
 and my_flat = List.fold_right flatten
 ;;

 my_flat [] [[1];[2;3];[4]]

我得到的错误如下
错误:此表达式的类型为 'a，但期望表达式的类型为
'一个列表

错误发生在 match 语句的最后一个模式中读取 head::( my_flat acc 余数 ) 的行上

任何帮助表示赞赏。

Answer 1

在 OCaml 中，列表的所有元素必须是相同的类型。因此值 [1; [2; 3]; 4]本身无效。它包含两个类型为 int 的元素。和一个 int list 类型的元素.从本质上讲，您对要解决的问题的陈述是不可能的。

$ ocaml312
        Objective Caml version 3.12.0

# [1; [2; 3]; 4];;
Characters 4-10:
  [1; [2; 3]; 4];;
      ^^^^^^
Error: This expression has type 'a list
       but an expression was expected of type int

这听起来像是一个家庭作业问题，所以我只想说，将自己限制在 OCaml 中有效的列表中可能会更容易解决。

编辑

好的，现在问题可以解决了!

报告的类型错误的本质是这样的。你有你的累积结果 acc (示例中类型为 int list)。您要添加列表 x (也是 int list 类型)到它。你坏了 x进入 head (一个 int)和 remainder (一个 int list )。如您所见， remainder不适合您的 my_flat功能。它想要一个 int list list ，即整数列表的列表。事实上，您的递归调用几乎肯定会转到 flatten而不是 my_flat .

我看到的另一个问题: List.fold_right 的参数是:一个函数、一个列表和一个起始值。在您调用 my_flat 的测试电话中，您按其他顺序提供最后两个。空列表 []是你的起始值。

我希望这足以让你前进。由于您刚刚开始使用 OCaml，因此在它起作用之前可能还会遇到一两个问题。

编辑 2

这里还有一些评论，如果您仍在研究自己的解决方案，可能会剧透....

更简洁的函数版本 my_flat位于 OCaml 标准库中，名称为 List.flatten .看一下实现很有趣:

let rec flatten = function
    [] -> []
  | l::r -> l @ flatten r

我称之为一个非常优雅的解决方案，但不幸的是它不是尾递归。所以它会消耗一些(线性)数量的堆栈空间，甚至可能会因为一个很长的列表而崩溃。

这是基于相同想法的一个，使用标准的 FP 累加器技巧来获得尾递归行为(如 Thomas 所述):

let flatten2 ll =
    let rec go acc = function
    | [] -> List.rev acc
    | l :: r -> go (List.rev_append l acc) r
in
    go [] ll

通常情况下，尾递归版本以相反的顺序累积结果，并在最后将其反转。