What does (f .) . g mean in Haskell?
This is a matter of taste, but I find such style to be unpleasant. First I'll describe what it means, and then I suggest an alternative that I prefer.
You need to know that (f . g) x = f (g x)
and (f ?) x = f ? x
for any operator ?
. From this we can deduce that
countWhere p = ((length .) . filter) p
= (length .) (filter p)
= length . filter p
so
countWhere p xs = length (filter p xs)
I prefer to use a function called .:
(.:) :: (r -> z) -> (a -> b -> r) -> a -> b -> z
(f .: g) x y = f (g x y)
Then countWhere = length .: filter
. Personally I find this a lot clearer.
(.:
is defined in Data.Composition
and probably other places too.)
The dot operator (i.e. (.)
) is the function composition operator. It is defined as follows:
infixr 9 .
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
As you can see it takes a function of type b -> c
and another function of type a -> b
and returns a function of type a -> c
(i.e. which applies the first function to the result of the second function).
The function composition operator is very useful. It allows you to pipe the output of one function into the input of another function. For example you could write a tac program in Haskell as follows:
main = interact (\x -> unlines (reverse (lines x)))
Not very readable. Using function composition however you could write it as follows:
main = interact (unlines . reverse . lines)
As you can see function composition is very useful but you can't use it everywhere. For example you can't pipe the output of filter
into length
using function composition:
countWhere = length . filter -- this is not allowed
The reason this is not allowed is because filter
is of type (a -> Bool) -> [a] -> [a]
. Comparing it with a -> b
we find that a
is of type (a -> Bool)
and b
is of type [a] -> [a]
. This results in a type mismatch because Haskell expects length
to be of type b -> c
(i.e. ([a] -> [a]) -> c
). However it's actually of type [a] -> Int
.
The solution is pretty simple:
countWhere f = length . filter f
However some people don't like that extra dangling f
. They prefer to write countWhere
in pointfree style as follows:
countWhere = (length .) . filter
How do they get this? Consider:
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
As you can see (f .) . g
is simply \x y -> f (g x y)
. This concept can actually be iterated:
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)
It's not pretty but it gets the job done. Given two functions you can also write your own function composition operators:
f .: g = (f .) . g
f .:: g = ((f .) .) . g
f .::: g = (((f .) .) .) . g
Using the (.:)
operator you could write countWhere
as follows instead:
countWhere = length .: filter
Interestingly though you could write (.:)
in point free style as well:
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:
(.:) = (.) . (.)
Similarly we get:
(.::) = (.) . (.) . (.)
(.:::) = (.) . (.) . (.) . (.)
As you can see (.:)
, (.::)
and (.:::)
are just powers of (.)
(i.e. they are iterated functions of (.)
). For numbers in Mathematics:
x ^ 0 = 1
x ^ n = x * x ^ (n - 1)
Similarly for functions in Mathematics:
f .^ 0 = id
f .^ n = f . (f .^ (n - 1))
If f
is (.)
then:
(.) .^ 1 = (.)
(.) .^ 2 = (.:)
(.) .^ 3 = (.::)
(.) .^ 4 = (.:::)
That brings us close to the end of this article. For a final challenge let's write the following function in pointfree style:
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
We can further simplify this as follows:
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 (.))
Using compose
you can now write mf
as:
mf = compose map filter
Yes it is a bit ugly but it's also a really awesome mind-boggling concept. You can now write any function of the form \x y z -> f x (g y z)
as compose f g
and that is very neat.