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

Question

Estoy tratando de entender cómo funcionan las comprensiones de listas de Haskell & "; 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 " Nothing " y seleccione solo " Just " valores. Entiendo que List es una mónada, definida como (fuente de Real World Haskell, cap. 14):

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

Por lo tanto, una comprensión de la lista básicamente construye una lista singleton para cada elemento seleccionado en la comprensión de la lista y los concatena. Si una coincidencia de patrón falla en algún paso, el resultado de & Quot; fail & Quot; La función se utiliza en su lugar. En otras palabras, el & Quot; Just x & Quot; El patrón no coincide, por lo que [] se utiliza como marcador de posición hasta que se llame a 'concat'. Eso explica por qué & Quot; Nothing & Quot; parece omitirse.

Lo que no entiendo es, ¿cómo sabe Haskell llamar a " fail " ¿función? ¿Es & Quot; compiler magic & Quot ;, o funcionalidad que puede escribir usted mismo en Haskell? ¿Es posible escribir lo siguiente & Quot; seleccione & Quot; ¿funciona 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

Si bien las implementaciones de Haskell podrían no hacerlo directamente de esta manera internamente, es útil pensarlo de esta manera :)

[x | Just x <- myList]

... se convierte en:

do
    Just x <- myList
    return x

... que es:

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

En cuanto a su pregunta:

  

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

En do-notation, si falla un enlace de patrón (es decir, el Just x), se llama al método fail. Para el ejemplo anterior, se vería así:

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

Entonces, cada vez que tiene una coincidencia de patrones en un contexto monádico que puede fallar, Haskell inserta una llamada a fail. Pruébelo con IO:

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

Answer 2

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

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

Las versiones anteriores de Haskell tenían comprensión de mónadas , que se eliminaron del idioma porque eran difíciles de leer y redundantes con la notación l. (Las comprensiones de listas también son redundantes, pero no son tan difíciles de leer.) creo desugaring do como una (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 desugars to

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

Cuando tomamos la Lista Mónada, tenemos

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

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

Answer 3

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

Las comprensiones de listas 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 fail.

Esto es a lo que se compila la comprensión de la lista: (Bueno, creo que en realidad no lo comparé con 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 select, simplemente puede insertar una lista vacía, porque sabe qué es una lista .

---

Curiosamente, este hecho de que la sintaxis de comprensión de listas '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 su pregunta, no puede llamar a su función Nothing con la lambda que le dio. De hecho, fallará en una falla de coincidencia de patrón si la llama con un valor f.

Puede pasarle la función concatMap del código anterior, pero que <=> tendría el tipo:

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

que está perfectamente bien, puede usar la función <=> internamente :-)

Además, ese nuevo <=> 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)