algorithm - 使用 fold_left 的插入排序，bool 函数作为参数传递

Question

我想使用 fold_left 编写简单的插入排序函数，但我也想传递在我的排序乐趣中指定顺序的函数。我不知道的是如何将它传递给 fold_left..

let rec insert f l e = 
match l with
    | [] -> [e]
    | h :: t -> if f e h then h :: insert f t e else e :: l;;

let insertion_sort f l = List.fold_left insert f [] l;;

let less x y = x < y;;

let result = insertion_sort less  [2 ; 5 ; 1 ; 9 ; 7 ; -2 ; 0 ; 124];;

这就是我所说的，但 fold_left 不接受该解决方案。当我对排序函数进行专门化时，它就可以正常工作。

let insertLess = insert less;;

let insertion_sortLess l = List.fold_left insertLess [] l;;

let result = insertion_sortLess [2 ; 5 ; 1 ; 9 ; 7 ; -2 ; 0 ; 124];;
#   val result : int list = [124; 9; 7; 5; 2; 1; 0; -2]

Answer 1

List.fold_left insert f ...会申请insert和 f作为 List.fold_left 的单独参数.你要的是List.fold (insert f) ... ，这将适用 f至 insert , 然后将其结果发送到 List.fold_left .

编辑:此外，您不需要定义 less .你可以通过>通过将其括在括号中直接作为函数:insertion_sort (<) ...