Comment trouver le plus grand élément dans une liste d'entiers récursivement?
Je suis en train d'écrire une fonction récursive de trouver le plus grand élément dans une liste d'entiers. Je sais comment le faire en Java, mais ne peut pas comprendre comment le faire à la Scala.
Voici ce que j'ai à ce jour, mais sans la récursivité:
def max(xs: List[Int]): Int = {
if (xs.isEmpty) throw new java.util.NoSuchElementException();
else xs.max;
}
Comment peut-on le trouver de manière récursive avec Scala sémantique.
source d'informationauteur nazar_art
Vous devez vous connecter pour publier un commentaire.
C'est le plus minime récursive de la mise en œuvre de max je n'ai jamais été capable de penser, jusqu':
Il fonctionne en comparant les deux premiers éléments de la liste, à jeter le plus petit (ou le premier, si les deux sont égaux), puis en appelant lui-même sur le reste de la liste. Finalement, cela permettra de réduire la liste à un élément qui doit être le plus grand.
- Je retourner une Option pour traiter le cas d'une liste vide, sans jeter une exception, ce qui oblige le code appelant à reconnaître les risques et de les traiter avec elle (jusqu'à l'appelant si ils souhaitez lancer une exception).
Si vous voulez qu'il soit plus générique, il doit être écrit comme ceci:
Qui fonctionne avec n'importe quel type qui s'étend de la
Ordered
trait ou pour lesquels il y a une conversion implicite deA
àOrdered[A]
dans la portée. Donc par défaut il fonctionne pourInt
BigInt
Char
String
et ainsi de suite, parce que scala.Predef définit le nombre de conversions pour eux.Nous pouvons devenir encore plus générique comme ceci:
Qui fonctionne non seulement avec les listes, mais les vecteurs et toute autre collection qui s'étend de la
Seq
trait. Notez que j'ai dû ajouter une vérification pour voir si la séquence a en fait une certaine taille, il pourrait être un courant infini, nous avons donc marche arrière si cela pourrait être le cas. Si vous êtes sûr de votre flux, vous avez une certaine taille, vous pouvez toujours forcer avant d'appeler cette fonction, il va parcourir l'ensemble des flux de toute façon. Voir les notes à la fin pour expliquer pourquoi je vraiment ne voudrait pas retournerNone
pour une durée indéterminée de flux, si. Je suis en train de faire ici purement pour des raisons de simplicité.Mais cela ne fonctionne pas pour les ensembles et des cartes. Que faire? La prochaine commun supertype est
Iterable
mais qui ne prend pas en chargeupdated
ou quelque chose d'équivalent. Tout ce que nous construction peut être très performants pour le type réel. Donc mon propre pas-helper-fonction de la récursivité se décompose. Nous pourrait changement à l'aide d'une fonction d'assistance, mais il y a beaucoup d'exemples dans les autres réponses et je vais m'en tenir à une simple fonction de l'approche. Donc, à ce stade, nous pouvons passer àreduceLeft
(et tant que nous y sommes, allons-y pour "Traversable" et répondre à tous collections):mais si vous ne considérez pas reduceLeft récursive, on peut faire ceci:
Il utilise le
collect
combinator pour éviter une lourde méthode de bodging un nouvel Itérateur dexs.head
etxs drop 2
.L'une de ces permettra de travailler en toute sécurité avec presque n'importe quelle collection de tout ce qui a un ordre. Exemples:
Je n'ai pas l'habitude de donner à ces autres que des exemples, car il nécessite plus de connaissances d'experts de la Scala.
Aussi, ne pas oublier que la base
Traversable
trait fournit unmax
méthode, donc c'est juste pour la pratique 😉Remarque: j'espère que tous mes exemples montrent comment le choix de la séquence de votre cas expressions peuvent rendre chaque cas individuel d'expression aussi simple que possible.
Plus Important Remarque: Oh, aussi, alors je suis particulièrement à l'aise de retourner
None
pour une entrée deNil
dans la pratique, je serais fortement enclin à jeter une exception pourhasDefiniteSize == false
. Tout d'abord, une durée de flux pourrait avoir une nette ou non-définitive dépend de la taille purement sur la séquence de l'évaluation et cette fonction de manière efficace au hasard de retourOption
dans ces cas - ce qui pourrait prendre un certain temps à traquer. Deuxièmement, je veux que les gens à être en mesure de différencier entre le fait d'avoir passéNil
et ayant passé vraiment de risque d'entrée (qui est, un courant infini). Je ne retournaOption
dans ces manifestations pour que le code soit aussi simple que possible.L'approche la plus simple serait d'utiliser la fonction max de
TraversableOnce
trait, comme suit,pour se prémunir contre le vide que vous pouvez faire quelque chose comme cela,
Ci-dessus vous donnera une
Option[Int]
Ma deuxième approche serait d'utiliser
foldLeft
ou si vous connaissez une valeur par défaut retournée dans le cas de la liste vide, cela deviendra plus simple.
De toute façon depuis votre exigence est de le faire de manière récursive, je vous propose la suite,
ou que les cas de défaillance,
Noter que, c'est
tail recursive
. Par conséquent, la pile est également enregistré.Si vous voulez approche fonctionnelle de ce problème alors utiliser
reduceLeft
:Cette fonction spécifique pour la liste d'entiers, si vous avez besoin de plus approche générale puis utilisez
Ordering
typeclass:reduceLeft
est une fonction d'ordre supérieur, qui prend une fonction de type(A, A) => A
il ce cas, il prend deux entiers, les compare et retourne le plus grand.Vous pouvez utiliser le pattern matching comme ça
Scala est un langage fonctionnel par lequel on est d'encourager à penser de manière récursive. Ma solution ci-dessous. Je réapparaître il base sur votre méthode donnée.
Mis à jour ma solution à la queue récursive grâce aux suggestions.
J'ai utilisé juste la tête() et la queue ()
Ici, c'est de tester:
Pliage peut aider:
Liste et le pattern matching (mis à jourgrâce à @x3ro)
(Cette solution ne permet pas de créer
Option
instance à chaque fois. Il est également récursives terminales et sera aussi rapide qu'un impératif solution).Dirait que vous êtes débutant avec la scala, j'ai donc essayer de vous donner la réponse la plus simple pour votre réponse, comment le faire de manière récursive:
Cette méthode définit une méthode interne (
maxrec
) pour prendre soin de l'ressemble. Ce sera un échec ( exception), il vous donnera une liste vide ( il n'y a pas de maximum sur une Liste vide)liste.sortWith(_ > ).head & liste.sortWith( > _).inverse.tête pour le plus grand et le plus petit nombre
Si vous devez écrire un récursif de la fonction max sur une liste à l'aide de la fonction isEmpty, la tête et la queue et jeter l'exception de la liste vide:
si vous étiez à utiliser la fonction max sur la liste, il est tout simplement (vous n'avez pas besoin d'écrire votre propre fonction récursive):