Pattern matching does not work like this?

newer
IFL 2009: Third Call for Papers

Magicloud Magiclouds

15 Jul 2009 15 Jul '09

5:57 a.m.

Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error. -- 竹密岂妨流水过山高哪阻野云飞

Show replies by date

minh thu

15 Jul 15 Jul

5:59 a.m.

2009/7/15 Magicloud Magiclouds :

...

Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

++ is a function; you can't pattern-match on that. Cheers, Thu

minh thu

6 a.m.

2009/7/15 minh thu :

...

2009/7/15 Magicloud Magiclouds :

...
Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

++ is a function; you can't pattern-match on that.

But here you can match against (0:1:xs).

Eugene Kirpichov

6:25 a.m.

Technically, the reason is not that (++) is a function, but that it is not a constructor of the [] type. And, not only is it not a constructor, but it also *can't* be one, because the main characteristic of pattern matching in Haskell is that it is (contrary to Prolog's unification) unambiguous (unambiguity of constructors is guaranteed by the semantics of Haskell's algebraic datatypes). If ++ could be pattern matched, what should have been the result of "let (x++y)=[1,2,3] in (x,y)"? 2009/7/15 minh thu :

...

2009/7/15 Magicloud Magiclouds :

...
Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

++ is a function; you can't pattern-match on that.

Cheers, Thu _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Hans Aberg

7:08 a.m.

On 15 Jul 2009, at 12:25, Eugene Kirpichov wrote:

...

If ++ could be pattern matched, what should have been the result of "let (x++y)=[1,2,3] in (x,y)"?

It will branch. In terms of unification, you get a list of substitutions. Hans

Luke Palmer

7:22 a.m.

On Wed, Jul 15, 2009 at 3:08 AM, Hans Aberg wrote:

...

On 15 Jul 2009, at 12:25, Eugene Kirpichov wrote:

If ++ could be pattern matched, what should have been the result of

...
"let (x++y)=[1,2,3] in (x,y)"?

It will branch. In terms of unification, you get a list of substitutions.

f :: [a] -> ([a],[a]) f (x ++ y) = (x,y) If this pattern branches, it could hardly be considered a *function *which takes lists and returns pairs. It would have to return something else. Luke

Hans Aberg

8:30 a.m.

On 15 Jul 2009, at 13:22, Luke Palmer wrote:

...

If ++ could be pattern matched, what should have been the result of "let (x++y)=[1,2,3] in (x,y)"?

It will branch. In terms of unification, you get a list of substitutions.

f :: [a] -> ([a],[a]) f (x ++ y) = (x,y)

For an argument s, any pair (x, y) satisfying s = x ++ y will match. That is, if s = [s_1, ..., s_k], the solutions j = 0, ..., k, x = [s_1, ..., s_j], y = [s_(j+1), ..., s_k]. And for each one, a potentially different value could given. That is, s could produce multiple values.

...

If this pattern branches, it could hardly be considered a function which takes lists and returns pairs. It would have to return something else.

So this would be a multi-valued function, which sometime is useful as a concept. But if the choices are indexed, they can be reduced to a single valued function. Like g(x,y) with the requirement that if x ++ y = x' ++ y', then g(x, y) = g(x', y'). This branching is what would happen if one tries to make a type theory based on sets. (It is possible to implement Horn clauses as unification branching.) The selection of branches correspond to a choice in the proof tree. Hans

Sebastian Fischer

16 Jul 16 Jul

3:21 a.m.

On Jul 15, 2009, at 2:30 PM, Hans Aberg wrote:

...

...
If ++ could be pattern matched, what should have been the result of "let (x++y)=[1,2,3] in (x,y)"?

It will branch. In terms of unification, you get a list of substitutions.

f :: [a] -> ([a],[a]) f (x ++ y) = (x,y)

For an argument s, any pair (x, y) satisfying s = x ++ y will match. That is, if s = [s_1, ..., s_k], the solutions j = 0, ..., k, x = [s_1, ..., s_j], y = [s_(j+1), ..., s_k]. And for each one, a potentially different value could given. That is, s could produce multiple values.

Curry (a Haskell extension with non-determinism) supports exactly that. Sergio Antoy and Michael Hanus: Declarative Programming with Function Patterns available at: <http://www.informatik.uni-kiel.de/~mh/papers/ LOPSTR05.pdf> -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

Andrew Wagner

15 Jul 15 Jul

8:09 a.m.

Err, technically, aren't functions and constructors mutually exclusive? So if something is a function, it's, by definition, not a constructor? On Wed, Jul 15, 2009 at 6:25 AM, Eugene Kirpichov wrote:

...

Technically, the reason is not that (++) is a function, but that it is not a constructor of the [] type.

And, not only is it not a constructor, but it also *can't* be one, because the main characteristic of pattern matching in Haskell is that it is (contrary to Prolog's unification) unambiguous (unambiguity of constructors is guaranteed by the semantics of Haskell's algebraic datatypes).

If ++ could be pattern matched, what should have been the result of "let (x++y)=[1,2,3] in (x,y)"?

2009/7/15 minh thu :

...
2009/7/15 Magicloud Magiclouds :

...
Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

++ is a function; you can't pattern-match on that.

Cheers, Thu _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Miguel Mitrofanov

8:14 a.m.

No. Most constructors are functions, e.g. Just :: a -> Maybe a - a function. On the other hand, Nothing :: Maybe a is a constructor, but not a function. Andrew Wagner wrote:

...

Err, technically, aren't functions and constructors mutually exclusive? So if something is a function, it's, by definition, not a constructor?

On Wed, Jul 15, 2009 at 6:25 AM, Eugene Kirpichov mailto:ekirpichov@gmail.com> wrote:

Technically, the reason is not that (++) is a function, but that it is not a constructor of the [] type.

And, not only is it not a constructor, but it also *can't* be one, because the main characteristic of pattern matching in Haskell is that it is (contrary to Prolog's unification) unambiguous (unambiguity of constructors is guaranteed by the semantics of Haskell's algebraic datatypes).

If ++ could be pattern matched, what should have been the result of "let (x++y)=[1,2,3] in (x,y)"?

2009/7/15 minh thu mailto:noteed@gmail.com>: > 2009/7/15 Magicloud Magiclouds mailto:magicloud.magiclouds@gmail.com>: >> Hi, >> I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code >> could not be compiled, parse error. > > ++ is a function; you can't pattern-match on that. > > Cheers, > Thu > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

-- Eugene Kirpichov Web IR developer, market.yandex.ru http://market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto: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

Felipe Lessa

8:32 a.m.

On Wed, Jul 15, 2009 at 08:09:37AM -0400, Andrew Wagner wrote:

...

Err, technically, aren't functions and constructors mutually exclusive? So if something is a function, it's, by definition, not a constructor?

I guess what Eugene Kirpichov meant was that not being a function (and being a constructor) isn't sufficient, it must also be a constructor of the correct type, e.g. f Nothing = ... f (x:xs) = ... isn't correct, however it pattern matches on constructors only. -- Felipe.

Richard O'Keefe

9:45 p.m.

On Jul 15, 2009, at 9:59 PM, minh thu wrote:

...

2009/7/15 Magicloud Magiclouds :

...
Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

++ is a function; you can't pattern-match on that.

Doesn't matter, it's not trying to. Part of Erlang syntax is that in a pattern [c1,...,cn] ++ P is equivalent to [c1,...,cn|P] For example, wee(X) -> F = fun ([0,1] ++ L) -> L end, F(X). is perfectly legal. The problem might be the "xs", or it might be the "=". Presumably it should be fun ([0,1] ++ Xs) -> ...

Maurício

10:09 a.m.

...

I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

Maybe a small abstract can help, as I once also got confused by that. * First, syntax without operators You can only match on constructors. So, if you have data Test = Test1 String | Test2 Integer | Test3 you can do function (Test1 s) = ... function (Test2 i) = ... function Test3 = ... * Second, syntax with operators Haskell allow constructors made of symbols, but you have to start them with ':', so this is valid: data Test = Test1 String | Integer :** String and then function (Test1 s) = ... function (i :** s) = ... * Third, special syntax Haskell has special syntax for tuples and lists (and something else I forgot?). You can ask information about a name in ghci using ':i <name>', see what it says about (,) and []: data (,) a b = (,) a b data [] a = [] | a : [a] As you can see, (,), [] and : are actually constructors, and you can pattern match on them: function [] = ... function (a:b) = ... function ((:) a b) = ... function (a,b) = ... function ((,) a b) = ... Best, Maurício

Richard O'Keefe

9:56 p.m.

On Jul 15, 2009, at 9:57 PM, Magicloud Magiclouds wrote:

...

Hi, I do not notice this before. "fun ([0, 1] ++ xs) = .." in my code could not be compiled, parse error.

I apologise to everyone for my previous message in this thread. There was a Haskell message in amongst some Erlang messages, and I thought this was an Erlang problem. There are some programming languages, including Erlang, in which <explicit list> ++ <pattern> IS accepted as a <pattern>. Haskell is not one of them. It could be, and there would be no ambiguity in elementary cases, and it would no more involve matching against ++ than n+1 involves matching against +. Since the pattern on the left of the ++ is required to be an explicit list, there is no the slightest question of backtracking or anything more general than ordinary pattern matching. Consider [a,b,c]++xs a:b:c:xs The second is in general shorter (though less clear; it is a real pity that Haskell syntax doesn't include something like Clean's [head:tail], the inconsistency is irritating). It's not the general case that this syntax was invented for, but the case where the list is a string. "abc"++xs 'a':'b':'c':xs One of the arguments advanced against n+k patterns is "which scope should + be looked up in? what if the + in the standard prelude is not in scope?" The same question can be asked about list++tail patterns; what should it mean if the prelude's ++ was not in scope? Programmers who have met "abc"++Xs sometimes turn around and ask for Xs++"abc". Perhaps it is better to keep the camel's nose out of the tent.

5789

Age (days ago)

5790

Last active (days ago)

List overview

Download

13 comments

11 participants

participants (11)

Andrew Wagner
Eugene Kirpichov
Felipe Lessa
Hans Aberg
Luke Palmer
Magicloud Magiclouds
Maurício
Miguel Mitrofanov
minh thu
Richard O'Keefe
Sebastian Fischer