如何折叠每折叠列表的 x 个元素

Question

所以，假设我们有如下列表：[1; 2; 3; 4; 5; 6]，假设我想在每次函数调用时折叠 2 个元素。

所以，我会按顺序在 (1, 2)、(3, 4) 和 (5, 6) 上应用函数。

这是我尝试使用的函数：

let fold_left_multiple (func: 'a -> 'b list -> 'a) (base: 'a) (lst: 'b list) (items_per_fold: int): 'a * 'b list =
    let (acc, remainder, _) = List.fold_left (fun (acc, cur_fold_acc, cur_num) el ->
        if cur_num mod items_per_fold = 0 then (func acc (List.rev (el::cur_fold_acc)), [], 1)
        else (acc, el::cur_fold_acc, cur_num + 1)
    ) (base, [], 1) lst in (acc, remainder)

这有点管用；但是，这样做的问题是在函数中使用这些元素并不容易。

我的首选实现方式是使用元组或数组来简化元素访问。

这里有一个 input/output 的例子，更符合预期（使用 utop 语法）。在这种情况下，我对每对元素求和。

# fold_left_multiple (fun lst (e1, e2, e3) -> (e1 + e2 + e3)::lst) [] [1; 2; 3; 4; 5; 6; 7; 8] 3;;
- : int list * int list = ([15; 6], [7; 8])

在这里，如果列表的长度不能被 n 整除，则剩余的元素将放入元组的第二个元素中。

（我不介意这个余数在一个解中是否反转。）

Answer 1

您只需修改标准 fold_left 函数即可对多个元素进行操作。这是对操作的一个：

let rec fold_left_2 f acc l =
  match l with
  | a::b::rest -> fold_left_2 f (f acc a b) rest
  | remainder -> (acc, remainder)

编辑：根据要求修改为 return 余数，而不是忽略它。

为了说明我在评论中的观点，将其推广到任意数量的元素是可能的，但不是很有用，这里有一个允许使用拆分函数任意拆分输入列表的实现：

let rec fold_left_n splitf f acc l =
  match splitf l with
  | None, remainder -> (acc, remainder)
  | Some x, rest -> fold_left_n splitf f (f acc x) rest

并使用您的示例进行调用：

fold_left_n
  (function a::b::c::rest -> (Some (a, b, c), rest) | remainder -> (None, remainder))
  (fun lst (e1, e2, e3) -> (e1 + e2 + e3)::lst) [] [1; 2; 3; 4; 5; 6; 7; 8];;

类似地，可以编写一个函数来提取任意长度的子列表，我没有费心去实现它，但它的调用看起来像这样：

fold_left_n 3
  (fun lst -> function
    | [e1, e2, e3] -> (e1 + e2 + e3)::lst
    | _ -> lst (* we assume we're getting a 3-element list, but the compiler doesn't know that so we need to ignore everything else *)
  ) [] [1; 2; 3; 4; 5; 6; 7; 8];;

它们在使用上都非常复杂和冗长，并且与仅编写专门的实现相比没有什么好处。

Answer 2

这可能有助于确定您希望函数具有的类型。

不存在表示具有不同数量元素的元组的类型，即使所有元素都是整数。每个元素的数量都是不同的类型：int * int、int * int * int 等

如果您想编写一个通用函数，那么您的折叠函数将需要以元组以外的某种形式获取其输入——也许是一个列表。

Answer 3

如果插槽数量已知且数量有限，则元组很方便。但一旦情况并非如此，它们确实会变得非常笨拙。因此，我认为让文件夹功能接收输入列表的 sub-list 没有错。

在函数式语言中获取前 n 个元素（或更少）的常用方法是一个叫做 take 的函数的意思。分别地，摆脱前 n 个元素（或更少）的常用方法是使用名为 drop.

的函数

借助这两个函数，你想要的功能可以这样实现：

(* take and drop seem to be missing in ocamls half full batteries... 
   maybe because it is not idiomatic or efficient or both... 
 *)
let take n lst =
  let rec loop acc n l =
    match n with
    | 0 -> List.rev acc
    | x ->
       match l with
       | [] -> List.rev acc
       | x::xs -> loop (x::acc) (n-1) (List.tl l) in
  loop [] n lst

let drop n lst =
  let rec loop n l =
    match n with
    | 0 -> l
    | _ ->
       match l with
       | [] -> l
       | _::_ -> loop (n-1) (List.tl l) in
  loop n lst


let fold_windowed folder wsize acc lst =
  let rec loop acc l =
    match l with
    | [] -> List.rev acc
    | _::_ ->
       loop (folder acc (take wsize l)) (List.tl l) in
  loop acc lst

借助一些我在 F# 中习惯使用但在 Ocaml 中开箱即用的功能的一些帮助，您可以按如下方式使用 fold_windowed：

let id x = x (* ocaml should have that right out of the box... *)

(* shamelessly derived from F# List.init, with the diff, that the name initializer 
   seems to be reserved in ocaml, hence the somewhat silly name 'initor'
 *)
let list_init n initor =
  let rec loop acc i =
    match i with
    | 0 -> acc
    | _ -> loop ((initor i)::acc) (i-1) in
  loop [] n

# fold_windowed (fun acc l -> l::acc) 3 [] (list_init 10 id);;
_ : int list list =
[[1; 2; 3]; [2; 3; 4]; [3; 4; 5]; [4; 5; 6]; [5; 6; 7]; [6; 7; 8]; [7; 8; 9];
[8; 9; 10]; [9; 10]; [10]]

如何折叠每折叠列表的 x 个元素

How to fold on x elements of list per fold

ocaml

fold

foldleft