home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / function / 945 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  1.5 KB
  1. Path: sparky!uunet!mcsun!uknet!harrier.ukc.ac.uk!owl.ukc.ac.uk!dat
  2. From: dat@ukc.ac.uk (D.A.Turner)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: algorithmic efficiency and lazy languages
  5. Message-ID: <501@owl.ukc.ac.uk>
  6. Date: 23 Jul 92 15:36:00 GMT
  7. References: <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU>
  8. Reply-To: dat@ukc.ac.uk (D.A.Turner)
  9. Distribution: comp
  10. Organization: Computing Lab, University of Kent at Canterbury, UK.
  11. Lines: 22
  12.  
  13. In article <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> dtarditi@CS.CMU.EDU (David Tarditi) writes:
  14. >I have always been under the impression that lazy evaluation
  15. >makes it difficult to determine the time and space efficiency
  16. >of programs.  
  17. >
  18. >If this is true, then it is a strong practical argument against using 
  19. >lazy evaluation, since asymptotic efficiency is quite important in
  20. >practice.   An O(n^2) algorithm may be unusable in practice, while
  21. >an O(n log n) algorithm may do quite nicely.
  22.  
  23. I think it is only  half  true.   There  is  no  special  difficulty  in
  24. reasoning   about  the  *time*  complexity  of  programs  written  in  a
  25. non-strict  functional  language.   One  can  derive  from  the  program
  26. equations   for  functions  fi  say,  similar  equations  for  Tfi,  the
  27. time-to-execute of function fi.  There is quite  a  nice  discussion  of
  28. this,   with   some   examples,  in  chapter  6  of  Bird  and  Wadler's
  29. "Introduction to Functional Programming".
  30.  
  31. On the other  hand  reasoning  about  the  *space*  complexity  of  such
  32. programs seems to be much more difficult.
  33.  
  34. David Turner
  35.