MLton 20051202

ProductType

Home Index

Standard ML has special syntax for products (tuples). A product type is written as

    t1 * t2 * ... * tN

and a product pattern is written as

    (p1, p2, ..., pN)

In most situations the syntax is quite convenient. However, there are special circumstances under which the syntax for product patterns can be cumbersome.

The problem is best shown through parser combinators. A typical parser combinator library provides a combinator that has a type of the form

    'a parser * 'b parser -> ('a * 'b) parser

and produces a parser for the concatenation of two parsers. When more than two parsers are concatenated, the result of the resulting parser is a nested structure of pairs

    (...((p1, p2), p3)..., pN)

which is somewhat cumbersome.

One way around this problem is to use a product datatype

    datatype ('a, 'b) product = & of 'a * 'b

with an infix constructor

    infix &

The type of the concatenation combinator then becomes

    'a parser * 'b parser -> ('a, 'b) product parser

While this doesn't stop the nesting, it makes the pattern significantly easier to write. Instead of

    (...((p1, p2), p3)..., pN)

the pattern is written as

    p1 & p2 & p3 & ... & pN

which is considerably more concise.

The symbol `&` is inspired by the Curry-Howard isomorphism: the proof of a conjunction `(A & B)` is a pair of proofs `(a, b)`.

Last edited on 2005-12-02 04:23:58 by StephenWeeks.