Context of a pattern variable
Hello! I have an idea for a funny extension to pattern matching in Haskell. I wonder if it was proposed before, and most importantly, if it would be seen as useful. Currently, pattern variables get only the values of the corresponding subterms of a matched term. What if we could mark a pattern variable to match not the corresponding subterm, but *the rest* of the term, as a "context" function. Such a function would wrap its argument with *the rest*. It would allow to easily exchange some deep part of a data structure. The extension introduces a new syntax for patterns, similar to the as-pattern - @. In the following examples, I'll use @> for this. The syntax case expr of (... (ctx @> pat) ...) -> expr2 ... would mean that if the pattern succeeds, then in expr2 ctx is bound to the function: (\x -> (... (x) ...)) This is very informal, but I'm sure you understand. Note that the dots stand for corresponding, but different things in "case" and in the lambda (pattern vs value). Here are some simple examples how Haskell code could be rewritten using the proposed extension: before: case t of (x, y, z) -> (x, y, z+1) after: case t of (_, _, ctx @> z) -> ctx z before: case t of (x, y, (a, Just z)) -> (x, y, (a, z)) after: case t of (x, y, (a, ctx @> Just z)) -> ctx z Note that in the above example ctx is a polymorphic function. I am not sure this extension would be so useful, that is, if its usefulness would outweigh the cost of implementation. However, it seems to me that the implementation would be quite a simple code transformation, that wouldn't even require to look up datatype definitions. It is probably possible to hack a working proof of concept eg. in Template Haskell. BTW, I already see some problems with this syntax. For example, this code case t of (x, y, (a, ctx @> Just z)) -> ctx z wouldn't be equivalent to this one case t of (x, y, v) -> case v of ctx @> Just z -> ctx z I would love to hear you opinions. Maybe you can think of some really convincing (or unconvincing) code examples? Best regards, Tomasz
Tomasz Zielonka <tomasz.zielonka@gmail.com> proposed an interesting kind of ``second-order as-patterns'' that are ``safe'' from the usual problems of second-order matching by virtue of fixing (at least) the spine of the images of the second-order variables. Tomasz' first example (incorporating Stefan Holdermans' correction) is: | before: | | case t of | (x, y, z) -> (x, y, z+1) | | after: | | case t of | (_, _, ctx @> z) -> ctx (z + 1) Stefan Monnier <monnier@iro.umontreal.ca> generalised to contexts with arbitrarily many holes:
case t of (x, y, z) -> (x, y, z+1)
How would you do:
case t of (x, y, z, a, b, c) -> (x+1, y, z, a, b, c+2)
would you allow:
case t of (ctx @> x, _, _, _, _, ctx @> c) -> ctx (x+1) (c+2)
First a minor point of ``getting the names right'': In either case ``ctx'' is a second-order variable, or a metavariable in the sense of Klop's Combinatory Rewriting Systems (CRSs, [Klop-1980]), and not a variable for a ``context'' in the technical sense of ``term with a hole''. Even if patterns in Haskell included variable binders, we would want to avoid the variable capture allowed by instantiating the hole of a context containing variable binders on its spine. (In the context of first-order patterns this distinction is not so relevant, but I still believe that it makes sense to be careful.) Already in his original message, Tomasz identifies the following problem:
case t of (x, y, (a, ctx @> Just z)) -> ctx z
wouldn't be equivalent to this one
case t of (x, y, v) -> case v of (a, ctx @> Just z) -> ctx z
[ The last line contains my interpretation of Tomasz' intention. ] This could be alleviated by making the character of the intended binding as a second-order binding more explicit by allowing as-patterns to bind against function left-hand sides, where variables occurring in patterns may be ``co-bound'' in the pattern part of the as-pattern by a SINGLE occurrence of the ``co-as'' for which I continue to use Tomasz' symbol ``@>''. The first example would then be written: case t of (ctx zH) @ (_, _, zH @> z) -> ctx (z + 1) I continue to use the variable name ``ctx'' to better exhibit the relation with the original notation. ``zH'' stands for ``z-hole'' for lack of a better naming convention. 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.) The first version of Tomasz' counterexample is treated in the same way as the first example: case t of (ctx zH) @ (x, y, (a, zH @> Just z)) -> ctx z The expression corresponding to the ``broken'' context then exhibits a composed context: case t of (ctx1 vH) @ (x, y, vH @> v) -> case v of (ctx2 zH) @ (a, zH @> Just z) -> ctx1 (ctx2 z) Allowing arbitrary function left-hand sides (non-terminal ``funlhs'' from the Haskell98 report) is probably not useful, but should be otherwise unproblematic ;-) As an example, case q1 of (f (xH, yH)) @ ((xH @> x, yH @> y) : _) -> f p would be equivalent to: case q1 of (f pH) @ (pH @> (x, y) : _) -> f p Essentially the same holds for admitting ``hole variables'' that are not bound by a @>, since they will just be ignored arguments of the ``context'' function. case q2 of (f xH yH) @ (xH @> x, Nothing) -> f (x+1) (Right 2) would be equivalent to: case q2 of (f xH) @ (xH @> x, Nothing) -> f (x+1) (The restriction to only single occurrences to the left of @> corresponds directly to the linearity requirement for Haskell patterns.) I think that this way we have the concepts right --- how useful this feature would be is probably going to be mostly a question of programming style. For very deep pattern matching in, for example, XSLT-like applications it could probably be quite convenient. Best regards, Wolfram @TechReport{Klop-1980, author = {Jan Willem Klop}, title = {Combinatory Reduction Systems}, year = 1980, type = {Mathematical Centre Tracts}, number = 127, note = {PhD thesis}, institution = {Centre for Mathematics and Computer Science}, address = {Amsterdam}, }
On Tue, Jan 11, 2005 at 10:12:06PM -0500, kahl@cas.mcmaster.ca wrote:
Tomasz Zielonka <tomasz.zielonka@gmail.com> proposed an interesting kind of ``second-order as-patterns'' that are ``safe'' from the usual problems of second-order matching by virtue of fixing (at least) the spine of the images of the second-order variables.
So it is a known idea?
This could be alleviated by making the character of the intended binding as a second-order binding more explicit by allowing as-patterns to bind against function left-hand sides, where variables occurring in patterns may be ``co-bound'' in the pattern part of the as-pattern by a SINGLE occurrence of the ``co-as'' for which I continue to use Tomasz' symbol ``@>''.
The first example would then be written:
case t of (ctx zH) @ (_, _, zH @> z) -> ctx (z + 1)
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 @> ? Anyway, I like your notation very much. Mine was a bit clumsy.
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?
The first version of Tomasz' counterexample is treated in the same way as the first example:
case t of (ctx zH) @ (x, y, (a, zH @> Just z)) -> ctx z
The expression corresponding to the ``broken'' context then exhibits a composed context:
case t of (ctx1 vH) @ (x, y, vH @> v) -> case v of (ctx2 zH) @ (a, zH @> Just z) -> ctx1 (ctx2 z)
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)
I think that this way we have the concepts right --- how useful this feature would be is probably going to be mostly a question of programming style. For very deep pattern matching in, for example, XSLT-like applications it could probably be quite convenient.
I wonder if this idea could be nicely combined with HaRP - Haskell Regular Patterns... Thanks for your insightful and enlightening comment! Best regards, Tomasz
On Tue, Jan 11, 2005 at 06:30:02PM -0500, Stefan Monnier wrote:
case t of (x, y, z) -> (x, y, z+1)
How would you do:
case t of (x, y, z, a, b, c) -> (x+1, y, z, a, b, c+2)
would you allow:
case t of (ctx @> x, _, _, _, _, ctx @> c) -> ctx (x+1) (c+2)
I thought about it, but not too much. Wolfram's idea seems nice. Best regards, Tomasz
Tomasz,
I have an idea for a funny extension to pattern matching in Haskell. I wonder if it was proposed before, and most importantly, if it would be seen as useful.
I haven't seen anything like this before, which if of course not to say that there has never been made a similar proposal before. To be honest---please note that I haven't give this too much thought yet---I did not immediately fell in love this proposed extension. Surely, it makes programs shorter; but does it makes them more readable? Maybe it would take some time to get used to it, but I don't think it provides for a more intuitive coding style. Furthermore, I think with this syntax, it is just too easy to get wrong. Maybe I'm mistaken, but, to illustrate, I believe there's even an error in the very examples given by you:
before:
case t of (x, y, z) -> (x, y, z+1)
after:
case t of (_, _, ctx @> z) -> ctx z
Shouldn't that be <code>case t of (_, _, ctx @> z) -> ctx (z + 1)</code>? So, for now: I'd say "no", but that's really just my opinion. Regards, Stefan
On Wed, Jan 12, 2005 at 01:02:43AM +0100, Stefan Holdermans wrote:
Furthermore, I think with this syntax, it is just too easy to get wrong. Maybe I'm mistaken, but, to illustrate, I believe there's even an error in the very examples given by you:
after:
case t of (_, _, ctx @> z) -> ctx z
Shouldn't that be <code>case t of (_, _, ctx @> z) -> ctx (z + 1)</code>?
Yes, it should. I didn't have much time to think about this idea, so I thought I will pass it on to other people with more time and/or brains before I completely forget it. As for the bug, let me give you more data points to consider. At the time I was writing the examples I was simultaneously distracted by my wife (accusing me of being a computer-o-holic ;) and my cat (wanting me to play with her). I think it was a bigger "contribution" to this bug :) Best regards, Tomasz
Below are corrections of embarassing mistakes in my examples, pointed out by Wolfram and Stefan Holdermans. On Tue, Jan 11, 2005 at 11:12:04PM +0100, Tomasz Zielonka wrote:
before:
case t of (x, y, z) -> (x, y, z+1)
after:
case t of (_, _, ctx @> z) -> ctx z
(_, _, ctx @> z) -> ctx (z+1)
BTW, I already see some problems with this syntax. For example, this code
case t of (x, y, (a, ctx @> Just z)) -> ctx z
wouldn't be equivalent to this one
case t of (x, y, v) -> case v of ctx @> Just z -> ctx z
(a, ctx @> Just z) -> ctx z Best regards, Tomasz
"Tomasz Zielonka" <tomasz.zielonka@gmail.com> escreveu na mensagem news:20050111221204.GA15394@students.mimuw.edu.pl... [snip]
BTW, I already see some problems with this syntax. For example, this code
case t of (x, y, (a, ctx @> Just z)) -> ctx z
wouldn't be equivalent to this one
case t of (x, y, v) -> case v of ctx @> (a, Just z) -> ctx z
I think it would work better if the context was always bound to the whole pattern, using '_' patterns to define which parts of the pattern would be copied and naming only the parts which are going to be changed: case t of ctx @> (_, _, v) -> case v of (a, Just z) -> ctx (a, z) or case t of ctx @> (_, _, (_, Just z)) -> ctx z This don't have the ambiguity and the need to keep track wether the context is declared inside a pattern match or not. Also it could be used to more complex changes: case t of ctx @> (x, _, _, _, _, c) -> ctx (x+1) (c+2)
I would love to hear you opinions. Maybe you can think of some really convincing (or unconvincing) code examples?
Best regards, Tomasz
Best regards, Daniel Yokomizo. "You may want Star Wars compilers, but I'm no Luke Skywalker." - Cyril Adrian --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.832 / Virus Database: 566 - Release Date: 10/1/2005
Tomasz Zielonka <tomasz.zielonka@gmail.com> writes:
I have an idea for a funny extension to pattern matching in Haskell. I wonder if it was proposed before, and most importantly, if it would be seen as useful.
Yes, it has been proposed before. See Marcus Mohnen, "Context Patterns", Proceedings of IFL'96 (LNCS 1268) Marcus Mohnen, "Context Patterns II", Proceedings of IFL'97 (LNCS 1467) Regards, Malcolm
Malcolm Wallace <Malcolm.Wallace@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
On Wed, Jan 12, 2005 at 11:47:51AM +0000, Malcolm Wallace wrote:
Malcolm Wallace <Malcolm.Wallace@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. Also, I am not sure what this expressions should evaluate to: case ([1], [2]) of (c [x]) -> c [] Will it be ([], [2]) or ([1], []) ? Perhaps I should just RTFP (Read The Fine Paper). Thanks! Tomasz
Tomasz Zielonka <tomasz.zielonka@gmail.com> continues the thread on his second-order extension of as-patterns:
Malcolm Wallace <Malcolm.Wallace@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}}, }
participants (6)
-
Daniel Yokomizo -
kahl＠cas.mcmaster.ca -
Malcolm Wallace -
Stefan Holdermans -
Stefan Monnier -
Tomasz Zielonka