doc/guide/src/VariableArityPolymorphism.adoc

   1 VariableArityPolymorphism
   2 =========================
   3
   4 <:StandardML:Standard ML> programmers often face the problem of how to
   5 provide a variable-arity polymorphic function.  For example, suppose
   6 one is defining a combinator library, e.g. for parsing or pickling.
   7 The signature for such a library might look something like the
   8 following.
   9
  10 [source,sml]
  11 ----
  12 signature COMBINATOR =
  13    sig
  14       type 'a t
  15
  16       val int: int t
  17       val real: real t
  18       val string: string t
  19       val unit: unit t
  20       val tuple2: 'a1 t * 'a2 t -> ('a1 * 'a2) t
  21       val tuple3: 'a1 t * 'a2 t * 'a3 t -> ('a1 * 'a2 * 'a3) t
  22       val tuple4: 'a1 t * 'a2 t * 'a3 t * 'a4 t
  23                   -> ('a1 * 'a2 * 'a3 * 'a4) t
  24       ...
  25    end
  26 ----
  27
  28 The question is how to define a variable-arity tuple combinator.
  29 Traditionally, the only way to take a variable number of arguments in
  30 SML is to put the arguments in a list (or vector) and pass that.  So,
  31 one might define a tuple combinator with the following signature.
  32 [source,sml]
  33 ----
  34 val tupleN: 'a list -> 'a list t
  35 ----
  36
  37 The problem with this approach is that as soon as one places values in
  38 a list, they must all have the same type.  So, programmers often take
  39 an alternative approach, and define a family of `tuple<N>` functions,
  40 as we see in the `COMBINATOR` signature above.
  41
  42 The family-of-functions approach is ugly for many reasons.  First, it
  43 clutters the signature with a number of functions when there should
  44 really only be one.  Second, it is _closed_, in that there are a fixed
  45 number of tuple combinators in the interface, and should a client need
  46 a combinator for a large tuple, he is out of luck.  Third, this
  47 approach often requires a lot of duplicate code in the implementation
  48 of the combinators.
  49
  50 Fortunately, using <:Fold01N:> and <:ProductType:products>, one can
  51 provide an interface and implementation that solves all these
  52 problems.  Here is a simple pickling module that converts values to
  53 strings.
  54 [source,sml]
  55 ----
  56 structure Pickler =
  57    struct
  58       type 'a t = 'a -> string
  59
  60       val unit = fn () => ""
  61
  62       val int = Int.toString
  63
  64       val real = Real.toString
  65
  66       val string = id
  67
  68       type 'a accum = 'a * string list -> string list
  69
  70       val tuple =
  71          fn z =>
  72          Fold01N.fold
  73          {finish = fn ps => fn x => concat (rev (ps (x, []))),
  74           start = fn p => fn (x, l) => p x :: l,
  75           zero = unit}
  76          z
  77
  78       val ` =
  79          fn z =>
  80          Fold01N.step1
  81          {combine = (fn (p, p') => fn (x & x', l) => p' x' :: "," :: p (x, l))}
  82          z
  83    end
  84 ----
  85
  86 If one has `n` picklers of types
  87 [source,sml]
  88 ----
  89 val p1: a1 Pickler.t
  90 val p2: a2 Pickler.t
  91 ...
  92 val pn: an Pickler.t
  93 ----
  94 then one can construct a pickler for n-ary products as follows.
  95 [source,sml]
  96 ----
  97 tuple `p1 `p2 ... `pn $ : (a1 & a2 & ... & an) Pickler.t
  98 ----
  99
 100 For example, with `Pickler` in scope, one can prove the following
 101 equations.
 102 [source,sml]
 103 ----
 104 "" = tuple $ ()
 105 "1" = tuple `int $ 1
 106 "1,2.0" = tuple `int `real $ (1 & 2.0)
 107 "1,2.0,three" = tuple `int `real `string $ (1 & 2.0 & "three")
 108 ----
 109
 110 Here is the signature for `Pickler`.  It shows why the `accum` type is
 111 useful.
 112 [source,sml]
 113 ----
 114 signature PICKLER =
 115    sig
 116       type 'a t
 117
 118       val int: int t
 119       val real: real t
 120       val string: string t
 121       val unit: unit t
 122
 123       type 'a accum
 124       val ` : ('a accum, 'b t, ('a, 'b) prod accum,
 125                'z1, 'z2, 'z3, 'z4, 'z5, 'z6, 'z7) Fold01N.step1
 126       val tuple: ('a t, 'a accum, 'b accum, 'b t, unit t,
 127                   'z1, 'z2, 'z3, 'z4, 'z5) Fold01N.t
 128    end
 129
 130 structure Pickler: PICKLER = Pickler
 131 ----