¿Qué es la "coincidencia de patrones" en lenguajes funcionales?

Estoy leyendo sobre programación funcional y he notado que la coincidencia de patrones se menciona en muchos artículos como una de las características principales de los lenguajes funcionales.

¿Alguien puede explicar para un desarrollador de Java / C ++ / JavaScript qué significa?

Comprender la coincidencia de patrones requiere explicar tres partes:

1. Tipos de datos algebraicos.
2. ¿Qué patrón de coincidencia es
3. ¿Por qué es asombroso?

Tipos de datos algebraicos en pocas palabras

Los lenguajes funcionales tipo ML le permiten definir tipos de datos simples llamados "uniones disjuntas" o "tipos de datos algebraicos". Estas estructuras de datos son contenedores simples y pueden definirse recursivamente. Por ejemplo:

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

define una estructura de datos tipo pila. Piense en ello 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;
        }
    }
}

Entonces, los identificadores Consy Nildefinen una clase simple simple, donde of x * y * z * ...define un constructor y algunos tipos de datos. Los parámetros para el constructor no tienen nombre, se identifican por posición y tipo de datos.

Crea instancias de su a listclase como tales:

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

Que es lo mismo que:

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

Coincidencia de patrones en pocas palabras

La coincidencia de patrones es una especie de prueba de tipo. Entonces, digamos que creamos un objeto de pila como el anterior, podemos implementar métodos para mirar y reventar la pila de la siguiente manera:

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"

Los métodos anteriores son equivalentes (aunque no se implementan como tales) al siguiente 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();
}

(Casi siempre, los lenguajes ML implementan la coincidencia de patrones sin pruebas de tipo o conversiones en tiempo de ejecución, por lo que el código C # es algo engañoso. Dejemos de lado los detalles de implementación con un poco de agitación manual, por favor :))

Descomposición de la estructura de datos en pocas palabras

Ok, volvamos al método de mirar:

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

El truco es comprender que los identificadores hdy tlson variables (errm ... ya que son inmutables, no son realmente "variables", sino "valores";)). Si stiene el tipo Cons, entonces sacaremos sus valores del constructor y los vincularemos a las variables llamadas hdy tl.

La coincidencia de patrones es útil porque nos permite descomponer una estructura de datos por su forma en lugar de su contenido . Entonces imagine si definimos un árbol binario de la siguiente manera:

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

Podemos definir algunas rotaciones de árbol de la siguiente manera:

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

(El let rotateRight = functionconstructor es sintaxis de azúcar para let rotateRight s = match s with ...).

Entonces, además de vincular la estructura de datos a las variables, también podemos profundizar en ella. Digamos que tenemos un nodo let x = Node(Nil, 1, Nil). Si llamamos rotateLeft x, ponemos a prueba xcontra el primer patrón, que no coincide porque el niño tiene derecho tipo Nilen lugar de Node. Se moverá al siguiente patrón, x -> xque coincidirá con cualquier entrada y lo devolverá sin modificaciones.

A modo de comparación, escribiríamos los métodos anteriores en 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))));
    }
}

Por enserio.

La coincidencia de patrones es increíble

Puede implementar algo similar a la coincidencia de patrones en C # usando el patrón de visitante , pero no es tan flexible porque no puede descomponer efectivamente estructuras de datos complejas. Además, si está utilizando coincidencia de patrones, el compilador le dirá si omitió un caso . ¿Qué tan maravilloso es eso?

Piense en cómo implementaría una funcionalidad similar en C # o lenguajes sin coincidencia de patrones. Piensa en cómo lo harías sin pruebas de prueba y lanzamientos en tiempo de ejecución. Ciertamente no es difícil , solo engorroso y voluminoso. Y no tiene que verificar el compilador para asegurarse de que ha cubierto todos los casos.

Por lo tanto, la coincidencia de patrones lo ayuda a descomponer y navegar por las estructuras de datos en una sintaxis compacta muy conveniente, le permite al compilador verificar la lógica de su código, al menos un poco. Realmente es una característica asesina.

Respuesta corta: la coincidencia de patrones surge porque los lenguajes funcionales tratan el signo igual como una afirmación de equivalencia en lugar de una asignación.

Respuesta larga: La coincidencia de patrones es una forma de envío basada en la "forma" del valor que se le da. En un lenguaje funcional, los tipos de datos que define suelen ser lo que se conoce como uniones discriminadas o tipos de datos algebraicos. Por ejemplo, ¿qué es una lista (vinculada)? Una lista vinculada Listde cosas de algún tipo aes la lista vacía Nilo algún elemento de tipo a Consed en una List a(una lista de as). En Haskell (el lenguaje funcional con el que estoy más familiarizado), escribimos esto

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

Todas las uniones discriminadas se definen de esta manera: un solo tipo tiene un número fijo de formas diferentes de crearlo; Los creadores, como Nily Consaquí, se llaman constructores. Esto significa que un valor del tipo List apodría haberse creado con dos constructores diferentes, podría tener dos formas diferentes. Supongamos que queremos escribir una headfunción para obtener el primer elemento de la lista. En Haskell, escribiríamos esto 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 los List avalores pueden ser de dos tipos diferentes, necesitamos manejar cada uno por separado; Esta es la coincidencia de patrones. En head x, si xcoincide con el patrón Nil, ejecutamos el primer caso; si coincide con el patrón Cons h _, ejecutamos el segundo.

Respuesta corta, explicada: Creo que una de las mejores formas de pensar acerca de este comportamiento es cambiando la forma en que piensas del signo igual. En los idiomas de corchetes, en general, =denota asignación: a = bsignifica "hacer aen b". En muchos lenguajes funcionales, sin embargo, =denota una afirmación de igualdad: let Cons a (Cons b Nil) = frob x afirma que lo de la izquierda Cons a (Cons b Nil), es equivalente a lo de la derecha frob x,; Además, todas las variables utilizadas a la izquierda se hacen visibles. Esto también es lo que está sucediendo con los argumentos de la función: afirmamos que se ve el primer argumento Nil, y si no es así, seguimos comprobando.

Significa que en lugar de escribir

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

Puedes escribir

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

Hola, C ++ también admite la coincidencia de patrones.

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 coincidencia de patrones es como métodos sobrecargados en esteroides. El caso más simple sería el mismo más o menos lo mismo que viste en Java, los argumentos son una lista de tipos con nombres. El método correcto para llamar se basa en los argumentos pasados ​​y funciona como una asignación de esos argumentos al nombre del parámetro.

Los patrones solo van un paso más allá y pueden desestructurar los argumentos pasados ​​aún más. También puede usar guardias para que coincidan según el valor del argumento. Para demostrarlo, simularé que JavaScript tenía coincidencia de patrones.

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

En foo2, espera que a sea una matriz, separa el segundo argumento, esperando un objeto con dos accesorios (prop1, prop2) y asigna los valores de esas propiedades a las variables d y e, y luego espera que el tercer argumento sea 35)

A diferencia de JavaScript, los idiomas con coincidencia de patrones generalmente permiten múltiples funciones con el mismo nombre, pero patrones diferentes. De esta manera es como sobrecargar el método. Daré un ejemplo en erlang:

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

Desenfoca un poco tus ojos y puedes imaginar esto en javascript. Tal vez algo como esto:

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

Señale que cuando llama a fibo, la implementación que utiliza se basa en los argumentos, pero donde Java se limita a los tipos como el único medio de sobrecarga, la coincidencia de patrones puede hacer más.

Más allá de la sobrecarga de funciones como se muestra aquí, el mismo principio se puede aplicar en otros lugares, como declaraciones de casos o evaluaciones de desestructuración. JavaScript incluso tiene esto en 1.7 .

La coincidencia de patrones le permite hacer coincidir un valor (o un objeto) con algunos patrones para seleccionar una rama del código. Desde el punto de vista de C ++, puede sonar un poco similar a la switchdeclaración. En lenguajes funcionales, la coincidencia de patrones se puede utilizar para la coincidencia de valores primitivos estándar, como los enteros. Sin embargo, es más útil para los tipos compuestos.

Primero, demostremos la coincidencia de patrones en valores primitivos (usando pseudo-C ++ extendido 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')
}

El segundo uso trata con tipos de datos funcionales como las tuplas (que le permiten almacenar múltiples objetos en un solo valor) y uniones discriminadas que le permiten crear un tipo que puede contener una de varias opciones. Esto suena un poco como, enumexcepto que cada etiqueta también puede llevar algunos valores. En una sintaxis de pseudo-C ++:

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

Un valor de tipo Shapeahora puede contener ya sea Rectanglecon todas las coordenadas o Circlecon el centro y el radio. La coincidencia de patrones le permite escribir una función para trabajar con el 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)
}

Finalmente, también puede usar patrones anidados que combinen ambas características. Por ejemplo, podría usar Circle(0, 0, radius)para hacer coincidir todas las formas que tienen el centro en el punto [0, 0] y tienen cualquier radio (el valor del radio se asignará a la nueva variable radius).

Esto puede sonar un poco desconocido desde el punto de vista de C ++, pero espero que mi pseudo-C ++ aclare la explicación. La programación funcional se basa en conceptos bastante diferentes, por lo que tiene más sentido en un lenguaje funcional.

La coincidencia de patrones es donde el intérprete de su idioma elegirá una función particular en función de la estructura y el contenido de los argumentos que le dé.

No es solo una función de lenguaje funcional, sino que está disponible para muchos idiomas diferentes.

La primera vez que me encontré con la idea fue cuando aprendí el prólogo donde es realmente central para el idioma.

p.ej

last ([LastItem], LastItem).

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

El código anterior le dará el último elemento de una lista. El argumento de entrada es el primero y el resultado es el segundo.

Si solo hay un elemento en la lista, el intérprete elegirá la primera versión y el segundo argumento será igual al primero, es decir, se asignará un valor al resultado.

Si la lista tiene una cabeza y una cola, el intérprete elegirá la segunda versión y repetirá hasta que solo quede un elemento en la lista.

Para muchas personas, elegir un nuevo concepto es más fácil si se proporcionan algunos ejemplos fáciles, así que aquí vamos:

Digamos que tiene una lista de tres enteros y desea agregar el primer y el tercer elemento. Sin coincidencia de patrones, podría hacerlo así (ejemplos en Haskell):

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

Ahora, aunque este es un ejemplo de juguete, imagine que nos gustaría vincular el primer y tercer entero a las variables y sumarlas:

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

Esta extracción de valores de una estructura de datos es lo que hace la coincidencia de patrones. Básicamente "reflejas" la estructura de algo, dando variables para unir los lugares de interés:

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

Cuando llame a esta función con [1,2,3] como argumento, [1,2,3] se unificará con [first _,, third], enlazando primero a 1, tercero a 3 y descartando 2 ( _es un marcador de posición para cosas que no te importan).

Ahora, si solo desea hacer coincidir las listas con 2 como segundo elemento, puede hacerlo así:

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

Esto solo funcionará para listas con 2 como su segundo elemento y, de lo contrario, arrojará una excepción, ya que no se proporciona una definición para addFirstAndThird para las listas que no coinciden.

Hasta ahora, utilizamos la coincidencia de patrones solo para desestructurar el enlace. Por encima de eso, puede dar múltiples definiciones de la misma función, donde se utiliza la primera definición de coincidencia, por lo tanto, la coincidencia de patrones es un poco como "una declaración de cambio en estereoides":

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

addFirstAndThird agregará felizmente el primer y el tercer elemento de las listas con 2 como su segundo elemento, y de lo contrario "caerá" y "regresará" 0. Esta funcionalidad "similar a un interruptor" no solo puede usarse en definiciones de funciones, por ejemplo:

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

Además, no está restringido a listas, sino que también se puede usar con otros tipos, por ejemplo, haciendo coincidir los constructores de valor Just y Nothing del tipo Maybe para "desenvolver" el valor:

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

Claro, esos eran simples ejemplos de juguetes, y ni siquiera intenté dar una explicación formal o exhaustiva, pero deberían ser suficientes para comprender el concepto básico.

Debes comenzar con la página de Wikipedia que da una muy buena explicación. Luego, lea el capítulo correspondiente del wikibook de Haskell .

Esta es una buena definición del wikibook anterior:

Entonces, la coincidencia de patrones es una forma de asignar nombres a las cosas (o vincular esos nombres a esas cosas), y posiblemente dividir las expresiones en subexpresiones al mismo tiempo (como hicimos con la lista en la definición del mapa).

Aquí hay un ejemplo realmente corto que muestra la utilidad de coincidencia de patrones:

Supongamos que desea ordenar un elemento en una lista:

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

a (he ordenado "Nueva York")

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

en un idioma más imperativo escribirías:

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

En un lenguaje funcional, en su lugar, escribiría:

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

Como puede ver, la solución de patrón combinado tiene menos ruido, puede ver claramente cuáles son los diferentes casos y cuán fácil es viajar y desestructurar nuestra lista.

He escrito una publicación de blog más detallada al respecto aquí .