scala - scala：实现一个通用的递归最大函数

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 无模式匹配和泛型类型类似的练习，并得出以下结论：

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

此外，您应该 throwRuntimeException或它的子类，而不是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)
    }
}

Answer 4

我想出了一个非常简单的解决方案，很容易理解。它适用于空列表、只有一个元素的列表和负数。

def max(xs: List[Int]): Int = {

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

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

      if (list.isEmpty) max
      else inner(compare(max, list.head), list.tail)
    }
    inner(xs.head, xs.tail)
  } 
}

Answer 5

哎呀，问之前应该更好看

我在这个线程中找到了答案：https ://stackoverflow.com/a/691674/47633

似乎 Haskell 的类型类是使用 scala 中的隐式实现的（就像在 dhg 的示例中一样）

所以它最终是这样的：

def max[T](list: List[T])(implicit f: T => Ordered[T]): T = {

 def maxElement(value1: T, value2: T): T = if (value1 > value2) value1 else value2

 list match {
    case Nil => throw new Error("empty list found")
    case head :: Nil => head
    case list => maxElement(list.head, max(list.tail))
  }
} 

或者加上一些语法糖，只是

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

不过，我认为编译器有足够的信息可以自己完成......

ps：我把这个功能美化了一点...

Answer 6

def genFunc[A](a1: A, a2: A)(f:(A, A) => Boolean):A = if (f(a1, a2)) a1 else a2
def min[A : Ordering] = (a1: A, a2: A) => implicitly[Ordering[A]].lt(a1, a2)
def max[A : Ordering] = (a1: A, a2: A) => implicitly[Ordering[A]].gt(a1, a2)

List(1,2,8,3,4,6,0).reduce(genFunc(_,_)(min))
List(1,2,8,3,4,6,0).reduce(genFunc(_,_)(max))

或者如果只需要带有尾递归的函数 max 并且类型 Option[_] 不会破坏引用透明度

def max[A: Ordering](list: List[A]): Option[A] = list match {
  case Nil => None
  case h :: Nil => Some(h)
  case h :: t => if(implicitly[Ordering[A]].gt(h, t.head)) max(h :: t.tail) else max(t)
}

max(List(1,2,8,3,4,6,0)).getOrElse("List is empty") // 8: Any
max(List()).getOrElse("List is empty")              // List is empty: Any

Answer 7

这是我能想到的最简单的方法：

def max(xs: List[Int]): Int = { if (xs.length == 1) xs.head

else if(xs.isEmpty) throw new NoSuchElementException

else if(xs.head > max(xs.tail))  xs.head

else max(xs.tail)}  }

Answer 8

这行得通

def max(xs: List[Int]): Int = xs match{
  case Nil => 0
  case head :: Nil => head
  case head :: tail => max(List(head, max(tail)))
}

Answer 9

我的解决方法：

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