¿Cómo "concatMap" de mono-traversable es capaz de "extraer" un argumento común?

9

Estoy aprendiendo Haskell y estaba haciendo un simple programa de semilla de base de datos para Yesod cuando me topé con este comportamiento que me resulta difícil de entender:

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

Sesión 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]

De alguna manera fue capaz de "sacar" ese segundo "Bool" de cada una de las asignaciones en un solo argumento curioso.

La sesión base estándar Prelude GHCI se niega incluso a compilar esta expresión:

$ :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]

Resulta que Yesod usa una biblioteca mono-transitable que tiene su propia concatMap:

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

En mi nivel actual de comprensión de Haskell, no pude entender cómo se distribuyen los tipos aquí. ¿Podría alguien explicarme (tanto como sea posible para principiantes) cómo se hace este truco? ¿Qué parte de lo testFnanterior se ajusta al Element monotipo?

dimsuz
fuente

Respuestas:

6

Comenzamos enumerando algunos tipos que conocemos. (Suponemos que los números son Intpor simplicidad; esto no es realmente relevante).

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

(concatMap testFn [1,2,3]) Truees el mismo que concatMap testFn [1,2,3] True, por lo que concatMapdebe tener un tipo que coincida con todos esos argumentos:

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

donde ???es el tipo de resultado Tenga en cuenta que, debido a las reglas de asociatividad, se ->asocia a la derecha, por lo que la escritura anterior es la misma que:

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

Escribamos el tipo general arriba de ese. Estoy agregando algunos espacios para marcar la similitud.

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

Ah-ha! Tenemos una coincidencia si elegimos mcomo Bool -> [Int]y monocomo [Int]. Si lo hacemos, satisfacemos las restricciones MonoFoldable mono, Monoid m(ver más abajo), y también lo tenemos Element mono ~ Int, así que todo tipo verifica.

Inferimos que ???es [Int]de la definición de m.

Sobre las restricciones: porque MonoFoldable [Int], hay poco que decir. [Int]es claramente una lista similar de tipo con un Inttipo de elemento, y eso es suficiente para convertirlo en un MonaFoldablecon Intcomo su Element.

Para Monoid (Bool -> [Int]), es un poco más complejo. Tenemos que cualquier tipo de función A -> Bes un monoide si Bes un monoide. Esto sigue realizando la operación de manera puntual. En nuestro caso específico, confiamos en [Int]ser un monoide y obtenemos:

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

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b
chi
fuente
1
¡Gran explicación! La forma en que ha explicado y alineado los tipos es justo lo que quería ver, ¡gracias!
Dimsuz