🚀 go-pugleaf

In article <1992Nov10.164456.18062@email.tuwien.ac.at> Ulrich Neumerkel
E185/1 +43158801/4477, 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.

The following rewrite yields the desired result in constant space
in Haskell B:

main = print (h::Integer)

hd (e:l) = e

g n = n : g (n+1)

f [] n = []
f (x:v) n = if (x>n)
               then (x:f v n)
               else (f v n)

h :: Integer
h = hd (f (g 0) 1000000)

But if you change the function 'main' to:

main = print (hd (f (g 0) 1000000)::Integer)

the program runs in linear space !

>Is there ANY implementation of a lazy functional language to execute
>the program above in an efficient manner (i.e. in constant space)?

Yes, Chalmers LML implementation.


                         John van Groningen