Haskell non functions recursion (or value recursion or recursive let bindings)

Question

I'm new to Haskell and reading Haskell from first principles.

in chapter 10 page 378 I came across with this new syntax

fibs = 1 : scanl (+) 1 fibs

seems like fibs is a function bcs its being used or called on right

but its type is fibs :: Num a => [a] so its a value

how a value can be accessed inside it's own definition ?

if I do try to see what inside fibs, it just printout towards infinity.

and other example i = 1 + i which is perfectly valid syntax,

but when I run it in side ghci it also halt it.

• what kind of recursion it is if its not recursion what it is ?
• what is the execution flow ?
• how i can can accessed on right side when its not been assigned at all ?
• what is the value of i for first time on right ?
• what is the value of i on right ?

any articles that can help ?

Answer 1

In Haskell, let is what's known as letrec i.e. "recursive let" in other languages, meaning that both occurrences of a name in an equation refer to the same entity.

This makes sense as the equation is not an assignment, but a definition.^(*)

fibs = 1 : scanl (+) 1 fibs

Here on the right fibs refers to the same fibs as the one on the left. It is not being called, but rather it is being used. It is being used according to its definition. It is defined with a lazy data constructor, :.

The evaluation can be imagined to proceed by naming all the interim entities and writing down their definitions according to what we already have:

print $ take 4 fibs ==>
take 4 fibs =
= take 4 (let {fibs = 1 : scanl (+) 1 fibs} in fibs)
= take 4 (let {fibs = 1 : s1 ; s1 = scanl (+) 1 fibs} in fibs)
= take 4 (let {fibs = 1 : s1 ; s1 = scanl (+) 1 fibs} in (1 : s1))
= take 4 (1 : let {fibs = 1 : s1 ; s1 = scanl (+) 1 fibs} in s1)
= 1 : take 3 (let {fibs = 1 : s1 ; s1 = scanl (+) 1 fibs} in s1)
= 1 : take 3 (let {s1 = scanl (+) 1 (1 : s1)} in s1)
= 1 : take 3 (let {s1 = 1 : scanl (+) 2 s1} in s1)
= 1 : take 3 (let {s1 = 1 : s2; s2 = scanl (+) 2 s1} in (1 : s2))
= 1 : take 3 (1 : let {s1 = 1 : s2; s2 = scanl (+) 2 s1} in s2)
= 1 : 1 : take 2 (let {s1 = 1 : s2; s2 = scanl (+) 2 s1} in s2)
= 1 : 1 : take 2 (let {s2 = scanl (+) 2 (1 : s2)} in s2)
= 1 : 1 : take 2 (let {s2 = 2 : scanl (+) 3 s2} in s2)
= 1 : 1 : take 2 (let {s2 = 2 : s3; s3 = scanl (+) 3 s2} in (2 : s3))
= 1 : 1 : 2 : take 1 (let {s2 = 2 : s3; s3 = scanl (+) 3 s2} in s3)
= 1 : 1 : 2 : take 1 (let {s3 = scanl (+) 3 (2 : s3)} in s3)
= 1 : 1 : 2 : take 1 (let {s3 = 3 : scanl (+) 5 s3} in s3)
= 1 : 1 : 2 : take 1 (let {s3 = 3 : s4; s4 = scanl (+) 5 s3} in (3 : s4))
= 1 : 1 : 2 : 3 : take 0 (let {s3 = 3 : s4; s4 = scanl (+) 5 s3} in s4)
= 1 : 1 : 2 : 3 : [] 
= [1,1,2,3]

That's how it goes.^(**)

The i in let { i = i+1 } in i uses + which is strict, so any attempt to use the value of i loops, as + demands the values of both its arguments before ever returning its value, unlike the lazy : which actually demands none.

---

You've asked,

how a value can be accessed inside it's own definition ?

The above gives the answer, which is twofold. Firstly, because the (implied) let is recursive, both the names on the left and the right of the equal sign refer to the same entity. Secondly, since Haskell's evaluation is lazy, there are no assignments (and no "values" really in the usual sense) -- just definitions. A list is not a list, but a definition of a computational process to compute that list, etc.

---

_{(*) or in technical jargon, a lazy binding.}

_{(**) turns out it's a song, and a nice one too.}

Answer 2

In many (most?) languages functions are "special" values, which receive special status in the language syntax and semantics.

In Haskell, not so much. They share many properties with non-functions. In particular:

• We can pass functions (and non functions) as arguments to functions.
• We can return functions (and non functions) from functions.
• We can put functions (and non functions) into containers like lists, pairs, and so on.
• We can recursively define functions (and non functions).

The last point might be puzzling if you are not used to it, but there's no reason to allow recursion only when defining a function value in a lazy language like Haskell.

For instance one can define the infinite list 1:1:1:.... by letting list = 1 : list. If you can only understand recursive definitions for functions, just know that it is similar to list() = 1 : list(), except list is not a function, but a list.

You can also try to understand that 1:2:3:4:.... could be defined recursively as list = 1 : map (+1) list. Indeed, unfolding the definition we get:

list
= 1 : map (+1) list
= 1 : map (+1) (1 : map (+1) list)
= 1 : 2 : map (+1) (map (+1) list)
= 1 : 2 : map (+1) (map (+1) (1 : map (+1) list))
= 1 : 2 : 3 : map (+1) (map (+1) (map (+1) list))
...

Note that the above definition "works" because it can generate a part of the value before it recursively need its own value. In the i = i + 1 example you mention, this does not happen, since i + 1 needs the value of i immediately, before any part of the output can be produced. (Well, at least on the standard integer types.) Hence, it has the same behavior we would observe from an infinite recursive function such as i() = i() + 1.