Commit | Line | Data |
---|---|---|
7f918cf1 CE |
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 | ---- |