Ce qui est ' Pattern Matching ' dans les langages fonctionnels ?

Question

Je lis sur la programmation fonctionnelle (à but académique) et j’ai remarqué que Pattern Matching est mentionné dans de nombreux articles comme l’une des caractéristiques fondamentales des langages fonctionnels.

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

Answer 1

La compréhension de la correspondance de modèle nécessite d'expliquer en trois parties:

1. Types de données algébriques.
2. Ce filtrage est
3. Pourquoi c'est génial.

Types de données algébriques en un mot

ML-comme les langages fonctionnels vous permettent de définir des types de données simples appelé "disjoints des syndicats" ou "types de données algébriques". Ces structures de données sont de simples conteneurs, et peut être définie de manière récursive. Par exemple:

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

définit une pile comme structure de données. Il pense que l'équivalent de 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, l' Cons et Nil identifiants définir simple d'une classe simple, où l' of x * y * z * ... définit un constructeur et certains types de données. Les paramètres du constructeur sont sans nom, ils sont identifiés par la position et le type de données.

Vous créez des instances de votre a list de la classe en tant que telle:

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

Qui est le même que:

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

La correspondance de motif dans un mot

Le Pattern matching est une sorte d'essais de type. Donc, disons que nous avons créé une pile d'objet comme celui ci-dessus, nous pouvons mettre en œuvre des méthodes de peek et de la pop 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 n'étant pas mis en œuvre en tant que telle) à la suite de C#:

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, ML langues implémenter le pattern matching sans de type à l'exécution de tests ou de moulages, de sorte que le code C# est quelque peu trompeur. Laissez la brosse détails de mise en œuvre de côté avec quelques à la main en agitant s'il vous plaît :) )

La structure de données de décomposition en un mot

Ok, revenons à la méthode lire:

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

Le truc est de comprendre que l' hd et tl identificateurs de variables (errm... car ils sont immuables, ils ne sont pas vraiment des "variables", mais "valeurs" ;) ). Si s type Cons, puis nous allons sortir de ses valeurs, de constructeur et de les lier à des variables nommées hd et tl.

Le Pattern matching est utile, car elle nous permet de décomposer une structure de données par sa forme à la place 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 quelques rotations de l'arbre 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

( let rotateRight = function Constructeur est la syntaxe de sucre pour let rotateRight s = match s with ....)

Donc, en plus de la liaison de la structure de données pour les variables, on peut aussi descendre en elle. Disons que nous avons un nœud let x = Node(Nil, 1, Nil). Si nous appelons rotateLeft x, nous testons x contre le premier modèle, qui ne parvient pas à égaler, parce que le droit de l'enfant de type Nil au lieu de Node. Il se déplacera pour le motif suivant, x -> x, qui correspondent à n'importe quelle entrée et de le retourner sans modification.

Pour comparaison, nous aimerions écrire les méthodes ci-dessus en C#:

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 au sérieux.

Le Pattern matching est génial

Vous pouvez mettre en place quelque chose de similaire à la correspondance de motif en C# à l'aide du modèle visiteur, mais ce n'est pas près d'aussi flexible car vous ne pouvez pas effectivement décomposer les structures de données complexes. En outre, si vous utilisez le filtrage, le compilateur va vous dire si vous avez quitté un cas. C'est pas génial?

Pensez à comment vous pouvez mettre en œuvre une fonctionnalité similaire en C# ou en langues, sans filtrage. Pensez à comment vous pouvez le faire sans test-tests et les jette au moment de l'exécution. Son certainement pas dur, juste lourd et encombrant. Et vous n'avez pas le compilateur de vérifier que vous avez couvert tous les cas.

Afin de filtrage vous permet de décomposer et de naviguer dans des structures de données dans un emplacement très pratique, syntaxe compacte, il permet au compilateur de vérifier la logique de votre code, au moins un peu. Il vraiment est une killer feature.

Answer 2

Réponse courte: Pattern matching se pose parce que les langages fonctionnels traiter le signe égal comme une affirmation de l'équivalence au lieu d'affectation.

Réponse longue: le Pattern matching est une forme de l'expédition basée sur la “forme” de la valeur de la donnée. Dans un langage fonctionnel, les types de données que vous définissez sont généralement ce qu'on appelle les victimes de syndicats ou des types de données algébriques. Par exemple, qu'est ce qu'un (liée) à la liste? Une liste chaînée List de choses d'un certain type a est soit la liste vide Nil ou un élément de type a Consed sur un List a (une liste d' as). En Haskell (le langage fonctionnel je suis plus familier avec), nous écrivons ce

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

Toutes les victimes de syndicats sont définis de cette façon: un seul type a un nombre fixe de différentes façons pour créer; les créateurs, comme Nil et Cons ici, sont appelées des constructeurs. Cela signifie qu'une valeur de type List a pourrait avoir été créé avec deux différents constructeurs—il peut avoir deux formes différentes. Supposons donc que nous voulons écrire un head fonction pour obtenir le premier élément de la liste. En Haskell, nous devons écrire ce que

-- `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

Depuis List a valeurs peuvent être de deux types différents, nous avons besoin de traiter séparément chacun d'eux; c'est le pattern matching. En head x, si x correspond au modèle Nil, alors nous courons le premier cas; si elle correspond au modèle Cons h _, nous courons le deuxième.

Réponse courte, a expliqué: je pense que l'une des meilleures façons de penser à ce problème est de changer la façon dont vous pensez du signe égal. Dans le frisé support de langues, en gros, = indique l'affectation: a = b signifie “faire a en b.” Dans beaucoup de langages fonctionnels, cependant, = indique une affirmation de l'égalité: let Cons a (Cons b Nil) = frob x affirme que la chose sur la gauche, Cons a (Cons b Nil), est l'équivalent de la chose, sur la droite, frob x; en outre, toutes les variables utilisées sur la gauche est devenu visible. C'est aussi ce qui se passe avec les arguments de la fonction: nous affirmons que le premier argument ressemble Nil, et si ça ne marche pas, on peut garder le contrôle.

Answer 3

Cela signifie qu’au lieu d’écrire

Vous pouvez écrire

---

Hé, C++ prend en charge les filtrages trop.

Answer 4

Le Pattern matching est un peu comme les méthodes surchargées sur les stéroïdes. Le cas le plus simple serait le même à peu près le même que vous avez vu en java, les arguments sont d'une liste de types avec des noms. La bonne méthode à appeler est basée sur les arguments passés, et il se double d'une cession de ces arguments, le nom du paramètre.

Modèles juste aller une étape plus loin et se déstructurent les arguments passés en encore plus loin. Il peut aussi éventuellement utiliser des gardes à fait match en fonction de la valeur de l'argument. Pour le démontrer, je vais faire comme si JavaScript avait pattern matching.

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 à être un tableau, elle se divise la deuxième argument, s'attendant à un objet avec deux accessoires (prop1,prop2) et affecte les valeurs de ces propriétés à des variables d et e, puis attend le troisième argument à 35.

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

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

Flou un peu les yeux et vous pouvez imaginer cela en javascript. Quelque chose comme ceci 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 Point étant que lorsque vous appelez fibo, la mise en œuvre, il utilise est basée sur les arguments, mais où Java est limitée à des types comme le seul moyen de surcharge, le filtrage n'en peut plus.

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

Answer 5

Filtrage vous permet de faire correspondre une valeur (ou un objet) à l'encontre de certains modèles pour sélectionner une branche de la code. À partir du C++ point de vue, il peut sembler un peu similaire à l' switch déclaration. Dans les langages fonctionnels, le filtrage peut être utilisée pour la correspondance sur la norme des valeurs primitives comme des entiers. Cependant, il est plus utile pour le composé types.

Tout d'abord, nous allons démontrer le filtrage sur les valeurs primitives (à l'aide de longues pseudo-C++ 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')
}

Les cpdn traite de l'utilisation fonctionnelle des types de données tels que les n-uplets (qui vous permettent de stocker plusieurs objets en une seule valeur) et les victimes de syndicats qui vous permettent de créer du texte qui peut contenir une ou plusieurs options. Cela sonne un peu comme enum sauf que chaque étiquette peut également effectuer certaines valeurs. Dans un pseudo-syntaxe 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 Shape peut maintenant contenir Rectangle avec toutes les coordonnées ou un Circle avec le centre et le rayon. La correspondance de modèle vous permet d'écrire la fonction de travail avec l' Shape type:

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 imbriqués les modèles qui combinent à la fois des caractéristiques. Par exemple, vous pouvez utiliser Circle(0, 0, radius) de match pour toutes les formes qui ont dans le centre le point de [0, 0], et ont un rayon de (la valeur du rayon sera affectée à la variable radius).

Cela peut sembler un peu inconnu à partir du C++ point de vue, mais j'espère que mon pseudo C++ de faire l'explication claire. La programmation fonctionnelle est basée sur des concepts différents, de sorte qu'il est plus logique dans un langage fonctionnel!