How does (co)recursive definition work in Haskell?

Question

I'm playing around with the language to start learning and I am puzzled beyond my wits about how a recursive definition works.

For example, let's take the sequence of the Triangular numbers (TN n = sum [1..n])

The solution provided was:

triangularNumbers = scanl1 (+) [1..]

So far, so good.

But the solution I did come up with was:

triangularNumbers = zipWith (+) [1..] $ 0 : triangularNumbers

Which is also correct.

Now my question is: how does this translate to a lower level implementation? What happens exactly behind the scene when such a recursive definition is met?

Schizoid

It's probably been asked and answered before, but searching for "recursive definition" brings up only questions related to recursion in the algorithmic sense – Schizoid

this might help. – Citizenship

Start with understanding [1..]. – Anorthic

@EugeneSh. I think I understand lazy infinite structures, but I still don't see how the self-recursive definition would help, as there is no 0 point? – Schizoid

@DiegoMartinoia Can you define yourself something similar to [1..] (well it won't look that nicely, but you can call it "naturals") ? It is using (or might use) self recursion as well and a little simpler than triangular numbers. Or even an infinite list of ones will do. Of course without using any predefined infinite lists. – Anorthic

@EugeneSh. Coming from Java, I can see how to implement such an infinite iterator rather easy. But with an iterator you do have an internal state (i.e. the last number you +1 to). I'm curious as to a) how this internal state is actually mapped in low level after haskell crunches it and b) how a more sophisticated example such as the triang numb definition I gave gets "crunched" – Schizoid

Answer 1

Here is a simple recursive function that gives you the nth Triangular number:

triag 0 = 0
triag n = n + triag (n-1)

Your solution triag' = zipWith (+) [1..] $ 0 : triag' is something more fancy: It's corecursive (click, click). Instead of calculating the nth number by reducing it to the value of smaller inputs, you define the whole infinite sequence of triangular numbers by recursively specifying the next value, given an initial segment.

How does Haskell handle such corecursion? When it encounters your definition, no calculation is actually performed, it is deferred until results are needed for further computations. When you access a particular element of your list triag', Haskell starts computing the elements of the list based on the definition, up to the element that gets accessed. For more detail, I found this article on lazy evaluation helpful. In summary, lazy evaluation is great to have, unless you need to predict memory usage.

Here is a similar SO question, with a step-by step explanation of the evaluation of fibs = 0 : 1 : zipWith (+) fibs (tail fibs), a corecursive definition of the Fibonacci sequence.

Laodicean

But where is the base case in the definition I provided as an example? Does it take it from 1 from [1..] and 0 from 0:tn ? – Schizoid

Suppose you access the first element of the triag': that can be computed directly, it's 1+0, the sum of the first elements of [1..] and 0:triag'. Now the second: It is 2 + 1 where 2 is the second element from [1..] and 1 the second element of 0:triag', i.e. is the first element of triag', 1. In this way any element of triag' is defined by your solution and can be computed as needed. – Laodicean