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

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无限期的流.我在这里纯粹为了简单起见.

但这不适用于集合和地图.该怎么办？下一个常见的超类型是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组合子,以避免bodging一个新的迭代出来的一些笨拙的方法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在这些演示中返回,以使代码尽可能简单.

Answer 2

最简单的方法是使用TraversableOncetrait的max函数,如下所示,

val list = (1 to 10).toList
list.max

为了防止空虚你可以做这样的事情,

if(list.empty) None else Some(list.max)

以上会给你一个 Option[Int]

我的第二种方法是使用 foldLeft

(list foldLeft None)((o, i) => o.fold(Some(i))(j => Some(Math.max(i, j))))

或者如果您知道在空列表的情况下要返回的默认值,这将变得更加简单.

val default = 0
(list foldLeft default)(Math.max)

无论如何,因为你的要求是以递归的方式做,我建议如下,

def recur(list:List[Int], i:Option[Int] = None):Option[Int] = list match {
  case Nil => i
  case x :: xs => recur(xs, i.fold(Some(x))(j => Some(Math.max(j, x))))
}

或作为默认情况,

val default = 0
def recur(list:List[Int], i:Int = default):Int = list match {
  case Nil => i
  case x :: xs => recur(xs, i.fold(x)(j => Math.max(j, x)))
}

请注意,这是tail recursive.因此堆栈也被保存.

Answer 3

如果您想要解决此问题的功能方法,请使用reduceLeft:

def max(xs: List[Int]) = {
  if (xs.isEmpty) throw new NoSuchElementException
  xs.reduceLeft((x, y) => if (x > y) x else y)
}

这个函数特定于int的列表,如果你需要更通用的方法,那么使用Ordering类型类:

def max[A](xs: List[A])(implicit cmp: Ordering[A]): A = {
  if (xs.isEmpty) throw new NoSuchElementException
  xs.reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
}   

reduceLeft是一个高阶函数,它取一个类型的函数(A, A) => A,这种情况下需要两个整数,比较它们并返回较大的一个.

Answer 4

你可以像这样使用模式匹配

def max(xs: List[Int]): Int = xs match {
  case Nil => throw new NoSuchElementException("The list is empty")
  case x :: Nil => x
  case x :: tail => x.max(max(tail)) //x.max is Integer's class method
}

Answer 5

Scala是一种功能性语言,鼓励人们递归思考.我的解决方案如下.我根据你给定的方法重复它.

  def max(xs: List[Int]): Int = {
    if(xs.isEmpty == true) 0
    else{
      val maxVal= max(xs.tail)
      if(maxVal >= xs.head) maxVal 
      else                  xs.head     
    }
  }

由于建议,更新了我的尾部递归解决方案.

  def max(xs: List[Int]): Int = {    
    def _max(xs: List[Int], maxNum: Int): Int = {   
      if (xs.isEmpty) maxNum
      else {
        val max = {
          if (maxNum >= xs.head) maxNum
          else xs.head
        }
        _max(xs.tail, max)
      }
    }
    _max(xs.tail, xs.head)
  }