Ok basically I have a problem knowing whether option 1 or 2 applies in the following case:
naturals = 0 : map (+ 1) naturals
Where options are:
1. The execution is awful, everything is recomputed at each step:
naturals = [0]
naturals' = 0:map (+ 1) [0] // == [0, 1]
naturals'' = 0:map (+ 1) [0, 1] // == [0, 1, 2]
naturals''' = 0:map (+ 1) [0, 1, 2] // == [0, 1, 2, 3]
naturals'''' = 0:map (+ 1) [0, 1, 2, 3] // == [0, 1, 2, 3, 4]
2. The execution is not awful, the list is always infinite and map
is applied once only
naturals = 0:something
|
naturals' = 0: map (+ 1) (0: something)
|
naturals'' = 0:1: map (+ 1) (0:1: something')
|
naturals''' = 0:1:2: map (+ 1) (0:1:2: something'')
|
naturals'''' = 0:1:2:3:map (+ 1) (0:1:2:3:something''')
with |
indicating where map
is at in its execution.
I do know that answers may be only 1 or 2 but I'd appreciate some pointers to good explanations on co-recursion too to clear the last doubts :)
Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function. The C programming language supports recursion, i.e., a function to call itself.
Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. For example, we can define the operation "find your way home" as: If you are at home, stop moving. Take one step toward home.
The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of natural number.
Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This is similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item.
Execution isn't going to be, as you put it, "awful". :) Lazy evaluation is your best friend here. What does laziness mean?
"Things", here, are "not-yet-evaluated expressions", also known as "thunks".
Here is what happens:
You define
naturals = 0 : map (+1) naturals
Merely defining naturals
doesn't introduce a need to evaluate it, so initially naturals
will just point to a thunk for the unevaluated expression 0 : map (+1) naturals
:
naturals = <thunk0>
At some point, your program may pattern match on naturals. (Pattern matching is essentially the only thing that forces evaluation in a Haskell program.) That is, your program needs to know whether naturals is the empty list or a head element followed by a tail list. This is where the right-hand side of your definition will be evaluated, but only as far as needed to find out whether naturals
is constructed by []
or (:)
:
naturals = 0 : <thunk1>
That is naturals will now point to an application of the constructor (:)
on the head element 0
and a thunk for the still-unevaluated tail. (Actually, the head element will also be still-unevaluated, so really naturals
will point to something of the form <thunk> : <thunk>
, but I will be leaving that detail out.)
It is not until some later point in your program where you may pattern match on the tail that the thunk for the tail gets "forced", i.e., evaluated. This means that the expression map (+1) naturals
is to be evaluated. Evaluating this expression reduces to map
pattern matching on naturals
: it needs to know whether naturals
is constructed by []
or (:)
.
We saw that, at this point, rather than pointing to a thunk, naturals
is already pointing to an application of (:)
, so this pattern match by map
requires no further evaluation. The application of map
does immediately see enough of naturals
to figure out that it needs to produce an application of (:)
itself and so it does: map
produces 1 : <thunk2>
where the thunk contains an unevaluated expression of the form map (+1) <?>
. (Again, instead of 1
, we actually have a thunk for 0 + 1
.) What is <?>
pointing to? Well, the tail of naturals
, which happens to be what map
was producing. Hence, we now have
naturals = 0 : 1 : <thunk2>
with <thunk2>
containing the yet-unevaluated expression map (+1) (1 : <thunk2>)
.
At yet a later point in your program, pattern matching may force <thunk2>
, so that we get
naturals = 0 : 1 : 2 : <thunk3>
with <thunk3>
containing the yet-unevaluated expression map (+1) (2 : <thunk3>)
. And so forth.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With