Haskell: composición de la función acaba de mi cerebro dañado

Question

Si

*Main> :t concatMap 
concatMap :: (a -> [b]) -> [a] -> [b] 

y

*Main> :t replicate 
replicate :: Int -> a -> [a] 

entonces, ¿cómo funciona eso

*Main> :t concatMap . replicate 
concatMap . replicate :: Int -> [b] -> [b] 

dado:

*Main> :t (.) 
(.) :: (b -> c) -> (a -> b) -> a -> c 

?

Quiero decir, mi comprensión de la composición de funciones es que replicate debe devolver lo que concatMap espera como argumentos para que (.) funcione. Pero no parece ser el caso. Entonces, ¿cuál es el truco?

Answer 1

Podría ayudar a ver lo que está pasando si se agrega paréntesis, a las firmas y luego alinearlos:

replicate :: Int -> (a -> [a]) 
concatMap ::  (a -> [b]) -> ([a] -> [b]) 

Ahora debería ser bastante obvio que la salida de replicate se ajusta a la entrada del concatMap si unificamos b y a, en cuyo caso el tipo de salida de la composición es [b] -> [b].

Answer 2

La dificultad probablemente provenga de variables de tipo confusas y de cómo razonas sobre la unificación de tipos. El truco es tener en cuenta, como otros han dicho, que el (->) es asociativo por la derecha, lo que significa que puede cosas se alinean como esto (hacer nuevas variables de tipo para cada firma para evitar confusiones):

(.)  :: (b   -> c  ) -> (a -> b  ) -> a -> c 
concatMap :: (q -> [r]) -> ([q] -> [r]) 
replicate ::        (Int -> (s -> [s]) 

Esto esencialmente nos da algunas limitaciones que debemos resolver. Digamos que "a ~ b" significa "a es del mismo tipo que b" o equivalentemente "a puede ser sustituido con b".

A partir de sólo lo anterior, podemos deducir los siguientes hechos:

a ~ Int 
b ~ (q -> [r]) ~ (s -> [s]) 
c ~ ([q] -> [r]) 

Pero los dos equivalencias para b nos dicen que

(q -> [r]) ~ (s -> [s]) 

lo que implica que

q ~ s and [r] ~ [s] 

Así luego reescribimos c como:

(.)

c ~ ([q] -> [r]) ==> ([s] -> [s])) 

El tapar las sustituciones de A y C de nuevo en el original tipo de con las dos funciones rendimientos aplicados

a -> c ~ Int -> ([s] -> [s]) 

que por supuesto es ahora en la forma que ghci informes: Int -> [b] -> [b].