Pourquoi les compréhensions de liste Haskell ne provoquent-elles pas une erreur lorsque la correspondance de modèle échoue?

Question

J'essaie de comprendre comment fonctionne la compréhension de liste Haskell & "sous le capot &"; en ce qui concerne la correspondance des modèles. La sortie ghci suivante illustre mon propos:

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

Comme vous pouvez le voir, il est capable de sauter le & "Rien &"; et sélectionnez uniquement le " Juste " valeurs. Je comprends que List est une monade, définie comme (source du Real World Haskell, chapitre 14):

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

Par conséquent, une compréhension de liste construit essentiellement une liste de singleton pour chaque élément sélectionné dans la compréhension de liste et les concatène. Si une correspondance de modèle échoue à un moment ou à un autre, le résultat de la & "Échec &"; la fonction est utilisée à la place. En d’autres termes, le & Quot; Just x & Quot; le motif ne correspond pas, alors [] est utilisé comme espace réservé jusqu'à ce que "concat" soit appelé. Cela explique pourquoi & "Rien &"; semble être ignoré.

Ce que je ne comprends pas, c'est comment Haskell sait appeler le & "fail &"; une fonction? Est-ce & "La magie du compilateur &" Ou une fonctionnalité que vous pouvez écrire vous-même dans Haskell? Est-il possible d’écrire ce qui suit & "Select &"; fonctionner pour fonctionner de la même manière qu'une compréhension de liste?

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

Answer 1

Bien que l'implémentation de Haskell puisse ne pas le faire directement en interne, il est utile de penser de cette façon:)

[x | Just x <- myList]

... devient:

do
    Just x <- myList
    return x

... qui est:

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

En ce qui concerne votre question:

  

Ce que je ne comprends pas, c'est comment Haskell sait appeler le & "fail &"; fonction?

En do-notation, si une liaison de modèle échoue (c'est-à-dire le Just x), la méthode fail est appelée. Pour l'exemple ci-dessus, cela ressemblerait à quelque chose comme ceci:

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

Ainsi, chaque fois que vous avez une correspondance de motif dans un contexte monadique qui peut échouer, Haskell insère un appel à fail. Essayez-le avec IO:

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

Answer 2

La règle permettant de supprimer la compréhension d'une liste requiert une expression du formulaire < => (où [ e | p <- l ] est une expression, e un motif et p une expression de liste) se comportent comme

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

Les versions précédentes de Haskell contenaient des monades , qui ont été supprimés de la langue car ils étaient difficiles à lire et redondants avec la notation l. (Les descriptions de liste sont également redondantes, mais elles sont faciles à lire.) Je pense que désaspère do comme une monade (ou, pour être précis, monade avec zéro ) donnerait quelque chose comme

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

où mzero provient de la MonadPlus classe. Ceci est très proche de

do { p <- l; return e }

qui desugars à

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

Lorsque nous prenons la liste Monad, nous avons

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

I.e., les 3 approches (compréhension de liste, compréhension de monade, <=> expressions) sont équivalentes pour les listes.

Answer 3

Je ne pense pas que la syntaxe de compréhension de liste ait beaucoup à faire avec le fait que List ([]), ou Maybe d'ailleurs, se trouve être une instance de la classe de type Monad.

Les interprétations de liste sont bien magiques du compilateur ou sucre de syntaxe , mais cela est possible car le compilateur connaît la structure du type de données fail.

Voici en quoi la liste de compréhension est compilée: (Eh bien, je pense que je ne l'ai pas comparée au GHC)

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

Comme vous pouvez le constater, le compilateur n'a pas à appeler la fonction select, il peut simplement insérer une liste vide, car il sait en quoi consiste une liste .

Fait intéressant, le fait que la syntaxe de compréhension de liste "saute" les correspondances de modèle est utilisé dans certaines bibliothèques pour effectuer de la programmation générique. Voir l'exemple dans la bibliothèque Uniplate .

Modifier: Oh, et pour répondre à votre question, vous ne pouvez pas appeler votre fonction Nothing avec le lambda que vous lui avez donné. Il échouera en cas d'échec d'une correspondance de motif si vous l'appelez avec une valeur f.

Vous pouvez lui passer la concatMap fonction du code ci-dessus, mais <=> aurait le type:

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

ce qui convient parfaitement, vous pouvez utiliser la <=> fonction en interne: -)

De plus, ce nouveau <=> a maintenant le type de l'opérateur de liaison monadique pour les listes (avec ses arguments retournés):

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