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 函数包含了如何遍历数据结构的所有知识。折叠函数只需要知道如何处理每个元素。因此，您可以自由更改数据结构(和折叠)，而无需更改任何其他代码。您还可以使用具有不同数据结构的相同折叠函数(上面的add1)。