Hugs, functions and how it calculate

Question

I have an input:

 [ 8 `div` 2 + 1 .. ] !! 2 : [ 1 .. 3 ]

the Output is:

 [7,1,2,3]

But.. what does Haskell calculate first?

I don't know the priority, where's the 7 from?

Answer 1

Your question sort of contains two questions, so I'll do my best to briefly answer both.

1. Order of operations in Haskell

Given an expression such as 2 + 4 * 3, will Haskell calculate 2+4 first and then multiply it by three, or will it calculate 4*3 before that and then add two? As you might have guessed, 4*3 goes first.

How do you know which comes first? You look in the documentation and/or source code for the operator in question. Or you can figure it out experimentally. In your example of

[ 8 `div` 2 + 1 .. ] !! 2 : [ 1 .. 3 ]

I know just from experience that if you were to put parentheses everywhere, they would look like this:

([ ((8 `div` 2) + 1) .. ] !! 2) : [ 1 .. 3 ]

Finding out precedence

In order to figure this out properly though, you need to open up ghci, and type

:info (+)

for example, and it will say something along the lines of

infixl 6 (+)

If we do this for the other operators as well, we can build us a neat table.

infixl 7 `div`
infixl 6 +
infixr 5 :
infixl 9 !!

ghci didn't say anything for (!!), But I went to the source code for list operations in the Prelude and found the line that said exactly what I showed in the table. Then you can assume that lists work a little like parentheses, so things inside the [] square brackets go before the things outside of them.

How precedence works

Now, the number before the operator name in the infix declarations says how high precedence the operator has – the higher the number, the more it goes before other things. In this case, for example, we had

infixl 7 `div`
infixl 6 +

This means that `div` goes before +, and indeed, in the expression

8 `div` 2 + 1

we find that Haskell calculates the result as

(8 `div` 2) + 1

because `div` had a higher precedence. If you do this for the rest of the expression, you will end up with the same parentheses as I did in the beginning of this answer.

You usually don't have to care very much though, because the more Haskell you write, the more are you going to get a feeling for how it all works out. And most often, if you get it wrong, you will also get a type error to remind you that you got it wrong. When in doubt, try both with parentheses and without in ghci and see which one gives the right answer.

2. Order of calculation in Haskell

Up to this point I have answered the question "how is an expression interpreted by Haskell?" The order in which it is actually calculated is a whole different question. Most programming languages calculate the inner parentheses first – Haskell does quite the opposite!

Given the expression

([ ((8 `div` 2) + 1) .. ] !! 2) : [ 1 .. 3 ]

Haskell will at the start just see it as

<something>

then when you ask for the value, it will groan a little and realise it's saying

<something> : <something>

It will realise it needs to calculate further to give you a value, so it will expand it into

(<something> !! <something>) : [ 1 .. 3 ]

(By the way, these <something>s are usually called thunks by Haskell people.) Then it will have to go even deeper, turning it into

([ <something> .. ] !! 2) : [ 1 .. 3 ]

Then it needs the second element of this list, so it will expand as much of the list as it has to.

([ <something>
 , (<something> + 1)
 , (<something> + 2) .. ] !! 2) : [ 1 .. 3 ]

Then it can reduce the !!, giving back the third element of the list (which has index 2), so the whole list disappears and is replaced by the third element.

(<something> + 2) : [ 1 .. 3 ]

and then it can reduce the :, so the result is a single list.

[ <something + 2>, 1, 2, 3 ]

At this point, it finally has to figure out what that <something> is, so it goes back to the definition of it and expands it into

[ (<something> + 1) + 2, 1, 2, 3 ]

and then

[ ((8 `div` 2) + 1) + 2, 1, 2, 3 ]

and then it starts calculating the actual value of the first element, giving you

[ (4 + 1) + 2, 1, 2, 3 ]
[ 5 + 2, 1, 2, 3 ]
[ 7, 1, 2, 3 ]

The thing to take away from this is that Haskell tries to not calculate any value unless it absolutely has to. It tries to, as far as possible, only work with descriptions of values, and not any actual values. It's in the very end that it performs all the calculations necessary.

If you didn't ask for the first value of the list, it would never have gotten calculated.

This is what's meant by "lazy evaluation."

Answer 2

8 `div` 2 ≡ 4, so [ 8 `div` 2 + 1 .. ] means [ 5 .. ]. This is an infinite list [5,6,7,8 ..].

list !! n – take n-th element (from 0) from the list, so [5 .. ] !! 2 ≡ 7.

Answer 3

[ 8 `div` 2 + 1 .. ] !! 2 : [ 1 .. 3 ]
[ 4 + 1 .. ] !! 2 : [ 1 .. 3 ]
[ 5 .. ] !! 2 : [ 1 .. 3 ]
7 : [ 1 .. 3 ]
[7,1,2,3]

Function application is from left to right.