What does (f .) . g mean in Haskell?

I have seen a lot of functions being defined according to the pattern (f .) . g. For example:

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

What does this mean?

Solution 1:

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.

Solution 2:

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

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.)

What does (f .) . g mean in Haskell?

Solution 1:

Solution 2:

Related

Recent Posts