W jaki sposób „concatMap” z mono-traversable jest w stanie „wyciągnąć” wspólny argument?

9

Uczę się Haskell i robiłem prosty program DB-seed dla Yesod, kiedy natknąłem się na takie zachowanie, które trudno mi zrozumieć:

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

Sesja GHCI Yesod:

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

W jakiś sposób udało mu się „wyciągnąć” ten drugi „Bool” z każdego z mapowań w jeden curry argument.

Standardowa podstawowa sesja GHCI Prelude nie kompiluje nawet tego wyrażenia:

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

Okazuje się, że Yesod korzysta z biblioteki mono-przejezdnej, która ma swoją własną concatMap:

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

Na obecnym poziomie rozumienia Haskell nie mogłem zrozumieć, w jaki sposób typy są tutaj dystrybuowane. Czy ktoś mógłby mi wyjaśnić (jak najbardziej zorientowany na początkującego), jak to się robi? Która część testFnpowyższego jest zgodna z Element monotypem?

dimsuz
źródło

Odpowiedzi:

6

Zaczynamy od listy niektórych znanych nam typów. (Udajemy, że liczby są Intdla uproszczenia - to nie jest tak naprawdę istotne).

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

(concatMap testFn [1,2,3]) Truejest taki sam jak concatMap testFn [1,2,3] True, więc concatMapmusi mieć typ pasujący do wszystkich tych argumentów:

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

gdzie ???jest typ wyniku. Zauważ, że z powodu reguł ->asocjatywności jest on przypisany do prawej, więc powyższe wpisanie jest takie samo jak:

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

Napiszmy ogólny typ powyżej tego. Dodaję kilka spacji, aby zaznaczyć podobieństwo.

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

Ah-ha! Mamy dopasowanie, jeśli wybierzemy mjako Bool -> [Int]i monojako [Int]. Jeśli to zrobimy, spełnimy ograniczenia MonoFoldable mono, Monoid m(patrz poniżej), a także mamy Element mono ~ Int, więc wszystko sprawdza typ.

Wnioskujemy, że ???pochodzi [Int]z definicji m.

O ograniczeniach: bo MonoFoldable [Int]niewiele można powiedzieć. [Int]jest wyraźnie lista podobnego typu z Inttypu elementu, a to wystarczy, aby uczynić go MonaFoldablez Intjak jego Element.

Ponieważ Monoid (Bool -> [Int])jest to trochę bardziej złożone. Mamy, że każdy typ funkcji A -> Bjest monoidem, jeśli Bjest monoidem. Następnie wykonuje się operację w sposób punktowy. W naszym konkretnym przypadku polegamy na [Int]byciu monoidem i otrzymujemy:

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

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b
chi
źródło
1
Świetne wyjaśnienie! Sposób, w jaki wyjaśniłeś i dopasowałeś typy, właśnie tego chciałem zobaczyć, dzięki!
dimsuz