Haskell: ¿Por qué la coincidencia de patrones funciona para tipos sin ser instancias de igualdad?

Question

Me preguntaba cómo funciona la coincidencia de patrones en Haskell, conozco este hilo, pero no pude entender las respuestas allí.

How does Haskell do pattern matching without us defining an Eq on our data types?

• Las respuestas indican que los tipos se corresponden con las expresiones booleanas, pero ¿cómo es esto posible.
• La otra cosa que obtuve fue que la coincidencia de patrones es más general que (==) y Eq se implementa mediante el uso de coincidencia de patrones.

Así que me puedes decir qué matchmatch3 y están trabajando incluso si omito deriving (Eq) en el siguiente fragmento de código, (está claro por qué está fallando match2).

data MyType = TypeA | TypeB 
      deriving (Eq) 

match :: MyType -> String 
match TypeA = "this is type A" 
match TypeB = "this is type B" 

match2 :: MyType -> String 
match2 a | a == TypeA = "this is type A matched by equality" 
     | a == TypeB = "this is type B matched by equality" 
     | otherwise = "this is neither type A nor type B" 

match3 :: MyType -> String 
match3 a = case a of TypeA -> "this is type A matched by case expression" 
        TypeB -> "this is type B matched by case expression" 

main :: IO() 
main = do 
    (print . match) TypeA 
    (print . match) TypeB 
    (print . match2) TypeA 
    (print . match2) TypeB 
    (print . match3) TypeA 
    (print . match3) TypeB 

Answer 1

Solo quiero señalar que los tipos de datos y la coincidencia de patrones (en una primera aproximación) son meramente útiles pero la característica del lenguaje redundante, que puede implementarse puramente utilizando el cálculo lambda. Si comprende cómo implementarlos en cálculo lambda, puede comprender por qué no necesitan Eq para implementar la coincidencia de patrones.

La implementación de tipos de datos en cálculo lambda se conoce como "codificación eclesiástica" (después de Alonzo Church, que demostró cómo hacerlo). Las funciones codificadas por la iglesia también se conocen como "estilo de continuación de paso".

Se denomina "estilo de paso de continuación" porque en lugar de proporcionar el valor, proporciona una función que procesará el valor. Así, por ejemplo, en lugar de dar a un usuario una Int, podría en lugar de darles un valor del siguiente tipo:

type IndirectInt = forall x . (Int -> x) -> x 

El tipo anterior es "isomorfo" a un Int. "Isomorfo" es sólo una forma elegante de decir que podemos convertir cualquier IndirectInt en un Int:

fw :: IndirectInt -> Int 
fw indirect = indirect id 

... y podemos convertir cualquier Int en un IndirectInt:

bw :: Int -> IndirectInt 
bw int = \f -> f int 

... tal que:

fw . bw = id -- Exercise: Prove this 
bw . fw = id -- Exercise: Prove this 

Uso de estilo de continuación de paso, que puede convertir cualquier tipo de datos en un plazo lambda-cálculo.Vamos a empezar con un tipo simple como:

data Either a b = Left a | Right b 

En el estilo de continuación de paso, esto se convertiría en:

type IndirectEither a b = forall x . (Either a b -> x) -> x 

Pero Alonzo Church era inteligente y se dio cuenta de que para cualquier tipo con varios constructores, sólo puede proporcionar una función separada para cada constructor. Así, en el caso del tipo anterior, en lugar de proporcionar una función del tipo (Either a b-> x), podemos en cambio ofrecemos dos funciones separadas, una para el a, y una para el b, y eso sería tan bueno:

type IndirectEither a b = forall x . (a -> x) -> (b -> x) -> x 
-- Exercise: Prove that this definition is isomorphic to the previous one 

¿Qué tal un tipo como Bool donde los constructores no tienen argumentos? Bueno, Bool es isomorfo a Either()() (Ejercicio: Demostrar esto), por lo que sólo puede codificar como:

type IndirectBool = forall x . (() -> x) -> (() -> x) -> x 

Y () -> x es sólo isomorfo a x (Ejercicio: Demostrar esto), así que podemos volver a escribir más como :

type IndirectBool = forall x . x -> x -> x 

sólo hay dos funciones que pueden tener el tipo anterior:

true :: a -> a -> a 
true a _ = a 

false :: a -> a -> a 
false _ a = a 

Debido a la i somorphism, podemos garantizar que todas las codificaciones Church tendrán tantas implementaciones como valores posibles del tipo de datos original, por lo que no es coincidencia que existan exactamente dos funciones que habitan IndirectBool, al igual que hay exactamente dos constructores para Bool.

Pero, ¿cómo podemos coincidir con el patrón en nuestro IndirectBool? Por ejemplo, con un ordinario Bool, podríamos escribir:

expression1 :: a 
expression2 :: a 

case someBool of 
    True -> expression1 
    False -> expression2 

Bueno, con nuestra IndirectBool que ya cuentan con las herramientas para deconstruir sí. Nos gustaría simplemente escribir:

myIndirectBool expression1 expression2 

Tenga en cuenta que si myIndirectBool es true, se recogerá la primera expresión, y si es false que captará la segunda expresión, al igual que si tuviéramos alguna manera avenido patrón en su valor .

Tratemos de hacer lo mismo con un IndirectEither. El uso de un ordinario Either, escribíamos:

f :: a -> c 
g :: b -> c 

case someEither of 
    Left a -> f a 
    Right b -> g b 

Con la IndirectEither, nos acaba de escribir:

someIndirectEither f g 

En resumen, cuando escribimos tipos de estilo de continuación de paso, son las continuaciones como los enunciados de caso de una construcción de caso, entonces todo lo que hacemos es pasar cada declaración de caso diferente como argumentos a la función.

Esta es la razón por la que no necesita ninguna sensación de Eq para emparejar patrones en un tipo. En el cálculo lambda, el tipo decide qué es "igual" simplemente definiendo qué argumento selecciona de entre los proporcionados.Entonces, si soy un true, pruebo que soy "igual" a true seleccionando siempre mi primer argumento. Si soy false, pruebo que soy "igual" a false seleccionando siempre mi segundo argumento. En resumen, la "igualdad" del constructor se reduce a la "igualdad posicional", que siempre se define en un cálculo lambda, y si podemos distinguir un parámetro como el "primero" y otro como el "segundo", eso es todo lo que necesitamos tener la capacidad de "comparar" constructores.

Answer 2

Lo que hace falta es que los constructores en Haskell pueden tener argumentos. Las etiquetas de tipo "ellos mismos" son comparables por igualdad (al menos internamente, detrás de las escenas), pero los valores completos solo son comparables si los argumentos constituyentes también son comparables.

Así que si usted tiene un tipo como

data Maybe a = Nothing | Just a 

continuación, aunque se puede probar si una etiqueta tipo es "nada" o "sólo" (es decir, .; ajuste de patrones sobre el valor tal vez), en general se no se puede comparar el total tal vez a menos que el valor del tipo "a" que está en manos de Just también sea comparable.

--note that your first and third examples are 
--just syntactic sugar for each other... 
matchMaybe mb = case mb of 
    Nothing -> "Got a Nothing" 
    Just _ -> "Got a Just but ignored its value" 

Ahora debería estar claro por qué no es posible escribir una variación de match2 para Maybes. ¿Qué usarías para evaluar la igualdad en el caso Just?

matchMaybe_2 mb | mb == Nothing = "Got a Nothing" 
       | mb == Just {- ??? -} = "This case is impossible to write like this" 

Answer 3

En primer lugar, y matchmatch3 son en realidad exactamente lo mismo (haciendo caso omiso de las diferentes cadenas): comparación de patrones en funciones se Desazucarado a una declaración de caso.

A continuación, la coincidencia de patrones funciona en constructores en lugar de valores arbitrarios. La coincidencia de patrones está integrada en el lenguaje y no depende de expresiones booleanas; simplemente actúa en los constructores directamente. Esto es más evidente con los partidos más complejos que incluyen algunos términos para apareamiento:

f :: MyType -> Int 
f (A a) = a + 1 
f (B a b) = a + b 

¿Cómo reescribir estos patrones en expresiones booleanas? No puede (sin saber nada más sobre MyType).

En su lugar, la coincidencia de patrones solo va por constructor. Cada patrón debe estar encabezado por un constructor; no se puede escribir un patrón como f (a b c) en Haskell. Luego, cuando la función obtiene un valor, puede mirar el constructor del valor y saltar a los casos apropiados inmediatamente. Esta es la forma en que debe funcionar para patrones más complicados (como A a), y también es la forma en que funciona para los patrones simples que utilizó.

Dado que la coincidencia de patrones simplemente funciona por ir al constructor apropiado, que no depende de Eq en absoluto.No solo no tiene que tener una instancia Eq para la coincidencia de patrones, sino que tener una también no cambia la forma en que se comporta la coincidencia de patrones. Por ejemplo, intente esto:

data MyType = TypeA | TypeB | TypeC 

instance Eq MyType where 
    TypeA == TypeA = True 
    TypeB == TypeC = True 
    TypeC == TypeB = True 
    _ == _   = False 

match :: MyType → String 
match TypeA = "this is type A" 
match TypeB = "this is type B" 
match TypeC = "this is type C" 

match2 :: MyType → String 
match2 a | a == TypeA = "this is type A matched by equality" 
     | a == TypeC = "this is type B matched by equality" 
     | a == TypeB = "this is type C matched by equality" 
     | otherwise = "this is neither type A nor type B" 

igualdad Ahora que ha definido de tal manera que TypeB es igual a TypeC pero no a sí mismo. (En la vida real, debe asegurarse de que la igualdad se comporta de manera razonable y sigue la propiedad reflexiva, pero este es un ejemplo de juguete.) Ahora, si usa la coincidencia de patrón, TypeB todavía coincide con TypeB y TypeC coincide con TypeC. Pero si usa sus expresiones de guardia, TypeB en realidad coincide con TypeC y TypeC coincide con TypeB. TypeA no se modifica entre los dos.

Además, tenga en cuenta cómo se definió la instancia Equsando coincidencia de patrón. Cuando utiliza una cláusula deriving, se define de manera similar con el código generado en tiempo de compilación. Entonces, la coincidencia de patrones es más fundamental que Eq --es parte del lenguaje donde Eq es solo parte de la biblioteca estándar.

En resumen: la coincidencia de patrones está integrada en el lenguaje y funciona comparando el constructor y luego haciendo coincidir recursivamente en el resto del valor. La igualdad generalmente se implementa en términos de coincidencia de patrones y compara el valor total en lugar de solo el constructor.

Answer 4

Por lo que yo pienso, la coincidencia de patrones es básicamente igualdad de bits. Se basa en tipos, no en una noción abstracta de valor.

Tenga en cuenta, sin embargo, usted debe pensar en decir Int como

data Int = ... | -2 :: Int | -1 :: Int | 0 :: Int | 1 :: Int | 2 :: Int | ... 

Así pues, en cierto modo, cada entero tiene un tipo diferente.

Es por eso que puede hacer coincidir con el Int decir 2.

Eq va un poco más allá, le permite establecer cosas iguales que pueden no ser lo mismo en bit.

Por ejemplo, es posible que tenga un árbol binario que almacena elementos ordenados. Dicen lo siguiente:

A  A 
/\ /\ 
B C B D 
    \ \ 
     D C 

pueden asimilarse por Eq, ya que contienen los mismos elementos, pero no sería capaz de comprobar la igualdad aquí usando coincidencia de patrones.

Pero en el caso de los números, la igualdad de bits es básicamente igual a la igualdad lógica (excepto tal vez el punto flotante positivo y negativo 0.0) así que aquí Eq y la coincidencia de patrones son prácticamente equivalentes.

---

Para una analogía a C++, pensar en Eq como operator== y comparación de patrones como memcmp. Puede comparar muchos tipos de igualdad simplemente usando memcmp, pero algunos no pueden, si pueden tener representaciones diferentes para valores "iguales".