algorithm - 理解 List.fold_left 并使用它实现插入排序

Question

我正在尝试学习 OCaml，但我仍然对折叠函数有些吃力。我做了一些研究，发现以下代码片段(用 Scala 编写)使用 foldleft 实现插入排序。我想我明白了，但我对 Scala 完全一无所知，所以我仍然需要一些澄清。所以，我想我的问题有两个(哈，明白了吗？)，这个函数如何用 Ocaml 编写，它实际上是如何工作的？

def insertionSort[A <% Ordered[A]](list: List[A]): List[A] =
  list.foldLeft(List[A]()) { (r,c) =>
    val (front, back) = r.span(_ < c)
    front ::: c :: back
  }

感谢您的帮助!

Answer 1

正如我在上面评论的那样，这不是一种特别好的排序方式(假设我了解 Scala 代码，但我可能不了解)。这是它似乎在做什么的 OCaml 翻译:

let insertion_sort l =
    let add1 sortedl x =
        let le, gt = List.partition ((>=) x) sortedl
        in
            le @ [x] @ gt
    in      
        List.fold_left add1 [] l

当你写了一段时间的 FP 代码后，折叠就变得很自然了。目的是以已知顺序(例如，最左边的优先)处理来自数据结构(例如，列表)的一系列元素，同时维护在您进行处理时传递的某些状态。在最简单的情况下(如此处)，状态也是您的最终答案。在其他情况下，您需要携带一些额外的状态以及最终答案。在这些情况下，您可以在最后提取最终答案。

也许我不应该这么说，但是折叠就像 C 系列中的 for(;;) 语句，只是它封装了您计划在循环中修改的所有状态.通过这种方式，它是一种很好控制的迭代形式。

通信看起来像这样:

for(state = S, x = first(D); more(D); x = next(D)) { state = E(state, x) }

fold_left (fun state x -> E state x) S D

封装修改后的状态的原则通常在您习惯后会非常有用。很多时候，您折叠的函数(如上面的 add1)在许多其他情况下都是有用的，因为折叠的结构需要在那个地方有一个普遍有用的函数。

请特别注意，fold 函数包含了如何遍历数据结构的所有知识。 folded 函数只需要知道如何处理每个元素。因此，您可以自由更改数据结构(和折叠)而无需更改任何其他代码。您还可以对不同的数据结构使用相同的折叠函数(add1)。