'any' and 'all' compared with the rest of the Report

Koen Claessen koen@cs.chalmers.se
Wed, 24 Jan 2001 03:45:09 +0100 (MET)


Eric Shade wrote:

 | Then I get to 'any' and 'all', whose specification
 | requires linear time and *linear* space when it should
 | run in constant space.

I do not understand this remark. What do you mean by this?

It is very difficult to say anything about space usage in a
lazy functional language, but let us assume that a list "xs"
is lazily produced in a one-by-one element fashion, and that
noone else than the following expression is looking at that
list. Then:

  any p xs

Runs in constant space (with respect to the size of the
list), for any of the discussed implementations of "any".

Or did you mean something else?

/Koen.

--
Koen Claessen         http://www.cs.chalmers.se/~koen
phone:+46-31-772 5424      mailto:koen@cs.chalmers.se
-----------------------------------------------------
Chalmers University of Technology, Gothenburg, Sweden