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?

Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
  • 5
    There is a camp that holds that right-associativity is [just plain wrong](http://www.mail-archive.com/haskell-cafe@haskell.org/msg12549.html) – Don Stewart Dec 03 '13 at 05:12
  • 2
    See [the full thread](http://www.mail-archive.com/haskell-cafe@haskell.org/msg12528.html) – Don Stewart Dec 03 '13 at 05: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. – Aadit M Shah Dec 03 '13 at 05: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 03 '13 at 06:33
  • 2
    Unfortunately, since arguments are after functions, the data flows from right to left. – Sassa NF Dec 03 '13 at 08:13
  • @Carl Ah. I see it now. Your answer was very insightful. Thank you. =) – Aadit M Shah Dec 03 '13 at 13:54

1 Answers1

43

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.

Carl
  • 26,500
  • 4
  • 65
  • 86
  • 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. – Ben Millwood Dec 14 '13 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 '17 at 00:22
  • 6
    @max Evaluation of Haskell code proceeds by graph reduction. Reduction steps are runtime. – Carl Jan 22 '17 at 06: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 '17 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 '17 at 20:14
  • "Since function composition is associative, it should always be parsed the more efficient way when chained ambiguously. That's the end of that story." that's not a correct assessment. – codeshot Jul 15 '17 at 00:20
  • The other operator is the second in a family that begins with (.), they all work to provide a more effective communication if they're all infixl, but giving them different precedence doesn't solve the communication problem. This efficiency problem can be solved in a myriad of ways that computers are good at but the effective communication problem only has relatively few solutions. – codeshot Jul 15 '17 at 00:31
  • @codeshot It seems like you want to increase complexity of making the normal case efficient in order to avoid using some parenthesis in very rare cases. This is not a convincing argument. – Carl Jul 15 '17 at 00:43
  • I don't want to increase the complexity, however, if that is what it takes to keep the overall software development system simple (a much bigger thing that we must always think about) then the complexity must be shared in the most appropriate way because there is a minimum complexity at each scale and we must try to find a low complexity in all of them by moving it around when it is too far imbalanced. This is a case of such imbalance. What is the actual measured impact of infixr ? Each expression using two adjacent compositions has an extra couple of steps *once* per whole program execution? – codeshot Jul 15 '17 at 00:59