19

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

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

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

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

4

16 回答 16

46

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

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有隐式转换的类型。所以默认情况下它适用于, ,等等，因为 scala.Predef 为它们定义了转换。AOrdered[A]IntBigIntCharString

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

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组合器来避免一些笨拙的方法将新的迭代器与xs.headand结合起来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在这些演示中返回以使代码尽可能简单。

于 2013-09-27T07:34:06.570 回答
18

最简单的方法是使用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. 因此堆栈也被保存。

于 2013-09-29T05:26:57.830 回答
13

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

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

此函数特定于整数列表，如果您需要更通用的方法，请使用Orderingtypeclass：

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，在这种情况下，它接受两个整数，比较它们并返回更大的一个。

于 2013-09-27T06:37:23.070 回答
8

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

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
}
于 2016-08-05T10:59:02.917 回答
6

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)
  }
于 2013-09-27T07:15:50.260 回答
4

我只用head()了tail()

def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new NoSuchElementException
    else maxRecursive(xs.tail, xs.head) 
  }
  
  def maxRecursive(xs: List[Int], largest: Int): Int = {
    if (!xs.isEmpty) {
      if (xs.head > largest) maxRecursive(xs.tail, xs.head)
      else maxRecursive(xs.tail, largest)
    } else {
      largest
    }
  }

这是此逻辑的测试：

test("max of a few numbers") {
    assert(max(List(3, 7, 2, 1, 10)) === 10)
    assert(max(List(3, -7, 2, -1, -10)) === 3)
    assert(max(List(-3, -7, -2, -5, -10)) === -2)
  }
于 2015-04-30T06:52:12.650 回答
1

  1. 折叠可以帮助：

    if(xs.isEmpty)
  throw new NoSuchElementException
else
  (Int.MinValue /: xs)((max, value) => math.max(max, value))

  2. 列表和模式匹配（更新，感谢@x3ro）

    def max(xs:List[Int], defaultValue: =>Int):Int = {
  @tailrec
  def max0(xs:List[Int], maxSoFar:Int):Int = xs match {
    case Nil => maxSoFar
    case head::tail => max0(tail, math.max(maxSoFar, head))
  }
  if(xs.isEmpty)
    defaultValue
  else
    max0(xs, Int.MinValue)
}

（此解决方案不会Option每次都创建实例。它也是尾递归的，并且与命令式解决方案一样快。）

于 2013-09-27T06:36:46.283 回答
0

看起来您刚刚开始使用 scala，所以我尝试为您的答案提供最简单的答案，如何递归：

 def max(xs: List[Int]): Int = {
   def maxrec(currentMax : Int, l: List[Int]): Int = l match {
     case Nil => currentMax
     case head::tail => maxrec(head.max(currentMax), tail) //get max of head and curretn max
   }
   maxrec(xs.head, xs)
 }

这个方法定义了一个自己的内部方法（maxrec）来处理递归。如果您给它一个空列表，它将失败（异常）（空列表没有最大值）

于 2013-09-27T11:45:51.820 回答
0

如果您需要使用 isEmpty、head 和 tail 在列表上编写递归 max 函数并为空列表抛出异常：

def max(xs: List[Int]): Int =
  if (xs.isEmpty) throw new NoSuchElementException("max of empty list")
  else if (xs.tail.isEmpty) xs.head
  else if (xs.head > xs.tail.head) max(xs.head :: xs.tail.tail)
  else max(xs.tail)

如果您要在 list 上使用 max 函数，它很简单（您不需要编写自己的递归函数）：

val maxInt = List(1, 2, 3, 4).max
于 2017-05-23T21:07:40.890 回答
0

list.sortWith(_ > ).head & list.sortWith( > _).reverse.head 表示最大和最小数字

于 2016-06-10T09:29:09.433 回答
0

使用尾递归

  @tailrec
  def findMax(x: List[Int]):Int =  x match {
    case a :: Nil => a
    case a :: b :: c =>  findMax( (if (a > b) a else b) ::c)
  }
于 2018-08-06T21:23:56.370 回答
0

这是我的代码（我是函数式编程的新手），我假设遇到这个问题的人都是像我这样的人。最佳答案虽然很棒，但对于新手来说有点太多了！所以，这是我的简单回答。请注意，我被要求（作为课程的一部分）仅使用头部和尾部来执行此操作。

/**
   * This method returns the largest element in a list of integers. If the
   * list `xs` is empty it throws a `java.util.NoSuchElementException`.
   *
   * @param xs A list of natural numbers
   * @return The largest element in `xs`
   * @throws java.util.NoSuchElementException if `xs` is an empty list
   */
    @throws(classOf[java.util.NoSuchElementException])
    def max(xs: List[Int]): Int = find_max(xs.head, xs.tail)

    def find_max(max: Int, xs: List[Int]): Int = if (xs.isEmpty) max else if (max >= xs.head) find_max(max, xs.tail) else find_max(xs.head, xs.tail)

一些测试：

test("max of a few numbers") {
    assert(max(List(3, 7, 2)) === 7)
    intercept[NoSuchElementException] {
      max(List())
    }
    assert(max(List(31,2,3,-31,1,2,-1,0,24,1,21,22)) === 31)
    assert(max(List(2,31,3,-31,1,2,-1,0,24,1,21,22)) === 31)
    assert(max(List(2,3,-31,1,2,-1,0,24,1,21,22,31)) === 31)
    assert(max(List(Int.MaxValue,2,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,22)) === Int.MaxValue)
  }
于 2016-06-02T01:49:55.093 回答
0 
def max(xs: List[Int]): Int = {
  def _max(xs: List[Int], maxAcc:Int): Int = {
    if ( xs.isEmpty ) 
      maxAcc 
    else 
      _max( xs.tail, Math.max( maxAcc, xs.head ) ) // tail call recursive
  }

  if ( xs.isEmpty ) 
    throw new NoSuchElementException() 
  else 
    _max( xs, Int.MinValue );
}
于 2017-10-19T07:45:23.847 回答
0

我想这是针对 progfun-example

这是我能想到的最简单的递归解决方案

  def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new NoSuchElementException("The list is empty")
    val tail = xs.tail
    if (!tail.isEmpty) maxOfTwo(xs.head, max(xs.tail))
    else xs.head
  }

  def maxOfTwo(x: Int, y: Int): Int = {
    if (x >= y) x
    else y
  }
于 2020-06-14T03:50:39.287 回答
0

使用模式匹配来查找最大值并在为空的情况下返回零

  def findMax(list: List[Int]) = {
    def max(list: List[Int], n: Int) : Int = list match {
      case h :: t => max(t, if(h > n) h else n)
      case _ => n
    }
    max(list,0)
  }
于 2019-05-16T21:24:10.657 回答
-1 
 def max(xs: List[Int]): Int = xs match {
    case Nil => throw new NoSuchElementException("empty list!")
    case x :: Nil => x
    case x :: tail => if (x > max(tail)) x else max(tail)
  }
于 2017-10-27T10:49:11.463 回答