Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Recursive calls inside lazy data constructors? (Galaxy Being)
2. Re: Recursive calls inside lazy data constructors? (Ut Primum)
----------------------------------------------------------------------
Message: 1
Date: Fri, 12 Feb 2021 17:01:44 -0600
From: Galaxy Being <borg...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: [Haskell-beginners] Recursive calls inside lazy data
constructors?
Message-ID:
<cafahfsvwh2cdo547tftswbh0jg8lz8vffdkd80jnaarpxqx...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20210212/10d6d8f3/attachment-0001.html>
------------------------------
Message: 2
Date: Sat, 13 Feb 2021 08:49:48 +0100
From: Ut Primum <utpri...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Recursive calls inside lazy data
constructors?
Message-ID:
<canjdmkjjprsbn9rg3qlkfp_xpnbutfrgyvkbn3y+cljhm2x...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <borg...@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@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-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 151, Issue 5
*****************************************
