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

Question

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?

Tensible

(f .) . g might also be part of a nicely disguised opinion on the original author's code. – Adrenaline

I am not really sure what that means. – Tensible

It means that the author was being to clever and ended up writing unreadable code. ;) – Dunagan

((f .) . g) x y = f (g x y) – Urus

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

Tensible

Expression of the form (.) ^ i are not well-typed, so they aren't actually valid Haskell. – Pimentel

True. However I did write "Similarly for functions in Mathematics:" and since this is a mathematical explanation I think it's alright to use ^ for functions instead of numbers. Nevertheless I'll change the operator to .^ to distinguish between the two. – Tensible

I'd be surprised to see (.) ^ i in mathematics too. Perhaps a formal framework for such a thing exists in dependent type theory. It would be interesting. – Pimentel

+1 -- Nice and clear answer. However I completely disagree that point-free is more readable or better in any way. countWhere f xs = length (filter f xs) is much more readable than all the other versions because it's immediately clear 1) how many arguments the function has and 2) what kind of parameters it accepts (via "smart" names) 3) Almost any programmer could read that and have some intuition of what's happening in a matter of seconds. Figuring out the point-free versions take much more time, especially when the expressions get more complex than a simple composition. – Tarmac

@Tarmac I never mentioned that the pointfree style is more readable or better in any way. The only time I mentioned the word "readable" was in conjunction with the tac example. I agree, people can get carried away by pointfree programming. The mf function written in pointfree style is paradigmatic of that. Nevertheless the pointfree style of programming is interesting to study from a mathematical point of view because it makes the structure of the program more mathematically tractable. It can make your code shorter but only in limited capacity. – Tensible

After 5 years of Haskell I've finally groked pointfree due to reading this answer. – Montenegro

I think this style can find its niche in working with zipWith family zipWith ((abs .) . (-)) [1, 3] [2, 7] – Ease

Answer 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

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

Pimentel

You can also define (.:) as (.:) = fmap fmap fmap. It's more generic because you can use it for any functor. For example you could do (* 2) .: Just [1..5]. Of course you would need to give it the correct type signature of (.:) :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b). – Tensible

@AaditMShah In that case, I would prefer something like <$$> = fmap . fmap, since (.:) is by convention specialised to (->) r, and the "outer" fmap is on the (->) r functor anyway. – Corenda