O que é 'Correspondência de Padrões' em linguagens funcionais?

Estou lendo sobre programação funcional e notei que a correspondência de padrões é mencionada em muitos artigos como um dos principais recursos das linguagens funcionais.

Alguém pode explicar para um desenvolvedor Java / C ++ / JavaScript o que isso significa?

Para entender a correspondência de padrões, é necessário explicar três partes:

1. Tipos de dados algébricos.
2. O que é a correspondência de padrões
3. Por que é incrível.

Tipos de dados algébricos em poucas palavras

As linguagens funcionais do tipo ML permitem definir tipos de dados simples chamados "uniões disjuntas" ou "tipos de dados algébricos". Essas estruturas de dados são contêineres simples e podem ser definidas recursivamente. Por exemplo:

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

define uma estrutura de dados do tipo pilha. Pense nisso como equivalente a este 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;
        }
    }
}

Portanto, os identificadores Conse Nildefinem uma classe simples e simples, onde of x * y * z * ...define um construtor e alguns tipos de dados. Os parâmetros para o construtor não têm nome, são identificados por posição e tipo de dados.

Você cria instâncias da sua a listclasse como tal:

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

Qual é o mesmo que:

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

Correspondência de padrões em poucas palavras

A correspondência de padrões é um tipo de teste de tipo. Então, digamos que criamos um objeto de pilha como o descrito acima, podemos implementar métodos para espiar e exibir a pilha da seguinte maneira:

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"

Os métodos acima são equivalentes (embora não implementados como tais) aos seguintes 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();
}

(Quase sempre, as linguagens ML implementam a correspondência de padrões sem testes de tipo ou conversão em tempo de execução; portanto, o código C # é um tanto enganador. Vamos deixar de lado os detalhes da implementação com alguns acenos de mão :))

Decomposição da estrutura de dados em poucas palavras

Ok, vamos voltar ao método peek:

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

O truque é entender que os identificadores hde tlsão variáveis ​​(errm ... já que são imutáveis, na verdade não são "variáveis", mas "valores";)). Se stiver o tipo Cons, retiraremos seus valores do construtor e os vincularemos às variáveis ​​nomeadas hde tl.

A correspondência de padrões é útil porque nos permite decompor uma estrutura de dados por sua forma, em vez de seu conteúdo . Imagine se definirmos uma árvore binária da seguinte maneira:

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

Podemos definir algumas rotações em árvore da seguinte maneira:

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

(O let rotateRight = functionconstrutor é açúcar de sintaxe para let rotateRight s = match s with ....)

Portanto, além de vincular a estrutura de dados às variáveis, também podemos fazer uma busca detalhada. Digamos que temos um nó let x = Node(Nil, 1, Nil). Se chamarmos rotateLeft x, testamos xo primeiro padrão, que falha ao corresponder porque o filho certo tem o tipo em Nilvez de Node. Ele x -> xpassará para o próximo padrão, que corresponderá a qualquer entrada e a retornará sem modificação.

Para comparação, escreveríamos os métodos acima em C # como:

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))));
    }
}

Para serio.

A correspondência de padrões é incrível

Você pode implementar algo semelhante à correspondência de padrões em C # usando o padrão de visitante , mas não é tão flexível porque você não pode decompor efetivamente estruturas de dados complexas. Além disso, se você estiver usando correspondência de padrões, o compilador informará se você deixou um caso de fora . Quão incrível é isso?

Pense em como você implementaria funcionalidades semelhantes em C # ou idiomas sem correspondência de padrões. Pense em como você faria isso sem testes de teste e transmissões em tempo de execução. Certamente não é difícil , apenas pesado e volumoso. E você não tem a verificação do compilador para garantir que cobriu todos os casos.

Portanto, a correspondência de padrões ajuda a decompor e navegar nas estruturas de dados em uma sintaxe muito conveniente e compacta, permitindo que o compilador verifique a lógica do seu código, pelo menos um pouco. Realmente é uma característica do assassino.

Resposta curta: a correspondência de padrões surge porque as linguagens funcionais tratam o sinal de igual como uma asserção de equivalência em vez de atribuição.

Resposta longa: a correspondência de padrões é uma forma de envio com base na "forma" do valor que é fornecido. Em uma linguagem funcional, os tipos de dados que você define são geralmente conhecidos como uniões discriminadas ou tipos de dados algébricos. Por exemplo, o que é uma lista (vinculada)? Uma lista vinculada Listde itens de algum tipo aé a lista vazia Nilou algum elemento do tipo a Consed em uma List a(uma lista de as). Em Haskell (a linguagem funcional com a qual estou mais familiarizado), escrevemos isso

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

Todas as uniões discriminadas são definidas desta maneira: um único tipo possui um número fixo de maneiras diferentes de criá-lo; os criadores, como Nile Consaqui, são chamados de construtores. Isso significa que um valor do tipo List apode ter sido criado com dois construtores diferentes - ele pode ter duas formas diferentes. Então, suponha que desejemos escrever uma headfunção para obter o primeiro elemento da lista. Em Haskell, escreveríamos isso como

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

Como os List avalores podem ser de dois tipos diferentes, precisamos lidar com cada um separadamente; esta é a correspondência de padrões. Em head x, se xcorresponder ao padrão Nil, executamos o primeiro caso; se corresponder ao padrão Cons h _, executamos o segundo.

Resposta curta, explicada: acho que uma das melhores maneiras de pensar sobre esse comportamento é alterando a maneira como você pensa no sinal de igual. Nas línguas entre parênteses, em geral, =denota atribuição: a = bsignifica "transformar aem b". Em muitas linguagens funcionais, contudo, =denota uma afirmação de igualdade: let Cons a (Cons b Nil) = frob x afirma que a coisa à esquerda Cons a (Cons b Nil), é equivalente à coisa à direita frob x; além disso, todas as variáveis ​​usadas à esquerda se tornam visíveis. Também é o que está acontecendo com os argumentos das funções: afirmamos que o primeiro argumento se parece Nile, se não, continuamos verificando.

Isso significa que, em vez de escrever

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;
}

Você pode escrever

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

Ei, C ++ também suporta correspondência de padrões.

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;
};

A correspondência de padrões é como métodos sobrecarregados com esteróides. O caso mais simples seria o mesmo que você viu em java, argumentos são uma lista de tipos com nomes. O método correto para chamar é baseado nos argumentos passados ​​e funciona como uma atribuição desses argumentos ao nome do parâmetro.

Os padrões dão um passo adiante e podem desestruturar os argumentos transmitidos ainda mais. Ele também pode potencialmente usar guardas para realmente corresponder com base no valor do argumento. Para demonstrar, vou fingir que o JavaScript tinha correspondência de padrões.

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

Em foo2, espera que a seja uma matriz, divide o segundo argumento, esperando um objeto com dois props (prop1, prop2) e atribui os valores dessas propriedades às variáveis ​​d e e, em seguida, espera que o terceiro argumento seja 35)

Diferentemente do JavaScript, os idiomas com correspondência de padrões geralmente permitem várias funções com o mesmo nome, mas com padrões diferentes. Dessa forma, é como uma sobrecarga de método. Vou dar um exemplo em erlang:

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

Borrar os olhos um pouco e você pode imaginar isso em javascript. Algo assim talvez:

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

Aponte que, quando você chama fibo, a implementação usada é baseada nos argumentos, mas onde o Java é limitado a tipos como o único meio de sobrecarga, a correspondência de padrões pode fazer mais.

Além da sobrecarga de funções, como mostrado aqui, o mesmo princípio pode ser aplicado em outros locais, como declarações de caso ou asserções de desestruturação. JavaScript ainda tem isso em 1.7 .

A correspondência de padrões permite combinar um valor (ou um objeto) com alguns padrões para selecionar uma ramificação do código. Do ponto de vista do C ++, pode parecer um pouco semelhante à switchdeclaração. Em linguagens funcionais, a correspondência de padrões pode ser usada para correspondência em valores primitivos padrão, como números inteiros. No entanto, é mais útil para tipos compostos.

Primeiro, vamos demonstrar a correspondência de padrões em valores primitivos (usando pseudo-C ++ estendido 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')
}

O segundo uso lida com tipos de dados funcionais, como tuplas (que permitem armazenar vários objetos em um único valor) e uniões discriminadas, que permitem criar um tipo que pode conter uma das várias opções. Parece um pouco, enumexceto que cada rótulo também pode conter alguns valores. Em uma sintaxe pseudo-C ++:

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

Um valor do tipo Shapeagora pode conter Rectangletodas as coordenadas ou a Circlecom o centro e o raio. A correspondência de padrões permite escrever uma função para trabalhar com o Shapetipo:

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)
}

Por fim, você também pode usar padrões aninhados que combinam os dois recursos. Por exemplo, você pode usar Circle(0, 0, radius)para corresponder a todas as formas que têm o centro no ponto [0, 0] e têm qualquer raio (o valor do raio será atribuído à nova variável radius).

Isso pode parecer um pouco estranho do ponto de vista do C ++, mas espero que meu pseudo-C ++ deixe a explicação clara. A programação funcional é baseada em conceitos bem diferentes, por isso faz mais sentido em uma linguagem funcional!

A correspondência de padrões é onde o intérprete do seu idioma seleciona uma função específica com base na estrutura e no conteúdo dos argumentos que você fornecer.

Não é apenas um recurso de idioma funcional, mas está disponível para muitos idiomas diferentes.

A primeira vez que me deparei com a ideia foi quando aprendi prólogo, onde é realmente central para o idioma.

por exemplo

last ([LastItem], LastItem).

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

O código acima dará o último item de uma lista. O argumento de entrada é o primeiro e o resultado é o segundo.

Se houver apenas um item na lista, o intérprete selecionará a primeira versão e o segundo argumento será definido como igual ao primeiro, ou seja, um valor será atribuído ao resultado.

Se a lista tiver uma cabeça e um rabo, o intérprete escolherá a segunda versão e será recursiva até restar apenas um item na lista.

Para muitas pessoas, a escolha de um novo conceito é mais fácil se forem fornecidos alguns exemplos fáceis, então vamos lá:

Digamos que você tenha uma lista de três números inteiros e queira adicionar o primeiro e o terceiro elemento. Sem a correspondência de padrões, você poderia fazer assim (exemplos em Haskell):

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

Agora, embora este seja um exemplo de brinquedo, imagine que gostaríamos de vincular o primeiro e o terceiro número inteiro às variáveis ​​e somar:

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

Essa extração de valores de uma estrutura de dados é o que a correspondência de padrões faz. Você basicamente "espelha" a estrutura de algo, fornecendo variáveis ​​a serem vinculadas aos locais de interesse:

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

Quando você chama essa função com [1,2,3] como argumento, [1,2,3] será unificado com [primeiro _, terceiro], vinculando primeiro a 1, terceiro a 3 e descartando 2 ( _é um espaço reservado por coisas que você não gosta).

Agora, se você deseja combinar apenas as listas com 2 como o segundo elemento, é possível fazer o seguinte:

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

Isso funcionará apenas para listas com 2 como seu segundo elemento e gerará uma exceção caso contrário, porque nenhuma definição para addFirstAndThird é dada para listas não correspondentes.

Até agora, usamos a correspondência de padrões apenas para a desestruturação da ligação. Acima disso, você pode fornecer várias definições da mesma função, onde a primeira definição de correspondência é usada; portanto, a correspondência de padrões é um pouco como "uma declaração de alternância nos esteroides":

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

addFirstAndThird adicionará felizmente o primeiro e o terceiro elemento de listas com 2 como seu segundo elemento e, caso contrário, "passará" e "retornará" 0. Essa funcionalidade "alternada" não pode ser usada apenas nas definições de funções, por exemplo:

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

Além disso, não está restrito a listas, mas também pode ser usado com outros tipos, por exemplo, combinando os construtores de valor Just and Nothing do tipo Maybe para "desembrulhar" o valor:

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

Certamente, esses eram meros exemplos de brinquedos, e eu nem tentei dar uma explicação formal ou exaustiva, mas eles deveriam bastar para entender o conceito básico.

Você deve começar com a página da Wikipedia que fornece uma boa explicação. Em seguida, leia o capítulo relevante do wikibook de Haskell .

Esta é uma boa definição do wikibook acima:

Portanto, a correspondência de padrões é uma maneira de atribuir nomes a coisas (ou vinculá-los a essas coisas) e possivelmente dividir expressões em subexpressões ao mesmo tempo (como fizemos com a lista na definição de mapa).

Aqui está um exemplo muito curto que mostra a utilidade de correspondência de padrões:

Digamos que você queira classificar um elemento em uma lista:

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

para (eu ordenei "Nova York")

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

em uma linguagem mais imperativa, você escreveria:

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;
}

Em uma linguagem funcional, você escreveria:

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

Como você pode ver que a solução combinada com padrões tem menos ruído, é possível ver claramente quais são os diferentes casos e como é fácil viajar e desestruturar nossa lista.

Eu escrevi um post mais detalhado sobre isso aqui .