Perché la comprensione dell'elenco Haskell non causa un errore quando la corrispondenza del modello fallisce?

Question

Sto cercando di capire come funzionano le comprensioni dell'elenco di Haskell " sotto il cofano " per quanto riguarda la corrispondenza dei motivi. Il seguente output di ghci illustra il mio punto:

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

Come puoi vedere, è in grado di saltare il " Niente " e seleziona solo il " Solo " valori. Comprendo che List è una monade, definita come (fonte da Real World Haskell, cap. 14):

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

Pertanto, una comprensione della lista fondamentalmente crea una lista singleton per ogni elemento selezionato nella comprensione della lista e li concatena. Se ad un certo punto una corrispondenza del modello fallisce, il risultato del & Quot; fail & Quot; viene invece utilizzata la funzione. In altre parole, il & Quot; Solo x & Quot; il pattern non corrisponde quindi [] viene utilizzato come segnaposto fino a quando viene chiamato 'concat'. Questo spiega perché il & Quot; Nothing & Quot; sembra essere saltato.

Quello che non capisco è come fa Haskell a chiamare il " fail " funzione? È & Quot; magic compilatore & Quot; o funzionalità che puoi scrivere tu stesso in Haskell? È possibile scrivere il seguente & Quot; selezionare & Quot; funzione per funzionare allo stesso modo di una comprensione dell'elenco?

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

Answer 1

Mentre le implementazioni di Haskell potrebbero non farlo direttamente in questo modo internamente, è utile pensarci in questo modo :)

[x | Just x <- myList]

... diventa:

do
    Just x <- myList
    return x

... ovvero:

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

Per quanto riguarda la tua domanda:

  

Quello che non capisco è come fa Haskell a chiamare il " fail " Funzione?

In notazione, se un'associazione di pattern non riesce (ovvero Just x), viene chiamato il metodo fail. Per l'esempio sopra, sarebbe simile a questo:

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

Quindi, ogni volta che si verifica un pattern-match in un contesto monadico che potrebbe non riuscire, Haskell inserisce una chiamata a fail. Provalo con IO:

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

Answer 2

La regola per eliminare la comprensione di un elenco richiede un'espressione del modulo < => (dove [ e | p <- l ] è un'espressione, e uno schema e p un'espressione di elenco) si comportano come

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

Le versioni precedenti di Haskell avevano comprensione della monade , che sono stati rimossi dalla lingua perché erano difficili da leggere e ridondanti con la notazione l. (Anche le comprensioni dell'elenco sono ridondanti, ma non sono così difficili da leggere.) penso desugarando do come monade (o, per essere precisi, come una monade con zero ) produrrebbe qualcosa del genere

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

dove mzero appartiene alla classe MonadPlus. Questo è molto vicino a

do { p <- l; return e }

che desugars in

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

Quando prendiamo la Monade Elenco, abbiamo

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

Ad esempio, i 3 approcci (comprensione delle liste, comprensione della monade, <=> espressioni) sono equivalenti per le liste.

Answer 3

Non credo che la sintassi di comprensione dell'elenco abbia molto a che fare con il fatto che List ([]) o Maybe del resto, sia un'istanza della classe di tipo Monad.

Le comprensioni dell'elenco sono in effetti magia del compilatore o zucchero della sintassi , ma ciò è possibile perché il compilatore conosce la struttura del fail tipo di dati.

Ecco a cosa viene compilata la comprensione dell'elenco: (Beh, penso di non averlo effettivamente confrontato con il GHC)

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

Come puoi vedere, il compilatore non deve chiamare la funzione select, può semplicemente incorporare un elenco vuoto, perché sa cos'è un elenco .

---

È interessante notare che questo fatto che l'elenco comprenda la sintassi "salta" gli errori di corrispondenza viene utilizzato in alcune librerie per eseguire la programmazione generica. Vedi l'esempio nella Libreria Uniplate .

---

Modifica: Oh, e per rispondere alla tua domanda, non puoi chiamare la tua funzione Nothing con la lambda che le hai dato. In effetti fallirà in caso di errore di corrispondenza del modello se lo chiami con un f valore.

Puoi passare la funzione concatMap dal codice sopra, ma <=> avrebbe il tipo:

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

che va benissimo, puoi usare la funzione <=> internamente :-)

Inoltre, quel nuovo <=> ora ha il tipo di operatore monadic bind per le liste (con i suoi argomenti capovolti):

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