Que signifie (f .) . g en Haskell ?

Question

J'ai vu beaucoup de fonctions être définies selon le modèle (f .) . g . Par exemple :

countWhere = (length .) . filter
duplicate  = (concat .) . replicate
concatMap  = (concat .) . map

Qu'est-ce que cela signifie ?

Answer 1

L'opérateur point (c'est-à-dire (.) ) est le composition des fonctions opérateur. Il est défini comme suit :

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

Comme vous pouvez le voir, il prend une fonction de type b -> c et une autre fonction de type a -> b et renvoie une fonction de type a -> c (c'est-à-dire qui applique la première fonction au résultat de la deuxième fonction).

L'opérateur de composition de fonctions est très utile. Il vous permet de faire passer la sortie d'une fonction dans l'entrée d'une autre fonction. Par exemple, vous pouvez écrire une fonction tac en Haskell comme suit :

main = interact (\x -> unlines (reverse (lines x)))

Pas très lisible. En utilisant la composition des fonctions, vous pourriez toutefois l'écrire comme suit :

main = interact (unlines . reverse . lines)

Comme vous pouvez le constater, la composition des fonctions est très utile, mais vous ne pouvez pas l'utiliser partout. Par exemple, vous ne pouvez pas faire passer la sortie de la fonction filter en length en utilisant la composition des fonctions :

countWhere = length . filter -- this is not allowed

La raison pour laquelle cela n'est pas autorisé est que filter est de type (a -> Bool) -> [a] -> [a] . En le comparant avec a -> b nous constatons que a est de type (a -> Bool) y b est de type [a] -> [a] . Cela entraîne une incompatibilité de type car Haskell s'attend à ce que length pour être de type b -> c (c'est-à-dire ([a] -> [a]) -> c ). Cependant, il s'agit en fait d'un type [a] -> Int .

La solution est assez simple :

countWhere f = length . filter f

Cependant, certaines personnes n'aiment pas cet élément supplémentaire. f . Ils préfèrent écrire countWhere sur sans point de contact comme suit :

countWhere = (length .) . filter

Comment l'obtiennent-ils ? Réfléchissez :

countWhere f xs = length (filter f xs)

-- But `f x y` is `(f x) y`. Hence:

countWhere f xs = length ((filter f) xs)

-- But `\x -> f (g x)` is `f . g`. Hence:

countWhere f = length . (filter f)

-- But `f . g` is `(f .) g`. Hence:

countWhere f = (length .) (filter f)

-- But `\x -> f (g x)` is `f . g`. Hence:

countWhere = (length .) . filter

Comme vous pouvez le constater (f .) . g est simplement \x y -> f (g x y) . Ce concept peut en fait être itéré :

f . g             --> \x -> f (g x)
(f .) . g         --> \x y -> f (g x y)
((f .) .) . g     --> \x y z -> f (g x y z)
(((f .) .) .) . g --> \w x y z -> f (g w x y z)

Ce n'est pas très joli, mais ça fait l'affaire. Étant donné deux fonctions, vous pouvez également écrire vos propres opérateurs de composition de fonctions :

f .: g = (f .) . g
f .:: g = ((f .) .) . g
f .::: g = (((f .) .) .) . g

Utilisation de la (.:) opérateur, vous pourriez écrire countWhere comme suit :

countWhere = length .: filter

Il est intéressant de noter que vous pourriez écrire (.:) dans le style libre de points également :

f .: g = (f .) . g

-- But `f . g` is `(.) f g`. Hence:

f .: g = (.) (f .) g

-- But `\x -> f x` is `f`. Hence:

(f .:) = (.) (f .)

-- But `(f .)` is `((.) f)`. Hence:

(f .:) = (.) ((.) f)

-- But `\x -> f (g x)` is `f . g`. Hence:

(.:) = (.) . (.)

De même, nous obtenons :

(.::)  = (.) . (.) . (.)
(.:::) = (.) . (.) . (.) . (.)

Comme vous pouvez le constater (.:) , (.::) y (.:::) sont juste des puissances de (.) (c'est-à-dire qu'ils sont fonctions itérées de (.) ). Pour les nombres en mathématiques :

x ^ 0 = 1
x ^ n = x * x ^ (n - 1)

De même pour les fonctions en mathématiques :

f .^ 0 = id
f .^ n = f . (f .^ (n - 1))

Si f es (.) alors :

(.) .^ 1 = (.)
(.) .^ 2 = (.:)
(.) .^ 3 = (.::)
(.) .^ 4 = (.:::)

Cela nous amène à la fin de cet article. Pour un dernier défi, écrivons la fonction suivante dans le style pointfree :

mf a b c = filter a (map b c)

mf a b c = filter a ((map b) c)

mf a b = filter a . (map b)

mf a b = (filter a .) (map b)

mf a = (filter a .) . map

mf a = (. map) (filter a .)

mf a = (. map) ((filter a) .)

mf a = (. map) ((.) (filter a))

mf a = ((. map) . (.)) (filter a)

mf = ((. map) . (.)) . filter

mf = (. map) . (.) . filter

Nous pouvons encore simplifier cela comme suit :

compose f g = (. f) . (.) . g

compose f g = ((. f) . (.)) . g

compose f g = (.) ((. f) . (.)) g

compose f = (.) ((. f) . (.))

compose f = (.) ((. (.)) (. f))

compose f = ((.) . (. (.))) (. f)

compose f = ((.) . (. (.))) (flip (.) f)

compose f = ((.) . (. (.))) ((flip (.)) f)

compose = ((.) . (. (.))) . (flip (.))

Utilisation de compose vous pouvez maintenant écrire mf comme :

mf = compose map filter

Oui, c'est un peu laid, mais c'est aussi un concept vraiment génial et époustouflant. Vous pouvez maintenant écrire n'importe quelle fonction de la forme \x y z -> f x (g y z) como compose f g et c'est très soigné.

Answer 2

C'est une question de goût, mais je trouve ce style désagréable. Je vais d'abord décrire ce qu'il signifie, puis je proposerai une alternative que je préfère.

Vous devez savoir que (f . g) x = f (g x) y (f ?) x = f ? x pour tout opérateur ? . On peut en déduire que

countWhere p = ((length .) . filter) p
              = (length .) (filter p)
              = length . filter p

donc

countWhere p xs = length (filter p xs)

Je préfère utiliser une fonction appelée .:

(.:) :: (r -> z) -> (a -> b -> r) -> a -> b -> z
(f .: g) x y = f (g x y)

Entonces countWhere = length .: filter . Personnellement, je trouve cela beaucoup plus clair.

( .: est défini dans Data.Composition et probablement d'autres endroits aussi).