CODEWITHSUNDEEP
haskell
xoux
xoux

Reputation: 3494

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

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?

Upvotes: 2

Views: 132

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80805

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

Upvotes: 11

Related Questions