[Haskell] Context of a pattern variable

[kahl at cas.mcmaster.ca]

Tomasz Zielonka <tomasz.zielonka at gmail.com> continues the thread
on his second-order extension of as-patterns:
 > 
 > > Malcolm Wallace <Malcolm.Wallace at cs.york.ac.uk> writes:
 > > 
 > > >     Marcus Mohnen, "Context Patterns", Proceedings of IFL'96 (LNCS 1268)
 > > >     Marcus Mohnen, "Context Patterns II", Proceedings of IFL'97 (LNCS 1467)
 > > 
 > > There is a web page too, with an implementation of context patterns
 > > for an old (2.01) version of ghc:
 > > 
 > > http://www-i2.informatik.rwth-aachen.de/Staff/Current/mohnen/CP/index.html
 > 
 > Wow, this gives much more than my proposal. 
 > 
 > Actually, it seems to be a similar, but different idea.
 > Mohnen's patterns must (AFAICS) be compiled to a
 > pattern _search_ algorithm, while "mine" can be
 > implemented with very simple code transformation. 

The way I would put this is that Mohnen's context patterns
are an addition to the matching aspect of patterns
(among other things, it introduces true second-order variables
 and replaces the Maybe monad
 used for example by Tullsen and Harrison to model pattern matching
 by a list monad),
while Tomasz' idea is an addition to the access interface
for the result of pattern matching (of which as-patterns are a part).


Tomasz' also asked:

 > Probably I get something wrong, but couldn't we simply write it this way?
 > 
 >   case t of
 >       (ctx z) @ (_, _, z) -> ctx (z + 1)
 > 
 > That is - completely forget about @> ?

One might, and I had considered it,
but I think that hiding the two sides of @> is conceptually not clean,
because z would then in some sense be bound by both the @ and the ->.

I would consider this as syntactic artificial sweetener ...


 > > The first occurrence of zH is a binding occurrence,
 > > and the second occurrence is co-bound by the ``@>''.
 > > (Replacing ``@>'' with ``@'' could give rise to confusing errors,
 > >  no matter which way the binding of its left argument is resolved.)
 > 
 > Could you give an example?

f3 z q3 = case q3 of
            (ctx z) @ (x, z @ Just y) -> f z (ctx y)

could be defined to be alpha-equivalent to either of the following two
(distinguishing @ and @>):

f3' z q3 = case q3 of
             (ctx zH) @ (x, zH @> Just y) -> f z (ctx y)

f3'' z q3 = case q3 of
             (ctx zH) @ (x, z @ Just y) -> f z (ctx y)

No matter which definition you choose,
somebody writing f3 could have the other definition in mind.
(They would probably arrive at the situation of f3 via modifying
 something else...)


 > Nice. So we could also collapse the case expressions, nesting the
 > second-order patterns?:
 > 
 > case t of
 >   (ctx1 vH) @ (x, y, vH @> (ctx2 zH) @ (a, zH @> Just z)) -> ctx1 (ctx2 z)

Of course.

We could even extend it to do third-order patterns, and so on:

case (1,[Left 2, Right 3, Left 4, Right 5]) of
  (ctx3 f) @ (x, (f h) @> (y : z : h @>> (Left q : _))) -> ctx List.inits
=
(1, [[], [Left 4], [Left 4, Right 5]])

since f matches to \ h -> Left 2 : Right 3 : h
and ctx3 therefore matches to

\ f -> (1, f [Left 4, Right 5])



Have fun!



Wolfram


-------------------------------------------------

@InProceedings{Tullsen-2000,
  author = {Mark Tullsen},
  title = {First Class Patterns},
  crossref = {PADL2000},
  pages = {1--15},
  URL = {http://www.cs.yale.edu/~tullsen/patterns.ps},
}

@InProceedings{Harrison-Sheard-Hook-2002,
  author = {William L. Harrison and Timothy Sheard and James Hook},
  title = {Fine Control of Demand in {Haskell}},
  crossref = {MPC2002}
}

For the syntactic side of Haskell pattern matching:

@InProceedings{Kahl-2004a,
  author = {Wolfram Kahl},
  title =  {Basic Pattern Matching Calculi: A Fresh View on Matching Failure},
  pages = {276--290},
  booktitle = {Functional and Logic Programming, {Proceedings of FLOPS 2004}},
  year = 	 2004,
  editor =	 {Yukiyoshi Kameyama and Peter Stuckey},
  volume =	 {2998},
  series =	 LNCS,
  publisher =	 Springer,
  note = {Long version: SQRL Report No. 16, available from
          \url{http://sqrl.mcmaster.ca/sqrl_reports.html}},
}