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

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

[Jon Harrop]

I'm currently storing stuff and things in a list. The ability to pattern match 
over the first element or two using a succinct notation is, of course, nifty. 
However, I'd like to replace my list with some other container, maybe an 
array, maybe something of my own creation. What's the easiest way to keep my 
ability to pattern match over the first few elements at the front of the 
container? I could try to extract the first couple of elements and match over 
a 2-tuple of "element option"s. Can a lazily evaluated stream help? How 
expensive is this in terms of performance?

In the case of lists, you can match against the first two elements using the 
pattern "a::b::_". As the "_" is not bound in the corresponding expression, 
an equivalent notation could be invented for arrays in this case. Is this 
feasible? Would anyone else find this useful?

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?

Cheers,
Jon.

-------------------
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

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

[skaller]

On Sat, 2004-06-26 at 21:15, Jon Harrop wrote:

> 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?


Also sometimes it would be nice to be able to introduce 
variables in patterns:

| (a,_,1) with b = 1 | (a,b,0) ->


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

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

[Richard Jones]

Also, being able to pattern match on substrings would be useful, if a
notation could be introduced for it.  Something like:

match str with
  "prefix" ^ str -> ...

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
PTHRLIB is a library for writing small, efficient and fast servers in C.
HTTP, CGI, DBI, lightweight threads: http://www.annexia.org/freeware/pthrlib/

-------------------
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

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

[William Lovas]

On Sun, Jun 27, 2004 at 11:11:24AM +0100, Richard Jones wrote:
> 
> Also, being able to pattern match on substrings would be useful, if a
> notation could be introduced for it.  Something like:
> 
> match str with
>   "prefix" ^ str -> ...

It seems like all of these requests are really just asking for a generic
method for defining different ways of pattern matching data types.  After
hearing about why `eqtype' isn't right for O'Caml, i'd doubt any of these
ad-hoc pattern matching transformations would be either -- support for a
mechanism like views [1] would be better.  Which probably means "not
anytime soon" :)

cheers,
William

[1] http://www.haskell.org/development/views.html

-------------------
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

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

[Luc Maranget]

Hello,
> 
> I'm currently storing stuff and things in a list. The ability to pattern match 
> over the first element or two using a succinct notation is, of course, nifty. 
> However, I'd like to replace my list with some other container, maybe an 
> array, maybe something of my own creation. What's the easiest way to keep my 
> ability to pattern match over the first few elements at the front of the 
> container? I could try to extract the first couple of elements and match over 
> a 2-tuple of "element option"s. Can a lazily evaluated stream help? How 
> expensive is this in terms of performance?
Well, have a try, you may pay a little in performance, most of the time it
does not matter.


> 
> In the case of lists, you can match against the first two elements using the 
> pattern "a::b::_". As the "_" is not bound in the corresponding expression, 
> an equivalent notation could be invented for arrays in this case. Is this 
> feasible? Would anyone else find this useful?
It is certainly feasible, whether it is worth including in the compiler is debatable...


> 
> 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) !
Basically and you can interpret this by saying << = is suspect >>, this apparently innocent
addition is a radical change in semantics.


> 
> Cheers,
> Jon.
> 
> -------------------
> 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

-- 
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

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

[Jon Harrop]

On Monday 28 June 2004 08:57, Luc Maranget wrote:
> > In the case of lists, you can match against the first two elements using
> > the pattern "a::b::_". As the "_" is not bound in the corresponding
> > expression, an equivalent notation could be invented for arrays in this
> > case. Is this feasible? Would anyone else find this useful?
>
> It is certainly feasible, whether it is worth including in the compiler is
> debatable...

Yes, I can see what William Lovas meant about these being "ad-hoc" forms of 
pattern matching. These ideas came up while I was writing an interpreter for 
a host language which supports very exotic pattern matching. However, its 
pattern matcher has an unspecified (and often very high!) complexity, so 
apparently simple pieces of code fail to terminate on reasonable input before 
my patience runs out. This is clearly undesirable.

I thought my idea of using something like [|h1; h2; ..|] was rather nice, 
because it works in finite time in the limit of infinite input-array size, 
but it is ad-hoc: why not [|..; h2; h1|] then?

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.

> > 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?

> 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?

Cheers,
Jon.

-------------------
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

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

[Luc Maranget]

> 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

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

[Jon Harrop]

On Monday 28 June 2004 13:50, Luc Maranget wrote:
> ...
> Your ``...'' are sequences (?) they imply additional costs
> (BTY one can also consider those for lists , written for instance
> ... @ [1] @ ... )

I was working on the implicit assumption that bindings could only appear at 
the ends of the array and, therefore, pattern matching (e.g. [|h; ..|], [|..; 
h|] or [|h1; ..; h2|]) can all be guaranteed to be O(1) because they equate 
to, for example, "if Array.length a>1 then ..." with a binding for h 
equivalent to "let h=Array.get a 1 in ...". This seems (to me) to be an 
elegant equivalent to cons on lists although, of course, you can't access the 
tail in O(1) in the case of an array (hence I'm not allowing it to be named) 
and you can't reverse the meaning of the cons in O(1) on a list. I wasn't 
suggesting that something like [|..; h1; ..; h2; ..|] be allowed.

I'll swat up on the rest (e.g. the Church-Rosser property) before replying, 
but I think I understand and agree with what you're saying.

Cheers,
Jon.

-------------------
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