¿Cómo funcionan juntos el curry de Haskell y la coincidencia de patrones?

pattern-matching currying

Question

Soy nuevo en Haskell. Entiendo que las funciones se cambian para convertirse en funciones que toman un parámetro. Lo que no entiendo es cómo se puede lograr la comparación de patrones con múltiples valores cuando este es el caso. Por ejemplo:

Supongamos que tenemos la siguiente definición de función completamente arbitraria:

myFunc :: Int -> Int -> Int
myFunc 0 0 = 0
myFunc 1 1 = 1
myFunc x y = x `someoperation` y

Es la función parcialmente aplicada devuelta por myFunc 0 esencialmente:

partiallyAppliedMyFunc :: Int -> Int
partiallyAppliedMyFunc 0 = 0
partiallyAppliedMyFunc y = 0 `someoperation` y

¿Eliminando así el patrón extraño que no puede coincidir? O ... ¿qué está pasando aquí?

Answer 1

En realidad, esta pregunta es más sutil de lo que puede parecer en la superficie, e implica aprender un poco sobre los componentes internos del compilador para responder de manera correcta. La razón es que damos por sentado que podemos tener patrones y patrones anidados en más de un término, cuando en realidad, para los propósitos de un compilador, lo único que puede hacer es derivar en el constructor de nivel superior de un solo valor. Por lo tanto, la primera etapa del compilador es convertir patrones anidados (y patrones en más de un valor) en patrones más simples. Por ejemplo, un algoritmo ingenuo podría transformar su función en algo como esto:

myFunc = /x y -> case x of
    0 -> case y of
        0 -> 0
        _ -> x `someoperation` y
    1 -> case y of
        1 -> 1
        _ -> x `someoperation` y
    _ -> x `someoperation` y

Ya puede ver que hay muchas cosas subóptimas aquí: el término de someoperation se repite mucho, y la función espera ambos argumentos antes de que incluso comience a hacer un case ; vea Un compilador de concordancia de patrones de término inspirado en la teoría de autómatas finitos para una discusión de cómo podría mejorar esto.

De todos modos, en esta forma, debería ser un poco más claro cómo sucede el paso de curry. Podemos sustituir directamente por x en esta expresión para ver lo que hace myFunc 0 :

myFunc 0 = /y -> case 0 of
    0 -> case y of
        0 -> 0
        _ -> 0 `someoperation` y
    1 -> case y of
        1 -> 1
        _ -> 0 `someoperation` y
    _ -> 0 `someoperation` y

Dado que esto sigue siendo un lambda, no se realiza ninguna reducción adicional. Puede esperar que un compilador lo suficientemente inteligente pueda hacer un poco más, pero GHC explícitamente no hace más; Si desea que se realicen más cálculos después de proporcionar solo un argumento, debe cambiar su definición. (Hay una compensación de tiempo / espacio aquí, y elegir correctamente es demasiado difícil de hacer de manera confiable. Por lo tanto, GHC lo deja en las manos del programador para hacer esta elección). Por ejemplo, podría escribir explícitamente

myFunc 0 = /y -> case y of
    0 -> 0
    _ -> 0 `someoperation` y
myFunc 1 = /y -> case y of
    1 -> 1
    _ -> 1 `someoperation` y
myFunc x = /y -> x `someoperation` y

y luego myFunc 0 se reduciría a una expresión mucho más pequeña.