Como o "concatMap" do mono-traversable é capaz de "retirar" o argumento comum?

9

Estou aprendendo Haskell e estava fazendo um programa simples de semente de banco de dados para Yesod quando me deparei com esse comportamento que acho difícil de entender:

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

Sessão 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 alguma forma, ele foi capaz de "extrair" o segundo "Bool" de cada um dos mapeamentos em um único argumento.

A sessão Prelude GHCI de base padrão se recusa a compilar essa expressão:

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

Acontece que o Yesod usa uma biblioteca mono-atravessável que possui sua própria concatMap:

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

No meu nível atual de entendimento de Haskell, não conseguia descobrir como os tipos são distribuídos aqui. Alguém poderia me explicar (o mais orientado para iniciantes possível) como esse truque é feito? Que parte testFnacima está em conformidade com o Element monotipo?

dimsuz
fonte

Respostas:

6

Começamos listando alguns tipos que conhecemos. (Nós fingimos que os números são Intpara simplificar - isso não é realmente relevante.)

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

(concatMap testFn [1,2,3]) Trueé o mesmo que concatMap testFn [1,2,3] True, portanto, concatMapdeve ter um tipo que corresponda a todos esses argumentos:

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

onde ???é o tipo de resultado. Observe que, devido às regras de associatividade, ->associa à direita, portanto, a digitação acima é a mesma que:

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

Vamos escrever o tipo geral acima desse. Estou adicionando alguns espaços para marcar a semelhança.

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

Ah-ha! Temos uma partida se escolhermos mcomo Bool -> [Int]e monocomo [Int]. Se o fizermos, satisfazemos as restrições MonoFoldable mono, Monoid m(veja abaixo), e também o temos Element mono ~ Int, para que tudo seja verificado.

Inferimos que ???é [Int]da definição de m.

Sobre as restrições: pois MonoFoldable [Int], há pouco a dizer. [Int]é claramente um tipo de lista com um Inttipo de elemento, e isso é suficiente para transformá-lo em um MonaFoldablecom Intseu Element.

Para Monoid (Bool -> [Int]), é um pouco mais complexo. Temos que qualquer tipo de função A -> Bé um monóide se Bfor um monóide. A seguir, realizando a operação de maneira pontual. No nosso caso específico, confiamos em [Int]ser um monóide e obtemos:

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

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b
chi
fonte
11
Ótima explicação! A maneira como você explicou e alinha os tipos é exatamente o que eu queria ver, obrigado!
dimsuz 19/01