1

因此，假设我们有一些如下列表：[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)

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

我首选的实现会以某种方式使用元组或数组来使元素访问更容易。

这是一个更好的输入/输出示例（使用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被放入元组的第二个元素中。

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

4

3 回答 3

1

Tuples are handy if there is a known and limited number of slots. But they do become quite unwieldy once this is not the case. Thus, I think there is nothing wrong with having the folder function receive a sub-list of the input list.

The usual way to get the first n elements (or less) in functional languages is by means of a function called take. Respectively, the usual way to get rid of the first n elements (or less) is by means of a function named drop.

With the help of those 2 functions, the function you want could be implemented like this:

(* 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

With a little help of some additional functions I am used to in F# but could not find out of the box in Ocaml, you can use fold_windowed as follows:

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

于 2020-10-05T23:20:07.527 回答
0

您可以只修改标准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)

编辑：修改为按要求返回剩余部分，而不是忽略它。

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

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

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

于 2020-10-05T21:15:33.820 回答
0

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

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

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

于 2020-10-05T22:04:35.817 回答