functional-programming - pattern - programacion funcional java
¿Qué es ''Pattern Matching'' en lenguajes funcionales? (9)
Estoy leyendo acerca de la programación funcional y he notado que Pattern Matching se menciona en muchos artículos como una de las características principales de los lenguajes funcionales.
¿Alguien puede explicarle a un desarrollador de Java / C ++ / JavaScript qué significa?
Aquí hay un ejemplo realmente breve que muestra la utilidad de coincidencia de patrones:
Supongamos que desea ordenar un elemento en una lista:
["Venice","Paris","New York","Amsterdam"]
a (clasifiqué "Nueva York")
["Venice","New York","Paris","Amsterdam"]
en un lenguaje 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 cambio escribirías:
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 patrones combinados tiene menos ruido, puede ver claramente cuáles son los diferentes casos y lo fácil que es viajar y desestructurar nuestra lista.
He escrito una publicación de blog más detallada al respecto here .
Comprender la coincidencia de patrones requiere explicar tres partes:
- Tipos de datos algebraicos
- Qué combinación de patrones es
- Por qué es increíble.
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 se pueden definir recursivamente. Por ejemplo:
type ''a list =
| Nil
| Cons of ''a * ''a list
define una estructura de datos similar a una pila. Piense que es 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 Cons y Nil definen una clase sencilla simple, donde el 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.
Usted crea instancias de su clase de a list como tal:
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 un tipo de prueba de tipo. Entonces, digamos que creamos un objeto de pila como el anterior, podemos implementar métodos para mirar y abrir 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 en tiempo de ejecución o conversiones, por lo que el código C # es un tanto engañoso. Vamos a cepillar los detalles de implementación a un lado con un gesto de mano :))
Descomposición de la estructura de datos en pocas palabras
Ok, volvamos al método Peek:
let peek s =
match s with
| Cons(hd, tl) -> hd
| Nil -> failwith "Empty stack"
El truco está en entender que los identificadores hd y tl son variables (errm ... ya que son inmutables, no son realmente "variables", sino "valores";)). Si s tiene el tipo Cons , vamos a sacar sus valores del constructor y vincularlos a las variables llamadas hd y 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 = function constructor de let rotateRight = function es sintaxis sugar 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 a rotateLeft x , probamos x respecto al primer patrón, que no coincide porque el hijo derecho tiene el tipo Nil lugar de Node . Pasará al siguiente patrón, x -> x , que coincidirá con cualquier entrada y la devolverá sin modificaciones.
Para comparación, escribiremos 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))));
}
}
Para en serio.
La coincidencia de patrones es asombrosa
Puede implementar algo similar a la coincidencia de patrones en C # utilizando el patrón de visitante , pero no es tan flexible porque no puede descomponer de manera efectiva estructuras de datos complejas. Además, si usa la 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 en idiomas sin coincidencia de patrones. Piense en cómo lo haría sin pruebas de prueba y lanzamientos en tiempo de ejecución. Sin duda no es difícil , solo engorroso y voluminoso. Y no tiene que verificar al compilador para asegurarse de haber cubierto todos los casos.
Entonces, la coincidencia de patrones te ayuda a descomponer y navegar por las estructuras de datos en una sintaxis compacta muy conveniente, que permite al compilador verificar la lógica de tu código, al menos un poco. Realmente es una característica clave.
Deberías comenzar con la página de Wikipedia que da una explicación bastante buena. Luego, lea el capítulo correspondiente del haskell wikibook .
Esta es una buena definición del wikibook anterior:
Así que la coincidencia de patrones es una forma de asignar nombres a cosas (o vincular esos nombres a esas cosas), y posiblemente dividir expresiones en subexpresiones al mismo tiempo (como lo hicimos con la lista en la definición de mapa).
La coincidencia de patrones es algo así como métodos sobrecargados de esteroides. El caso más simple sería el mismo más o menos el mismo que el 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 se dobla 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 que se aprobaron aún más. También puede usar guardias para hacer coincidir realmente en función del valor del argumento. Para demostrarlo, pretendo que JavaScript tiene una 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, rompe el segundo argumento, espera un objeto con dos apoyos (prop1, prop2) y asigna los valores de esas propiedades a las variables dye, 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 diferentes patrones. De esta manera, es como la sobrecarga de métodos. Daré un ejemplo en erlang:
fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .
Desenfoca tus ojos un poco y puedes imaginar esto en javascript. Algo como esto tal vez:
function fibo(0){return 0;}
function fibo(1){return 1;}
function fibo(N) when N > 0 {return fibo(N-1) + fibo(N-2);}
El punto es que cuando llamas a fibo, la implementación que usa se basa en los argumentos, pero cuando Java está limitado a 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 a otros lugares, como declaraciones de casos o asignaciones de desestructuración. JavaScript incluso tiene esto en 1.7 .
La coincidencia de patrones es donde el intérprete de su idioma seleccionará una función particular en función de la estructura y el contenido de los argumentos que le proporcione.
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í prólogo donde es realmente central para el lenguaje.
p.ej
last ([LastItem], LastItem).
last ([Head | Tail], LastItem): - last (Tail, LastItem).
El código anterior dará el último elemento de una lista. La entrada arg es la primera y el resultado es la segunda.
Si solo hay un elemento en la lista, el intérprete elegirá la primera versión y el segundo argumento se establecerá igual al primero, es decir, se asignará un valor al resultado.
Si la lista tiene una cabecera y una cola, el intérprete seleccionará la segunda versión y recurrirá hasta que solo quede un elemento en la lista.
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 declaración de switch . En los lenguajes funcionales, la coincidencia de patrones se puede usar para la coincidencia en valores primitivos estándar tales como enteros. Sin embargo, es más útil para tipos compuestos.
Primero, demostremos la coincidencia de patrones en valores primitivos (usando el switch pseudo-C ++ extendido):
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 tuplas (que le permiten almacenar múltiples objetos en un solo valor) y sindicatos discriminados que le permiten crear tipos que pueden contener una de varias opciones. Esto suena un poco como enum excepto que cada etiqueta también puede llevar algunos valores. En una sintaxis 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 Shape ahora puede contener Rectangle con todas las coordenadas o un Circle con centro y el radio. La coincidencia de patrones le permite escribir funciones para trabajar con el tipo de Shape :
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, puede usar Circle(0, 0, radius) para que coincida con todas las formas que tienen centro en el punto [0, 0] y tienen cualquier radio (el radio asignará el nuevo radius variable).
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, ¡así que tiene más sentido en un lenguaje funcional!
Para muchas personas, es más fácil elegir un nuevo concepto si se proporcionan algunos ejemplos fáciles, así que aquí vamos:
Supongamos que tiene una lista de tres enteros y desea agregar el primer y el tercer elemento. Sin coincidencia de patrones, puedes 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, imaginemos 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, "duplicas" la estructura de algo, dando variables para enlazar para los lugares de interés:
addFirstAndThird [first,_,third] = first + third
Cuando llame a esta función con [1,2,3] como su argumento, [1,2,3] se unificará con [primero, _ , tercero], vinculando primero a 1, tercero a 3 y descartando 2 ( _ es un marcador de posición para las cosas que no te importan).
Ahora, si solo desea unir listas con 2 como segundo elemento, puede hacerlo así:
addFirstAndThird [first,2,third] = first + third
Esto solo funcionará para las listas con 2 como su segundo elemento y arrojar una excepción de lo contrario, porque no se da ninguna 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 usa 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 tercer elemento de listas con 2 como su segundo elemento, y de lo contrario "caerá" y "devolverá" 0. Esta funcionalidad de "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 valores 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 fueron 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.
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;
Oye, C ++ admite la coincidencia de patrones también.
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;
};
Respuesta corta: la coincidencia de patrones surge porque los lenguajes funcionales tratan el signo igual como una afirmación de equivalencia en lugar de asignación.
Respuesta larga: la coincidencia de patrones es una forma de envío basada en la "forma" del valor que se otorga. En un lenguaje funcional, los tipos de datos que define generalmente son lo que se conoce como uniones discriminadas o tipos de datos algebraicos. Por ejemplo, ¿qué es una lista (vinculada)? Una lista vinculada La lista de cosas de algún tipo a es la lista vacía, Nil o algún elemento de tipo a Cons en una List a (una lista de a s). 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 Nil y Cons aquí, se llaman constructores. Esto significa que un valor del tipo List a podría haber creado con dos constructores diferentes: podría tener dos formas diferentes. Supongamos que queremos escribir una función de head 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 valores de List a pueden ser de dos tipos diferentes, necesitamos manejar cada uno por separado; este es el patrón de coincidencia. En la head x , si x coincide 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 maneras de pensar acerca de este comportamiento es cambiando la forma en que piensas en el signo igual. En los lenguajes de corchetes, en general, = denota asignación: a = b significa "hacer a en b ". Sin embargo, en muchos lenguajes funcionales, = denota una afirmación de igualdad: let Cons a (Cons b Nil) = frob x afirma que lo que está a la izquierda, Cons a (Cons b Nil) , es equivalente a lo que está a la derecha, frob x ; Además, todas las variables utilizadas a la izquierda se vuelven visibles. Esto también es lo que está sucediendo con los argumentos de función: afirmamos que el primer argumento parece Nil , y si no lo hace, seguimos comprobando.