带有几个函数F#的递归

Question

我的主任务需要一些帮助：通过其他函数(最小、删除、插入(来表达一个函数(排序(。如果你知道如何，请告诉我，我可以如何运行我的递归cicle？它现在只做了一步。可能是这样的：val4->head:：tail|>在第25行对tail排序(val4(？

let rec smallest = function
| x :: y :: tail when x <= y -> smallest (x :: tail)
| x :: y :: tail when x > y -> smallest (y :: tail)
| [x] -> Some x
| _ -> None
let rec delete (n, xs) =
match (n, xs) with
| (n, x :: xs) when n <> x -> x :: delete (n, xs)
| (n, x :: xs) when n = x -> xs
| (n, _) -> []
let rec insert (xs, n) =
match (xs, n) with
| ([x], n) when x < n -> [x]@[n]
| (x :: xs, n) when x < n -> x :: insert (xs, n)
| (x :: xs, n) when x >= n -> n :: x :: xs
| (_, _) -> []
let rec sort = function
| xs -> let val1 = smallest xs
let val2 = val1.[0]
let val3 = delete (val2, xs)
let val4 = insert (val3, val2)
val4
let res = sort [5; 4; 3; 2; 1; 1]
printfn "%A" res

Answer 1

这有点像插入排序，但由于您总是在整个列表中找到最小的数字，而不是下一个最高的数字，除非您跳过已经找到的最小数字，否则它将永远重复出现。

此外，您的insert和delete函数不作用于项索引，而是作用于值的相等性，因此它将无法处理重复的数字。

保持大部分原始代码不变，通常您有一个内部递归函数来帮助跟踪状态。这是一种常见的FP模式。

let sort lst = 
let size = lst |> List.length
let rec sort' xs = function
| index when index = size -> xs
| index -> 
let val1 = smallest (xs |> List.skip index)
let val2 = val1.[0]
let val3 = delete (val2, xs)
let val4 = insert (val3, val2)
sort' val4 (index + 1)
sort' lst 0
let res = sort [5; 3; 2; 4; 1; ]
printfn "%A" res

不用说，这是不正确的，也不具有性能，而且每次迭代都会多次遍历列表。它可能以立方时间运行。但是继续学习！

Answer 2

我找到了……我只更改了4&上面"最小"的5行：|[x]->一些x|_->无，当存在：|[x]->[x]时|_->[]

let rec sort = function
| xs -> match xs with
| head :: tail -> let val1 = smallest xs
match val1 with
| Some x -> let val2 = delete (x, xs)
let val3 = insert (val2, x)
let val4 = (fun list -> match list with head :: tail -> head :: sort tail | _ -> []) 
val4 val3
| None -> []
| _ -> []
// let res = sort [5; 4; 3; 2; 1]
// printfn "%A" res