From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.ada
Subject: Re: How to get Ada to ?cross the chasm??
Date: Tue, 08 May 2018 14:31:33 -0700
Organization: A noiseless patient Spider
Message-ID: <87y3gt6dhm.fsf@nightsong.com>
References: <1c73f159-eae4-4ae7-a348-03964b007197@googlegroups.com>
	<pb7eii$bf1$1@dont-email.me>
	<b75ad71f-a917-4638-9b38-ccfe69b04e53@googlegroups.com>
	<slrnpdpiv9.ntv.address@is.invalid>
	<pbr3mi$leu$1@franka.jacob-sparre.dk> <87k1su7nag.fsf@nightsong.com>
	<pbtlno$3k2$1@franka.jacob-sparre.dk> <87po2la2qt.fsf@nightsong.com>
	<87in8buttb.fsf@jacob-sparre.dk> <87wowqpowu.fsf@nightsong.com>
	<16406268-83df-4564-8855-9bd0fe9caac0@googlegroups.com>
	<87o9i2pkcr.fsf@nightsong.com> <pc8l7e$km5$1@franka.jacob-sparre.dk>
	<87in88m43h.fsf@nightsong.com>
	<cd866ee8-ad4d-489e-a38b-d8e5f5d4af00@googlegroups.com>
	<87efiuope8.fsf@nightsong.com> <pcdagp$7pn$1@franka.jacob-sparre.dk>
	<87lgd1heva.fsf@nightsong.com> <pcg54t$gul$1@franka.jacob-sparre.dk>
	<87zi1gz3kl.fsf@nightsong.com> <fleghiFj0qjU2@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org;
 posting-host="52b5ce8581a197e35f17678a348070d7";
	logging-data="20322"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX18NTJ7XposPliVD1rbLJNqo"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux)
Cancel-Lock: sha1:r0WLsXLfs9sWSdc75vKn+/qxSsA=
	sha1:sFQLqyJNthQpa2DfBBANr28HrKk=
Xref: reader02.eternal-september.org comp.lang.ada:52133
Date: 2018-05-08T14:31:33-07:00
List-Id: <comp.lang.ada>

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>>     x = 1 : 2 : 3 : x
> Can you construct such a list in Haskell without using and setting
> explicit references?

If you mean writing the list without using x on both sides of the equal
sign, you could use a fixpoint combinator:
   
    Prelude Control.Monad.Fix> let f = fix ([1,2,3]++)
    Prelude Control.Monad.Fix> take 20 f
    [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2]

But fix is written something like this:

   fix f = x where x = f x

and there's an explicit reference there.  There's a corresponding object
called the Y combinator in untyped lambda calculus that can be written
without such a reference, but I think it's not possible to write it that
way in a typed system, because of the "strong normalization" property of
typed lambda calculus.  There's some discussion here:

https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion


> Is there some kind of "letrec" for recursive data objects (as opposed
> to recursive functions)?

There's no letrec per se, since ordinary let is allowed to be recursive.
Mathematically when self-reference happens in data rather than functions
it's called "corecursion" rather than recursion, but most people just
call such data recursive, slightly incorrectly I think.  Fwiw, recursive
data is supposedly called "codata".

There's an argument for eliminating unrestricted recursion from
programming so that all functions must eventually return, so codata is
the only way to implement non-termination (like if you wanted to write
an OS).  You get a programming language that's non-Turing-complete (you
can tell by inspection whether a given program halts, based on whether
it uses codata) but the claim is that Turing completeness is not that
useful in practice:

http://www.jucs.org/jucs_10_7/total_functional_programming