如何递归查找整数列表中的最大元素？

这是我曾经想过的max的最小最小递归实现：

def max(xs: List[Int]): Option[Int] = xs match {
  case Nil => None
  case List(x: Int) => Some(x)
  case x :: y :: rest => max( (if (x > y) x else y) :: rest )
} 

它通过比较列表中的前两个元素，丢弃较小的元素（如果两个元素相等，则丢弃第一个元素），然后在其余列表中调用自身来工作。最终，这会将列表减少到一个必须是最大的元素。

我回一个选项来处理报错空单的情况下，没有抛出异常- （如果到调用者调用代码来识别的可能性，并处理它哪支部队，他们想抛出一个异常）。

如果您希望它更通用，则应这样编写：

def max[A <% Ordered[A]](xs: List[A]): Option[A] = xs match {
  case Nil => None
  case x :: Nil => Some(x)
  case x :: y :: rest => max( (if (x > y) x else y) :: rest )
}

它将与任何扩展Ordered特征或对范围进行隐式转换的类型A一起Ordered[A]使用。因此，在默认情况下它的工作原理为Int，BigInt，Char，String等等，因为scala.Predef定义为他们的转换。

我们可以像这样变得更加通用：

def max[A <% Ordered[A]](xs: Seq[A]): Option[A] = xs match {
  case s if s.isEmpty || !s.hasDefiniteSize => None
  case s if s.size == 1 => Some(s(0))
  case s if s(0) <= s(1) => max(s drop 1)
  case s => max((s drop 1).updated(0, s(0)))
}

它不仅适用于列表，而且适用于vectors和扩展该Seq特性的任何其他集合。请注意，我必须添加一个检查以查看序列实际上是否具有确定的大小-它可能是无限的流，因此如果可能的话，我们将退出。如果您确定流具有确定的大小，则可以始终在调用此函数之前对其进行强制-无论如何它将贯穿整个流。不过，请参阅最后的注释，以了解为什么我真的不想返回None不确定的流。我在这里纯粹是为了简单起见。

但这不适用于集合和地图。该怎么办？下一个常见的超类型是Iterable，但不支持updated或任何等效形式。对于实际类型，我们构建的任何内容可能都无法很好地执行。因此，我干净的无辅助功能递归失败了。我们可以更改为使用辅助函数，但其​​他答案中有很多示例，我将坚持使用一个简单函数的方法。因此，在这一点上，我们可以切换到reduceLeft（同时，我们可以使用“ Traversable”并满足所有集合的需求）：

def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = {
  if (xs.hasDefiniteSize) 
    xs reduceLeftOption({(b, a) => if (a >= b) a else b}) 
  else None
}

但是，如果您不考虑使用reduceLeft递归，则可以执行以下操作：

def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = xs match {
  case i if i.isEmpty => None
  case i if i.size == 1 => Some(i.head)
  case i if (i collect { case x if x > i.head => x }).isEmpty => Some(i.head)
  case _ => max(xs collect { case x if x > xs.head => x })
}

它使用collect组合器避免笨拙的从xs.head和中绑定新迭代器的方法xs drop 2。

这些中的任何一个都可以与几乎任何有订单的任何集合安全地工作。例子：

scala>  max(Map(1 -> "two", 3 -> "Nine", 8 -> "carrot"))
res1: Option[(Int, String)] = Some((8,carrot))

scala> max("Supercalifragilisticexpialidocious")
res2: Option[Char] = Some(x)

我通常不提供其他示例，因为它需要更多有关Scala的专业知识。

另外，请记住，基本Traversable特征提供了一种max方法，因此，所有这些仅用于练习;）

注意：我希望所有示例都能说明如何精心选择case表达式的顺序，以使每个单独的case表达式尽可能简单。

更重要的说明：哦，虽然我非常乐意返回None的输入Nil，但实际上，我会非常倾向于为抛出异常hasDefiniteSize == false。首先，有限流的大小可能完全取决于评估顺序，而Option在某些情况下，此函数将有效地随机返回，这可能需要很长时间才能找到。其次，我希望人们能够区分已经通过Nil和已经通过了真正的风险输入（即无限流）。我只是Option在这些演示中返回了以使代码尽可能简单。