我可以使用List.fold_left简化这个递归concat函数吗？

Question

我已经为 concat 创建了一个工作解决方案，但我觉得我可以使用 List.fold_lift 来减少它。

这是我当前的代码：

let rec concat (lists : 'a list list) : 'a list =
    match lists with
    | [] -> []
    | hd :: tl -> hd @ concat tl ;;

这是我尝试过的：

let concat (lists : 'a list list) : 'a list =
    List.fold_left @ lists ;;

这给了我错误：此表达式的类型为“列表列表，但需要一个表达式”类型 '清单

我认为这是因为 list.fold_left 的返回值给了我们一个列表，但我们向它提供了一个列表列表，所以它然后再次返回一个列表列表。在不匹配的情况下如何解决这个问题？

我也在玩 List.map 但到目前为止还没有运气：

let concat (lists : 'a list list) : 'a list =
    List.map (fun x -> List.fold_left @ x) lists ;;

Answer 1

考虑

List.fold_left

的类型签名：

('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

List.fold_left

需要三个参数。

1. 一个函数。
2. 初始值。
3. A

   list

   进行迭代。

List.fold_left @ lists

你犯了两个错误。

首先，这会解析为

(List.fold_left) @ (lists)

。

您正在寻找

List.fold_left (@) lists

。但这仍然不太正确，因为...

您仅传递 两个 参数，其中

lists

是初始值，而

List.fold_left

需要三个。

我认为您正在寻找类似的东西：

let concat lists = List.fold_left (@) [] lists

展示：

# let concat lists = List.fold_left (@) [] lists in
  concat [[1;2;3]; [4;5;6]; [7;8;9]];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

运行时复杂度

这种连接列表的方法的危险在于，虽然它在恒定的堆栈空间中运行，因为

List.fold_left

是尾递归的，而

@

是（至少截至本次编辑），但它的运行时复杂度是 O(n² ).

concat [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]

相当于：

(([] @ [1; 2; 3]) @ [4; 5; 6]) @ [7; 8; 9]

此代码必须迭代到

[1; 2; 3]

的末尾才能生成

[1; 2; 3; 4; 5; 6]

，并且 then 必须迭代到

[1; 2; 3; 4; 5; 6]

的末尾才能生成

[1; 2; 3; 4; 5; 6; 7; 8; 9]

。

现在想象我们的列表列表有非常多的列表，并且每个列表都很大。运行时间很快就会失去控制。

我们可以使用

::

，它具有恒定的运行时间，将其减少到 O(n) 运行时间，如下面的代码所示。

let rec concat = function
  | [] -> []
  | []::tl -> concat tl
  | (x::xs)::tl -> x :: concat (xs :: tl)

当然，这不是尾递归，因此它在线性堆栈空间中运行，但幸运的是

tail_mod_cons

为我们提供了一个简单的解决方案。

let[@tail_mod_cons] rec concat = function
  | [] -> []
  | []::tl -> concat tl
  | (x::xs)::tl -> x :: concat (xs :: tl)

Answer 2

可以将

concat

写为

fold_left

，同时通过临时切换到列表的不同表示来避免二次复杂性

如果我有一个列表

l

，我可以轻松地使用附加功能：

let to_append l  = fun new_list -> l @ new_list

我还可以使用

从追加函数中获取列表

let to_list append = append []

并且由于对于任何列表

l

，我都有

to_list @@ to_append l

=

l

，这意味着

to_append

是一对一的：它不会丢失任何信息。

而且连接两个appends函数就是函数组合

let append_concat f g l = f (g l)

由于我们还没有构建任何具体列表，

append_concat

具有恒定的成本（我们将时间复杂度延迟到调用追加函数的时刻）。

我们可以使用

append_concat

的这种更好的行为来编写线性

concat'

函数，将列表列表映射到附加函数：

let concat' l =
  List.fold_left 
    (fun append l -> append_concat append (to_append l))
    (to_append [] (* aka Fun.id *))
    l

注意，这个

concat'

还没有构建一个列表，它正在构建一个闭包，它记录了稍后调用的追加函数列表。

从

concat

构建

concat'

就是将我的附加函数转换回列表的问题：

let concat l = to_list (concat' l)

这是

to_list

的调用，其时间复杂度等于最终列表的大小。

为了检查我们是否获得了正确的复杂性，我们可以测试压平以下列表

let test =
  List.init 1_000_000 
   (fun i ->
     List.init 4 (fun k -> k + 4 * i)
   )
(* this is [[0;1;2;3]; [4;5;6;7]; ... [...; 3_999_999]] *)

与

let flattened = concat test

几乎是即时的。