doc/guide/src/ProductType.adoc

   1 ProductType
   2 ===========
   3
   4 <:StandardML:Standard ML> has special syntax for products (tuples). A
   5 product type is written as
   6 [source,sml]
   7 ----
   8 t1 * t2 * ... * tN
   9 ----
  10 and a product pattern is written as
  11 [source,sml]
  12 ----
  13 (p1, p2, ..., pN)
  14 ----
  15
  16 In most situations the syntax is quite convenient.  However, there are
  17 situations where the syntax is cumbersome.  There are also situations
  18 in which it is useful to construct and destruct n-ary products
  19 inductively, especially when using <:Fold:>.
  20
  21 In such situations, it is useful to have a binary product datatype
  22 with an infix constructor defined as follows.
  23 [source,sml]
  24 ----
  25 datatype ('a, 'b) product = & of 'a * 'b
  26 infix &
  27 ----
  28
  29 With these definitions, one can write an n-ary product as a nested
  30 binary product quite conveniently.
  31 [source,sml]
  32 ----
  33 x1 & x2 & ... & xn
  34 ----
  35
  36 Because of left associativity, this is the same as
  37 [source,sml]
  38 ----
  39 (((x1 & x2) & ...) & xn)
  40 ----
  41
  42 Because `&` is a constructor, the syntax can also be used for
  43 patterns.
  44
  45 The symbol `&` is inspired by the Curry-Howard isomorphism: the proof
  46 of a conjunction `(A & B)` is a pair of proofs `(a, b)`.
  47
  48
  49 == Example: parser combinators ==
  50
  51 A typical parser combinator library provides a combinator that has a
  52 type of the form.
  53 [source,sml]
  54 ----
  55 'a parser * 'b parser -> ('a * 'b) parser
  56 ----
  57 and produces a parser for the concatenation of two parsers. When more
  58 than two parsers are concatenated, the result of the resulting parser
  59 is a nested structure of pairs
  60 [source,sml]
  61 ----
  62 (...((p1, p2), p3)..., pN)
  63 ----
  64 which is somewhat cumbersome.
  65
  66 By using a product type, the type of the concatenation combinator then
  67 becomes
  68 [source,sml]
  69 ----
  70 'a parser * 'b parser -> ('a, 'b) product parser
  71 ----
  72 While this doesn't stop the nesting, it makes the pattern significantly
  73 easier to write. Instead of
  74 [source,sml]
  75 ----
  76 (...((p1, p2), p3)..., pN)
  77 ----
  78 the pattern is written as
  79 [source,sml]
  80 ----
  81 p1 & p2 & p3 & ... & pN
  82 ----
  83 which is considerably more concise.
  84
  85
  86 == Also see ==
  87
  88 * <:VariableArityPolymorphism:>
  89 * <:Utilities:>