Ocaml

Question

大家好，我写了一个接受 (int* float* int) list -> int* float * int

的函数

let least lst = 
  List.fold_left 
    (fun (a1,f1,b1) (a2,f2,b2) ->  
       if f1 < f2 then (a1,f1,b1) 
       else (a2,f2,b2)) 
    (List.hd lst) 
    lst

这给了我浮点值最低的元素，我已经测试过它并且工作正常。

现在我在想我可以使用这个函数使它按

降序排列

let descending lst = 
  let rec desc lst acc = 
    match lst with
    | [] -> acc
    | (_, _, _)::t -> desc t ((least lst)::acc)
  in 
  desc lst []

我认为降序函数应该 return 元素按降序排列，但在输出中一些元素是重复的，有些根本不包含

谁能告诉我如何解决这个问题？

Answer 1

考虑这个表达式：

desc t ((least lst) :: acc)

它实质上是说忽略您正在查看的列表的头部，并将列表的最小元素添加到累加器。因此，您忽略了一些列表元素，并且（如果最小的元素恰好不在列表的头部），您不止一次地将一些元素添加到累加器中。

在我看来，您并不真正关心哪个元素位于列表的开头。您想为递归调用删除最少的元素，而不是头部。

Answer 2

你的递归是有缺陷的。您在每个步骤中删除列表的头部，但添加最少的成员。如果 head 不是最小的成员，那么你删除了错误的元素，并且 least 被添加了多次。

这看起来像插入排序，只是相反：提取排序。

给定一个未排序的列表，提取最少的元素并将其附加到结果中。重复。

let extract_least = function
| [] -> raise Not_found
| x::xs ->
  List.fold_left     
    (fun (least, list) x ->
      if least <= x
      then (least, x::list)
      else (x, least::list))
    (x, [])
    xs;;

let rec extract_sort = function
| [] -> []
| list ->
  let (least, list) = extract_least list
  in
    least :: extract_sort list;;

Ocaml - 列表输出不正确

Ocaml - incorrect output with lists

function