scala:实现通用的递归max函数

Question

我正在尝试将此haskell max函数实现移植到scala

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs) = max x (maximum' xs) 

这是我的第一次尝试:

def max[T <: Ordered[T]](list: List[T]): T = list match {

  case Nil => throw new Error("maximum of empty list")
  case head :: Nil => head
  case list => {
    val maxTail = max(list.tail)
    if (list.head > maxTail) list.head else maxTail
  }
}


max(List[Int](3,4))

但是我收到以下错误:

inferred type arguments [Int] do not conform to method max's type parameter bounds [T <: Ordered[T]]

我试着订购,比较等,结果相似......

什么缺少的任何想法？

Answer 1

通过与OP sans模式匹配和泛型类型相似的练习,并提出以下内容:

def max(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new NoSuchElementException

    if (xs.length == 1) 
        return xs.head 
      else 
        return max(xs.head, max(xs.tail))
  }

  def max(x: Int, y: Int): Int = if (x > y) x else y

Answer 2

也许你想要Ordering类型类？

def max[T: Ordering](list: List[T]): T = list match {
  case Nil => throw new RuntimeException("maximum of empty list")
  case head :: Nil => head
  case list =>
    val maxTail = max(list.tail)
    if (implicitly[Ordering[T]].gt(list.head, maxTail)) list.head else maxTail
}

毕竟,这是内置max方法的工作原理:

// From GenTraversableOnce
def max[A1 >: A](implicit ord: Ordering[A1]): A

如果你这样做,你可以清理很多东西:

def max[T](list: List[T])(implicit ord: Ordering[T]): T = list match {
  case Nil => throw new RuntimeException("maximum of empty list")
  case head :: Nil => head
  case head :: tail => ord.max(head, max(tail))
}

或者,您可以使其尾递归以提高效率(因为编译器将对其进行优化):

def max[T](list: List[T])(implicit ord: Ordering[T]): T = {
  if (list.isEmpty)
    throw new RuntimeException("maximum of empty list")

  @tailrec
  def inner(list: List[T], currMax: T): T =
    list match {
      case Nil => currMax
      case head :: tail => inner(tail, ord.max(head, currMax))
    }
  inner(list.tail, list.head)
}

此外,你应该扔它RuntimeException或它的子类,而不是Error.

Answer 3

我刚刚想出了这个解决方案.

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