Qu'est-ce que le 'Pattern Matching' dans les langages fonctionnels?

Je lis sur la programmation fonctionnelle et j'ai remarqué que la correspondance de modèles est mentionnée dans de nombreux articles comme l'une des fonctionnalités de base des langages fonctionnels.

Quelqu'un peut-il expliquer à un développeur Java / C ++ / JavaScript ce que cela signifie?

Comprendre la correspondance de modèles nécessite d'expliquer trois parties:

1. Types de données algébriques.
2. Qu'est-ce que la correspondance de motifs
3. Pourquoi c'est génial.

Types de données algébriques en un mot

Les langages fonctionnels de type ML vous permettent de définir des types de données simples appelés «unions disjointes» ou «types de données algébriques». Ces structures de données sont de simples conteneurs et peuvent être définies de manière récursive. Par exemple:

type 'a list =
    | Nil
    | Cons of 'a * 'a list

définit une structure de données de type pile. Pensez-y comme équivalent à ce C #:

public abstract class List<T>
{
    public class Nil : List<T> { }
    public class Cons : List<T>
    {
        public readonly T Item1;
        public readonly List<T> Item2;
        public Cons(T item1, List<T> item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }
}

Ainsi, les identificateurs Conset Nildéfinissent une classe simple, où le of x * y * z * ...définit un constructeur et certains types de données. Les paramètres du constructeur ne sont pas nommés, ils sont identifiés par position et type de données.

Vous créez des instances de votre a listclasse en tant que telles:

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))

Ce qui équivaut à:

Stack<int> x = new Cons(1, new Cons(2, new Cons(3, new Cons(4, new Nil()))));

Correspondance de motifs en quelques mots

La correspondance de modèles est une sorte de test de type. Supposons donc que nous ayons créé un objet de pile comme celui ci-dessus, nous pouvons implémenter des méthodes pour jeter un coup d'œil et faire apparaître la pile comme suit:

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

let pop s =
    match s with
    | Cons(hd, tl) -> tl
    | Nil -> failwith "Empty stack"

Les méthodes ci-dessus sont équivalentes (bien que non implémentées en tant que telles) au C # suivant:

public static T Peek<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return hd;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

public static Stack<T> Pop<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return tl;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

(Presque toujours, les langages ML implémentent la correspondance de modèles sans tests de type ou casts au moment de l'exécution, donc le code C # est quelque peu trompeur.

Décomposition de la structure des données en quelques mots

Ok, revenons à la méthode peek:

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

L'astuce consiste à comprendre que les identificateurs hdet tlsont des variables (errm ... puisqu'ils sont immuables, ils ne sont pas vraiment des "variables", mais des "valeurs";)). Si sa le type Cons, alors nous allons extraire ses valeurs du constructeur et les lier aux variables nommées hdet tl.

La correspondance de motifs est utile car elle nous permet de décomposer une structure de données par sa forme au lieu de son contenu . Alors imaginez si nous définissons un arbre binaire comme suit:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

Nous pouvons définir certaines rotations d'arbres comme suit:

let rotateLeft = function
    | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
    | x -> x

let rotateRight = function
    | Node(Node(a, p, b), q, c) -> Node(a, p, Node(b, q, c))
    | x -> x

(Le let rotateRight = functionconstructeur est le sucre de syntaxe pour let rotateRight s = match s with ....)

Ainsi, en plus de lier la structure de données aux variables, nous pouvons également l'explorer. Disons que nous avons un nœud let x = Node(Nil, 1, Nil). Si nous appelons rotateLeft x, nous testons xle premier modèle, qui ne correspond pas car le bon enfant a le type Nilau lieu de Node. Il x -> xpassera au modèle suivant , qui correspondra à n'importe quelle entrée et le renverra sans modification.

À titre de comparaison, nous écririons les méthodes ci-dessus en C # comme suit:

public abstract class Tree<T>
{
    public abstract U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc);

    public class Nil : Tree<T>
    {
        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nilFunc();
        }
    }

    public class Node : Tree<T>
    {
        readonly Tree<T> Left;
        readonly T Value;
        readonly Tree<T> Right;

        public Node(Tree<T> left, T value, Tree<T> right)
        {
            this.Left = left;
            this.Value = value;
            this.Right = right;
        }

        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nodeFunc(Left, Value, Right);
        }
    }

    public static Tree<T> RotateLeft(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => r.Match(
                () => t,
                (rl, rx, rr) => new Node(new Node(l, x, rl), rx, rr))));
    }

    public static Tree<T> RotateRight(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => l.Match(
                () => t,
                (ll, lx, lr) => new Node(ll, lx, new Node(lr, x, r))));
    }
}

Pour sérieusement.

La correspondance des motifs est géniale

Vous pouvez implémenter quelque chose de similaire à la correspondance de modèles en C # en utilisant le modèle de visiteur , mais ce n'est pas aussi flexible car vous ne pouvez pas décomposer efficacement des structures de données complexes. De plus, si vous utilisez la correspondance de motifs, le compilateur vous dira si vous avez omis un cas . C'est vraiment génial?

Pensez à la façon dont vous implémenteriez des fonctionnalités similaires en C # ou en langages sans correspondance de modèle. Pensez à la façon dont vous le feriez sans tests de test et sans cast au moment de l'exécution. Ce n'est certainement pas difficile , juste encombrant et encombrant. Et vous ne faites pas vérifier par le compilateur pour vous assurer que vous avez couvert tous les cas.

Ainsi, la correspondance de modèles vous aide à décomposer et à parcourir les structures de données dans une syntaxe très pratique et compacte, elle permet au compilateur de vérifier la logique de votre code, au moins un peu. Il vraiment est une caractéristique de tueur.

Réponse courte: L' appariement de motifs survient parce que les langages fonctionnels traitent le signe égal comme une assertion d'équivalence au lieu d'affectation.

Réponse longue: La correspondance de modèles est une forme de répartition basée sur la «forme» de la valeur qui est donnée. Dans un langage fonctionnel, les types de données que vous définissez sont généralement ce que l'on appelle des unions discriminées ou des types de données algébriques. Par exemple, qu'est-ce qu'une liste (liée)? Une liste chaînée Listd'objets d'un certain type aest soit la liste vide, Nilsoit un élément de type a Consédité sur a List a(une liste de as). En Haskell (le langage fonctionnel avec lequel je suis le plus familier), nous écrivons ceci

data List a = Nil
            | Cons a (List a)

Toutes les unions discriminées sont définies de cette manière: un seul type a un nombre fixe de manières différentes de le créer; les créateurs, comme Nilet Consici, sont appelés constructeurs. Cela signifie qu'une valeur de type List aaurait pu être créée avec deux constructeurs différents - elle pourrait avoir deux formes différentes. Supposons donc que nous voulions écrire une headfonction pour obtenir le premier élément de la liste. Dans Haskell, nous écririons ceci comme

-- `head` is a function from a `List a` to an `a`.
head :: List a -> a
-- An empty list has no first item, so we raise an error.
head Nil        = error "empty list"
-- If we are given a `Cons`, we only want the first part; that's the list's head.
head (Cons h _) = h

Puisque les List avaleurs peuvent être de deux types différents, nous devons gérer chacune séparément; c'est la correspondance de motif. Dans head x, si xcorrespond au modèle Nil, alors nous exécutons le premier cas; s'il correspond au modèle Cons h _, nous exécutons le second.

Réponse courte, expliquée: Je pense que l'une des meilleures façons de penser à ce comportement est de changer la façon dont vous pensez du signe égal. Dans les langages entre accolades, en gros, =désigne l'affectation: a = bsignifie «faire aen b». Dans beaucoup de langages fonctionnels, cependant, =dénote une affirmation d'égalité: let Cons a (Cons b Nil) = frob x affirme que la chose à gauche Cons a (Cons b Nil),, est équivalente à la chose à droite frob x,; de plus, toutes les variables utilisées à gauche deviennent visibles. C'est aussi ce qui se passe avec les arguments de fonction: nous affirmons que le premier argument ressemble Nil, et si ce n'est pas le cas, nous continuons à vérifier.

Cela signifie qu'au lieu d'écrire

double f(int x, int y) {
  if (y == 0) {
    if (x == 0)
      return NaN;
    else if (x > 0)
      return Infinity;
    else
      return -Infinity;
  } else
     return (double)x / y;
}

Tu peux écrire

f(0, 0) = NaN;
f(x, 0) | x > 0 = Infinity;
        | else  = -Infinity;
f(x, y) = (double)x / y;

Hé, C ++ prend également en charge la correspondance de modèles.

static const int PositiveInfinity = -1;
static const int NegativeInfinity = -2;
static const int NaN = -3;

template <int x, int y> struct Divide {
  enum { value = x / y };
};
template <bool x_gt_0> struct aux { enum { value = PositiveInfinity }; };
template <> struct aux<false> { enum { value = NegativeInfinity }; };
template <int x> struct Divide<x, 0> {
  enum { value = aux<(x>0)>::value };
};
template <> struct Divide<0, 0> {
  enum { value = NaN };
};

#include <cstdio>

int main () {
    printf("%d %d %d %d\n", Divide<7,2>::value, Divide<1,0>::value, Divide<0,0>::value, Divide<-1,0>::value);
    return 0;
};

La correspondance de modèle est un peu comme des méthodes surchargées sur les stéroïdes. Le cas le plus simple serait à peu près le même que celui que vous avez vu en java, les arguments sont une liste de types avec des noms. La méthode correcte à appeler est basée sur les arguments transmis et elle sert également à affecter ces arguments au nom du paramètre.

Les modèles vont juste un peu plus loin et peuvent déstructurer encore plus les arguments passés. Il peut également potentiellement utiliser des gardes pour correspondre en fonction de la valeur de l'argument. Pour démontrer, je vais faire comme si JavaScript avait une correspondance de modèle.

function foo(a,b,c){} //no pattern matching, just a list of arguments

function foo2([a],{prop1:d,prop2:e}, 35){} //invented pattern matching in JavaScript

Dans foo2, il s'attend à ce que a soit un tableau, il sépare le deuxième argument, attend un objet avec deux accessoires (prop1, prop2) et attribue les valeurs de ces propriétés aux variables d et e, puis s'attend à ce que le troisième argument soit 35.

Contrairement à JavaScript, les langages avec correspondance de modèles autorisent généralement plusieurs fonctions avec le même nom, mais des modèles différents. De cette façon, c'est comme une surcharge de méthode. Je vais donner un exemple en erlang:

fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .

Brouillez un peu vos yeux et vous pouvez l'imaginer en javascript. Quelque chose comme ça peut-être:

function fibo(0){return 0;}
function fibo(1){return 1;}
function fibo(N) when N > 0 {return fibo(N-1) + fibo(N-2);}

Le fait est que lorsque vous appelez fibo, l'implémentation qu'il utilise est basée sur les arguments, mais où Java est limité aux types comme seul moyen de surcharge, la correspondance de modèles peut faire plus.

Au-delà de la surcharge de fonction comme indiqué ici, le même principe peut être appliqué à d'autres endroits, tels que les déclarations de cas ou les assingments de déstructuration. JavaScript a même cela dans la version 1.7 .

La correspondance de modèles vous permet de faire correspondre une valeur (ou un objet) à certains modèles pour sélectionner une branche du code. Du point de vue C ++, cela peut sembler un peu similaire à l' switchinstruction. Dans les langages fonctionnels, la correspondance de modèle peut être utilisée pour la correspondance sur des valeurs primitives standard telles que des entiers. Cependant, il est plus utile pour les types composés.

Tout d'abord, démontrons la correspondance de modèles sur les valeurs primitives (en utilisant le pseudo-C ++ étendu switch):

switch(num) {
  case 1: 
    // runs this when num == 1
  case n when n > 10: 
    // runs this when num > 10
  case _: 
    // runs this for all other cases (underscore means 'match all')
}

La seconde utilisation concerne les types de données fonctionnels tels que les tuples (qui vous permettent de stocker plusieurs objets dans une seule valeur) et les unions discriminées qui vous permettent de créer un type pouvant contenir l'une des nombreuses options. Cela ressemble un peu, enumsauf que chaque étiquette peut également porter certaines valeurs. Dans une syntaxe pseudo-C ++:

enum Shape { 
  Rectangle of { int left, int top, int width, int height }
  Circle of { int x, int y, int radius }
}

Une valeur de type Shapepeut maintenant contenir soit Rectangleavec toutes les coordonnées, soit a Circleavec le centre et le rayon. La correspondance de motifs vous permet d'écrire une fonction pour travailler avec le Shapetype:

switch(shape) { 
  case Rectangle(l, t, w, h): 
    // declares variables l, t, w, h and assigns properties
    // of the rectangle value to the new variables
  case Circle(x, y, r):
    // this branch is run for circles (properties are assigned to variables)
}

Enfin, vous pouvez également utiliser des modèles imbriqués qui combinent les deux fonctionnalités. Par exemple, vous pouvez utiliser Circle(0, 0, radius)pour faire correspondre toutes les formes qui ont le centre au point [0, 0] et ont un rayon quelconque (la valeur du rayon sera affectée à la nouvelle variable radius).

Cela peut sembler un peu inconnu du point de vue C ++, mais j'espère que mon pseudo-C ++ clarifiera l'explication. La programmation fonctionnelle est basée sur des concepts assez différents, elle a donc plus de sens dans un langage fonctionnel!

La correspondance de modèles est l'endroit où l'interpréteur de votre langue choisira une fonction particulière en fonction de la structure et du contenu des arguments que vous lui donnez.

Ce n'est pas seulement une fonctionnalité de langage fonctionnel, mais il est disponible pour de nombreuses langues différentes.

La première fois que je suis tombé sur cette idée, c'est lorsque j'ai appris le prologue où il est vraiment au cœur du langage.

par exemple

dernier ([LastItem], LastItem).

last ([Head | Tail], LastItem): - dernier (Tail, LastItem).

Le code ci-dessus donnera le dernier élément d'une liste. L'entrée arg est le premier et le résultat est le second.

S'il n'y a qu'un seul élément dans la liste, l'interpréteur choisira la première version et le second argument sera mis à égalité au premier, c'est-à-dire qu'une valeur sera attribuée au résultat.

Si la liste a à la fois une tête et une queue, l'interprète choisira la deuxième version et la répétera jusqu'à ce qu'il ne reste qu'un seul élément dans la liste.

Pour de nombreuses personnes, il est plus facile de choisir un nouveau concept si des exemples simples sont fournis, alors allons-y:

Supposons que vous ayez une liste de trois entiers et que vous vouliez ajouter le premier et le troisième élément. Sans correspondance de modèle, vous pouvez le faire comme ceci (exemples dans Haskell):

Prelude> let is = [1,2,3]
Prelude> head is + is !! 2
4

Maintenant, bien que ce soit un exemple de jouet, imaginez que nous aimerions lier le premier et le troisième entier à des variables et les additionner:

addFirstAndThird is =
    let first = head is
        third = is !! 3
    in first + third

Cette extraction de valeurs à partir d'une structure de données est ce que fait la correspondance de modèles. Vous "miroir" fondamentalement la structure de quelque chose, en donnant des variables à lier pour les lieux d'intérêt:

addFirstAndThird [first,_,third] = first + third

Lorsque vous appelez cette fonction avec [1,2,3] comme argument, [1,2,3] sera unifié avec [first _,, third], liant d'abord à 1, troisième à 3 et rejetant 2 ( _est un espace réservé pour les choses qui ne vous intéressent pas).

Maintenant, si vous vouliez seulement faire correspondre les listes avec 2 comme deuxième élément, vous pouvez le faire comme ceci:

addFirstAndThird [first,2,third] = first + third

Cela ne fonctionnera que pour les listes avec 2 comme deuxième élément et lèvera une exception dans le cas contraire, car aucune définition pour addFirstAndThird n'est donnée pour les listes non correspondantes.

Jusqu'à présent, nous n'utilisions la correspondance de modèles que pour la déstructuration de la liaison. Au-dessus de cela, vous pouvez donner plusieurs définitions de la même fonction, où la première définition correspondante est utilisée, ainsi, la correspondance de motif est un peu comme "une instruction de commutation sur les stéréoïdes":

addFirstAndThird [first,2,third] = first + third
addFirstAndThird _ = 0

addFirstAndThird ajoutera volontiers le premier et le troisième élément des listes avec 2 comme deuxième élément, et sinon "passer" et "retourner" 0. Cette fonctionnalité "de type interrupteur" ne peut pas seulement être utilisée dans les définitions de fonction, par exemple:

Prelude> case [1,3,3] of [a,2,c] -> a+c; _ -> 0
0
Prelude> case [1,2,3] of [a,2,c] -> a+c; _ -> 0
4

De plus, il n'est pas limité aux listes, mais peut également être utilisé avec d'autres types, par exemple en faisant correspondre les constructeurs de valeur Just and Nothing du type Maybe afin de "dérouler" la valeur:

Prelude> case (Just 1) of (Just x) -> succ x; Nothing -> 0
2
Prelude> case Nothing of (Just x) -> succ x; Nothing -> 0
0

Bien sûr, ce n'étaient que de simples exemples de jouets, et je n'ai même pas essayé de donner une explication formelle ou exhaustive, mais ils devraient suffire à saisir le concept de base.

Vous devriez commencer par la page Wikipédia qui donne une assez bonne explication. Ensuite, lisez le chapitre correspondant du wikibook Haskell .

C'est une belle définition du wikibook ci-dessus:

Ainsi, la correspondance de motifs est un moyen d'attribuer des noms à des choses (ou de lier ces noms à ces choses), et éventuellement de décomposer des expressions en sous-expressions en même temps (comme nous l'avons fait avec la liste dans la définition de la carte).

Voici un exemple très court qui montre l'utilité de la correspondance de modèles:

Disons que vous souhaitez trier un élément dans une liste:

["Venice","Paris","New York","Amsterdam"] 

à (j'ai trié "New York")

["Venice","New York","Paris","Amsterdam"] 

dans un langage plus impératif vous écririez:

function up(city, cities){  
    for(var i = 0; i < cities.length; i++){
        if(cities[i] === city && i > 0){
            var prev = cities[i-1];
            cities[i-1] = city;
            cities[i] = prev;
        }
    }
    return cities;
}

Dans un langage fonctionnel, vous écririez à la place:

let up list value =  
    match list with
        | [] -> []
        | previous::current::tail when current = value ->  current::previous::tail
        | current::tail -> current::(up tail value)

Comme vous pouvez le voir, la solution correspondant au modèle a moins de bruit, vous pouvez clairement voir quels sont les différents cas et à quel point il est facile de voyager et de déstructurer notre liste.

J'ai écrit un article de blog plus détaillé à ce sujet ici .