What is the evaluaton order in simple List creation?

Question

How is 1:(2:(3:[])) evaluated?

What rewriting steps are taken until we arrive to [1,2,3] ?

Is it

   1:(2:([3])
   1:([2,3])
   [1,2,3]

or something else? Is the above described way the only way? Or is there an other way?

Answer 1

There isn't anything for Haskell to actually evaluate here, since : is the constructor for lists. When you write something like [1, 2, 3], the compiler first de-sugars this to the form 1 : 2 : 3 : [], and this is its representation in memory. It'd be like asking what the evaluation order is for Just 1. There isn't an evaluation order, because it's already in its "most evaluated" form, also known as normal form.

For lists, normal form is elements consed together in front of an empty list. If it helps, you can think of lists defined as

data [a] = [] | a : [a]

Or alternatively

data List a = Empty | Cons a (List a)

When you do pattern matching like

f (x:xs) = ...

This is equivalent to doing pattern matching like

f (Cons x xs) = ...

The only real difference is the names used.

---

So I guess the answer to your question is that you have the evaluation backwards, you don't go from 1:2:3:[] to [1, 2, 3], you go from [1, 2, 3] to 1:2:3:[], although this step occurs during de-sugaring. As for list comprehensions, these get de-sugared into maps and filters using monadic functions like >> and >>=. When you see something like [1..10], this actually uses the Enum instance for its elements and gets de-sugared to fromEnumTo and similar functions. All of these functions work with lists on the level of : and [], so they're just working with the list type's constructors just as it would with any other data type.

---

As proof, if I had the code

module Foo where

x :: [Int]
x = [1, 2, 3]

And I compiled it with ghc -c Foo.hs -ddump-ds, I'd get

Foo.x :: [GHC.Types.Int]
[LclIdX]
Foo.x =
  GHC.Types.:
    @ GHC.Types.Int
    (GHC.Types.I# 1)
    (GHC.Types.:
       @ GHC.Types.Int
       (GHC.Types.I# 2)
       (GHC.Types.:
          @ GHC.Types.Int (GHC.Types.I# 3) (GHC.Types.[] @ GHC.Types.Int)))

Which is has quite a lot of extra meta-data in there, so let's remove all the extra type annotations, module names, and other noise:

Foo.x :: [Int]
Foo.x = GHC.Types.: 1 (GHC.Types.: 2 (GHC.Types.: 3 []))

Or even more removed

x :: [Int]
x = : 1 (: 2 (: 3 []))

Note that in core (what GHC compiles Haskell source to, one of the 3 intermediate language used), we don't need parens around operators in prefix form. But it's pretty easy to see that once everything is de-sugared it's simply represented as a list consed together.

But wait! I thought you said that the parens weren't needed? That was true when it was in infix form, but now the : is being applied as a prefix function. It's pretty easy to see that with prefix, the parens are needed, especially if you replace : with Cons and [] with Empty:

x = Cons 1 (Cons 2 (Cons 3 Empty))

Since the following wouldn't type-check. It makes it look like Cons takes 6 arguments!

x = Cons 1 Cons 2 Cons 3 Empty