34

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?

6
  • 5
    There is a camp that holds that right-associativity is just plain wrong Dec 3, 2013 at 5:12
  • 2
    See the full thread Dec 3, 2013 at 5:13
  • Interesting read. I agree, there's no reason the $ operation should be right associative either. However right associativity is not always wrong. For example the ++ operation and the logical operations && and || must clearly be right associative so that concatenation cost is minimal and so that logical expressions may be short circuited, respectively. Dec 3, 2013 at 5:21
  • 4
    Well, $ isn't associative. It has different semantics if you change it to an infixl definition. And those different semantics would probably be better. But since . is associative, the semantics are the same either way - all that changes is operational details, where infixr is definitely better.
    – Carl
    Dec 3, 2013 at 6:33
  • 2
    Unfortunately, since arguments are after functions, the data flows from right to left.
    – Sassa NF
    Dec 3, 2013 at 8:13

1 Answer 1

42

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.

9
  • 8
    Essentially, you're going to hand off control to the leftmost function in the chain, and you want to do that as soon as possible, so you bunch the rest of them together. Dec 14, 2013 at 17:31
  • Do I understand correctly that only the number of reduction steps is different; the number of evaluation steps is the same in both cases? In other words, the run-time (after the code is compiled) would be the same for infixr and infixl, but compilation is faster for infixr?
    – max
    Jan 22, 2017 at 0:22
  • 6
    @max Evaluation of Haskell code proceeds by graph reduction. Reduction steps are runtime.
    – Carl
    Jan 22, 2017 at 6:28
  • Is this the reason that the choice was made? I wonder because (.) is impractical when also trying to use its two-argument counterpart (...) or (.:) where each of those = (.) . (.) -- (f . g ... h) a b c should be equal to f (g (h a b)) c - but with infixr (.) it can't be expressed like that at all ! fixity should be decided by how you want to express things rather than by the number of reduction steps.
    – codeshot
    Jun 19, 2017 at 19:30
  • @codeshot function composition is associative. The example you raise is a problem because some other non-associative operator shares precedence with it. That is not a problem with the fixity of (.). Since function composition is associative, it should always be parsed the more efficient way when chained ambiguously. That's the end of that story. Now if you wanted to say it should have a precedence other than 9, you could probably make a decent argument there.
    – Carl
    Jun 29, 2017 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.