Haskell: złożenie funkcji jest po prostu uszkodzony mój mózg

Question

Jeśli

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

i

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

Więc jak to działa

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

podane:

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

?

To znaczy, moje rozumienie złożenie funkcji jest to, że replicate powinien zwrócić cokolwiek concatMap oczekuje jako argumentów w celu (.) do pracy. Ale to NIE WYGLĄDA, aby tak było. Więc jaki jest haczyk?

Answer 1

To może pomóc, aby zobaczyć, co się dzieje, jeśli dodać nawiasy do podpisu, a następnie ich układanie:

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

Teraz powinno być dość oczywiste, że wyjście replicate pasuje wejście concatMap if ujednolicamy b i a, w którym to przypadku typem wyjściowym kompozycji jest [b] -> [b].

Answer 2

Trudność wynika prawdopodobnie z mylących zmiennych typu i tego, w jaki sposób wywołujesz typ unifikacji. Sztuką jest, aby rozważyć, jak mówili inni, że (->) jest prawym asocjacyjne, dzięki czemu można linia rzeczy się jak ten (poznawanie nowych zmiennych typu dla każdego podpisu aby uniknąć nieporozumień):

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

To zasadniczo daje nam pewne ograniczenia, które musimy rozwiązać. Powiedzmy, że "a ~ b" oznacza "a jest tego samego typu co b" lub równoważnie "a można zastąpić b."

Od dopiero powyżej, możemy wywnioskować następujące fakty:

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

Ale dwa odpowiedniki dla b mówią nam, że

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

co oznacza, że ​​

q ~ s and [r] ~ [s] 

Tak następnie przepisujemy c jako:

(.)

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

Podłączenie podstawienia przez A i C z powrotem do pierwotnego typu z dwoma funkcjami stosowane wydajności

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

co oczywiście jest w postaci, która ghci raportów: Int -> [b] -> [b].