Haskell – priority of operations

March 16, 2023

I’m trying to be clear with the precedence rules in Haskell.
When I write the line of code "f a b" it will be interpreted (f a) b ie with a left-associative mechanism.

But let’s imagine that I am coding in Haskell a function calculating the terms of the fibonnaci sequence. I then run the following program:

fibo 0 = 1
fibo 1 = 1
fibo n = fibo(n-1) + fibo(n-2)

For the last expression, this will be interpreted as :

(((fibo(n-1))+)fibo)(n-2))

Why there is no error when it fetches the second fibo. How does the compiler know that fibo must apply to (n-2) before the result is given as an argument to the function (+)? Is it related to arithmetic operators?

I try many tests on ghci and the syntax

g = fibo 2 + fibo

is not accepted.

>Solution :

Haskell makes a strong distinction between infix operator and prefix / nonfix (is that a word?) functions or variables.

Anything containing only letters, underscores and/or non-leading numbers and beginning with either a lowercase letter or underscore is a variable. This includes simple function-arguments like n as well as normal prefix functions like length or print or cos. It is these functions for which the left-associative parsing rule applies.
Anything containing non-letter/number codepoints is an infix operator. These are parsed completely different, namely the always bind weaker than function application, they bind things on both sides of the operator, and they have their own precedence hierarchy.

For your example, the + operator is the only infix that’s not in parentheses, so the parsing starts by separating the subexpressions on each side of it.

fibo n = ░ + ░

Only then does it parse the prefix applications, like

fibo n =    ░    +     ░
        ┌───┴───┐  ┌───┴───┐
        fibo(n-2)  fibo(n-2)

Same thing of course with the inner expressions:

fibo n =     ░     +      ░
        ┌────┴────┐  ┌────┴────┐
        fibo(░ - ░)  fibo(░ - ░)
            ┌┴┐ ┌┴┐      ┌┴┐ ┌┴┐
             n   1        n   2