scala: implementare una generica funzione di max ricorsiva

Question

sto cercando di porto questo Haskell implementazione max funzione per Scala

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

Questo è il mio primo tentativo:

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

ma ottengo il seguente errore :

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

ho provato con l'ordinazione, comprable, ecc con risultati simili ...

012.

Qualche idea su cosa manca?

Answer 1

Forse vuoi la classe di tipo 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 
} 

Questo è, dopo tutto, come il max metodo incorporato funziona:

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

È possibile pulire le cose molto se si esegue questa operazione:

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

Oppure, puoi renderlo ricorsivo in coda per una maggiore efficienza (perché il compilatore lo ottimizzerà):

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

Inoltre, è necessario inviare RuntimeException o una sottoclasse di esso, non Error.

Answer 2

Ops, shoulda guardare meglio prima di chiedere

ho trovato la risposta in questa discussione: https://stackoverflow.com/a/691674/47633

Sembra che le classi di tipo di Haskell sono implementati utilizzando impliciti in scala (come nell'esempio di DHG)

così finisce in questo modo:

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 qualche zucchero sintattico, appena

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

Eppure, penso che il compilatore dispone di informazioni sufficienti per farlo da solo ...

ps: prettied un po 'la funzione ...

Answer 3

ho appena venuto con questa soluzione.

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

Mi è venuta una soluzione piuttosto semplice che è facile da capire. Si occupa di una lista vuota, una lista con un solo elemento e numeri negativi.

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

ha attraversato un esercizio simile a quello del corrispondente OP sans modello e tipi generici, e si avvicinò con la seguente:

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