🚀 go-pugleaf

In <1992Jul19.151418.16386@odin.diku.dk> bombadil@diku.dk (Kristian Nielsen) writes:

>I think there is another aspect that is often overlooked when lazy
>functional programs are deemed slower than en equivalent program in a
>more traditional language such as C or Pascal. I often find myself
>writing 'better' programs in say Haskell to solve a particular problem
>than I would have done otherwise. A very common example of this is the
>tendency to have artificial constrains on the size of data structures
>used in programs, like the dreaded maximum identifier length in
>compilers or 256 character limit on input lines. In functional
>languages (eager and lazy alike) the natural use of dynamic data
>structures avoids this. Another example more related to laziness would

IMHO this is due to ease of using dynamic data structures, and not
anything to do with functional languages as such, let alone laziness.
I don't think that languages like LISP,Smalltalk, or even APL suffer
very much from artificial size constraints.

>be a binary tree implementation. In a straitforward implementation in
>an eager language the time complexity of m insertions followed by n
>lookups would be O((m+n)log(m)). In a lazy implementation the
>complexity might be somewhat better, since the insertions are not
>taking place until/unless actually needed by the lookup operations.

I can't see this being very beneficial. As soon as I search for a key
which is not in the tree, I need to do all pending insertions. As soon
as I search for a key which has recently been added I need to do most
pending insertions. If I support deletions or change of keys, these
will also require pending insertions to be done.  Further, I am
postponing a great deal of work that will probably need to be done
anyway. If I do many insertions, the next query may take a very long
time.

The biggest potential benefit of this might arise in a parallel
implementation, where insertions can be evaluted in the background.
Even here, I suspect that additional code would be needed to preserve
ordering, at least between queries and insertions.

I am not arguing for or against lazy evaluation, but I think these are
poor examples. 

-- 
 Alan Knight  knight@mrco.carleton.ca  +1 613 788 2600x5783   Join
 Dept. of Mechanical and Aerospace Engineering                the
 Carleton University, Ottawa, Ontario, Canada, K1S 5B6        LPF