2

我正在尝试学习 OCaml，但我仍在努力使用折叠功能。我做了一些研究，发现以下代码片段（用 Scala 编写）使用 foldleft 实现插入排序。我想我明白了，但我对 Scala 一无所知，所以我仍然需要澄清一下。所以，我想我的问题是 2 倍的（哈，明白了吗？），这个函数将如何用 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
  }

谢谢您的帮助！

4

2 回答 2

2

正如我上面评论的那样，这不是一种特别好的排序方式（假设我理解 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 代码一段时间后，折叠变得很自然。其目的是以已知顺序（例如，最左边的优先）处理来自数据结构（例如，列表）的一系列元素，同时保持一些在您进行处理时传递的状态。在最简单的情况下（如这里），状态也是您的最终答案。在其他情况下，您需要携带一些额外的状态以及最终答案。在这些情况下，您会在最后提取最终答案。

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

对应看起来像这样：

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具有不同数据结构的相同折叠函数（如上）。

于 2012-09-08T20:24:27.973 回答
0 
let insertion_sort (l: int list) : int list = 
  let rec insert (e: int) (a: int list) =
    match a with
    | [] -> e::a 
    | h::t -> if (e > h) then e::a else h::(insert e t)
  in 
  List.rev (List.fold_left (fun a e -> insert e a) [] l)

List.fold_left 接受一个函数、一个累加器和一个列表。累加器应该被初始化为一个空列表 []，这样当 List.fold_left 接收到一个空列表作为 'l' 参数时，它将返回一个空列表，因为没有任何东西可以排序。

(fun ae -> insert ea) 更新累加器。当 List.fold_left 折叠列表时，它获取每个元素并将其插入到排序列表的正确位置。帮助函数 let rec insert 执行这项工作。

let rec insert (e: int) (a: int list) =
  match a with
  | [] -> e::a 
  | h::t -> if (e > h) then e::a else h::(insert e t)

它首先查看排序列表是否为空。如果是，则将元素插入到空列表中。否则（排序列表不为空），然后将要插入的元素与排序列表的头部进行比较，并递归检查以找到该元素在排序列表中的排序位置。

最后，调用 List.rev 是因为 insert 函数使用 cons 运算符 (::) 将元素附加到列表的前面。因此，最终名单必须颠倒过来。

于 2014-10-09T07:03:29.053 回答