[Caml-list] ANN: pattern guards
Jeremy Yallop
extension providing general-purposes additions to pattern matching.
This release includes a single feature: "pattern guards"; others will
be made available in the near future.
You can download patterns from
http://code.google.com/p/ocaml-patterns/
Pattern guards generalize "when"-guards to allow arbitrary pattern
matching with binding. After each pattern in a match you can write
one or more binding phrases as follows:
match e with
| patt1 with p1 = e1
...
with pn = en
-> e
| patt2 ...
The expressions e1 ... en are evaluated in turn and matched with
the corresponding patterns p1 ... pn until either a match fails (in
which case matching proceeds with patt2 etc.) or all matches
succeed. Any variables bound in p1 ... pn are in scope within
subsequent guards and within e.
For example, given a function
val lookup : 'a -> ('a * 'b) list -> 'b option
you might write the following
let f env = function
| Var x
with Some v = lookup x env -> ... v ...
instead of the less elegant and less efficient
let f env = function
| Var x
when mem_assoc x env -> ... assoc x env ...
Pattern guards and regular guards can be freely intermixed; for
example, you can write
match e with
| patt when c1
with patt1 = e1
when c2
with patt2 = e2 -> e
| ...
Pattern guards were proposed (for Haskell) in
Martin Erwig and Simon Peyton Jones
Pattern Guards and Transformational Patterns
Haskell Workshop, 2000
See also: http://research.microsoft.com/~simonpj/Haskell/guards.html
Jeremy.
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
skaller
> I'm pleased to announce the initial release of `patterns', an OCaml
> extension providing general-purposes additions to pattern matching.
I want to do this:
match x with
| Y x with a=x and b=x
| X (y,z) with a=y and b=z
-> f a b
This won't work at the moment for two reasons:
* I assume the precedence of 'with' is the same as 'when',
which is not convenient
* the variables in the basic patterns don't agree
The whole point of the above is to switch all the branches
to normalised variables. At the moment I have to write:
match x with
| Y x -> f x x
| X (y,z) -> f y z
This is very bad, because either I duplicate lots of code,
or I actually define a subroutine f .. the problem with that
is that in a large match, the only place to put it is before
the top of the match .. a long way from where it is required.
The need for the above occurs in term rewriting systems
for which there are abbreviations or redundant encodings.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
Jeremy Yallop
> On Fri, 2007-06-29 at 15:19 +0100, Jeremy Yallop wrote:
>> I'm pleased to announce the initial release of `patterns', an OCaml
>> extension providing general-purposes additions to pattern matching.
>
> I want to do this:
>
> match x with
> | Y x with a=x and b=x
> | X (y,z) with a=y and b=z
> -> f a b
Interesting. Do you want 'z' to be in scope in the guards ("a=y" etc.)
but not in the expression ("f a b")? Or do you just generally want to
allow or-patterns where the branches have different bindings as long as
the expression only uses variables that are bound in every branch?
> This won't work at the moment for two reasons:
>
> * I assume the precedence of 'with' is the same as 'when',
> which is not convenient
Right: "with" scopes over an entire match-case, which might include
or-patterns, just as with "when".
> * the variables in the basic patterns don't agree
>
> The whole point of the above is to switch all the branches
> to normalised variables. At the moment I have to write:
>
> match x with
> | Y x -> f x x
> | X (y,z) -> f y z
Unless I'm mistaken you can write this as
match x with
| Y (y as z)
| X (y,z) -> f y z
Is there some more general case for which this won't work out?
Jeremy.
Brian Hurt
>
> Unless I'm mistaken you can write this as
>
> match x with
> | Y (y as z)
> | X (y,z) -> f y z
>
> Is there some more general case for which this won't work out?
>
I often times want to be able to write code like:
match foo with
| Y (y) with x = 3
| X(x, y) ->
f x y
Brian
skaller
> skaller wrote:
> > On Fri, 2007-06-29 at 15:19 +0100, Jeremy Yallop wrote:
> >> I'm pleased to announce the initial release of `patterns', an OCaml
> >> extension providing general-purposes additions to pattern matching.
> >
> > I want to do this:
> >
> > match x with
> > | Y x with a=x and b=x
> > | X (y,z) with a=y and b=z
> > -> f a b
>
> Interesting. Do you want 'z' to be in scope in the guards ("a=y" etc.)
> but not in the expression ("f a b")? Or do you just generally want to
> allow or-patterns where the branches have different bindings as long as
> the expression only uses variables that are bound in every branch?
Good question. I don't know. In theory, the idea is a
'change of variables' as in a coordinate transformation, so only the
'final' variables should be in scope, i.e. 'z' would not be in scope.
In practice, a suitable syntax needs to be devised which is convenient
to use: a common case would be:
| X with x = 1
| Y x -> f x
and it would be messy to have to write the identity change of variables
in the second branch.. so I'm open to suggestions as to syntax.
> > This won't work at the moment for two reasons:
> >
> > * I assume the precedence of 'with' is the same as 'when',
> > which is not convenient
>
> Right: "with" scopes over an entire match-case, which might include
> or-patterns, just as with "when".
Which is a pain, you can't write:
(
| X
| Y x when f x
| Z x when g x
)
-> ....
[Felix allows nested 'when' clauses but not alternatives .. the latter
due to laziness on my part implementing it]
> > * the variables in the basic patterns don't agree
> >
> > The whole point of the above is to switch all the branches
> > to normalised variables. At the moment I have to write:
> >
> > match x with
> > | Y x -> f x x
> > | X (y,z) -> f y z
>
> Unless I'm mistaken you can write this as
>
> match x with
> | Y (y as z)
> | X (y,z) -> f y z
>
> Is there some more general case for which this won't work out?
Of course! See above. Conceptually you need an arbitrary
change of variables. For example:
| Polar (r, theta) with z = polar r theta
| Cartesian (x,y) with z = cartesian x y
-> f z
As far as I can see this is basically eta-expansion,
known to dummies like me as a 'wrapper function',
which for functions allows you call a function with one
set of variables with a completely different set of variables
by a standard change of variables
The idea is basically that, but 'moved' to the other
side of the -> sign in a pattern match. The above case
can of course be written:
| Polar (r, theta) -> let z = polar r theta in f z
| Cartestian (x,y) -> let z = cartesian x y in f z
but involves duplicating the call to f.
BTW: I'm writing some basic Scheme at the moment and I'm struck
by how much is lost, not having pattern matching -- yet
of course it is almost all just sugar.
BTW2: It also strikes me good syntactic design is a tradeoff
between the tensions of avoiding duplication and gratuitous
invention, retaining localisation (things should be
defined near where they're used), and modularity
(name anything complex).
So for example simple anonymous functions are good
(localisation), let/in is good (factor complexity
but retain localisation) and C++ sucks (loss of
localisation).
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
_______________________________________________
Arnaud Spiwack
clause', it is considered the identity 'with clause'". But I'm not sure
it's that satisfying in practice. (it precisely and accurately adresses
this very case John Skaller is raising, but not the same example with an
additional variable in each constructor...).
A suitable solution for nested guarded patterns could be, instead of
saying "all the branches of the or-pattern must agree on the variable",
to use a less coercive, but more compromising law : "only the variable
common in all the branches of the or-pattern are bound in the match
branch". This sentence uses "branch" far too many times, which makes it
awkward and slighlty evil, but the principle is there :
function
| A x | B t -> %1
Would bind nothing in %1, but still be legal (should raise "unused
variable" warnings though). More interestingly :
function
| C x with z=3 and w=2*x | D z r s v with w = r+s+v -> %2
Would bind z and w only in %2 (without "unused variable" warning this
time, provided %2 contains z and w).
At the moment I'm writing this mail, it sounds like a safe way to
proceed. And to be resemble what Jeremy Yallop was suggesting in his
last mail as well.
PS : Slight variants this solution, which I would consider messier
myself, would be to say that "only the with -clause pattern variables
are considered bound in the branch body", as Skaller suggested. And that
an identity with clause is added "each time it is necessary for the
branch body" (though this is not clear in case of naming conflict) or
"each time is is necessary for all the branches to have the same set of
variables" (plus the "no with is all identities" thingy) which may be
safe as well (but the original one sounds more flexible).
Arnaud Spiwack
skaller a écrit :
_______________________________________________
Jeremy Yallop
> A (too) quick answer could of course be: "in the absence of a 'with
> clause', it is considered the identity 'with clause'". But I'm not sure
> it's that satisfying in practice. (it precisely and accurately adresses
> this very case John Skaller is raising, but not the same example with an
> additional variable in each constructor...).
>
> A suitable solution for nested guarded patterns could be, instead of
> saying "all the branches of the or-pattern must agree on the variable",
> to use a less coercive, but more compromising law : "only the variable
> common in all the branches of the or-pattern are bound in the match
> branch".
This seems like a good rule. I think it should be refined a little,
though. The refinement is: "any variables which occur free in the
expression must be bound in either all or no branches of the pattern".
For example, this should be an error:
let z = 3
let f = function
| A x with z = 10
| B x -> x + z
Without the refinement `f (A 5)' evaluates to 8, which is pretty
confusing (even with an unused variable warning).
Jeremy.
pemore...@gmail.com
project in 1995.
You can find a description in the manual (http://elan.loria.fr/manual-
elan/index-manual.html), page 34.
As fas as I remember, the possibility to write complex nested
disjunctions of assignments is very expressive but makes the code a
bit more difficult to understand.
Pierre-Etienne