🚀 go-pugleaf

In many textbooks and papers about functional languages it is suggested
that lazy evaluation allows to implement backtracking by representing
the sequence of solutions by an appropriate datastructure which is
generated in a lazy manner. Is seems however, that such an encoding,
although conceptually elegant, requires space proportional to the
number of choices already considered.

Below is such a backtracking program `strangesucc' that computes the
successor of a number by searching through all natural numbers and
selecting the first solution found. This program here is a little
overkill. It serves only as an example for the problems I
encountered in more complex backtracking programs. Take a more
complex condition and the program does make sense.

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)?

Thank You, Ulrich

[1] more precicely in log n space and n log n time, if we consider
numbers of arbitrary magnitude.

PS: Note that backtracking as implemented in Prolog does not have
such problems.
-- 
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