Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!munnari.oz.au!bunyip!moondance!batserver.cs.uq.oz.au!farrell
From: farrell@batserver.cs.uq.oz.au (Friendless)
Newsgroups: comp.lang.functional
Subject: Laziness and Back-to-front Lists
Message-ID: <3738@moondance.cs.uq.oz.au>
Date: 28 May 90 05:09:28 GMT
References: <14531@dime.cs.umass.edu> <2535@skye.ed.ac.uk> <8691@cs.utexas.edu> <4170@castle.ed.ac.uk>
Sender: news@moondance.cs.uq.oz.au
Reply-To: farrell@batserver.cs.uq.oz.au
Lines: 32

In comp.lang.functional Nick writes:
>I can write things like
>	fun f x = cons(1, f x)
>to build an infinite list, but not
>	fun f x = reverse_cons(f x, 1)
>because of the reduction order.

  I suppose you mean:

fun = cons 1 fun
fun = reverse_cons fun 1

  ? f and x seem entirely useless.

  I'm not sure what you want here. The fact is that the two definitions of fun
don't define the same function - the first has an infinite tail, and the
second has an infinite head. In say, Miranda, you won't be able to get
anything out of the second because lists are evaluated head to tail only.
If you defined a list by

list * = Nil | Cons * (list *) | RCons (list *) *

and for the second said 

fun = RCons fun 1

  then the definitions would be symmetric. Of course lists aren't ever defined
like this. I think someone did a paper on this sort of stuff (maybe Kennaway &
Sleep?) which I can hunt down if anyone cares.


							John