Why is function composition in Haskell right associative?

Question

Mathematically the function composition operation is associative. Hence:

f . (g . h) = (f . g) . h 

Thus the function composition operation may be defined to be either left associative or right associative.

Since normal function application in Haskell (i.e. the juxtaposition of terms, not the $ operation) is left associative in my opinion function composition should also be left associative. After all most people in the world (including myself) are used to reading from left to right.

Nevertheless function composition in Haskell is right associative:

infixr 9 . 

I know that it doesn't really make a difference whether the function composition operation is left associative or right associative. Nevertheless I'm curious to know why is it not left associative. Two reasons come to my mind for this design decision:

1. The makers of Haskell wanted function composition to be logically as similar as the $ operation.
2. One of the makers of Haskell was a Japanese who found it more intuitive to make function composition right associative instead of left associative.

Jokes aside, is there any beneficial reason for function composition to be right associative in Haskell? Would it make any difference if function composition in Haskell was left associative?

Answer 1

In the presence of non-strict evaluation, right-associativity is useful. Let's look at a very dumb example:

foo :: Int -> Int foo = const 5 . (+3) . (`div` 10) 

Ok, what happens when this function is evaluated at 0 when . is infixr?

foo 0 => (const 5 . ((+3) . (`div` 10))) 0 => (\x -> const 5 (((+3) . (`div` 10)) x)) 0 => const 5 (((+3) . (`div` 10)) 0) => 5 

Now, what if . was infixl?

foo 0 => ((const 5 . (+3)) . (`div` 10)) 0 => (\x -> (const 5 . (+3)) (x `div` 10)) 0 => (const 5 . (+3)) (0 `div` 10) => (\x -> const 5 (x + 3)) (0 `div` 10) => const 5 ((0 `div` 10) + 3) => 5 

(I'm sort of tired. If I made any mistakes in these reduction steps, please let me know, or just fix them up..)

They have the same result, yes. But the number of reduction steps is not the same. When . is left-associative, the composition operation may need to be reduced more times - in particular, if a function earlier in the chain decides to shortcut such that it doesn't need the result of the nested computation. The worst cases are the same, but in the best case, right-associativity can be a win. So go with the choice that is sometimes better, instead of the choice that is sometimes worse.