如何递归查找整数列表中的最大元素? [英] How to find the largest element in a list of integers recursively?

问题描述

我正在尝试编写一个函数，该函数将递归地找到整数列表中的最大元素.我知道如何在Java中执行此操作，但是在Scala中不知道如何执行此操作.

I'm trying to write a function which will recursively find the largest element in a list of integers. I know how to do this in Java, but can't understand how to do this at Scala.

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

Here is what I have so far, but without recursion:

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

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

How can we find it recursively with Scala semantic.

推荐答案

这是我想出的max的最小最小递归实现:

This is the most minimal recursive implementation of max I've ever been able to think up:

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

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

It works by comparing the first two elements on the list, discarding the smaller (or the first, if both are equal) and then calling itself on the remaining list. Eventually, this will reduce the list to one element which must be the largest.

我返回一个Option来处理被提供为空列表而不会引发异常的情况-这会强制调用代码识别并处理可能性(如果他们，则取决于调用者要引发异常).

I return an Option to deal with the case of being given an empty list without throwing an exception - which forces the calling code to recognise the possibility and deal with it (up to the caller if they want to throw an exception).

如果您希望它更通用，应该这样写:

If you want it to be more generic, it should be written like this:

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为其定义了转换.

Which will work with any type which either extends the Ordered trait or for which there is an implicit conversion from A to Ordered[A] in scope. So by default it works for Int, BigInt, Char, String and so on, because scala.Predef defines conversions for them.

我们可以变得更加通用:

We can become yet more generic like this:

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的原因.我在这里纯粹是为了简单起见.

Which will work not just with lists but vectors and any other collection which extends the Seq trait. Note that I had to add a check to see if the sequence actually has a definite size - it might be an infinite stream, so we back away if that might be the case. If you are sure your stream will have a definite size, you can always force it before calling this function - it's going to work through the whole stream anyway. See notes at the end for why I really would not want to return None for an indefinite stream, though. I'm doing it here purely for simplicity.

但这不适用于集合和地图.该怎么办?下一个常见的超类型是Iterable，但是不支持updated或任何等效的类型.对于实际类型，我们构造的任何内容都可能表现不佳.因此，我干净的无辅助功能递归失败了.我们可以可以更改为使用辅助函数，但是其他答案中有很多示例，而我将坚持使用一个简单函数的方法.因此，在这一点上，我们可以切换到reduceLeft(在我们使用它的同时，我们去做`Traversable'并迎合 all 集合):

But this doesn't work for sets and maps. What to do? The next common supertype is Iterable, but that doesn't support updated or anything equivalent. Anything we construct might be very poorly performing for the actual type. So my clean no-helper-function recursion breaks down. We could change to using a helper function but there are plenty of examples in the other answers and I'm going to stick with a one-simple-function approach. So at this point, we can to switch to reduceLeft (and while we are at it, let's go for `Traversable' and cater for all collections):

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递归，则可以执行以下操作:

but if you don't consider reduceLeft recursive, we can do this:

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中绑定出来的方法.

It uses the collect combinator to avoid some clumsy method of bodging a new Iterator out of xs.head and xs drop 2.

这两种方法中的任何一种都可以安全地与几乎所有有订单的任何物品集合一起使用.例子:

Either of these will work safely with almost any collection of anything which has an order. Examples:

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的专业知识.

I don't usually give these others as examples, because it requires more expert knowledge of Scala.

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

Also, do remember that the basic Traversable trait provides a max method, so this is all just for practice ;)

注意:我希望我所有的示例都表明，精心选择案例表达式的顺序可以使每个单独的案例表达式尽可能简单.

Note: I hope that all my examples show how careful choice of the sequence of your case expressions can make each individual case expression as simple as possible.

更多重要说明:另外，尽管我非常愿意返回None作为Nil的输入，但实际上，我强烈倾向于为.首先，有限流的大小可能完全取决于确定的顺序，而在某些情况下，此函数将有效地随机返回Option，这可能需要很长时间才能进行跟踪.其次，我希望人们能够在通过Nil和通过真正的风险输入(即无限流)之间进行区分.在这些演示中，我只返回了Option来使代码尽可能简单.

More Important Note: Oh, also, while I am intensely comfortable returning None for an input of Nil, in practice I'd be strongly inclined to throw an exception for hasDefiniteSize == false. Firstly, a finite stream could have a definite or non-definite size dependent purely on the sequence of evaluation and this function would effectively randomly return Option in those cases - which could take a long time to track down. Secondly, I would want people to be able to differentiate between having passed Nil and having passed truly risk input (that is, an infinite stream). I only returned Option in these demonstrations to keep the code as simple as possible.

这篇关于如何递归查找整数列表中的最大元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！