[hcoop/debian/mlton.git] / doc / guide / src / ProductType.adoc

ProductType
===========

<:StandardML:Standard ML> has special syntax for products (tuples). A
product type is written as
[source,sml]
----
t1 * t2 * ... * tN
----
and a product pattern is written as
[source,sml]
----
(p1, p2, ..., pN)
----

In most situations the syntax is quite convenient.  However, there are
situations where the syntax is cumbersome.  There are also situations
in which it is useful to construct and destruct n-ary products
inductively, especially when using <:Fold:>.

In such situations, it is useful to have a binary product datatype
with an infix constructor defined as follows.
[source,sml]
----
datatype ('a, 'b) product = & of 'a * 'b
infix &
----

With these definitions, one can write an n-ary product as a nested
binary product quite conveniently.
[source,sml]
----
x1 & x2 & ... & xn
----

Because of left associativity, this is the same as
[source,sml]
----
(((x1 & x2) & ...) & xn)
----

Because `&` is a constructor, the syntax can also be used for
patterns.

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


== Example: parser combinators ==

A typical parser combinator library provides a combinator that has a
type of the form.
[source,sml]
----
'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
[source,sml]
----
(...((p1, p2), p3)..., pN)
----
which is somewhat cumbersome.

By using a product type, the type of the concatenation combinator then
becomes
[source,sml]
----
'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
[source,sml]
----
(...((p1, p2), p3)..., pN)
----
the pattern is written as
[source,sml]
----
p1 & p2 & p3 & ... & pN
----
which is considerably more concise.


== Also see ==

* <:VariableArityPolymorphism:>
* <:Utilities:>
Commit	Line	Data
7f918cf1 CE	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:>