[Haskell-cafe] Prolog-style patterns

[Jan Stolarek]

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
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ivan Lazar Miljenovic]

On 8 April 2013 21:11, Jan Stolarek <jan.st...@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
> Haskel...@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

--
Ivan Lazar Miljenovic
Ivan.Mi...@gmail.com
http://IvanMiljenovic.wordpress.com

[Tillmann Rendel]

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

[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

[David Virebayre]

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.st...@p.lodz.pl>

[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

[Joachim Breitner]

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

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

[Tom Murphy]

On Mon, Apr 8, 2013 at 7:59 AM, Joachim Breitner <ma...@joachim-breitner.de> 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/has...@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

[Stephen Tetley]

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 <ami...@gmail.com> wrote:

>
> Also, for some history, this was discussed a while back:
> http://www.mail-archive.com/has...@haskell.org/msg03721.html
>

[Roman Cheplyaka]

* 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

[Yuras Shumovich]

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

[Richard A. O'Keefe]

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.

[Daniel Trstenjak]

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

[Jon Fairbairn]

Jan Stolarek <jan.st...@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.Fa...@cl.cam.ac.uk

[Roman Cheplyaka]

* Daniel Trstenjak <daniel.t...@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

[Daniel Trstenjak]

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

[Jan Stolarek]

> Also, for some history, this was discussed a while back:
> http://www.mail-archive.com/has...@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.

[Roman Cheplyaka]

* Daniel Trstenjak <daniel.t...@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

[Daniel Trstenjak]

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

[Sturdy, Ian]

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-ca...@haskell.org [haskell-ca...@haskell.org] on behalf of Daniel Trstenjak [daniel.t...@gmail.com]
Sent: Tuesday, April 09, 2013 9:07 AM
To: haskel...@haskell.org
Subject: Re: [Haskell-cafe] Prolog-style patterns

[Malcolm Wallace]

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)

[Roman Cheplyaka]

* Malcolm Wallace <malcolm...@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

[Johannes Waldmann]

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/

[Peter Selinger]

I don't think the prelude thing is really a problem. Note that the Eq class
is already used by some parts of the pattern matching mechanism anyway.
Consider the following example, where we define the integers modulo 2 as a
copy of the ordinary integers, just with a non-standard equality:

newtype Z2 = Z2 Int

instance Eq Z2 where
  Z2 x == Z2 y = (x-y) `mod` 2 == 0

instance Num Z2 where
  Z2 x + Z2 y = Z2 (x+y)
  Z2 x * Z2 y = Z2 (x*y)
  Z2 x - Z2 y = Z2 (x-y)
  negate (Z2 x) = Z2 (negate x)
  fromInteger x = Z2 (fromInteger x)
  abs (Z2 x) = Z2 (abs x)
  signum (Z2 x) = Z2 (signum x)

myfunc 0 = "0"
myfunc 1 = "1"

main =
  putStrLn (myfunc (Z2 2))

The output, naturally, is "0". Haskell will not allow you to hide (Eq) and
define your own (==) function in this case - the pattern matching always
uses GHC.Classes.Eq regardless of whether it is in scope or not.
It would stand to reason to use the same behavior for non-linear patterns.

[Peter Selinger]

I realize why non-linear patterns can sometimes lead to confusing errors if they are used unintentionally. Nevertheless, I wrote a lot of lines of code like the following today:

peephole (p, H j1 : ZZ j2 k1 : H k2 : H j3 : ZZ j4 k3 : H k4 : ZZ i1 j5 : H j6 : H i2 : ZZ i3 j7 : H j8 : ZZ j9 k5 : H k6 : H j10 : ZZ i4 j11 : H j12 : H i5 : ZZ i6 j13 : ZZ j14 k7 : H k8 : H j15 : ZZ j16 k9 : H j17 : H i7 : ZZ i8 j18 : H i9 : t)
  | equal [i1,i2,i3,i4,i5,i6,i7,i8,i9]
    && equal [j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12,j13,j14,j15,j16,j17,j18]
    && equal [k1,k2,k3,k4,k5,k6,k7,k8,k9] =
    ...

Here, a non-linear pattern language extension sure would have come in handy - the code, as it is written, is far more error-prone in this case (did I remember to include all variables?). The use of a custom "equal" function (to check if all members of a list are equal) helps to make the tests as short as possible, but they are still very cumbersome.

I'm not arguing that non-linear patterns should be part of standard Haskell. But a language extension would be nice.