以布尔函数传递为参数的fold_left插入排序

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 (<) ...