scala: mettre en œuvre un générique récursif de la fonction max

J'essaie de port ce haskell max implémentation de la fonction à la scala

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

Ceci est ma première tentative:

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

Mais j'obtiens l'erreur suivante:

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

J'ai essayé avec la commande, comprable, etc avec des résultats similaires...

La moindre idée de ce qu'il manque?

InformationsquelleAutor opensas | 2012-09-20

Peut-être que vous voulez le Ordering type de classe?

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
}

C'est, après tout, comment l'intégré dans max méthode fonctionne:

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

Vous pouvez nettoyer les choses beaucoup si vous faites cela:

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

Ou, vous pouvez en faire la queue-récursive pour une meilleure efficacité (parce que le compilateur de l'optimiser):

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

Aussi, vous devriez jeter RuntimeException ou une sous-classe, pas Error.

+1 pour avoir un coup d'oeil à la source... (je n'ai pas encore assez de courage... l'utilisation de la source!!!)
Je suppose que l'aide de l'ord.max serait comme de la triche, je fais ça juste pour des fins éducatives... de toute façon, j'ai créé un maxElement fonction d'assistance pour éviter que val, il n'y...
ord.max est différente de List.max. L'un est à la base un opérateur qui compare deux choses, tandis que l'autre est une méthode d'un ensemble de la collection. Ils ont juste arriver à avoir le même nom.
vous avez raison, je comprends maintenant, j'ai fini par mettre en place si moi-même...

InformationsquelleAutor dhg

Est allé par le biais d'un exercice similaire que l'OP sans filtrage et de types génériques, et est venu avec les éléments suivants:

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

> return max(xs.la tête, max(xs.la queue)) Vous ne pouvez pas faire cet appel, que vous n'avez pas la fonction max(x: Int, xs: List[Int]) défini.

InformationsquelleAutor dejon97

5

J'ai juste de venir avec cette solution.
```
def max(xs: List[Int]): Int = {
    if (xs.isEmpty) 0
    else {
      if( xs.head >= max(xs.tail) ) xs.head
      else max(xs.tail)
    }
}
```
- Je pense que ce n'est pas une solution générique
- Non, mais j'ai rites de l'attacher à la plus pertinente question, actuellement, c'est l'un.
- À proximité, mais votre solution ne fonctionne pas pour les nombres négatifs (essayez max(List(-3, -7, -2)). Cela peut être résolu en modifiant la seconde if à if( xs.tail.isEmpty || xs.head >= max(xs.tail) ).
- Merci
- Pas de probs, peut-être que vous pouvez mettre à jour votre réponse à l'aide de quelqu'un d'autre. Vous devez également lancer une exception si la liste est vide, comme 0 est incorrect (max peut aussi être négative).
InformationsquelleAutor eomeroff

Je suis venu avec une solution simple qui est facile à comprendre. Il accueille une liste vide, une liste avec un seul élément, et les nombres négatifs.

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

InformationsquelleAutor Hegemon

0

Oups, aurais dû regarder mieux avant de demander

J'ai trouvé la réponse dans ce fil: https://stackoverflow.com/a/691674/47633

Il semble que Haskell des classes de type sont mis en œuvre à l'aide implicites dans scala (comme dans la dhg de l'exemple)

de sorte qu'il se termine comme ça:
```
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))
  }
} 
```
ou avec un sucre syntaxique, juste
```
def max[T <% Ordered[T]](list: List[T]): T = list match {
```
Encore, je pense que le compilateur a suffisamment d'informations pour le faire par lui-même...

ps: je prettied un peu la fonction...

InformationsquelleAutor opensas

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

ou, si nécessaire, seulement la fonction max avec la queue de la récursivité et le type de l'Option[_] ne pas casser la transparence référentielle

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

InformationsquelleAutor flydes

0

c'est la façon la plus simple qui me vient en tête:
```
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)}  }
```
- Relativement simple, vrai, mais massivement inefficace. Un petit List de seulement 7 éléments, avec le max élément à la fin, répète 126 fois. Changement à 8 éléments et il parcourt 254 fois, soit environ le double pour chaque (plus petit) élément ajouté (avant la fin).
InformationsquelleAutor Hind Ahmad
0

cela fonctionne
```
def max(xs: List[Int]): Int = xs match{
  case Nil => 0
  case head :: Nil => head
  case head :: tail => max(List(head, max(tail)))
}
```
- Malheureusement, ce n'est pas générique, comme demandé dans le titre, et il ne fonctionne pas. Pour les listes de deux ou plusieurs éléments, il est infiniment récursive.
InformationsquelleAutor Jay A
-1

Mon résoudre:
```
  def max(xs: List[Int]): Int = {
    if (xs.isEmpty) 0
    else xs.max
  }
```
- Ce n'est pas récursif, ce qui est ce qui a été demandé (il y a 6 ans).
InformationsquelleAutor Buggi

Vous devez vous connecter pour publier un commentaire.