Operador de puntos en Haskell: necesita más explicación

86

Estoy tratando de entender qué está haciendo el operador de puntos en este código de Haskell:

sumEuler = sum . (map euler) . mkList

El código fuente completo está a continuación.

Mi punto de vista

El operador de punto toma las dos funciones sumy el resultado de map eulery el resultado de mkListcomo entrada.

Pero, sum¿no es una función, es el argumento de la función, verdad? Entonces, ¿qué está pasando aquí?

Además, ¿qué está (map euler)haciendo?

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
fuente

Respuestas:

138

En pocas palabras, .es la composición de funciones, como en matemáticas:

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

En su caso, está creando una nueva función, sumEulerque también podría definirse así:

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

El estilo en su ejemplo se llama estilo "sin puntos": se omiten los argumentos de la función. Esto hace que el código sea más claro en muchos casos. (Puede ser difícil asimilarlo la primera vez que lo ve, pero se acostumbrará después de un tiempo. Es un modismo común de Haskell).

Si todavía está confundido, puede ser útil relacionarse .con algo como una tubería UNIX. Si fla salida de g'se convierte en la entrada de', cuya salida se convierte hen la entrada de ', escribirías eso en la línea de comandos como f < x | g | h. En Haskell, .funciona como UNIX |, pero "al revés" - h . g . f $ x. Encuentro que esta notación es muy útil cuando, digamos, procesando una lista. En lugar de una construcción difícil de manejar map (\x -> x * 2 + 10) [1..10], simplemente podría escribir (+10) . (*2) <$> [1..10]. (Y, si solo desea aplicar esa función a un solo valor, es (+10) . (*2) $ 10. ¡Consistente!)

La wiki de Haskell tiene un buen artículo con más detalles: http://www.haskell.org/haskellwiki/Pointfree

jrockway
fuente
1
Pequeña objeción: el primer fragmento de código no es realmente válido para Haskell.
SwiftsNamesake
2
@SwiftsNamesake Para aquellos de nosotros que no dominamos Haskell, ¿quiere decir simplemente que el signo igual único no es significativo aquí? (¿Entonces el fragmento debería tener el formato " f (g x)= (f . g) x"?) ¿O algo más?
user234461
1
@ user234461 Exactamente, sí. En su ==lugar, necesitaría si quisiera Haskell estándar válido.
SwiftsNamesake
Ese pequeño fragmento de arriba es solo oro. Como las otras respuestas aquí son correctas, pero ese fragmento simplemente hizo clic directamente de forma intuitiva en mi cabeza, lo que hizo que no fuera necesario leer el resto de su respuesta.
Tarick Welling
24

Los . operador compone funciones. Por ejemplo,

a . b

Donde un y b son funciones es una nueva función que se ejecuta b en sus argumentos, entonces A en esos resultados. Tu codigo

sumEuler = sum . (map euler) . mkList

es exactamente lo mismo que:

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

pero espero que sea más fácil de leer. La razón por la que hay parens alrededor de map euler es porque deja más claro que se componen 3 funciones: sum , map euler y mkList - map euler es una sola función.

Jesse Rusak
fuente
23

sumes una función en Haskell Prelude, no un argumento para sumEuler. Tiene el tipo

Num a => [a] -> a

El operador de composición de funciones . tiene tipo

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

Entonces tenemos

           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

Tenga en cuenta que, de Inthecho, es una instancia de la Numclase de tipos.

Chris Conway
fuente
11

Los . El operador se utiliza para la composición de funciones. Al igual que con las matemáticas, si tiene que utilizar las funciones f (x) y g (x) f. g se convierte en f (g (x)).

map es una función incorporada que aplica una función a una lista. Al poner la función entre paréntesis, la función se trata como un argumento. Un término para esto es curry . Deberías buscar eso.

Lo que hace es que toma una función con dos argumentos, aplica el argumento euler. (mapa euler) ¿verdad? y el resultado es una nueva función, que solo toma un argumento.

suma. (mapa euler). mkList es básicamente una forma elegante de juntar todo eso. Debo decir que mi Haskell está un poco oxidado, pero ¿tal vez puedas armar esa última función tú mismo?

John Leidegren
fuente
5

Operador punto en Haskell

Estoy tratando de entender qué está haciendo el operador de puntos en este código de Haskell:

sumEuler = sum . (map euler) . mkList

Respuesta corta

Código equivalente sin puntos, eso es solo

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

o sin la lambda

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

porque el punto (.) indica la composición de la función.

Respuesta más larga

Primero, simplifiquemos la aplicación parcial de eulera map:

map_euler = map euler
sumEuler = sum . map_euler . mkList

Ahora solo tenemos los puntos. ¿Qué indican estos puntos?

De la fuente :

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

Así (.)es el operador de composición .

Componer

En matemáticas, podríamos escribir la composición de funciones, f (x) y g (x), es decir, f (g (x)), como

(f ∘ g) (x)

que puede leerse "f compuesta con g".

Entonces en Haskell, f ∘ g, o f compuesta con g, se puede escribir:

f . g

La composición es asociativa, lo que significa que f (g (h (x))), escrito con el operador de composición, puede omitir los paréntesis sin ambigüedad.

Es decir, dado que (f ∘ g) ∘ h es equivalente af ∘ (g ∘ h), simplemente podemos escribir f ∘ g ∘ h.

Dando vueltas hacia atrás

Volviendo a nuestra simplificación anterior, esto:

sumEuler = sum . map_euler . mkList

solo significa que sumEuleres una composición no aplicada de esas funciones:

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

El operador de punto aplica la función de la izquierda ( sum) a la salida de la función de la derecha. En su caso, está encadenando varias funciones juntas: está pasando el resultado de mkLista (map euler)y luego pasando el resultado de eso a sum. Este sitio tiene una buena introducción a varios de los conceptos.

Andy Mikula
fuente