list - 如何递归地找到整数列表中的最大元素？

Question

我正在尝试编写一个函数，它将递归地找到整数列表中的最大元素。我知道如何在 Java 中做到这一点，但无法理解如何在 Scala 中做到这一点。

这是我到目前为止所拥有的，但没有递归:

  def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new java.util.NoSuchElementException();
    else xs.max;
  }

我们如何使用 Scala 语义递归地找到它。

Answer 1

这是我能想到的最大的最小递归实现:

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)))
}

这不仅适用于列表，还适用于向量和任何其他扩展 Seq 的集合特征。请注意，我必须添加一个检查以查看序列是否确实具有确定的大小 - 它可能是一个无限流，因此如果可能是这种情况，我们会后退。如果你确定你的流有一个确定的大小，你总是可以在调用这个函数之前强制它——无论如何它都会在整个流中工作。为什么我真的不想返回 None 请参阅最后的注释不过，对于无限期的流。我在这里这样做纯粹是为了简单。

但这不适用于集合和 map 。该怎么办？下一个常见的父类(super class)型是 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 trait 提供了 max方法，所以这只是为了练习;)

注意:我希望我所有的例子都表明，仔细选择你的 case 表达式的顺序可以使每个单独的 case 表达式尽可能简单。

更重要的提示:哦，还有，虽然我很乐意返回 None对于 Nil 的输入，在实践中，我强烈倾向于为 hasDefiniteSize == false 抛出异常.首先，有限流可以具有完全取决于评估序列的确定或非确定大小，并且该函数将有效地随机返回Option。在这些情况下 - 这可能需要很长时间才能找到。其次，我希望人们能够区分已通过 Nil并通过了真正的风险输入(即无限流)。我只返回了Option在这些演示中保持代码尽可能简单。