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

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 ;;

这给了我错误：这个表达式的类型是'a list list but an expression was expected of type '一个列表

我认为这是因为 list.fold_left 的 return 值给了我们一个列表，但我们给它提供了一个列表列表，所以它又是一个列表列表 return .如果没有匹配，我如何解决这个问题？

我也在玩 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 需要三个个参数。

List.fold_left @ lists

你犯了两个错误。

首先，这被解析为 (List.fold_left) @ (lists)。

您正在寻找 List.fold_left (@) lists。但这仍然不太正确，因为...

您只传递两个个参数，lists 是初始值，而 List.fold_left 需要三个。

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

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

展示：

utop # 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]

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 是 one-to-one：它不会丢失任何信息。

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

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

几乎是即时的。

Can I simplify this recursive concat function using List.fold_left?