Re: [Caml-list] Pattern matching over elements at the front of a container

[Luc Maranget <Luc.Maranget@inria.fr>]

> I suppose list decapitation "h1::h2::t" marks the limit in the usefulness vs 
> difficulty tradeoff. Internally, I guess list matching is also based upon 
> data structure's shape, whereas my [|h; ..|] and Richard Jones' "prefix"^str 
> are not, because the data structures are both arrays which are "atomic" in 
> this sense.
We here agree, a pattern describles some immediately accessible
part of some data-structure.

Your ``...'' are sequences (?) they imply additional costs
(BTY one can also consider those for lists , written for instance
... @ [1] @ ... )

I am not saying that all those are bad, they just don't fit the
ML  pattern matching model.


> 
> > > Also, is it not possible to alter the definition and implementation of
> > > OCaml such that the pattern "(a, a)" is treated as "(a, b) when a=b"? Has
> > > this not been done because the "=" is suspect?
> >
> > Just say No (to non-linear patterns) !
> 
> Can you define "non-linear pattern" for me?
Heu, it just means that the same variable can appear twice in a pattern.

> 
> > Basically and you can interpret this by saying << = is suspect >>, this
> > apparently innocent addition is a radical change in semantics.
> 
> Mikael Brockman wrote to me, pointing out that matching this could use "the 
> same unification algorithm as is used in other pattern matching" which sounds 
> like a much better interpretation of the equality to me. Is that not correct 
> because patterns can only contain constant values and cannot be matched 
> against arbitrary values, like expressions or variables? So the pattern 
> matcher does not currently require any notion of equality beyond those of 
> constructors and of values of primitive types?
I am not sure I understand, but you can probably see it that way.

Here is what I meant:
If you consider the underlying model of term rewriting systems,
introducing non-linear patterns change a lot of things. In particular
the Church-Rosser property changes of nature.


This somehow ideological point of view has the following pratical consequences:

Without non-linear patterns...

  The cost of testing a value against a pattern remains linear
  (in pattern size) and involve no other computations than basic
   constructor equality.

  Pattern analysis (unused match case etc.) is simpler.


More generally, pattern matching is such a convenient formalism (and
syntax) that many people ask for more. Unfortunately, apparently
harmless extensions often distroy the simple model of pattern
matching on algebraic data types (standard ML types). An illustration
of my opinion is the fate of Haskell n+k patterns (they are now more
or less deprecated).


I would like to add that there has been research  on extending the power
of pattern matching since pattern matching exists.

They are views, of course, but also matching of XML data, there was
sequences. All those are interesting but all those significantly depart from
ML pattern matching underlying model, which is what ocaml provides at the
moment (+ when guards).



-- Luc Maranget

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners