Operador de ponto em Haskell: preciso de mais explicações

86

Estou tentando entender o que o operador ponto está fazendo neste código Haskell:

sumEuler = sum . (map euler) . mkList

Todo o código-fonte está abaixo.

Meu entendimento

O operador ponto toma as duas funções sume o resultado de map eulere o resultado de mkListcomo a entrada.

Mas, sumuma função não é o argumento da função, certo? Então, o que está acontecendo aqui?

Além disso, o que está (map euler)fazendo?

Código

mkList :: Int -> [Int]
mkList n = [1..n-1]

euler :: Int -> Int
euler n = length (filter (relprime n) (mkList n))

sumEuler :: Int -> Int
sumEuler = sum . (map euler) . mkList
Cbrulak
fonte

Respostas:

138

Simplificando, .é a composição de funções, assim como na matemática:

f (g x) = (f . g) x

No seu caso, você está criando uma nova função, sumEulerque também pode ser definida assim:

sumEuler x = sum (map euler (mkList x))

O estilo em seu exemplo é denominado estilo "sem pontos" - os argumentos da função são omitidos. Isso torna o código mais claro em muitos casos. (Pode ser difícil grocar na primeira vez que você vê, mas você vai se acostumar com isso depois de um tempo. É um idioma comum em Haskell.)

Se você ainda está confuso, pode ser útil relacionar .- se com algo como um canal UNIX. Se fa saída de se torna ga entrada de, cuja saída se torna ha entrada de, você escreveria isso na linha de comando como f < x | g | h. Em Haskell, .funciona como o UNIX |, mas "para trás" - h . g . f $ x. Acho que essa notação é bastante útil, digamos, no processamento de uma lista. Em vez de alguma construção pesada como map (\x -> x * 2 + 10) [1..10], você poderia simplesmente escrever (+10) . (*2) <$> [1..10]. (E, se você quiser aplicar essa função apenas a um único valor; é (+10) . (*2) $ 10. Consistente!)

O wiki Haskell tem um bom artigo com mais alguns detalhes: http://www.haskell.org/haskellwiki/Pointfree

Jrockway
fonte
1
Tiny quibble: o primeiro trecho de código não é realmente Haskell válido.
SwiftsNamesake
2
@SwiftsNamesake Para aqueles de nós que não são fluentes em Haskell, você apenas quer dizer que o único sinal de igual não é significativo aqui? (Portanto, o snippet deveria ter sido formatado como " f (g x)= (f . g) x"?) Ou algo mais?
user234461
1
@ user234461 Exatamente, sim. Você precisaria ==se quisesse Haskell padrão válido.
SwiftsNamesake
Esse pequeno fragmento no topo é apenas ouro. Como as outras respostas aqui estão corretas, mas aquele trecho simplesmente clicou diretamente na minha cabeça intuitivamente, o que tornou desnecessário ler o resto da sua resposta.
Tarick Welling
24

O . operador compõe funções. Por exemplo,

a . b

Onde a e b são funções é uma nova função que corre b em seus argumentos, então uma base nesses resultados. Seu código

sumEuler = sum . (map euler) . mkList

é exatamente o mesmo que:

sumEuler myArgument = sum (map euler (mkList myArgument))

mas espero que seja mais fácil de ler. A razão de haver parênteses ao redor do euler do mapa é porque torna mais claro que há 3 funções sendo compostas: soma , euler do mapa e mkList - euler do mapa é uma função única.

Jesse Rusak
fonte
23

sumé uma função do Prelúdio de Haskell, não um argumento para sumEuler. Tem o tipo

Num a => [a] -> a

O operador de composição de função . tem tipo

(b -> c) -> (a -> b) -> a -> c

Então nós temos

           euler           ::  Int -> Int
       map                 :: (a   -> b  ) -> [a  ] -> [b  ]
      (map euler)          ::                 [Int] -> [Int]
                    mkList ::          Int -> [Int]
      (map euler) . mkList ::          Int ->          [Int]
sum                        :: Num a =>                 [a  ] -> a
sum . (map euler) . mkList ::          Int ->                   Int

Observe que Inté realmente uma instância da Numtypeclass.

Chris Conway
fonte
11

O . operador é usado para a composição da função. Assim como a matemática, se você tiver que funções f (x) e g (x) f. g torna-se f (g (x)).

map é uma função incorporada que aplica uma função a uma lista. Ao colocar a função entre parênteses, a função é tratada como um argumento. Um termo para isso é currying . Você deveria pesquisar isso.

O que acontece é que recebe uma função com, digamos, dois argumentos, e aplica o argumento euler. (mapa euler) certo? e o resultado é uma nova função, que leva apenas um argumento.

soma (mapa euler). mkList é basicamente uma maneira sofisticada de colocar tudo isso junto. Devo dizer que meu Haskell está um pouco enferrujado, mas talvez você mesmo possa montar essa última função?

John Leidegren
fonte
5

Operador de ponto em Haskell

Estou tentando entender o que o operador ponto está fazendo neste código Haskell:

sumEuler = sum . (map euler) . mkList

Resposta curta

Código equivalente sem pontos, isso é apenas

sumEuler = \x -> sum ((map euler) (mkList x))

ou sem o lambda

sumEuler x = sum ((map euler) (mkList x))

porque o ponto (.) indica a composição da função.

Resposta mais longa

Primeiro, vamos simplificar a aplicação parcial de eulerpara map:

map_euler = map euler
sumEuler = sum . map_euler . mkList

Agora temos apenas os pontos. O que é indicado por esses pontos?

Da fonte :

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

Assim (.)é o operador de composição .

Compor

Em matemática, podemos escrever a composição das funções, f (x) e g (x), ou seja, f (g (x)), como

(f ∘ g) (x)

que pode ser lido como "f composto com g".

Assim, em Haskell, f ∘ g, ou f composto com g, pode ser escrito:

f . g

A composição é associativa, o que significa que f (g (h (x))), escrita com o operador de composição, pode deixar de fora os parênteses sem qualquer ambigüidade.

Ou seja, como (f ∘ g) ∘ h é equivalente af ∘ (g ∘ h), podemos simplesmente escrever f ∘ g ∘ h.

Circulando de volta

Voltando à nossa simplificação anterior, isto:

sumEuler = sum . map_euler . mkList

apenas significa que sumEuleré uma composição não aplicada dessas funções:

sumEuler = \x -> sum (map_euler (mkList x))
Aaron Hall
fonte
4

O operador ponto aplica a função à esquerda ( sum) à saída da função à direita. No seu caso, você está encadeando várias funções - está passando o resultado de mkListpara (map euler)e, em seguida, passando o resultado disso para sum. Este site tem uma boa introdução a vários dos conceitos.

Andy Mikula
fonte