Как "concatMap" из mono-traversable способен "вытащить" общий аргумент? - PullRequest
Новая
       7

Как "concatMap" из mono-traversable способен "вытащить" общий аргумент?

9 голосов
/ 19 января 2020

Я изучаю Haskell и выполнял простую программу DB-seed для Yesod, когда наткнулся на это поведение, которое мне трудно понять: 

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

Сессия 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]

Каким-то образом ему удалось "вытащить" этот второй "Bool" из каждого из отображений в один аргумент с карри.

Стандартный базовый сеанс Prelude GHCI отказывается даже компилировать это выражение: 

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

Оказывается, Йесод использует монотранслябельную библиотеку, которая имеет собственную concatMap: 

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

На моем текущем уровне понимания Haskell я не мог выяснить, как типы распространяются здесь. Может ли кто-нибудь объяснить мне (насколько это возможно для начинающих), как это делается? Какая часть testFn выше соответствует типу Element mono?

1 Ответ

6 голосов
/ 19 января 2020

Мы начнем с перечисления некоторых известных нам типов. (Мы притворяемся, что числа Int для простоты - это на самом деле не имеет значения.) 

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

(concatMap testFn [1,2,3]) True совпадает с concatMap testFn [1,2,3] True, поэтому concatMap должен иметь тип, соответствующий всем эти аргументы: 

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

, где ??? - тип результата. Обратите внимание, что из-за правил ассоциативности -> ассоциируется справа, поэтому приведенная выше типизация такая же, как: 

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

Давайте напишем общий тип выше этого. Я добавляю несколько пробелов, чтобы отметить сходство. 

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

Ах-ха! У нас есть совпадение, если мы выберем m в качестве Bool -> [Int] и mono в качестве [Int]. Если мы это сделаем, мы удовлетворяем ограничениям MonoFoldable mono, Monoid m (см. Ниже), и у нас также есть Element mono ~ Int, поэтому все проверяет тип.

Мы делаем вывод, что ??? равно [Int] из определения из m.

Об ограничениях: для MonoFoldable [Int] мало что можно сказать. [Int] явно является списочным типом с типом элемента Int, и этого достаточно, чтобы превратить его в MonaFoldable с Int в качестве Element.

для Monoid (Bool -> [Int]), это немного сложнее. Мы имеем, что любой тип функции A -> B является моноидом, если B является моноидом. Это следует, выполняя операцию поточечно. В нашем конкретном случае c мы полагаемся на [Int] как моноид и получаем: 

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

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