尝试学习F#...排序整数列表

Question

我这几个月一直在用Python，现在想试试F#。可是...我真的搞不太懂。过去几天我一直在看文档，但还是不太明白怎么完成一些基本的任务。

我一直在跟着tryfsharp.org和fsharp.net上的教程。

比如说，我想知道怎么用F#来完成这个在Python中写的基本任务。

unsorted = [82, 9, 15, 8, 21, 33, 4, 89, 71, 7]
sorted = []
for n in range(1,len(unsorted)):
    lowest = 0
    for i in range(0,len(unsorted)-1):
        if unsorted[i] < unsorted[lowest]:
            lowest = i
    sorted.append(unsorted[lowest])
    del unsorted[lowest]
print sorted

Answer 1

我知道这可能不是你想要的直接翻译，但F#和函数式编程更注重声明式编程，而不是像命令式语言那样。举个例子，如果你想对一串数字进行排序，你只需要直接排序就可以了：

let unsorted = [2; 9; 15; 8; 21; 33; 4; 89; 71; 7]
let sorted = unsorted |> List.sort

//now print em out
sorted |> List.iter (printfn "%d")

如果你在理解F#时遇到困难，了解一下函数式编程可能会对你有帮助，这样你就能明白F#为什么会有不同的做法。我去年写的这篇文章可能会对你有帮助，http://msdn.microsoft.com/en-us/magazine/ee336127.aspx

Answer 2

注意，你的Python版本不对。它输出的是：

[4, 8, 9, 15, 21, 33, 71, 82, 89]

缺少了7。

这里有一个直接的F#翻译：

let unsorted = new ResizeArray<int> ([| 82; 9; 15; 8; 21; 33; 4; 89; 71; 7 |])
let sorted = new ResizeArray<int> ()
for n=1 to unsorted.Count-1 do
    let mutable lowest = 0
    for i=0 to unsorted.Count-1 do // i changed this line so the output is correct. 
        if unsorted.[i] < unsorted.[lowest] then
            lowest <- i
    sorted.Add(unsorted.[lowest])
    unsorted.RemoveAt(lowest)

printfn "%A" (sorted |> Seq.toArray)

这个翻译版本和Python的几乎一模一样。但这并不是编写F#程序的理想方式。关于F#中的排序算法，你可以看看我博客上的一篇文章：

http://fdatamining.blogspot.com/2010/03/test.html

Answer 3

当你把代码从一种命令式语言转到一种函数式语言时，我觉得你应该尝试转换代码中使用的算法，而不是直接转换代码本身。

这段代码在做一个选择排序，所以你需要问自己，选择排序到底是干什么的呢？

• 找到最小的数
• 把它放到已排序列表的最前面。
• 对剩下的项进行排序，把结果放在最小数的后面。

那么代码应该长什么样呢？这个方法肯定是可行的：

let rec selection_sort = function
    | [] -> []
    | l -> let min = List.min l in                         (* find the minimum *)
           let rest = List.filter (fun i -> i <> min) l in (* find the rest *)
           let sorted_rest = selection_sort rest in        (* sort the rest *)
           min :: sorted_rest                              (* put everything together *)