使用模式匹配和递归 F# 在列表中查找最大元素

Question

我试图在不使用 List.Max 的情况下使用下面给定的模板查找列表中的最大元素。

        let findMax l = 
        let rec helper(l,m) = failwith "Not implemented"

        match l with
        | [] -> failwith "Error -- empty list"
        | (x::xs) -> helper(xs,x)

我能想到的唯一解决问题的方法，atm是

        let rec max_value1 l =
          match l with
          |[] -> failwith "Empty List"
          |[x] -> x
          |(x::y::xs) ->  if x<y then max_value1 (y::xs)
                else max_value1 (x::xs)

        max_value1 [1; 17; 3; 6; 1; 8; 3; 11; 6; 5; 9];;

有什么方法可以从我构建的函数转到使用模板的函数吗？谢谢！

Answer 1

你的辅助函数应该完成这项工作，外部函数只是验证列表不为空，如果不是，则调用辅助函数，它应该是这样的：

let rec helper (l,m) = 
    match (l, m) with
    | []   , m -> m
    | x::xs, m -> helper (xs, max m x)

请注意，由于您要匹配函数的最后一个参数，您可以将其删除并使用 function 而不是 match with:

let rec helper = function
    | []   , m -> m
    | x::xs, m -> helper (xs, max m x)

Answer 2

您可以选择一个元组来传递两者，或者只是在主匹配中应用辅助函数（而不是空列表保护子句）。我为将来可能会发现此问题但没有明确答案的人提供答案。

let findMax l = 
   let rec walk maxValue = function
       | [] -> maxValue
       | (x::xs) -> walk (if x > maxValue then x else maxValue) xs
   match l with 
   | [] -> failwith "Empty list"
   | (head::tail) -> walk head tail

findMax [1; 12; 3; ] //12

使用折叠：

let findMax l = l |> List.fold (fun maxValue x -> if x > maxValue then x else maxValue) (List.head l)

Answer 3

let findMax l = 
  let rec helper(l,m) =
    match l with
    | [] -> m
    | (x::xs) -> helper(xs, if (Some x > m) then Some x else m)
  helper (l,None)

示例：

[-2;-6;-1;-9;-56;-3] |> findMax  
val it : int option = Some -1

空列表将 return None。

Answer 4

我不确定您分配的确切规则是什么，但列表的最大值实际上只是 List.reduce max。所以

let listMax : int list -> int = List.reduce max

您需要类型注释来取悦类型检查器。

let inline listMax xs = List.reduce max xs

也适用并且是通用的，因此它适用于例如还有浮点数和字符串。

使用模式匹配和递归 F# 在列表中查找最大元素

Finding the Maximum element in a list with pattern matching and recursion F#

f#

f#-3.0