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

[Iavor Diatchki]

hello

i myself am not an experienced Haskell user, so please correct me 
if i am wrong. it is difficult in general to reason about the
performance of lazy programs, so i don't think one can assume
much.  in particular i dont think  'any' and 'all' will
perform in linear space.  here is why i think so:

take an example when 'any' is applied to some list (x:xs)
and someone is actually interested in the result:

any p (x:xs)
1. -> (or . map p) (x:xs)
2. -> or (map p (x:xs))
3. -> foldr (||) False (map p (x:xs))

[at this stage we need to know what what kind of list is (map p (x:xs))
i.e. empty or a cons thing, so we need to do some evaluation]

4. -> foldr (||) False (p x : map p xs)     
5. -> p x || (foldr (||) False (map p xs))

[at this stage we need to know what kind of thing is p x, i.e.
True or False, so we need to evaluate p x]

6. -> if p x is True we are done (result True)

7. -> if p x is False the result is (foldr (||) False (map p xs))
and we go back to 3.  note that p x has become garbage and so it
doesnt really take up any space, so one really needs only enough
space to process the list one element at a time.


what causes problems is the need to create unnecessary cons cells
(i.e. the evaluation after 3.).  this is bad because it takes time.
of course it only adds a constant so the complexity is the same
but in practise programs run slower.  this is where i would expect
a good compiler to do some optimisation, i.e to remove the need
for the intermediate list.


i like the idea of programming at a higher level, as i believe it 
produces "better structured" programs.  what i mean is that one 
manages to capture certain aspects of a program, which would
be obscured if one always used explicit recursion.  i think
higher order functions like maps and folds really go a long way
toward structuring functional programs.  in a way this is simillar
to using loops instead of explicit gotos in procedural programs.
anyways these are my deep thought on the matter :)

bye
iavor



On Tue, Jan 23, 2001 at 12:35:19PM -0600, 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.  (By the
> way, I checked and GHC does *not* use the Prelude definitions but
> rather the obvious recursive ones, and most of its optimizations based
> on "good consumers/producers" use meta-linguistic rewrite rules.  So
> without knowing the specific optimizations that a compiler provides, I
> think it's safe to assume that the Prelude 'any' and 'all' *will*
> require linear space.)
...

-- 
+---------------------------------+---------------------------------------+
|Iavor S. Diatchki                | email: diatchki@cse.ogi.edu           |
|Dept. of Computer Science        | web: http://www.cse.ogi.edu/~diatchki |
|Oregon Graduate Institute        | tel: 5037481631                       |
+---------------------------------+---------------------------------------+