如何找到元组列表的最小值

Question

我必须找到一个元组列表的最小值，但我只想返回元组的

snd

元素的最小值，而不是整个元组。不幸的是，我在以下代码中遇到以下错误，我不知道为什么。 l 参数是一个元组列表

(float * float)

let rec minRight l = match l with
    | [] -> raise (Arg.Bad "minRight: empty list")
    | [x]-> x
    | (_,y)::xs -> min y (minRight xs)

错误：

| (_,y)::xs -> min y (minRight xs)
Error: This expression has type 'a but an expression was expected of type
         'b * 'a

提前致谢。

Answer 1

这里有一个问题，除了前面回答提到的那些：线

| [x]-> x

返回一个元组，而你说你想“返回元组的 snd 元素 [s] 的最小值”。

Answer 2

我想也许你的问题是你命名了你的函数

min

，但你也想使用标准的OCaml函数

min

。这可能吗？

OCaml 没有重载（作为补偿，它具有参数多态性）。所以你需要为事物使用不同的名称。

Answer 3

来自遥远未来的答案

我们可以将其分解为两个独立的问题。首先，您只需要从每个元组中获取第二个元素。然后你需要找到那些值的最小值。

第一部分很简单：

let min_right = function
  | [] -> invalid_arg "Empty list."
  | lst -> lst |> List.map snd

现在，我们可以使用

List.fold_left

来获得最小值。提供第一个值作为

List.fold_left

的初始最小值，我们只需要映射到列表的尾部（可能为空）。

let min_right = function
  | [] -> invalid_arg "Empty list."
  | (_, y)::tl -> 
    tl
    |> List.map snd
    |> List.fold_left min y 

但是，如果您觉得完全遍历列表以从每个列表中去除第二个元素，然后再次遍历整个列表again以找到最小值是重复的，未来的 OCaml 提供了sequences。 OCaml 4.07 - 2018 年 7 月。

let min_right = function
  | [] -> invalid_arg "Empty list."
  | (_, y)::tl -> 
    tl
    |> List.to_seq 
    |> Seq.map snd
    |> Seq.fold_left min y