Re: [Haskell-cafe] Prolog-style patterns
Hi Roman, One issue with it in Haskell is that it'd lead to inconsistent semantics: myEq x x = True is not the same as myEq x y = case y of x - True I don't think that it's inconsistent, because the 'case' defines a new name scope, like the function does for its arguments. Otherwise you would also expect a different behavior for: x = 2 myEq x x = True Greetings, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Jan Stolarek jan.stola...@p.lodz.pl writes: Hi all, consider this simple reimplementation of 'elem' function: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:xs) | x == y= True | otherwise = member y xs If Haskell allowed to write pattern matching similar to Prolog then we could write this function like this: member :: Eq a = a - [a] - Bool member _ [] = False member x (x:_) = True member x (_:xs) = member x xs This kind of pattern matching was considered and rejected by the very first Haskell committee. Others have given some of the reasoning, and I don’t recall the rest so won’t attempt to rehearse them here. What I would like to say (without meaning to attack you personally, Jan) is that we really need to make a rule that this sort of small convenience should never be considered. Every now and a language feature will be invented that really makes a large difference to a large number of programmes (do notation was a prime example), so the language should evolve. But against that, there is considerable value in having the basic syntax remain unchanged for as long as possible. I don’t know how to formulate it formally, but the rule should be something like, unless a new feature shortens programmes that can use it by a significant factor, it shouldn’t be included. -- Jón Fairbairn jon.fairba...@cl.cam.ac.uk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
* Daniel Trstenjak daniel.trsten...@gmail.com [2013-04-09 09:37:46+0200] Hi Roman, One issue with it in Haskell is that it'd lead to inconsistent semantics: myEq x x = True is not the same as myEq x y = case y of x - True I don't think that it's inconsistent, because the 'case' defines a new name scope, like the function does for its arguments. One should interpret consecutive function arguments as being in the nested scopes, too, rather than in one flat scope. Otherwise, in x = 2 f x ((x ==) - True) = True the 'x' in the view pattern would refer to the global x, rather than the function parameter. (And it would, indeed, if you swap the patterns.) The same applies to scoped type variables. (Haskell2010 does not have either of these extensions, so there the two interpretations — nested scopes and one flat scope — are equivalent.) Otherwise you would also expect a different behavior for: x = 2 myEq x x = True In fact, lots of Haskell newcomers are surprised that f 10 = 42 is not the same as n = 10 f n = 42 And this proposal further reinforces the impression that pattern-matching against a bound variable is interpreted as an equality test. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi Roman, In fact, lots of Haskell newcomers are surprised that f 10 = 42 is not the same as n = 10 f n = 42 Well, yes, at the beginning I've been also surprised about this. But allowing this seems to be even more error prone, because now you could bind function arguments to values by just importing a module. module Foo where n = 10 module Bar where import Foo f n = 42 By constraining this binding to only the current module you would just add an other inconsistency. Greetings, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Also, for some history, this was discussed a while back: http://www.mail-archive.com/haskell@haskell.org/msg03721.html Thanks for pointing me to earlier discussions on this subject - they are enlightening :) One particular argument against seems to be very convincing to me: From a language design point of view, it should be noted that turning non-left linear patterns into ones with == guards elevates the class Eq to built-in status - but the compiler has no semantic control over it. I see there are many things I didn't consider (and many more that I don't even understand). So is there some recommended reading on the subject of linear patterns? Most of all I'm wondering why they are called linear? Regarding the possibility of making accidental mistakes during refactoring etc. This could be implemented as a language extension, requiring explicit LANGUAGE pragma. So people using it would know they have semantics slightly changed and need to be aware that there is a possibility of making these kind of mistakes. Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
* Daniel Trstenjak daniel.trsten...@gmail.com [2013-04-09 13:01:07+0200] Hi Roman, In fact, lots of Haskell newcomers are surprised that f 10 = 42 is not the same as n = 10 f n = 42 Well, yes, at the beginning I've been also surprised about this. But allowing this seems to be even more error prone, because now you could bind function arguments to values by just importing a module. Oh, don't get me wrong — I'd never actually suggest that semantics. Just saying that allowing one and not other would confuse the newcomers about how pattern matching actually works. So I prefer to stay on the simple and consistent side. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi Jan, On Tue, Apr 09, 2013 at 01:32:33PM +0200, Jan Stolarek wrote: Thanks for pointing me to earlier discussions on this subject - they are enlightening :) One particular argument against seems to be very convincing to me: From a language design point of view, it should be noted that turning non-left linear patterns into ones with == guards elevates the class Eq to built-in status - but the compiler has no semantic control over it. Yes, I can see the point, but in the case of Haskell with its ability to automatically derive the Eq instance, there's some kind of semantic control, and if an user writes a nonsense Eq instance, than he just really asks for some hurting ;). Regarding the possibility of making accidental mistakes during refactoring etc. This could be implemented as a language extension, requiring explicit LANGUAGE pragma. So people using it would know they have semantics slightly changed and need to be aware that there is a possibility of making these kind of mistakes. I'm a bit torn between all these GHC extensions. If your code doesn't compile, did you really made a mistake or just forgot to include a GHC extension ... But I also have the feeling, that the extension perhaps might not be worth it, because the difference between foo x x = ... and foo x y | x == y = ... is just IMHO too small. Greetings, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
I am somewhat skeptical of this extension; guards seem to work, and while I use syntax extensions somewhat liberally I am not certain this provides enough benefit to restrict code to GHC. I used it extensively in Erlang, but I find myself doing much less pattern matching in Haskell. That said, I am unconvinced by most of the arguments against it. Accidental variable collisions from refactoring would usually produce a type error or a partial function warning, and in any event I have never seen Erlang programmers complaining about this feature causing problems (and Haskell has far better compile-time tools for identifying its misuse). As far as the use of Eq goes, Eq is already enshrined in pattern matching by pattern matching against literals. And yes, with OverloadedStrings you can pattern match against anything with an IsString instance. If a type has a nonsensical Eq instance, I do not think that the programmer is any more likely to absentmindedly try `f x x = ` than the equivalent `f x y | x == y =`. Bad Eq instances have enough pitfalls already that I do not see much problem with adding another. Ian From: haskell-cafe-boun...@haskell.org [haskell-cafe-boun...@haskell.org] on behalf of Daniel Trstenjak [daniel.trsten...@gmail.com] Sent: Tuesday, April 09, 2013 9:07 AM To: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Prolog-style patterns Hi Jan, On Tue, Apr 09, 2013 at 01:32:33PM +0200, Jan Stolarek wrote: Thanks for pointing me to earlier discussions on this subject - they are enlightening :) One particular argument against seems to be very convincing to me: From a language design point of view, it should be noted that turning non-left linear patterns into ones with == guards elevates the class Eq to built-in status - but the compiler has no semantic control over it. Yes, I can see the point, but in the case of Haskell with its ability to automatically derive the Eq instance, there's some kind of semantic control, and if an user writes a nonsense Eq instance, than he just really asks for some hurting ;). Regarding the possibility of making accidental mistakes during refactoring etc. This could be implemented as a language extension, requiring explicit LANGUAGE pragma. So people using it would know they have semantics slightly changed and need to be aware that there is a possibility of making these kind of mistakes. I'm a bit torn between all these GHC extensions. If your code doesn't compile, did you really made a mistake or just forgot to include a GHC extension ... But I also have the feeling, that the extension perhaps might not be worth it, because the difference between foo x x = ... and foo x y | x == y = ... is just IMHO too small. Greetings, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
On 9 Apr 2013, at 14:46, Sturdy, Ian wrote: As far as the use of Eq goes, Eq is already enshrined in pattern matching by pattern matching against literals. Not true. Pattern-matching literals explicitly avoids any use of Eq. Demonstration: data Foo = Foo | Bar instance Eq Foo where _ == _ = True isFoo Foo = True isFoo Bar = False main = do print (isFoo Bar) print (Foo==Bar) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
* Malcolm Wallace malcolm.wall...@me.com [2013-04-09 15:34:01+0100] On 9 Apr 2013, at 14:46, Sturdy, Ian wrote: As far as the use of Eq goes, Eq is already enshrined in pattern matching by pattern matching against literals. Not true. Pattern-matching literals explicitly avoids any use of Eq. Demonstration: data Foo = Foo | Bar instance Eq Foo where _ == _ = True isFoo Foo = True isFoo Bar = False main = do print (isFoo Bar) print (Foo==Bar) I think he meant numeric literals. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Yuras Shumovich shumovichy at gmail.com writes: Will not it be a nightmare to implement and maintain checker for overlapping/unused clauses for non-linear patterns? For sure it does not look straightforward. Note that there are some results and algorithms for non-linear patterns, cf. this short survey by S. Tison: Tree Automata, (Dis-)Equality Constraints and Term Rewriting: What's New? http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=3140 and some background in Tree automata with constraints (esp. Sec. 4.4.5) http://tata.gforge.inria.fr/chap4.php (advertisement starts here) (overlap checking for) non-linear patterns in Haskell looks like an ideal topic for a submission to the Haskell and Rewriting workshop http://www.imn.htwk-leipzig.de/HART2013/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Prolog-style patterns
Hi all, consider this simple reimplementation of 'elem' function: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:xs) | x == y= True | otherwise = member y xs If Haskell allowed to write pattern matching similar to Prolog then we could write this function like this: member :: Eq a = a - [a] - Bool member _ [] = False member x (x:_) = True member x (_:xs) = member x xs The meaning of pattern in the second equation is match this equation if the first argument equals to head of the list. Many times I have found myself instinctively writing patterns in this way, only to get a compilation error. I was thinking about implementing language extension for GHC that would allow to write Prolog-style patterns. Would there be an interest in such an extension? Also, if I missed something obvious please let me know. Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
On 8 April 2013 21:11, Jan Stolarek jan.stola...@p.lodz.pl wrote: Hi all, consider this simple reimplementation of 'elem' function: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:xs) | x == y= True | otherwise = member y xs If Haskell allowed to write pattern matching similar to Prolog then we could write this function like this: member :: Eq a = a - [a] - Bool member _ [] = False member x (x:_) = True member x (_:xs) = member x xs The meaning of pattern in the second equation is match this equation if the first argument equals to head of the list. Many times I have found myself instinctively writing patterns in this way, only to get a compilation error. I was thinking about implementing language extension for GHC that would allow to write Prolog-style patterns. Would there be an interest in such an extension? Also, if I missed something obvious please let me know. My initial take on this is that such capabilities would be too easy to mis-use accidentally; e.g. refactoring and changing variable names, thus causing patterns to match when you don't mean them to. Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com http://IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi, Jan Stolarek wrote: If Haskell allowed to write pattern matching similar to Prolog then we could write this function like this: member :: Eq a = a - [a] - Bool member _ [] = False member x (x:_) = True member x (_:xs) = member x xs The meaning of pattern in the second equation is match this equation if the first argument equals to head of the list. You can achieve something similar with the ViewPatterns language extension. See http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#view-patterns and http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns. member _ [] = False member x (((x ==) - True) : _) = True member x (_ : xs) = member x xs or member _ [] = False member x ((compare x - EQ) : _) = True member x (_ : xs) = member x xs Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
You can achieve something similar with the ViewPatterns language extension. member _ [] = False member x (((x ==) - True) : _) = True member x (_ : xs) = member x xs Hi Tillmann, there are a couple of ways to achieve this in Haskell, for example using guards: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:_) | x == y = True member y (_:xs) = member y xs The goal of my proposal is to provide a concise syntax, whereas ViewPatterns are very verbose and guards are slightly verbose. I want something simple and something that is very intuitive if you've programmed in Prolog :) Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi Jan, On one hand, I've never really needed this. On the other hand, it looks like a nice syntaxic sugar addition, so if you implemented this I would probably give it a try. David. 2013/4/8 Jan Stolarek jan.stola...@p.lodz.pl You can achieve something similar with the ViewPatterns language extension. member _ [] = False member x (((x ==) - True) : _) = True member x (_ : xs) = member x xs Hi Tillmann, there are a couple of ways to achieve this in Haskell, for example using guards: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:_) | x == y = True member y (_:xs) = member y xs The goal of my proposal is to provide a concise syntax, whereas ViewPatterns are very verbose and guards are slightly verbose. I want something simple and something that is very intuitive if you've programmed in Prolog :) Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi Jan, What you're suggesting is called non-linear patterns, and it's a perfectly sensible, well-defined feature in a language with pattern-matching. As you point out, non-linearity allows for more direct succinct programming. I've often wished for this feature when writing optimizations on data types, especially for syntactic types (languages). As Ivan mentioned, there is some danger that people may accidentally a non-linear pattern accidentally, and perhaps the early Haskell designers chose the linearity restriction out of this worry. The importance of such dangers is a subjective call, and certainly not one carried out consistently in Haskell. Consider, for instance, the choice that let where bindings are recursive by default in Haskell, unlike ML and Lisp. I like this choice, but I can understand objections that it leads to accidental recursions, especially for non-functions. -- Conal On Mon, Apr 8, 2013 at 6:11 AM, Jan Stolarek jan.stola...@p.lodz.pl wrote: You can achieve something similar with the ViewPatterns language extension. member _ [] = False member x (((x ==) - True) : _) = True member x (_ : xs) = member x xs Hi Tillmann, there are a couple of ways to achieve this in Haskell, for example using guards: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:_) | x == y = True member y (_:xs) = member y xs The goal of my proposal is to provide a concise syntax, whereas ViewPatterns are very verbose and guards are slightly verbose. I want something simple and something that is very intuitive if you've programmed in Prolog :) Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi, I believe one problem with non-linear patterns would be that the compiler has to figure out what notion of equality you want here. An obvious choice is (==), but the Eq instances might not do what you want. Using pattern guards or view patterns explicates this choice. Also, without an explicit call to == the cost model of such a function definition might be harder to see; an innocent looking change to the patterns of a function could cause a considerable amount of extra work if == is expensive. Greetings, Joachim Am Montag, den 08.04.2013, 07:06 -0700 schrieb Conal Elliott: Hi Jan, What you're suggesting is called non-linear patterns, and it's a perfectly sensible, well-defined feature in a language with pattern-matching. As you point out, non-linearity allows for more direct succinct programming. I've often wished for this feature when writing optimizations on data types, especially for syntactic types (languages). As Ivan mentioned, there is some danger that people may accidentally a non-linear pattern accidentally, and perhaps the early Haskell designers chose the linearity restriction out of this worry. The importance of such dangers is a subjective call, and certainly not one carried out consistently in Haskell. Consider, for instance, the choice that let where bindings are recursive by default in Haskell, unlike ML and Lisp. I like this choice, but I can understand objections that it leads to accidental recursions, especially for non-functions. -- Conal On Mon, Apr 8, 2013 at 6:11 AM, Jan Stolarek jan.stola...@p.lodz.pl wrote: You can achieve something similar with the ViewPatterns language extension. member _ [] = False member x (((x ==) - True) : _) = True member x (_ : xs) = member x xs Hi Tillmann, there are a couple of ways to achieve this in Haskell, for example using guards: member :: Eq a = a - [a] - Bool member _ [] = False member y (x:_) | x == y = True member y (_:xs) = member y xs The goal of my proposal is to provide a concise syntax, whereas ViewPatterns are very verbose and guards are slightly verbose. I want something simple and something that is very intuitive if you've programmed in Prolog :) Janek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Joachim nomeata Breitner Debian Developer nome...@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nome...@joachim-breitner.de | http://people.debian.org/~nomeata signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
On Mon, Apr 8, 2013 at 7:59 AM, Joachim Breitner m...@joachim-breitner.dewrote: Hi, I believe one problem with non-linear patterns would be that the compiler has to figure out what notion of equality you want here. An obvious choice is (==), but the Eq instances might not do what you want. Using pattern guards or view patterns explicates this choice. What other types of equality would be possibilities? Also, for some history, this was discussed a while back: http://www.mail-archive.com/haskell@haskell.org/msg03721.html Erlang programmers have this feature without shooting themselves in the foot too often. That said, I'm happy without it. Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
This is a recurring theme, see also here: http://www.haskell.org/pipermail/haskell-cafe/2009-May/061498.html On 8 April 2013 16:53, Tom Murphy amin...@gmail.com wrote: Also, for some history, this was discussed a while back: http://www.mail-archive.com/haskell@haskell.org/msg03721.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
* Conal Elliott co...@conal.net [2013-04-08 07:06:17-0700] What you're suggesting is called non-linear patterns, and it's a perfectly sensible, well-defined feature in a language with pattern-matching. One issue with it in Haskell is that it'd lead to inconsistent semantics: myEq x x = True is not the same as myEq x y = case y of x - True IINM, in Erlang they have non-linear patterns, and no name shadowing, to be consistent. Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
Hi, On Mon, 2013-04-08 at 07:06 -0700, Conal Elliott wrote: What you're suggesting is called non-linear patterns, and it's a perfectly sensible, well-defined feature in a language with pattern-matching. As you point out, non-linearity allows for more direct succinct programming. I've often wished for this feature when writing optimizations on data types, especially for syntactic types (languages). AFAIK pattern-match overlap checking is well defined for linear patterns, but it is not fully implemented and buggy in ghc (I found ~10 open tickets, most of them are pretty old). Will not it be a nightmare to implement and maintain checker for overlapping/unused clauses for non-linear patterns? We already have a number of language extensions without good warnings (and even worse -- with incorrect warnings): view patterns, overloaded literals, GADTs, etc. Thanks, Yuras ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Prolog-style patterns
There is no fundamental problem with non-linear patterns using ==. (The functional logic programming world long ago generalised the idea of unification to 'narrowing'.) There _is_ a technical problem in Haskell about whether the == here is necessarily the one from the Prelude or whether it might be a different == that is in scope: what would import Prelude hiding (Eq) x == y = x y member x (x:_ ) = True member x (_:ys) = member x ys member _ [] = False mean? What, if anything, would it mean when no == is in scope? This is something that could be sorted out with good will. For example, you could say that it is a compile-time error if this notation is used and Prelude.== is not in scope. But since guards make the linear pattern restriction less poctalgic than it is in say ML, people have found other maddened grizzly bears to stun first. We had similar questions about n+k patterns, a feature that I still love. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
