Comment «concatMap» de mono-traversable est-il capable de «retirer» l'argument commun?

J'apprends Haskell et je faisais un programme de base de données simple pour Yesod quand je suis tombé sur ce comportement que j'ai du mal à comprendre:

testFn :: Int -> Bool -> [Int]
testFn a b = if b then replicate 10 a else []

Session Yesod GHCI:

$ :t concatMap testFn [3]
concatMap testFn [3] :: Bool -> [Int]
$ (concatMap testFn [1,2,3]) True
[1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3]

D'une manière ou d'une autre, il a pu «extraire» ce deuxième «booléen» de chacune des correspondances en un seul argument curry.

La session Standard Prelude GHCI de base refuse même de compiler cette expression:

$ :t concatMap testFn [3]
error:
    • Couldn't match type 'Bool -> [Int]' with '[b]'
      Expected type: Int -> [b]
        Actual type: Int -> Bool -> [Int]
    • Probable cause: 'testFn' is applied to too few arguments
      In the first argument of 'concatMap', namely 'testFn'
      In the expression: concatMap testFn [3]

Il s'avère que Yesod utilise une bibliothèque mono-traversable qui a la sienne concatMap:

$ :t concatMap
concatMap
  :: (MonoFoldable mono, Monoid m) =>
     (Element mono -> m) -> mono -> m

À mon niveau actuel de compréhension de Haskell, je ne pouvais pas comprendre comment les types sont distribués ici. Quelqu'un pourrait-il m'expliquer (autant pour les débutants que possible) comment cette astuce est réalisée? Quelle partie de ce qui testFnprécède est conforme au Element monotype?

Nous commençons par énumérer certains types que nous connaissons. (Nous prétendons que les chiffres sont Intpour la simplicité - ce n'est pas vraiment pertinent.)

testFn :: Int -> Bool -> [Int]
[1,2,3] :: [Int]
True :: Bool

(concatMap testFn [1,2,3]) Trueest identique à concatMap testFn [1,2,3] True, concatMapdoit donc avoir un type correspondant à tous ces arguments:

concatMap :: (Int -> Bool -> [Int]) -> [Int] -> Bool -> ???

où ???est le type de résultat. Notez que, en raison des règles d'associativité, ->s'associe à droite, donc la saisie ci-dessus est identique à:

concatMap :: (Int -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

Écrivons le type général au-dessus de celui-là. J'ajoute quelques espaces pour marquer la similitude.

concatMap :: (MonoFoldable mono, Monoid m) =>
             (Element mono -> m              ) -> mono  -> m
concatMap :: (Int          -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

Ah-ha! Nous avons un match si nous choisissons mcomme Bool -> [Int], et monocomme [Int]. Si nous le faisons, nous satisfaisons aux contraintes MonoFoldable mono, Monoid m(voir ci-dessous), et nous avons aussi Element mono ~ Int, donc tout type vérifie.

Nous en déduisons que ???c'est à [Int]partir de la définition de m.

A propos des contraintes: car MonoFoldable [Int], il y a peu à dire. [Int]est clairement un type de liste avec un Inttype d'élément, et cela suffit pour en faire un MonaFoldableavec Intcomme son Element.

Pour Monoid (Bool -> [Int]), c'est un peu plus complexe. Nous avons que tout type de fonction A -> Best un monoïde si Best un monoïde. Cela suit en effectuant l'opération de manière ponctuelle. Dans notre cas spécifique, nous comptons [Int]être un monoïde et nous obtenons:

mempty :: Bool -> [Int]
mempty = \_ -> []

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b