F# 使用 foldBack 或 fold 对数组进行排序。

Question

我正在尝试使用 fold 或 foldBack 对数组进行排序。

我试过这样实现：

let arraySort anArray = 
    Array.fold (fun acc elem -> if acc >= elem then acc.append elem else elem.append acc) [||] anArray

这当然会出错。如果这是一个列表，那么我会知道如何通过递归函数实现这一点，但事实并非如此。

因此，如果有人能启发我关于折叠或折叠的可行功能的外观，那么我将很有创意。

在您开始建议使用 Array.sort anArray 之前，这是行不通的，因为这是一项学校作业，因此是不允许的。

Answer 1

回答问题

我们可以使用 Array.fold 作为简单的类似插入排序的算法：

let sort array =
    let insert array x =
        let lesser, greater = Array.partition (fun y -> y < x) array
        [| yield! lesser; yield x; yield! greater |]
    Array.fold insert [||] array

我认为这最接近您的尝试。

一点说明

您关于必须 return 同一数组的排序版本的评论在这里有点令人困惑 - 默认情况下 F# 是不可变的，因此以这种方式使用 Array.fold 实际上会创建一个新的数组，保持原始不变。这与将其转换为列表、排序然后再转换回来的情况非常相似。在 F# 中，数组类型是不可变的，但数组的元素都是可变的。这意味着您可以执行真正的就地排序（例如通过库函数 Array.sortInPlace），但我们在 F# 中不经常这样做，而是使用默认的 Array.sort，returns 一个新数组。

您的尝试有几个问题，这就是为什么您会遇到一些错误的原因。

首先，追加数组的操作与您尝试的非常不同。我们可以使用 yield 语法通过 [| yield! array ; yield element |] 附加到数组，如果它是一个数组（或者实际上，任何 IEnumerable），我们使用 yield!，并且 yield如果是单个元素。

其次，您不能将数组类型与数组的元素进行比较。这是一个类型错误，因为 compare 需要两个相同类型的参数，而您试图给它一个 'T 和一个 'T array。它们不能是同一类型，否则会是无限的（'T = 'T array 所以 'T array = 'T array array 等等）。你需要弄清楚你应该比较什么。

第三，即使你能把数组比作一个元素，你也有逻辑问题。您的元素要么在最后，要么在开头。如果大于第一个元素，但小于最后一个元素怎么办？

最后一点，您仍然可以在数组上使用递归和模式匹配，只是不如在列表上那么整洁，因为您不能使用经典的 | head :: tail -> 技巧。这是一个基本的（不太）快速排序实现。

let rec qsort = function
    | [||] -> [||]
    | arr  ->
        let pivot = Array.head arr
        let less, more = Array.partition (fun x -> x < pivot) (Array.tail arr)
        [| yield! qsort less ; yield pivot ; yield! qsort more |]

这里的速度可能比Array.sort慢几个数量级，因为我们在这样做的时候必须创建很多数组，而.NET的Array.Sort()方法不会。

F# 使用 foldBack 或 fold 对数组进行排序。

F# Sort an Array with foldBack or fold.

arrays

sorting

f#

append

fold

回答问题

一点说明