8 Apr 2013 13:11

## 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
```
8 Apr 2013 14:06

### Re: 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

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

8 Apr 2013 15:11

### Re: 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
```
8 Apr 2013 16:06

### Re: 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 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

_______________________________________________

```_______________________________________________
```
8 Apr 2013 16:59

### Re: 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.stolarek <at> 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
>
>         _______________________________________________
>
>
>
> _______________________________________________

--

--
Joachim "nomeata" Breitner
Debian Developer
nomeata <at> debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C
JID: nomeata <at> joachim-breitner.de | http://people.debian.org/~nomeata

```
```_______________________________________________
```
8 Apr 2013 17:53

### Re: Prolog-style patterns

On Mon, Apr 8, 2013 at 7:59 AM, Joachim Breitner wrote:
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 <at> 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
```_______________________________________________
```
9 Apr 2013 13:32

### Re: Prolog-style patterns

```> Also, for some history, this was discussed a while back:
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
```
9 Apr 2013 15:07

### Re: 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
```
9 Apr 2013 15:46

### Re: 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
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 m

Ian
________________________________________
Trstenjak [daniel.trstenjak <at> gmail.com]
Sent: Tuesday, April 09, 2013 9:07 AM

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

_______________________________________________
```
9 Apr 2013 16:34

### Re: 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)
```
9 Apr 2013 16:43

### Re: Prolog-style patterns

```* Malcolm Wallace <malcolm.wallace <at> 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
```
8 Apr 2013 23:07

### Re: Prolog-style patterns

```* Conal Elliott <conal <at> 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
```
9 Apr 2013 09:37

### Re: 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
```
9 Apr 2013 12:27

### Re: Prolog-style patterns

```* Daniel Trstenjak <daniel.trstenjak <at> 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

_______________________________________________
```
9 Apr 2013 13:01

### Re: 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

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
```
9 Apr 2013 14:20

### Re: Prolog-style patterns

```* Daniel Trstenjak <daniel.trstenjak <at> 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
>
>
> 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

_______________________________________________
```
9 Apr 2013 02:07

### Re: 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

Thanks,
Yuras
```
9 Apr 2013 20:42

### Re: 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

(overlap checking for) non-linear patterns in Haskell
looks like an ideal topic  for a submission to the
```
8 Apr 2013 15:18

### Re: 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
> 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

_______________________________________________

```_______________________________________________
```
8 Apr 2013 13:25

### Re: Prolog-style patterns

```On 8 April 2013 21:11, Jan Stolarek <jan.stolarek <at> 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
>
> _______________________________________________

--

--
Ivan Lazar Miljenovic
Ivan.Miljenovic <at> gmail.com
http://IvanMiljenovic.wordpress.com
```
9 Apr 2013 02:48

### Re: 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'.)

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.

that I still love.
```
9 Apr 2013 11:23

### Re: Prolog-style patterns

```Jan Stolarek <jan.stolarek <at> 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.Fairbairn <at> cl.cam.ac.uk

_______________________________________________