home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / scheme / 2552 < prev    next >
Encoding:
Text File  |  1992-11-07  |  2.1 KB  |  52 lines
  1. Newsgroups: comp.lang.scheme
  2. Path: sparky!uunet!brunix!brunix!mj
  3. From: mj@cs.brown.edu (Mark Johnson)
  4. Subject: Total ordering on scheme objects (Was Re: case sensitivity)
  5. Message-ID: <1992Nov6.171856.3414@cs.brown.edu>
  6. Sender: news@cs.brown.edu
  7. Organization: Brown University Department of Computer Science
  8. References: <1992Nov6.062357.8865@Informatik.TU-Muenchen.DE> <1de4rhINNn4u@agate.berkeley.edu>
  9. Date: Fri, 6 Nov 1992 17:18:56 GMT
  10. Lines: 40
  11.  
  12. > string->symbol is a concession to people with unusual needs.  The reason
  13. > it doesn't follow the usual rules for symbols is that it exists precisely
  14. > as a mechanism to escape from those rules.  Using string->symbol is
  15. > cheating, sort of like using goto in some other languages.
  16.  
  17. I disagree.  I use string->symbol as a way of defining a total ordering
  18. on symbols (and extend it to a total ordering on all Scheme objects).
  19. Lots of algorithms exploit an ability to compare keys.  For example,
  20. AVL trees can be used to implement an associator that runs in O(ln n)
  21. time per insertion/look-up, but they require a total ordering on keys.
  22.  
  23. I think one of the most insightful innovations of the Prolog designers
  24. was to include a general predicate called compare, which implements a
  25. total ordering on all Prolog objects.  With it, you can write 
  26. associator and set-manipulation utilities that are both fast and
  27. completely general.
  28.  
  29. I would like to suggest that Scheme too might also be extended to
  30. include a function
  31.  
  32.     (compare <entity1> <entity2>)
  33.  
  34. that returns one of the three symbols <, =, or >, depending on the
  35. relationship between <entity1> and <entity2> in the total ordering,
  36. where = indicates identity in the eq? sense.  All that needs to be 
  37. specified in the standard is that compare defines a total ordering.
  38.  
  39. I don't have much hope that anything like this will actually make
  40. it into the standard -- you'd actually have to be interested in
  41. using Scheme for real problems to find something like this useful. :-)
  42. But until it does, I'll have a very real need for symbol->string !.
  43.  
  44. Mark
  45.  
  46.  
  47.  
  48.  
  49. Mark Johnson
  50. Cognitive Science, Box 1978
  51. Brown University
  52.