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

问题描述 投票：0回答：4

因此，假设我们有一些如下所示的列表：

[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
整除，剩余的元素将被放入元组的第二个元素中。

（如果这个余数在解决方案中被颠倒，我不介意。）

ocaml fold foldleft
4个回答
1
投票

如果插槽数量已知且有限，则元组会很方便。但一旦情况并非如此，它们就会变得相当笨重。因此，我认为让文件夹函数接收输入列表的子列表没有任何问题。

在函数式语言中获取前 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);;

_ : 整数列表 =
[[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]]

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)

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

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

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

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

0
投票

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

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

int * int
、
int * int * int
等

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

0
投票

通过折叠，我们可以使用内部函数透明地跟踪计数，这可以防止我们重复计算列表长度，我们可以构建“块”列表，然后将它们与函数的初始值一起应用。

# let fold_leftn f init lst n =
    let rec aux acc count init lst =
      match lst with
      | [] when count = n -> f init acc
      | [] -> failwith "wrong length"
      | _ when count = n -> aux [] 0 (f init @@ List.rev acc) lst
      | x::xs -> aux (x :: acc) (count + 1) init xs
    in
    aux [] 0 init lst;; 
val fold_leftn : ('a -> 'b list -> 'a) -> 'a -> 'b list -> int -> 'a = <fun>
# fold_leftn (fun i lst -> lst :: i) [] [2; 3; 4; 5] 2;;
- : int list list = [[4; 5]; [2; 3]]

但是，在编程时，我们希望尝试将问题分解为可以组合起来构建解决方案的更小的问题。如果我们可以将列表转换为给定长度的块序列，那么我们可以利用 

Seq.fold_left
用很少的代码执行实际的折叠。

# let fold_leftn f init lst n =
  lst 
  |> List.to_seq
  |> seq_chunks n
  |> Seq.fold_left f init;;
val fold_leftn : ('a -> 'b list -> 'a) -> 'a -> 'b list -> int -> 'a = <fun>
# fold_leftn (fun i lst -> lst :: i) [] [2;3;4;5] 2;;
- : int list list = [[4; 5]; [2; 3]]

我们如何获得

seq_chunks
非常简单。它应该看起来很像第一块代码。

# let seq_chunks n seq =
    let rec aux count acc seq () =
      match seq () with
      | Seq.Nil when count = n -> Seq.Cons (List.rev acc, Seq.empty)
      | Seq.Nil -> failwith "wrong length"
      | _ when count = n -> Seq.Cons (List.rev acc, aux 0 [] seq)
      | Seq.Cons (x, xs) -> aux (count + 1) (x :: acc) xs ()
    in
    aux 0 [] seq;;
val seq_chunks : int -> 'a Seq.t -> 'a list Seq.t = <fun>
# [1; 2; 3; 4; 5; 6] 
  |> List.to_seq
  |> seq_chunks 3
  |> List.of_seq;;
- : int list list = [[1; 2; 3]; [4; 5; 6]]
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.