Pattern Matching Views

An approach invented by PhilipWadler for combining AbstractDataTypes with PatternMatching.

A View is an isomorphism between one data representation and another. For example, given ordinary integer arithmetic, you could construct a PeanoArithmetic view with:

  view int ::= Zero | Succ int
    in n         = Zero,         if n = 0
                 = Succ (n - 1), if n > 0
    out Zero     = 0
    out (Succ n) = n + 1

You can then pattern match on the Peano data types as if you were working with integers and GuardClauses. For example, you could define exponentiation as

  power x Zero     = 1
  power x (Succ n) = x * power x n

And you could define Fibonacci numbers as:

  fib Zero            = Zero
  fib (Succ Zero)     = Succ Zero
  fib (Succ (Succ n)) = (fib n) + (fib (Succ n))

I'm not sure if this is implemented in any production language. The paper is written in pseudo-MirandaLanguage, and IIRC there have been proposals to add it to HaskellLanguage.


See also: PredicateDispatching, PatternMatching

Contributors: JonathanTang

View edit of November 18, 2004 or FindPage with title or text search