🚀 go-pugleaf

In article <1992Nov10.164456.18062@email.tuwien.ac.at> ulrich@mips.complang.tuwien.ac.at writes:
>
>strangesucc n =	hd [x|x<-[0..];x>n];
>
>This program should run in constant space and linear time [1].
>However, for the implementations I tried, it turns out that the program
>seems to run in linear space! For a small n as 10000 the program aborts
>due to memory problems. Also a rewriting of the program to encode list comprehensions explicitly did not yield the desired result.
>
>Is there ANY implementation of a lazy functional language to execute
>the program above in an efficient manner (i.e. in constant space)?
>-- 
>Ulrich Neumerkel, ulrich@dec4.wu-wien.ac.at ulrich@mips.complang.tuwien.ac.at
>TU-Wien, Vienna University of Technology, +431 58801 4477 fax +431 5057838
>Institut fuer Computersprachen E185/1 Argentinierstr.8/4, A-1040 Wien Austria


I've tried this on an implementation based on the G-machine. My machine
uses the blackholing technique to avoid space leaks that I describe in [1].
I translate list comprehensions to their equivalent using foldr, map and
concat; for example see [2].
I have no problem with this function: it runs in constant space (262 words
of heap space if you want to compare figures with those give in [1]).

[1] Richard E. Jones. `Tail recursion without space leaks', Journal of 
    Functional Programming 2(1), 73--79, January 1992.
    
[2] Richard Bird & Phil Wadler. `Introduction to Functional Programming', 
    Prentice Hall, 1988. Page 63.


Richard Jones

===============================================================================

Computing Laboratory				email: rej@ukc.ac.uk
University of Kent at Canterbury		Telephone: 0227 764000 ext.7550
Canterbury, CT2 7NF, U.K.			FAX: 0227 762811

===============================================================================