从 oCaml 中的列表中获取两个最小值

Question

我需要使用foldl编写一个函数twoMin: int list → int * int，它返回列表的两个最小值（不是元素）。您可以假设该列表至少包含两个具有不同值的元素。

let rec foldl f l acc = match l with
  | [] -> acc
  | x :: xs -> foldl f xs (f x acc)

let twoMin lst =
  match lst with
  | [] | [_] -> failwith "List must contain at least two elements with different 
values."
   | x :: y :: rest ->
    let initial_acc = if x < y then (x, y) else (y, x) in
    let (min1, min2) = foldl (fun a b -> if b < fst a then (b, fst a) else if b < snd 
a then (fst a, b) else a) rest initial_acc in
    (min1, min2)

我不断收到错误，我不知道代码出了什么问题。

Answer 1

你已经很接近了。

您传递给

foldl

的累加器是一个包含两个值的元组。这可以。但是，传递给

foldl

的函数结果必须与累加器具有相同的类型。如果我们获取您的代码并更改一些名称：

let twoMin lst =
  match lst with
  | [] | [_] -> failwith "List must contain at least two elements with different 
values."
   | x :: y :: rest ->
    let initial_acc = if x < y then (x, y) else (y, x) in
    let (min1, min2) = 
      foldl 
        (fun x acc -> 
           if acc < fst x then (acc, fst x) 
           else if acc < snd x then (fst x, acc) 
           else x) 
        rest 
        initial_acc 
    in
    (min1, min2)

我们可以看到您将列表中的每个元素视为累加器，反之亦然。

当我们只能使用模式匹配时，像这样使用

fst

和

snd

很烦人。

let twoMin lst =
  match lst with
  | [] | [_] -> failwith "List must contain at least two elements with different 
values."
   | x :: y :: rest ->
    let initial_acc = if x < y then (x, y) else (y, x) in
    let (min1, min2) = 
      foldl 
        (fun x (min1, min2 as acc) -> 
           if x < min1 then (x, min1) 
           else if x < min2 then (min1, x) 
           else acc) 
        rest 
        initial_acc 
    in
    (min1, min2)

当然，模式匹配该元组，然后重建它并立即返回它是没有意义的。

此外，您对左折叠的定义可能会帮助您感到困惑，它与

List.fold_left

不同。尝试一下：

let rec foldl f init = 
  function
  | [] -> init
  | x::xs -> foldl f (f init x) xs