Coincidencia de patrones de Haskell: ¿qué es eso?

Question

¿Qué es la coincidencia de patrones en Haskell y cómo se relaciona con ecuaciones protegidas?

He intentado buscar una explicación simple, pero no he encontrado ninguna.

EDITAR: Alguien etiquetado como tarea. Ya no voy a la escuela, estoy aprendiendo a Haskell y estoy tratando de entender este concepto. Puro por interés.

Answer 1

En pocas palabras, los patrones son como definir las funciones por partes en matemáticas. Puede especificar diferentes cuerpos de funciones para diferentes argumentos usando patrones. Cuando se llama a una función, el cuerpo apropiado se elige comparando los argumentos reales con los diversos patrones de argumento. Lea A Gentle Introduction to Haskell para obtener más información.

Compare:

con el Haskell equivalente:

fib 0 = 1 
fib 1 = 1 
fib n | n >= 2 
     = fib (n-1) + fib (n-2) 

Nota del "n ≥ 2" en la función a trozos se convierte en un guardia en la versión Haskell, pero el otras dos condiciones son simplemente patrones. Los patrones son condiciones que evalúan los valores y la estructura, como x:xs, (x, y, z) o Just x. En una definición por partes, las condiciones basadas en relaciones = o ∈ (básicamente, las condiciones que dicen que algo "es" algo diferente) se convierten en patrones. Los guardias permiten condiciones más generales. Podríamos reescribir fib de usar guardias:

fib n | n == 0 = 1 
     | n == 1 = 1 
     | n >= 2 = fib (n-1) + fib (n-2) 

Answer 2

En un lenguaje funcional, la coincidencia de patrones consiste en comprobar un argumento en contra de diferentes formas. Un ejemplo simple implica operaciones definidas recursivamente en las listas. Usaré OCaml para explicar la coincidencia de patrones ya que es mi lenguaje de elección funcional, pero los conceptos son los mismos en F # y Haskell, AFAIK.

Aquí está la definición de una función para calcular la longitud de una lista lst. En OCaml, una `` lista is defined recursively as the empty list [] , or the structure h :: t , where h is an element of type a ( a being any type we want, such as an integer or even another list), t is a list (hence the recursive definition), and :: `es el operador contras, que crea una nueva lista de un elemento y una lista.

Así que la función se vería así:

let rec len lst = 
    match lst with 
    [] -> 0 
    | h :: t -> 1 + len t 

rec es un modificador que dice que una función OCaml llamará a sí mismo de forma recursiva. No te preocupes por esa parte. La declaración match es en lo que nos estamos enfocando. OCaml comprobará lst contra los dos patrones - lista vacía, o h :: t - y devolverá un valor diferente en función de eso. Como sabemos que cada lista coincidirá con uno de estos patrones, podemos estar seguros de que nuestra función regresará de forma segura.

Tenga en cuenta que, aunque estos dos patrones se ocuparán de todas las listas, no está limitado a ellas. Un patrón como h1 :: h2 :: t (que coincida con todas las listas de longitud 2 o más) también es válido.

Por supuesto, el uso de patrones no está restringido a estructuras de datos definidas recursivamente, o funciones recursivas.Aquí es una función (artificial) para indicar si un número es 1 o 2:

let is_one_or_two num = 
    match num with 
    1 -> true 
    | 2 -> true 
    | _ -> false 

En este caso, las formas de nuestro modelo son los propios números. _ es un comodín especial utilizado como caso predeterminado, en caso de que ninguno de los patrones anteriores coincida.

Answer 3

La concordancia de patrones es, al menos en Haskell, profundamente relacionada con el concepto de algebraic data types. Cuando se declara un tipo de datos de esta manera:

data SomeData = Foo Int Int 
       | Bar String 
       | Baz 

... se define Foo, Bar y Baz como constructores --No debe confundirse con "constructores" en programación orientada a objetos - que construyen un valor SomeData de otros valores.

patrón de juego es nada más que hacer esto a la inversa --un patrón sería "deconstruir" un valor SomeData sus partes constitutivas (de hecho, creo que la coincidencia de patrones es la única manera de extraer los valores de Haskell).

Cuando hay varios constructores para un tipo, escribe varias versiones de una función para cada patrón, seleccionándose la correcta según el constructor utilizado (suponiendo que haya escrito patrones para hacer coincidir todas las construcciones posibles-- que generalmente es una buena práctica hacer).

Answer 4

La coincidencia de patrones es una de esas operaciones dolorosas que es difícil de entender si proviene de un fondo de programación de procedimientos. Me resulta difícil entrar porque la misma sintaxis utilizada para crear una estructura de datos se puede usar para hacer coincidir.

En F # puede utilizar el operador contras :: añadir un elemento al principio de una lista de este modo:

let a = 1 :: [2;3] 
//val a : int list = [1; 2; 3] 

mismo modo se puede utilizar el mismo operador de dividir la lista en este modo:

let a = [1;2;3];; 
match a with 
    | [a;b] -> printfn "List contains 2 elements" //will match a list with 2 elements 
    | a::tail -> printfn "Head is %d" a //will match a list with 2 or more elements 
    | [] -> printfn "List is empty" //will match an empty list 

Answer 5

Hay otras buenas respuestas, así que le daré una respuesta muy técnica. La concordancia de patrones es la eliminación construir para tipos de datos algebraicos:

• "Eliminación construir" significa "cómo consumir o utilizar un valor de"

• "Algebraic tipo de datos", además de funciones de primera clase, es la gran idea en un lenguaje funcional de tipos estáticos como Limpio, F #, Haskell o ML

la idea de los tipos de datos algebraicos se que defines un tipo de cosa, y dices todas las formas en que puedes hacer esa cosa. A modo de ejemplo, vamos a definir "Secuencia de cadena" como un tipo de datos algebraica, con tres formas de hacerlo:

data StringSeq = Empty     -- the empty sequence 
       | Cat StringSeq StringSeq -- two sequences in succession 
       | Single String   -- a sequence holding a single element 

Ahora, hay todo tipo de cosas mal con esta definición, pero como ejemplo es interesante porque proporciona una concatenación de tiempo constante de secuencias de longitud arbitraria. (Hay otras formas de lograr esto.) La declaración introduce Empty, Cat y Single, que son todas las formas que hay de realizando las secuencias. (Eso hace que cada uno de ellos una introducción — construir una manera de hacer las cosas.)

• que pueda tomar una secuencia vacía y sin ningún otro valor.
• Para hacer una secuencia con Cat, necesita otras dos secuencias.
• Para hacer una secuencia con Single, necesita un elemento (en este caso una cadena)

Aquí viene el chiste: la construcción de la eliminación, la coincidencia de patrones, le da una manera de examinar una secuencia y pedir es la pregunta ¿con qué constructor se hizo?. Como debe estar preparado para cualquier respuesta, proporciona al menos una alternativa para cada constructor. He aquí una función de longitud:

slen :: StringSeq -> Int 
slen s = case s of Empty -> 0 
        Cat s s' -> slen s + slen s' 
        Single _ -> 1 

En la base de la lengua, toda la coincidencia de patrones se basa en este case constructo. Sin embargo, debido a los tipos de datos algebraicos y la coincidencia de patrones son tan importantes para los modismos de la lengua, no hay especial "azúcar sintáctico" para hacer la coincidencia de patrones en el formulario de declaración de una definición de función:

slen Empty = 0 
slen (Cat s s') = slen s + slen s' 
slen (Single _) = 1 

Con este azúcar sintáctica, el cálculo por coincidencia de patrones se parece mucho a la definición por ecuaciones. (El comité Haskell hizo esto a propósito.) Y como puede ver en las otras respuestas, es posible especializar una ecuación o una alternativa en una expresión case golpeando a un guardia sobre ella. No puedo pensar en un protector plausible para el ejemplo de secuencia, y hay muchos ejemplos en las otras respuestas, así que lo dejo ahí.