[Haskell-beginners] Recursive calls inside lazy data constructors?

[Ut Primum]

Hi,
the sequence defined in your example has been conjectured by Collatz to be
finite for all initial n. But by now this property hasn't been proved.
So, for what we know, there could be an integer such that the sequence
starting form it is infinite (no such n has been found yet, but there could
be one).
Anyway, even if such n existed, you chose it, and wrote

x=collatz n

there would not be a stack overflow. This is because computations will be
done "lazily", so just when really needed. So if you asked for the first,
say, 10 elements of the list x, they would be computed without problems,
even if the base case is never reached. Of course if you asked to print
collatz n for an n that makes the sequence infinite, the printing would
never end. But you could make many operations with the possibly infinite
list, if they required just a finite (not necessarily a priori bounded)
number of elements.

So in Haskell you can define lists or other data structures that are
infinite. Of course you must define the structure in such a way that to
compute the "next" element of the list there is no need to look at "future"
elements, but just at "past" ones.

I hope this answers your question,
Cheers,
Ut

Il sab 13 feb 2021, 00:03 Galaxy Being <borgauf at gmail.com> ha scritto:

> I'm looking at this
> <https://stackoverflow.com/questions/23768413/building-a-list-from-left-to-right-in-haskell-without>
> from Stackoverflow and wondering what is meant in the accepted answer when
> he says
>
> *In Haskell you can safely do recursive calls inside lazy data
> constructors, and there will be no risk of stack overflow or divergence.
> Placing the recursive call inside a constructor eliminates the need for an
> accumulator, and the order of elements in the list will also correspond to
> the order in which they are computed*:
>
> collatz :: Integer -> [Integer]
> collatz n | n <= 1 = []
> collatz n = n : collatz next where
>     next = if even n then div n 2 else n * 3 + 1
>
> What is meant by lazy data constructor in this context?
>
> LB
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20210213/3bb5894d/attachment.html>