🚀 go-pugleaf

In article <501@owl.ukc.ac.uk> dat@ukc.ac.uk (D.A.Turner) writes:
> In article <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> dtarditi@CS.CMU.EDU (David Tarditi) writes:
> >I have always been under the impression that lazy evaluation
> >makes it difficult to determine the time and space efficiency
> >of programs.>
> >If this is true, then it is a strong practical argument against using 
> >lazy evaluation, since asymptotic efficiency is quite important in
> >practice.> An O(n^2) algorithm may be unusable in practice, while
> >an O(n log n) algorithm may do quite nicely.

> I think it is only half true. There  is  no  special  difficulty  in
> reasoning   about  the  *time*  complexity  of  programs  written  in  a
> non-strict  functional  language.   One  can  derive  from  the  program
> equations   for  functions  fi  say,  similar  equations  for  Tfi,  the
> time-to-execute of function fi.  There is quite  a  nice  discussion  of
> this,   with   some   examples,  in  chapter  6  of  Bird  and  Wadler's
> "Introduction to Functional Programming".
>   On the other  hand  reasoning  about  the  *space*  complexity  of  such
> programs seems to be much more difficult.

If it is difficult to determine the space complexity of the programs, I wonder
why is it easy to determine their time complexity ? Allocating and 
initializing space takes time proportional to the space used (in the best
case -- assuming the space is never reused). Explicit freeing 
takes time proportional to the space freed (again in the best case -- not
much compaction needed), garbage collection needs time proportional to the
amount of live data (best case -- mark and sweep needs time proportional
to the all space available to the program). 

anurag