From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA12720; Mon, 28 Jun 2004 14:50:56 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA12709 for ; Mon, 28 Jun 2004 14:50:55 +0200 (MET DST) Received: from beaune.inria.fr (beaune.inria.fr [128.93.8.3]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i5SCosSH012089 for ; Mon, 28 Jun 2004 14:50:54 +0200 Received: by beaune.inria.fr (8.8.8/1.1.22.3/14Sep99-0328PM) id OAA0000030561; Mon, 28 Jun 2004 14:50:53 +0200 (MET DST) Date: Mon, 28 Jun 2004 14:50:53 +0200 From: Luc Maranget To: Jon Harrop Cc: caml-list Subject: Re: [Caml-list] Pattern matching over elements at the front of a container Message-ID: <20040628145053.A29706@beaune.inria.fr> References: <200406261215.26971.postmaster@jdh30.plus.com> <20040628095709.B17827@beaune.inria.fr> <200406281301.01048.postmaster@jdh30.plus.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <200406281301.01048.postmaster@jdh30.plus.com>; from postmaster@jdh30.plus.com on Mon, Jun 28, 2004 at 01:01:00PM +0100 X-Miltered: at concorde with ID 40E0142E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 usefulness:01 tradeoff:01 jones':01 model:01 non-linear:01 non-linear:01 unification:01 matcher:01 model:01 haskell:01 arrays:01 semantics:01 ocaml:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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