🚀 go-pugleaf

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.

David Turner