Active patterns
By Laurent Le Brun on Sunday, July 15 2007, 01:57 - [FR] Cours F# - Permalink
Ce billet est basé en grande partie sur le papier Extensible Pattern Matching via a Lightweight Language Extension. Il présente le concept d'active patterns, une généralisation du pattern matching.
Ce billet est basé en grande partie sur le papier Extensible Pattern Matching via a Lightweight Language Extension.
Introduction
La principale limitation du pattern matching dans Caml est son manque d'interaction avec la notion d'abstraction. En effet, le pattern matching est avant tout une déconstruction des types. Il faut donc que le constructeur et la structure interne du type soient connus. Si le pattern matching est extrêmement puissant quand il est utilisé sur des listes, des arbres, des types somme, des tuples ou des structures, il est relativement inefficace sur les objets (qui peuvent notamment avoir des membres privés). Il est aussi inefficace sur les types d'une bibliothèque externe : les détails de l'implémentation sont souvent cachés. Bref, abstraction et pattern matching se marient mal.
F#, de par son intégration dans .NET, est amené à manipuler souvent des objets (venant par exemple de C#). Le pattern matching étant très important dans les langages fonctionnels, F# a dû chercher a combiner les deux. Cela fait plus de vingt ans que des gens en parlent, il y a eu des propositions faites pour ajouter le pattern matching en Java, mais F# est le premier langage à implémenter efficacement la solution : cela s'appelle les active patterns (ou "motifs actifs" ? Bon, je garde le terme anglais).
Les active patterns sont de simples fonctions - avec une syntaxe spéciale - qui définissent comment déconstruire une valeur. En F#, il y a 4 types d'active patterns, ce qui permet la plus grande souplesse.
Active pattern complet, avec un seul choix
Imaginons que l'on souhaite manipuler des nombres complexes. On utilise une classe dont la représentation interne n'est pas accessible. On souhaite tout de même utiliser du pattern matching dessus. On peut écrire le code suivant en F# :
[fsharp] let (|Rect|) (x:complex) = (x.RealPart, x.ImaginaryPart) let add a b = match a, b with | Rect(ar,ai), Rect(br,bi) -> mkRect(ar+br, ai+bi)
On a défini un active pattern Rect, qui indique que le nombre complexe se décompose en un couple de flottants (partie réelle, partie imaginaire). Bien sûr, la fonction peut être écrite plus simplement, puisque le pattern matching est accepté au niveau du let (quand il n'y a qu'un seul cas à traiter) :
[fsharp] let add (Rect(ar,ai)) (Rect(br,bi)) = mkRect(ar+br,ai+bi)
La fonction Rect est exécutée à chaque fois que l'on rentre dans le pattern matching. Rect est typée comme une fonction classique, ici elle a pour type "Complex -> float * float". Elle peut également être utilisée comme une fonction ordinaire :
[fsharp] let c = mkRect(3., 4.) (|Rect|) c
Ce code renvoie bien le couple (3.0, 4.0). On peut également définir une autre façon de décomposer le nombre complexe :
[fsharp] let (|Polar|) (x:complex) = (x.Magnitude, x.Phase)
Les active patterns sont donc une solution pour pouvoir décomposer une même valeur de plusieurs façons, indépendamment de la déclaration du type, selon les besoins.
Active pattern complet, à choix multiple
Bien souvent, on souhaite décomposer une valeur en plusieurs cas. Par exemple : une liste peut être soit vide, soit un élément suivi d'une liste. On souhaite donc pouvoir poser une condition dans le pattern matching.
[fsharp] let (|Cons|Nil|) l = if nonempty l then Cons(hd l,tl l) else Nil
On a une fonction qui renvoie soit Cons, soit Nil. Cette fonction a pour type : 'a list -> Choice<('a * 'a list),unit>. Le type est un peu particulier. Il faut le comprendre comme : soit la fonction renvoie Cons et une valeur de type "'a * 'a list" ; soit elle renvoie Nil. Le type peut sembler inhabituel, mais c'est pour que tout soit parfaitement et fortement typé. En fait, il faut surtout voir cela comme étant un type somme anonyme. Il est à noter que le type Choice peut être paramétré par un, deux, trois ou plus paramètres. La gestion des generics dans .NET permet en effet la surcharge des types sur l'arité du constructeur.
Voici un exemple d'utilisation :
[fsharp] let rec pairSum xs = match xs with | Cons(x, Cons(y,ys)) -> x + y | Cons(x, Nil()) -> x | Nil() -> 0
Puisque la fonction de décomposition renvoie forcément Cons ou Nil, le compilateur est capable de vérifier statiquement l'exhaustivité du matching et sa non-redondance (dans les limites habituelles).
Active pattern partiel, à choix unique
Les exemples précédents ont montré comment décomposer de manière totale : tous les cas étaient gérés. Cependant, on souhaite parfois effectuer de simples tests, indépendants les uns des autres. En Caml, on utiliserait probablement une succession peu esthétique de "when". En F#, on veut plutôt pouvoir écrire :
[fsharp] match str with | ParseInt i -> IntVal i | ParseFloat f -> FloatVal f | ParseDate d -> DateVal d | ParseColor c -> ColorVal c | _ -> failwith "unrecognized data"
Les 4 active patterns ci-dessus ne forment pas une décomposition complète du type string. Ils peuvent aussi être redondants : la chaine "0" pourrait très bien correspondre aux motifs ParseInt et ParseFloat.
[fsharp] let (|ParseInt|_|) s = let i = ref 0 if Int32.TryParse(s, i) then Some !i else None
La fonction teste l'argument et renvoie soit un résultat de n'importe quel type (dans le Some), soit rien (None). Ici, ParseInt renvoie une valeur de type "int option", alors que le retour de ParseFloat a pour type "float option". Du coup, dans le pattern matching plus haut, la valeur i a pour type int, et la valeur f a pour type float. On peut définir les autres patterns de la même façon que ParseInt.
Active pattern paramétré
On peut également désirer paramétrer un motif. Imaginons que l'on souhaite faire correspondre une chaine à plusieurs expressions rationnelles. On ne souhaite pas définir un nouvel active pattern pour chaque expression. À la place, on préfère définir un pattern expression rationnelle, et le paramétrer par l'expression.
[fsharp] let foo s = match s with | ParseRegex "^ *$" _ -> "" | ParseRegex "http://(www\\.)?(.*)" [_;u] -> u | ParseRegex "(\\w+)-(\\w+)" [l;r] -> r ^ "-" ^ l | _ -> s
Ce qui donne :
[fsharp] foo " " = "" foo "http://www.foo.com" = "foo.com" foo "abc-def" = "def-abc" foo "bar" = "bar"
La définition de ParseRegex est assez simple. Il faut juste remarquer que la fonction prend un argument supplémentaire : le paramètre du pattern.
[fsharp] open System.Text.RegularExpressions let (|ParseRegex|_|) re s = let m = Regex(re).Match(s) if m.Success then Some (List.tl [ for x in m.Groups -> x.Value ]) else None
Conclusion
Il est désormais possible, grâce aux active patterns, d'avoir du pattern matching sur n'importe quel type, quelle que soit sa définition. Le papier cité en introduction présente notamment une façon d'utiliser les active patterns sur un document XML (de la bibliothèque .NET). Une fois les définitions des patterns faites, l'objet XML se manipule très élégamment, comme si c'était un simple type somme.
Last comments