lib/mlton/set/README

   1 Methods of implementing sets (not in terms of the underlying
   2 representation, but in terms of the public signature).
   3
   4 Polymorphic Elements
   5 --------------------------------------------------
   6  pass operations on 'a as arguments when needed
   7   (e.g. equality when testing for membership)
   8 This is bad, because it requires me to construct my own recursive
   9 descent functions.  Good because it checks types at compile
  10 time.  Cumbersome, because I must keep passing the helper functions
  11 everywhere.
  12
  13 What happens if I want a dynamically varying order type of sets?
  14 This can't possibly work.
  15
  16 Special case
  17 --------------------
  18 Use polymorhpism with equality types - this only works if the built
  19 in equality function is what you want.  Furthermore, it does nothing
  20 when you need functions other than equality (e.g. order relations)
  21
  22 Monomorphic Elements
  23 --------------------------------------------------
  24  Use monomorphism and encode the type of the set in the ML type.
  25 This requires a new functor application for each new type of set.
  26 Certainly doesn't work if the order type of the set isn't decided
  27 until run time.
  28 This can get very cumbersome.  Good because it checks types at
  29 compile time.  Also, it "automatically" constructs the proper
  30 recursive descent functions when the functors are applied.
  31 Bad because I can't even express the types of some functions
  32 (e.g. map) without having two different types (structures) around.
  33 This would
  34 be better if I could get it to automatically infer the appropriate
  35 functor applications based on type inference of the code that uses
  36 sets.  Not quite, not only do I want it to infer the appropriate
  37 functor applications, I want it to *share* the results of functor
  38 applications corresponding to objects of the same type.
  39
  40 Monomorphic Elements in a Universal Datatype
  41 --------------------------------------------------
  42 Bad because it doesn't check types at compile time.  However, one can
  43 build a layer on top that checks the types at run time.
  44 This requires a single functor application (if it works at all).
  45 This requires the user to build a union type for all objects that
  46 might be members of sets.  Furthermore, it doesn't even work if I want
  47 to include sets as parts of some of my base datatypes.  That is, the
  48 set and base datatypes can't be mutually recursive.  Maybe this isn't
  49 a problem.  Can I think of an example where I want this??
  50
  51 This gets very cumbersome, because the programmer must constantly
  52 inject to and project from the universal datatype.
  53 Furthermore, it reduces modularity, because all of the objects that
  54 will ever appear in sets must be collected together in one place to
  55 define the universal datatype.
  56
  57 I bet you pay a pretty good performance hit both in terms of time and
  58 space with this approach, because of all of the explicit unions that
  59 are constructed.  --- Wait a second!  Could you get away without
  60 constructing these unions in Scheme?  How would be sure that you could
  61 differentiate among elements?   Do you need to be able to
  62 differentiate in correct programs, or only to aid in debugging?
  63 When do you ever put things in a union and not know what they are???
  64 It seems to me that this happens whenever you have polymorphic
  65 functions that aren't parametric, e.g. print.
  66
  67 Object Oriented
  68 --------------------------------------------------
  69 Monomorphic elements that include the appropriate operations.
  70 I don't like this because each element carries its own equality
  71 function, but I know I want only a single equality function for the
  72 whole type, and I can't enforce (or even express) that they are the
  73 same.
  74
  75
  76 Other Considerations
  77 --------------------------------------------------
  78 Performance implications?
  79 How would each of these options work in scheme?
  80 What other options are there in scheme?