'any' and 'all' compared with the rest of the Report
Iavor Diatchki
[email protected]
Tue, 23 Jan 2001 12:16:05 -0800
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: [email protected] |
|Dept. of Computer Science | web: http://www.cse.ogi.edu/~diatchki |
|Oregon Graduate Institute | tel: 5037481631 |
+---------------------------------+---------------------------------------+