tuplas - multiplicar haskell

¿Por qué las comprensiones de la lista Haskell no causan un error cuando falla la coincidencia de patrones?

Question

Estoy tratando de entender cómo las comprensiones de la lista Haskell funcionan "bajo el capó" en lo que respecta a la coincidencia de patrones. La siguiente salida de ghci ilustra mi punto:

Prelude> let myList = [Just 1, Just 2, Nothing, Just 3]
Prelude> let xs = [x | Just x <- myList]
Prelude> xs
[1,2,3]
Prelude>

Como puede ver, puede omitir el "Nada" y seleccionar solo los valores "Justos". Entiendo que List es una mónada, definida como (fuente de Real World Haskell, capítulo 14):

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    xs >> f = concat (map (/_ -> f) xs)
    fail _ = []

Por lo tanto, una lista de comprensión básicamente crea una lista única para cada elemento seleccionado en la lista de comprensión y los concatena. Si una coincidencia de patrón falla en algún momento, se utiliza el resultado de la función "fail". En otras palabras, el patrón "Just x" no coincide, por lo que [] se usa como marcador de posición hasta que se llame a ''concat''. Eso explica por qué el "Nada" parece omitirse.

Lo que no entiendo es, ¿cómo sabe Haskell llamar a la función "fallar"? ¿Es "magia del compilador" o una funcionalidad que puedes escribir tú mismo en Haskell? ¿Es posible escribir la siguiente función "seleccionar" para que funcione de la misma manera que una lista de comprensión?

select :: (a -> b) -> [a] -> [b]
select (Just x -> x) myList       -- how to prevent the lambda from raising an error?
[1,2,3]

Answer 1

La regla para deslumbrar una lista de comprensión requiere una expresión de la forma [ e | p <- l ] [ e | p <- l ] (donde e es una expresión, p un patrón, l una expresión de lista) se comporta como

let ok p = [e]
    ok _ = []
in concatMap ok l

Las versiones anteriores de Haskell tenían una comprensión de mónadas , que fueron eliminadas del lenguaje porque eran difíciles de leer y redundantes con la " do -notación". (Las comprensiones de listas también son redundantes, pero no son tan difíciles de leer). Creo que desalar [ e | p <- l ] [ e | p <- l ] como una mónada (o, para ser precisos, como una mónada con cero ) produciría algo así como

let ok p = return e
    ok _ = mzero
in l >>= ok

donde mzero es de la clase MonadPlus . Esto está muy cerca de

do { p <- l; return e }

que desagua a

let ok p = return e
    ok _ = fail "..."
in l >>= ok

Cuando tomamos List Monad, tenemos

return e = [e]
mzero = fail _ = []
(>>=) = flip concatMap

Es decir, los 3 enfoques (listas de comprensión, mónadas y expresiones) son equivalentes para las listas.

Answer 2

No creo que la sintaxis de comprensión de la lista tenga mucho que ver con el hecho de que List ( [] ), o Maybe en ese caso, sea una instancia de la clase de tipo Monad .

Las listas de comprensión son, de hecho, magia del compilador o azúcar de sintaxis , pero eso es posible porque el compilador conoce la estructura del tipo de datos [] .

Esto es a lo que se compila la comprensión de la lista: (Bueno, creo, en realidad no lo compruebo contra el GHC)

xs = let f = /xs -> case xs of
                      Just x -> [x]
                      _      -> []
     in concatMap f myList

Como puede ver, el compilador no tiene que llamar a la función de fail , simplemente puede alinear una lista vacía, porque sabe lo que es una lista.

Curiosamente, este hecho de que la lista de sintaxis de comprensión omite fallas de coincidencia de patrones se usa en algunas bibliotecas para hacer programación genérica. Vea el ejemplo en la biblioteca Uniplate .

Editar: Ah, y para responder a tu pregunta, no puedes llamar a tu función de select con la lambda que le diste. De hecho, fallará en un error de coincidencia de patrón si lo llama con un valor Nothing .

Podría pasarle la función f desde el código anterior, pero luego select tendría el tipo:

select :: (a -> [b]) -> [a] -> [b]

lo cual está perfectamente bien, puedes usar la función concatMap internamente :-)

Además, esa nueva select ahora tiene el tipo de operador de enlace monádico para listas (con sus argumentos invertidos):

(>>=) :: [a] -> (a -> [b]) -> [b]
xs >>= f = concatMap f xs -- ''or as you said: concat (map f xs)

Answer 3

Si bien las implementaciones de Haskell pueden no hacerlo directamente así internamente, es útil pensar de esta manera :)

[x | Just x <- myList]

... se convierte en:

do
    Just x <- myList
    return x

... cual es:

myList >>= /(Just x) -> return x

En cuanto a tu pregunta:

Lo que no entiendo es, ¿cómo sabe Haskell llamar a la función "fallar"?

En notación do, si falla un enlace de patrón (es decir, el Just x ), se invoca el método fallido. Para el ejemplo anterior, se vería algo como esto:

myList >>= /temp -> case temp of
    (Just x) -> return x
    _        -> fail "..."

Por lo tanto, cada vez que tiene una coincidencia de patrones en un contexto monádico que puede fallar, Haskell inserta una llamada para que fail . Pruébalo con IO:

main = do
    (1,x) <- return (0,2)
    print x -- x would be 2, but the pattern match fails