如何在 ocaml 中的复杂函数上使用折叠

Question

如题所示，我想用fold。如果我理解正确的话，它曾经将一个函数应用于列表中的每个项目。这就是我想用我的函数做的，但我不知道如何格式化它。

这是我想与 fold 一起使用的函数：

let pairing list =
let rec aux counter length paired list = match list with
| [] -> paired
| [head] -> paired
| head :: head' :: tail -> if counter = length then aux (counter-1) length ((head, head) :: paired) (head :: head' :: tail) else aux counter length ((head, head') :: paired) (head' :: tail)
in List.rev(aux (List.length(listheads list)) (List.length(listheads list)) [] (listheads list));;

它的作用是 returns 列表中所有项目配对在一起的列表。

例如，如果我的列表是[3;4;2]，它应该return

[(3,3); (3,4); (3,2); (4,3); (4,4); (4,2); (2,3); (2,4); (2,2)]

目前 return 只是 [(3,3); (3,4); (3,2)]，因为该功能仅适用于列表的第一项。

以下是所有辅助函数：

let rec member list x = match list with
| [] -> false
| head :: tail -> head = x || member tail x

let head_list list =
let rec aux l1 list = match list with
 | [] -> l1
 | (x,y) :: tail -> aux (x :: l1) tail
in List.rev (aux [] list);;

let head'_list list =
let rec aux l2 list = match list with
 | [] -> l2
 | (x,y) :: tail -> aux (y :: l2) tail
in List.rev (aux [] list);;

let listheads list =
let rec aux returnlist l1 l2 = match l1 with
| [] -> returnlist
| head :: tail -> if member l2 head = true && member returnlist head = false then aux (head :: returnlist) tail l2 else aux returnlist tail l2
in List.rev(aux [] (head_list list) (head'_list list));;

listheads 的作用是获取我的原始列表（比如 [(3,4); (4,2); (2,3); (4,7); (9,4)]），使用 head_list 和 head'_list 以确定哪些整数都在 head 和 head' 在元组中的位置，并将它们放入列表中（在我给出的情况下，[3;4;2]）。

我知道 fold 接受一个函数、一个空列表和一个列表作为参数，但我不知道如何使用 fold 配对。

Answer 1

很难回答你的问题，因为没有干净的地方可以添加折叠以获得你想要的结果。

调试您的代码可能更有成效。在我看来，你正在倒着使用你的柜台。它的初始值是列表的长度，每次递归调用都会递减。但是您的终止测试针对列表的长度进行测试。在我看来你应该针对 0（或者可能是 1）进行测试。

如果您有一个函数 f 对一个值做一些有趣的事情，并且您有一个值列表，您可以使用 List.map 来获取 f 应用于列表的每个元素。你不需要弃牌。

折叠的目的是计算函数值列表以外的东西。例如，如果每次调用 f 都会生成一个值列表，您可以使用折叠将这些列表连接成一个更长的列表。

假设 f 将值 x 放入列表 [x; x] 中。然后你可以创建一个（反向的）双重列表，如下所示：

let f x = [x; x]

let double l =
    let aux sofar x = f x @ sofar in
    List.fold_left aux [] l

# double [1;2;3];;
- : int list = [3; 3; 2; 2; 1; 1]

如果你能想出像 f 这样的函数将一个值转换成一个列表，你就可以遵循这个模式。如果您在外部函数中定义 f，它将可以访问初始列表。

Answer 2

您的代码需要在列表上进行双重传递

   let pairing l =
     let second_pass x acc y = ......  in
     let first_pass  acc el = .......  in
     List.fold_left first_pass [] l |> List.rev

第一个pass函数应该调用第二个pass函数，第二个pass函数会创建pair元素。免费完成两个功能的代码。

这是我得到的结果：

    utop # pairing [3 ; 4 ; 2];;
    - : (int * int) list =
    [(3, 3); (3, 4); (3, 2); (4, 3); (4, 4); (4, 2); (2, 3); (2, 4); (2, 2)]

如何在 ocaml 中的复杂函数上使用折叠

How to use fold on an elaborate function in ocaml

ocaml

tuples

fold