simbolos - programa en haskell

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?

Intenté buscar una explicación simple, pero no encontré 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 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.

Comparar:

con el Haskell equivalente:

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

Tenga en cuenta que " n ≥ 2" en la función por partes se convierte en un guardia en la versión de Haskell, pero las 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 más) se convierten en patrones. Los guardias permiten condiciones más generales. Podríamos reescribir fib para 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 implica verificar un argumento contra 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 `` una lista is defined recursively as the empty list [] , or the structure h :: t , where h is an element of type a ( un 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 cons, que crea una nueva lista de un elemento y una lista.

Entonces 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 le dice a OCaml que una función se llamará recursivamente. No te preocupes por esa parte. La declaración del match es en lo que nos estamos enfocando. OCaml comprobará lst 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í hay una función (artificial) para decirle 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 patrón son los números mismos. _ es un comodín especial utilizado como caso predeterminado, en caso de que ninguno de los patrones anteriores coincida.

Answer 3

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

• "Construcción de eliminación" significa "cómo consumir o usar un valor"

• El "tipo de datos algebraico", además de las funciones de primera clase, es la gran idea en un lenguaje funcional tipado estático como Clean, F #, Haskell o ML.

La idea de los tipos de datos algebraicos es que definas un tipo de cosa, y dices todas las formas en que puedes hacer esa cosa. Como ejemplo, definamos "Secuencia de cadena" como un tipo de datos algebraico, 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 bien, hay muchas cosas malas con esta definición, pero a modo de ejemplo es interesante porque proporciona una concatenación constante de secuencias de longitud arbitraria. (Hay otras maneras de lograr esto). La declaración presenta Empty , Cat y Single , que son todas las formas de hacer secuencias . (Eso hace que cada uno sea una construcción de introducción , una forma de hacer las cosas).

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

Aquí viene la línea de golpe: la construcción de eliminación, la coincidencia de patrones, le da una forma de analizar una secuencia y le pregunta ¿con qué constructor se hizo? . Como debe estar preparado para cualquier respuesta, proporciona al menos una alternativa para cada constructor. Aquí hay 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 el núcleo del lenguaje, todas las coincidencias de patrones se basan en esta construcción de case . Sin embargo, debido a que los tipos de datos algebraicos y la coincidencia de patrones son tan importantes para las expresiones idiomáticas del idioma, existe un "azúcar sintáctico" especial para hacer la coincidencia de patrones en la forma 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áctico, el cálculo por coincidencia de patrones se parece mucho a la definición por ecuaciones. (El comité de 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 de 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í.

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 usar el operador cons :: para agregar un elemento al comienzo de una lista como sigue:

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

De forma similar, puede usar el mismo operador para dividir la lista de la siguiente manera:

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

La coincidencia de patrones está, al menos en Haskell, profundamente ligada al concepto de tipos de datos algebraicos . Cuando declaras un tipo de datos como este:

data SomeData = Foo Int Int
              | Bar String
              | Baz

... define a Foo , Bar y Baz como constructores --no debe confundirse con "constructores" en OOP - que construyen un valor SomeData partir de otros valores.

La coincidencia de patrones no es más que hacer esto en reversa: un patrón "deconstruiría" un valor de SomeData en sus componentes (de hecho, creo que la coincidencia de patrones es la única forma de extraer valores en Haskell).

Cuando hay varios constructores para un tipo, se escriben varias versiones de una función para cada patrón, seleccionándose el correcto según el constructor utilizado (suponiendo que haya escrito patrones que coincidan con todas las construcciones posibles, lo que generalmente es bueno) práctica para hacer).