3

大家好，我正在尝试在 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 remaining) 的行上

任何帮助表示赞赏。

4

4 回答 4

4

在 OCaml 中，列表的所有元素必须是同一类型。因此，该值[1; [2; 3]; 4]本身是无效的。它包含两个 typeint元素和一个 type 元素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 中有效的列表可能会更容易解决。

编辑

OK，现在问题可以解决了！

报类型错误的本质是这样的。您有累积的结果acc（int list示例中的类型）。您想将列表x（也是 type int list）添加到其中。您已经x分为head(an int) 和remainder(an int list)。如您所见，remainder这不是您的my_flat函数的合适参数。它需要一个int list list，即整数列表的列表。事实上，你的递归调用几乎肯定应该去flatten而不是去my_flat。

我看到的另一个问题：参数List.fold_right是：一个函数、一个列表和一个起始值。在您对 的测试调用中my_flat，您以另一种顺序提供最后两个。空列表[]是您的起始值。

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

编辑 2

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

OCaml 标准库中有一个更简洁的函数版本，my_flat名称为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

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

于 2012-02-10T04:54:17.537 回答
2

您可以从直接编写算法开始，分解输入值的基本情况，即。输入列表要么为空，要么输入列表的头部为空，要么输入列表的头部有头和尾：

let rec flatten = function
  | []          -> []
  | []     :: t -> flatten t
  | (x::y) :: t -> x :: (flatten (y::t))

然后您可以优化该函数，因为此代码不是尾递归的，因此当列表变得太大时会崩溃。因此，您可以使用通常的技术重写它：

let flatten list =
  let rec aux accu = function
    | []          -> accu
    | []     :: t -> aux accu t
    | (x::y) :: t -> aux (x::accu) (y::t) in
  List.rev (aux [] list)

所以我的建议是：首先根据输入类型分解你的问题，然后使用累加器来优化你的代码。

于 2012-02-10T11:05:13.633 回答
2

我喜欢这个，其中辅助函数采用累加器、列表列表的第一个元素以及列表列表的其余部分，这对我来说更清楚：

let flatten list =
  let rec aux acc list1 list2 =
    match list1 with
      | x :: tail -> aux (x :: acc) tail list2
      | [] ->
        match list2 with
          | [] -> List.rev acc
          | x :: tail -> aux acc x tail
  in
  aux [] [] list
于 2012-02-14T23:08:29.133 回答
1

感谢您的所有帮助这是我用来解决此问题的代码

let flatten list  =
    let rec flatten_each acc x =
        match x with 
               [] -> acc
        |  head :: remainder -> head :: ( flatten_each acc remainder )
in
List.fold_right flatten_each ( List.rev list ) []
;;

编辑：正如托马斯所指出的，这个解决方案不是尾递归的。尾递归版本如下

let flatten list  =
    let rec flatten_each acc x =
        match x with 
               [] -> acc
            |  head :: remainder -> (flatten_each (acc @ [head]) remainder )
    in
     List.fold_right flatten_each list []
;;
于 2012-02-12T01:44:32.250 回答