Maintenant que vous avez modifié pour poser une question presque complètement différente, je vais donner une réponse différente. Plutôt que de pointer vers un tutoriel sur les cartes et les plis, je vais en donner un.
Dans Scala, vous devez d'abord savoir comment créer une fonction anonyme. Il va comme si, de plus général 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, la méthode map
des listes et autres appliquera une fonction (anonyme ou autre) 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. Peut-être que vous avez un tas de chaînes et que vous voulez savoir combien de temps chacun est, ou vous voulez les faire tous en majuscules, ou vous voulez les revenir en arrière. Si vous avez une fonction qui fait ce que vous voulez un élément, carte fera à 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 la carte en général, et à Scala.
Mais que se passe-t-il si nous voulons collecter nos résultats? C'est là que le pli entre (foldLeft
étant la version qui commence à gauche et fonctionne bien). Supposons que nous ayons une fonction f:(B,A) => B
, c'est-à-dire qu'elle prenne un B et un A, et les combine pour produire un B. Eh bien, nous pourrions commencer par un B, et ensuite nourrir notre liste de A dans un à une fois, et à la fin de tout cela, nous aurions du B. C'est exactement ce que fait le pli. foldLeft
le fait à partir de l'extrémité gauche de la liste; foldRight
commence à partir de la droite. C'est,
List(a1,a2,...,aN) foldLeft(b0)(f)
produit
f(f(... f(f(b0,a1) , a2) ...), aN)
où b0
est, bien sûr, votre valeur initiale. Donc, peut-être que nous avons une fonction qui prend un int et une chaîne, et retourne l'int ou la longueur de la chaîne, selon celle qui est la plus grande - si nous avons plié notre liste en utilisant cela, elle nous dirait la plus longue (En supposant que nous commençons avec 0). Ou nous pourrions ajouter la longueur à l'int, accumulant des valeurs comme nous allons.
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
Bon, très bien, mais si nous voulons savoir qui est la plus longue? Un moyen (peut-être pas le meilleur, mais il illustre bien un modèle utile) est de porter à la fois la longueur (un entier) et le principal concurrent (une chaîne).Donnons qu'un coup:
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?)
Ici, i
est maintenant un tuple de type (Int,String)
et i._1
est la première partie de ce tuple (un Int).
Mais dans certains cas comme celui-ci, l'utilisation d'un pli n'est pas vraiment ce que nous voulons. Si nous voulons plus de deux chaînes, la fonction la plus naturelle serait une comme max:(String,String)=>String
. Comment appliquons-nous celui-là? Eh bien, dans ce cas, il y a un cas "le plus court" par défaut, donc nous pourrions replier la fonction string-max en commençant par "". Mais une meilleure façon est d'utiliser réduire. Comme avec fold, il existe deux versions, une qui fonctionne à partir de la gauche, l'autre qui fonctionne à partir de la droite. Il ne prend aucune valeur initiale et nécessite une fonction f:(A,A)=>A
. C'est-à-dire qu'il faut 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 n'y a que deux trucs supplémentaires. Tout d'abord, les deux signifient la même chose suivante:
list.foldLeft(b0)(f)
(b0 /: list)(f)
Remarquez que la seconde est plus courte, et ce genre de vous donne l'impression que vous prenez b0
et faire quelque chose à la liste avec elle (que vous êtes). (:\
est le même que foldRight
, mais vous l'utiliser comme ceci: (list :\ b0) (f)
Deuxièmement, si vous faites référence seulement à une variable une fois, vous pouvez utiliser _
au lieu du nom de variable et omettre la x =>
partie de la déclaration de 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 plan, plier, et de les réduire en utilisant Scala Ainsi, si vous savez comment votre algorithme devrait fonctionner, il doit être raisonnable facile à mettre en œuvre
Vous êtes dans le s Ame classe comme Tom? Voir http://stackoverflow.com/questions/2274852/scala-how-to-perform-pattern-matching-with-vararg-case-classes. – huynhjl
Ce n'est pas une question sur Scala et 'foldLeft'. C'est une question sur les algorithmes. Vous feriez mieux de demander _ "Comment puis-je calculer la plus petite boîte englobante à partir d'une liste de formes, en utilisant des structures de données immuables?" Marquer la question comme agnostique et algorithmes. Et peut-être la programmation fonctionnelle. Si vous rencontrez un problème lors de l'implémentation des algorithmes proposés dans Scala, vous ouvrez une question Scala à ce propos. La question actuelle est ciblée sur le mauvais groupe. –