home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / function / 1351 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  1.8 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!news2me.EBay.Sun.COM!exodus.Eng.Sun.COM!chivas!staffan
  2. From: staffan@chivas.Eng.Sun.COM (Staffan Liljegren)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Is efficient backtracking feasible in functional languages?
  5. Date: 11 Nov 1992 21:53:37 GMT
  6. Organization: Sun Microsystems
  7. Lines: 53
  8. Distribution: world
  9. Message-ID: <lg3071INN8m1@exodus.Eng.Sun.COM>
  10. References: <1992Nov11.171742.18783@eua.ericsson.se>
  11. Reply-To: staffan@chivas.Eng.Sun.COM
  12. NNTP-Posting-Host: chivas
  13.  
  14. In article 18783@eua.ericsson.se, joe@erix.ericsson.se (Joe Armstrong) writes:
  15. >
  16. >|> 
  17. >|>    strangesucc n =    hd [x|x<-[0..];x>n];
  18. >|> 
  19. >    ....
  20. >|> 
  21. >|>   - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
  22. >|>   
  23. >|>   [Major collection... 21% used (3397260/15733684), 1920 msec]
  24. >|>   
  25. >|>   [Major collection... 21% used (3397288/15730836), 1910 msec]
  26. >|>   
  27. >|>   [Major collection... 21% used (3397288/15730948), 1920 msec]
  28. >|>   
  29. >|>   [Major collection... 21% used (3397288/15730888), 1920 msec]
  30. >|>   
  31. >|>   [Major collection... 21% used (3397288/15730888), 1910 msec]
  32. >|>   val it = 1000001 : int
  33. >|>   -
  34. >
  35. >    Wonderfull  !!
  36. >
  37. >    This is the kind of stuff that gives FP a bad name :-)
  38. >
  39. >    Is their a transformation system which can prove that
  40. >
  41. >    strangesucc x == x + 1 ?
  42. >
  43. >    Joe
  44.  
  45. I thought I should try this in Haskell, so I started Haskell B (the Chalmers implementation)
  46. and I had no problem with 
  47.  
  48.     strangesucc 10000
  49.  
  50. Although it garbed three times it wasn't that slow. So ahead with some more courageus:
  51.  
  52.     strangesucc 100000
  53.  
  54. What happened ? Well:
  55.  
  56.     GC Stack Overflow !
  57.  
  58. So it's not only SML that has these problems. So what are some better mechanisms for 
  59. representing backtracking OR how can You circumvent this problem ?
  60.  
  61. /Staffan Liljegren
  62.  
  63.  
  64.  
  65.  
  66.  
  67.