Why is there infinite recursion when I apply a function with the argument n-1 (no parentheses), inside the application of another function?

2
votes

Here I can pass to function f the argument 7-1, without parentheses.

Prelude> f = (+1)
Prelude> f 7-1
7

1. Why is the following an infinite recursion?

Prelude> addRec :: (Eq a, Num a) => a -> a; addRec 0 = 0; addRec n = n + addRec n-1;
Prelude> addRec 5

2. I can fix it by either adding parentheses to n-1

Prelude> addRec :: (Eq a, Num a) => a -> a; addRec 0 = 0; addRec n = n + addRec (n-1);

3. Or by using the $ operator with parentheses on the whole addRec recursion term:

Prelude> addRec :: (Eq a, Num a) => a -> a; addRec 0 = 0; addRec n = n + (addRec $ n-1)

I'd like to understand exactly how each expression works or doesn't work.

Here is my line of reasoning:

In addRec n = n (...) we are effectively composing two function (without using the . composition operator). We are composing (+) and addRec. Is Haskell in this example understanding we have a third function (-)?

We are using function application (which as far as I understand is the operator represented by a whitespace after a function) to achieve this composition.

Function application is left associative, so my first question is: what does addRec n = n + addRec n-1 look like when we add the parentheses corresponding to the default left associativity?

1
haskell
Function application takes priority over all other operators. addRec n-1 is parsed as (addRec n) - 1. You can only fix that with explicit parentheses, or the $ operator. - Robin Zigmond
I disagree with the close votes. This is not a typographical error, but a (very common) misunderstanding of Haskell's operator precedence rules. - amalloy
It may not be a typographical error, but I don't believe it needs yet another answer that explains basic precedence rules. I thought there was a discussion in meta that indicated trivial questions that can be addressed by a simple comment could be included under "no longer reproduced". - chepner
@chepner I disagree that this is a "trivial" question, since if it was there would likely be a duplicate. Besides, what may be trivial to one person is not necessarily trivial to another. And I also disagree with justifying closing a question with an incorrect reason based on some discussion on meta. If SO want to formally introduce a justification for closing a question because it is trivial that's fine, but until then downvoting a question (as "not useful") is more appropriate than voting to close for a bogus reason. - skomisa
I think it's so basic that there is not a single duplicate, but there are various questions which boil down to the same fundamental problem: not understanding precedence. There probably should be a single, canonical question dealing with this, but I'm not sure how best to frame it. - chepner

1 Answers

12
votes

f 7-1 doesn't mean what you think it means.

In Haskell, function application has the highest priority. This means that f 7-1 is always interpreted as (f 7) - 1. The absence of a space around the minus sign is irrelevant, and it is only by coincidence that you get the correct answer: f 7 = (+ 1) 7 = 8, and then 8 - 1 = 7. This would not happen if your function was defined as f = (* 2).

Similarly, addRec n-1 is interpreted as (addRec n) - 1, thus calling addRec with the same argument n every time, producing infinite recursion.

The two ways to fix it, you already know: parens or operator $.