Value space transformations

Alastair Reid alastair at
Mon Nov 10 23:51:26 EST 2003

> So my questions are:
> (a) is there a common functional programming pattern that corresponds to
> vector space transformations so that a function defined over one space can
> be used in another, and
> (b) if so, are there any not-too-heavy papers or articles discussing this
> pattern?

Many times when you have a pair of functions:

  f : S -> T
  g : T -> S

you find that they form a projection-embedding pair:

   f . g =  id
   g . f <= id

where the <= ordering typically indicates loss of information.

For example, read and show are related this way with the read function losing 
information about whitespace, comments, etc.  Various kinds of lookup tables 
and set representations (linear lists, arrays, binary trees, etc.) are also 
related in this way.

A useful generalization is an "adjunction" or "galois connection".

Section 3 of this paper has a concise definition and, more usefully, helps 
give you some intuition about them. 

  A reflection on call-by-value, Amr Sabry and Philip Wadler.

Other people can probably suggest better papers.

Hope this helps,

Alastair Reid

More information about the Haskell-Cafe mailing list