scala: implementar una función máxima recursiva genérica

generics recursion

Question

Estoy tratando de portar esta implementación de la función haskell max a scala

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

Este es mi primer intento:

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

Pero me sale el siguiente error:

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

Intenté con ordenar, comprable, etc. con resultados similares ...

¿Alguna idea sobre lo que falta?

Answer 1

¿Tal vez quieres la clase de tipo de orden?

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
}

Esto es, después de todo, cómo funciona el método de max integrado:

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

Puedes limpiar mucho si haces esto:

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

O bien, puede hacer que sea recursivo para una mayor eficacia (porque el compilador lo optimizará):

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

Además, debe lanzar RuntimeException o una subclase de ella, no Error .

Answer 2

Acabo de presentar esta solución.

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

Answer 3

Se me ocurrió una solución bastante simple que es fácil de entender. Ofrece una lista vacía, una lista con un solo elemento y números negativos.

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 4

Realicé un ejercicio similar al OP sin emparejar patrones y tipos genéricos, y obtuve lo siguiente:

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 5

Uy, debería verse mejor antes de preguntar

Encontré la respuesta en este hilo: https://.com/a/691674/47633

Parece que las clases de tipos de Haskell se implementan usando implícitos en scala (como en el ejemplo de dhg)

por lo que termina así:

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

o con un poco de azúcar sintáctico, solo

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

Aún así, creo que el compilador tiene suficiente información para hacerlo solo ...

pd: preparé un poco la función ...