Maintenant que vous avez modifié votre question pour en poser une presque totalement différente, je vais y répondre différemment. Plutôt que de pointer vers un tutoriel sur les cartes et les plis, je vais simplement en donner un.
En Scala, vous devez d'abord savoir comment créer une fonction anonyme. Cela se passe comme suit, du plus général au plus spécifique :
(var1: Type1, var2: Type2, ..., varN: TypeN) => /* output */
(var1, var2, ..., varN) => /* output, if types can be inferred */
var1 => /* output, if type can be inferred and N=1 */
Voici quelques exemples :
(x: Double, y: Double, z: Double) => Math.sqrt(x*x + y*y + z*z)
val f:(Double,Double)=>Double = (x,y) => x*y + Math.exp(-x*y)
val neg:Double=>Double = x => -x
Maintenant, le map de listes et autres appliquera une fonction (anonyme ou non) à chaque élément de la carte. Autrement dit, si vous avez
List(a1,a2,...,aN)
f:A => B
puis
List(a1,a2,...,aN) map (f)
produit
List( f(a1) , f(a2) , ..., f(aN) )
Il y a toutes sortes de raisons pour lesquelles cela pourrait être utile. Vous avez peut-être un tas de chaînes de caractères et vous voulez connaître la longueur de chacune d'entre elles, ou vous voulez qu'elles soient toutes en majuscules, ou vous voulez qu'elles soient inversées. Si vous avez une fonction qui fait ce que vous voulez un la carte le fera pour tous les éléments :
scala> List("How","long","are","we?") map (s => s.length)
res0: List[Int] = List(3, 4, 3, 3)
scala> List("How","capitalized","are","we?") map (s => s.toUpperCase)
res1: List[java.lang.String] = List(HOW, CAPITALIZED, ARE, WE?)
scala> List("How","backwards","are","we?") map (s => s.reverse)
res2: List[scala.runtime.RichString] = List(woH, sdrawkcab, era, ?ew)
Donc, c'est map en général, et en Scala.
Mais que faire si nous voulons collecter nos résultats ? C'est là que le pli intervient ( foldLeft étant la version qui commence à gauche et travaille à droite).
Supposons que nous ayons une fonction f:(B,A) => B Nous pourrions commencer avec un B, puis y introduire notre liste de A un par un, et à la fin, nous aurions un B. C'est exactement ce que fait le pli. foldLeft le fait en commençant par l'extrémité gauche de la liste ; foldRight commence par la droite. C'est-à-dire,
List(a1,a2,...,aN) foldLeft(b0)(f)
produit
f( f( ... f( f(b0,a1) , a2 ) ... ), aN )
où b0 est, bien entendu, votre valeur initiale.
Ainsi, nous disposons peut-être d'une fonction qui prend un int et une chaîne de caractères et renvoie l'int ou la longueur de la chaîne de caractères, selon la valeur la plus élevée. Si nous plions notre liste en utilisant cette fonction, elle nous indiquerait la chaîne de caractères la plus longue (en supposant que nous commencions par 0). Ou nous pourrions ajouter la longueur à l'int, en accumulant les valeurs au fur et à mesure.
Faisons un essai.
scala> List("How","long","is","longest?").foldLeft(0)((i,s) => i max s.length)
res3: Int = 8
scala> List("How","long","is","everyone?").foldLeft(0)((i,s) => i + s.length)
res4: Int = 18
Ok, très bien, mais si nous voulons savoir qui est le plus long ? Une façon de procéder (qui n'est peut-être pas la meilleure, mais qui illustre bien un modèle utile) consiste à transporter à la fois la longueur (un nombre entier) et le premier prétendant (une corde). Faisons un essai :
scala> List("Who","is","longest?").foldLeft((0,""))((i,s) =>
| if (i._1 < s.length) (s.length,s)
| else i
| )
res5: (Int, java.lang.String) = (8,longest?)
Aquí, i est maintenant un tuple de type (Int,String) y i._1 est la première partie de ce tuple (un Int).
Mais dans certains cas comme celui-ci, utiliser un pli n'est pas vraiment ce que nous voulons. Si nous voulons la plus longue de deux chaînes de caractères, la fonction la plus naturelle serait une fonction du type max:(String,String)=>String . Comment appliquer celui-là ?
Dans ce cas, il y a un cas par défaut "le plus court", donc nous pourrions plier la fonction string-max en commençant par "". Mais une meilleure solution consiste à utiliser réduire le site . Comme pour le pli, il existe deux versions, l'une qui fonctionne à gauche, l'autre qui fonctionne à droite. Elle ne prend pas de valeur initiale, et nécessite une fonction f:(A,A)=>A . C'est-à-dire qu'elle prend deux choses et en retourne une du même type. Voici un exemple avec une fonction string-max :
scala> List("Who","is","longest?").reduceLeft((s1,s2) =>
| if (s2.length > s1.length) s2
| else s1
| )
res6: java.lang.String = longest?
Maintenant, il y a juste deux autres astuces. D'abord, les deux suivantes signifient la même chose :
list.foldLeft(b0)(f)
(b0 /: list)(f)
Remarquez que la seconde est plus courte et vous donne l'impression que vous êtes en train de prendre b0 et faire quelque chose à la liste avec (ce que vous faites). ( :\ est la même chose que foldRight mais vous l'utilisez comme ça : (list :\ b0) (f)
Deuxièmement, si vous ne faites référence à une variable qu'une seule fois, vous pouvez utiliser _ à la place du nom de la variable et omettre le x => de la déclaration de la fonction anonyme. Voici deux exemples :
scala> List("How","long","are","we?") map (_.length)
res7: List[Int] = List(3, 4, 3, 3)
scala> (0 /: List("How","long","are","we","all?"))(_ + _.length)
res8: Int = 16
À ce stade, vous devriez être en mesure de créer des fonctions et de les mapper, les plier et les réduire à l'aide de Scala. Ainsi, si vous savez comment votre algorithme doit fonctionner, il devrait être raisonnablement simple de l'implémenter.
