home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1359 < prev    next >
Encoding:
Text File  |  1992-11-12  |  1.7 KB  |  56 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!mcsun!sun4nl!sci.kun.nl!mac1p.cs.kun.nl!johnvg
  3. From: John van Groningen <johnvg@cs.kun.nl>
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Message-ID: <BxM4q9.Jos@sci.kun.nl>
  6. X-Xxmessage-Id: <A7284C6E630120D7@mac1p.cs.kun.nl>
  7. X-Xxdate: Thu, 12 Nov 92 18:01:18 GMT
  8. Sender: news@sci.kun.nl (NUnet News Owner)
  9. Organization: University of Nijmegen
  10. X-Useragent: Nuntius v1.1.1d9
  11. References: <1992Nov10.164456.18062@email.tuwien.ac.at>
  12. Date: Thu, 12 Nov 1992 17:03:44 GMT
  13. Lines: 41
  14.  
  15. In article <1992Nov10.164456.18062@email.tuwien.ac.at> Ulrich Neumerkel
  16. E185/1 +43158801/4477, ulrich@mips.complang.tuwien.ac.at writes:
  17.  
  18. >strangesucc n =    hd [x|x<-[0..];x>n];
  19. >
  20. >This program should run in constant space and linear time [1].
  21. >However, for the implementations I tried, it turns out that the program
  22. >seems to run in linear space! For a small n as 10000 the program aborts
  23. >due to memory problems. Also a rewriting of the program to encode list 
  24. >comprehensions explicitly did not yield the desired result.
  25.  
  26. The following rewrite yields the desired result in constant space
  27. in Haskell B:
  28.  
  29. main = print (h::Integer)
  30.  
  31. hd (e:l) = e
  32.  
  33. g n = n : g (n+1)
  34.  
  35. f [] n = []
  36. f (x:v) n = if (x>n)
  37.                then (x:f v n)
  38.                else (f v n)
  39.  
  40. h :: Integer
  41. h = hd (f (g 0) 1000000)
  42.  
  43. But if you change the function 'main' to:
  44.  
  45. main = print (hd (f (g 0) 1000000)::Integer)
  46.  
  47. the program runs in linear space !
  48.  
  49. >Is there ANY implementation of a lazy functional language to execute
  50. >the program above in an efficient manner (i.e. in constant space)?
  51.  
  52. Yes, Chalmers LML implementation.
  53.  
  54.  
  55.                          John van Groningen
  56.