Dear Haskellers Provoked by a discussion with Don Syme, and after some helpful conversations at POPL, I have finally written up a proposal for adding "view patterns" to Haskell. We've wanted views for a long time, but they have never made it, into GHC at any rate. This proposal is a very lightweight (and hence, I hope, cost-effective) proposal for a view-like mechanism. http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns I'm thinking of implementing it in GHC, so I'd be interested in feedback of the form - how desirable is it to have a feature of this general form? - can this particular proposal be improved? I've made it into a Wiki page on the Haskell Prime site. It's probably premature to treat it as a serious contender for Haskell Prime (unless there is wild enthusiasm), because it hasn't been tried in practice yet, but that seems like the right forum to discuss it. Discussion would best be directed via the open Haskell-Prime mailing list haskell-prime@haskell.org. http://haskell.org/mailman/listinfo/haskell-prime Thanks Simon
Just a quick note In the very first example (function f), the comment should say "f [n]" insteand of "f [x]" In the related work, the "Active Patterns" proposal by Palao et at is missing: http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM I thought this work should be included in the list because, I believe, they were the first to point out that computation should take place before matching, which was not the case in Wadler's and Burton's proposals? They also proposed types for patterns.
On Mon, Jan 22, 2007 at 02:57:27PM +0000, Simon Peyton-Jones wrote:
Dear Haskellers
Provoked by a discussion with Don Syme, and after some helpful conversations at POPL, I have finally written up a proposal for adding "view patterns" to Haskell. We've wanted views for a long time, but they have never made it, into GHC at any rate. This proposal is a very lightweight (and hence, I hope, cost-effective) proposal for a view-like mechanism.
http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns
I'm thinking of implementing it in GHC, so I'd be interested in feedback of the form - how desirable is it to have a feature of this general form? - can this particular proposal be improved?
It looks pretty cool to me, and simple enough to be reasonable. One feature that would be particularly interesting would be to add some sort of annotation mechanism to describe a possible "complete" set of views (with respect to improving warnings about inexhaustive pattern matching). I wonder if you could have something like: data Foo = FooBar Bar | FooBaz Baz foobar :: Foo -> Maybe Bar foobaz :: Foo -> Maybe Baz {-# COMPREHENSIVE_VIEWS Foo : foobar, foobaz #-} which tells the compiler that for any Foo, one of foobar and foobaz will return a non-Nothing result. It'd allow us--at least in the simple views case--to retain the existing level of warnings, and ought also to be useful in somewhat trickier case as well. Another idea is whether the syntax could be extended to indicate a failure to match? This would actually be useful even without views, but it's particularly useful with views (and especially so in the context of the above warnings). I'd imagine something like (with stupidly chosen syntax of !!!) foo (_:_) = True foo _ = False foo' !!![] = True foo' _ = False Here I've defined two identical functions to describe what I mean by "!!!". I didn't gain anything in this case, but might gain some clarity if there are multiple constructors. But more to the point, if we're using views (of the vanilla Maybe-always variety), we could gain some efficiency this way. foo ([], view -> a, []) = foo1 a foo (x, !!! view ->, []) = foo2 x foo (_, view -> a, y) = foo3 a y This isn't a very good example, but the point is I'd like to be able to match on Nothing and get the same benefits you mention about the compiler being assumed to optimize by calling view only once. We could achieve this by reordering the patterns, but I believe (although I failed to come up with one above) that there are sets of pattern matches that aren't reducible in that way, which it'd be nice to be able to express succinctly by matching on failure to match a pattern. Maybe this should be foo (x, view /->, []) = foo2 x or something like that, to indicate failure, that view doesn't match? -- David Roundy Department of Physics Oregon State University
David Roundy wrote:
Another idea is whether the syntax could be extended to indicate a failure to match? This would actually be useful even without views, but it's particularly useful with views (and especially so in the context of the above warnings). I'd imagine something like (with stupidly chosen syntax of !!!)
foo (_:_) = True foo _ = False
foo' !!![] = True foo' _ = False
Here I've defined two identical functions to describe what I mean by "!!!". I didn't gain anything in this case, but might gain some clarity if there are multiple constructors. But more to the point, if we're using views (of the vanilla Maybe-always variety), we could gain some efficiency this way.
foo ([], view -> a, []) = foo1 a foo (x, !!! view ->, []) = foo2 x foo (_, view -> a, y) = foo3 a y
This isn't a very good example, but the point is I'd like to be able to match on Nothing and get the same benefits you mention about the compiler being assumed to optimize by calling view only once. We could achieve this by reordering the patterns, but I believe (although I failed to come up with one above) that there are sets of pattern matches that aren't reducible in that way, which it'd be nice to be able to express succinctly by matching on failure to match a pattern.
Maybe this should be
foo (x, view /->, []) = foo2 x
or something like that, to indicate failure, that view doesn't match?
AFAIU, this would be superseded by the "Possible extension 2" (which I prefer anyway), i.e. drop the requirement that result type must be 'Maybe a'. The 'cost' of explicitly mentioning constructors becomes an asset in this case. For instance, your 2nd example becomes:
foo ([], view -> Just a, []) = foo1 a foo (x, view -> Nothing, []) = foo2 x foo (_, view -> Just a, y) = foo3 a y
Clearer, IMHO. Cheers Ben
Provoked by a discussion with Don Syme, and after some helpful conversations at POPL, I have finally written up a proposal for adding "view patterns" to Haskell. We've wanted views for a long time, but they have never made it, into GHC at any rate. This proposal is a very lightweight (and hence, I hope, cost-effective) proposal for a view-like mechanism.
http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns
It's nicely simple&general, but I find it at the same time disappointing, because a pattern guard would give you almost the same result without much syntactic overhead. I.e. in the above page you give an example with a "regexp" matching function, which is great when you match only against one regexp, but as soon as you try to match against several patterns, it seems you're stuck with either matching each pattern in turn, or resorting to an external lex tool. The way I see views, they should allow you to implement lex/yacc/burg directly. Stefan
Hmm.. this misses one of the major advantages of views IMHO, pattern synonyms, which would let you seamlessly upgrade interfaces to ADTs, which at the moment is cumbersome, you either have to plan from the beginning and use functions instead of pattern matching or create a new, incompatable API. in a few cases, records can also be used. so, oddly enough, the views subset I wanted to see would be something like this
data Term = Var String | Terms [Term] where EmptyTerm = Terms []
now, EmptyTerm can be used in pattern matching and as a normal constructor. The restrictions to the RHS of such declaraions are straightforward, the arguments must be valid, no variables may appear free. irrefutable patterns would be allowed, they would have no effect when using the alias as a constructor, but would have their normal meaning when used as a pattern match. in addition '_' would be allowed, having its normal meaning when used as a pattern match, but becoming 'undefined' when used as a constructor. perhaps this is unrelated to views, but this sort of thing is what I found attractive about the old proposal. John -- John Meacham - ⑆repetae.net⑆john⑈
Simon Peyton-Jones wrote:
http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns
I'm thinking of implementing it in GHC, so I'd be interested in feedback of the form - how desirable is it to have a feature of this general form? - can this particular proposal be improved?
I have several arguments, conveniently structured into sections. Most of them are not in favor of the current proposal, but I'd really like to have views. 1. *Look and feel* The most important feature of views is that they have the same look and feel as ordinary pattern matches. 1.1. *Against "->", pro "?"* With the "->" syntax, f (singleton -> n) does not have the same look and feel as f (Singleton n) The main problem is that in lambda expressions, "->" already expects the free variables on the left. I think that something along the lines of f ($snoc x xs) = ... g ($(bits 3) x bs) = ... is much better. I'd propose to use a simple question mark "?" either before f (?snoc x xs) = ... g (?(bits 3) x xs) = ... , as delimiter f (snoc? x xs) = ... g (bits 3? x xs) = ... or after f (snoc? x xs) = ... g ((bits 3)? x xs) = ... the view function. I currently favor before. The main argument for a question mark is its mnemonic value: eff (why not match snoc? x x-es) is equal to
From now on, this post will use postfix question marks, although my true preference currently fluctuates like the quantum vacuum.
1.2. *View functions are not interchangeable with ordinary pattern matches* This hinders changing a concrete representation to an abstract data type. Of course, the solution is to anticipate the change beforehand and do all pattern matches with view functions: type Stack a = [a] f :: Stack a f (null?) = .. f (pop? x xs) = .. This certainly discourages ordinary pattern matching. In other words, implementing the proposal has considerable impact on ordinary pattern matching (not in semantics but in use). The extension #2 illustrates this: the canonical ordinary pattern match form for (f :: Product -> ...) would be f SmallProd = ... f MediumProd = ... f BigProd = ... With view functions, the canonical form would become f (smallProd?) = f (medProd?) = f (bigProd?) = But because we are used to capital letters, f (prodSize? SmallProd) = f (prodSize? MediumProd) = f (prodSize? BigProd) = suddenly becomes feasible. Due to the tedious repetition of a long identifier (prodSize), I for one will invariable write it out as a case expression f prod = case prodSize prod of SmallProd -> ... MediumProd -> ... BigProd -> ... This can already be done in Haskell98. 2. *Projection to Maybe invariably looses sharing of expensive computations* This is a strong argument against view functions that project everything to Maybe a. Unfortunately, projecting things to Maybe is very compositional. Suppose that data Graph represents a graph and that we want a function g :: Graph -> [...] g (forest? xs) = concatMap g xs g (tree?) = ... g (dag?) = ... These three properties are expensive to calculate but all three only depend on the result of a single depth first search. By projecting teh disjoint sum to several Maybes, the depth first search has to be repeated every time. There is *no way* for the compiler to optimize this because this would mean common subexpression elimination across functions. The proposals from Wadler and Burton et.al. avoid this problem by projecting to a possibly larger sum. In fact, the three view functions arise from function commondfs :: Graph -> (Maybe Forest, Maybe Tree, Maybe DAG) by forest = (\(x,_,_) -> x) . commondsf tree = (\(_,x,_) -> x) . commondsf dag = (\(_,_,x) -> x) . commondsf While it is true that commondfs == forest ** tree ** dag with some join function (**) from category theory, the difference in computational complexity already shows up in the type of the three-fold join: join3 :: forall a b c d . (a -> b, a -> c, a -> d) -> (a -> (b,c,d)) join3 (b,c,d) = b ** c ** d The observation is that the type a does not appear linearly in the triple. 3. *Haskell98 can emulate patterns with view functions, at least as case expressions* Yesterday, i stumbled on the fact that we can have at least case expressions with arbitrary view functions in Haskell98. The trick is to pass from snoc :: [a] -> Maybe ([a],a) to its case expression (dual; continuation passing style; System F inductive type) snoc :: [a] -> forall b . ([a] -> a -> b) -> b -> b Interchanging the first two arguments gives us snoc :: ([a] -> a -> b) -> [a] -> (b -> b) which is perfectly suited for use as higher order pattern because the variables to be bound are only a lambda away. To unleash do-syntax abuse, we need some monad magic newtype Case a b c = Case (a -> b -> b) instance Monad (Case a b) where return x = undefined (~Case x) >>= f = Case $ \a -> (x a) . (y a) where Case y = f undefined Here are two higher order patterns: snoc :: ([a] -> a -> b) -> Case [a] b c snoc f = Case $\xs -> if null xs then id else const $ f (init xs) (last x) empty :: b -> Case [a] b c empty b = Case $\xs -> if null xs then const b else id Our new "case of"-statement is caseof :: a -> Case a b c -> b caseof x (Case c) = c x $ error "match: failed pattern match" Et voilà, defining last in terms of snoc and empty: last' :: [a] -> a last' xs = caseof xs $do snoc $ \ xs x -> x empty $ error "last: empty list" Of course, we have to use "$ \" instead of "?" or "->". 4. *People have different views about views* Judging from the replies so far, everybody seems to expect something completely different from views :) I think we should collect a lot of examples, attribute them to the particular intentions and map the intension to the set of features views might provide. Here is an attempt to start such a list. Intentions: "I need views for ..." * pattern matching on abstract data types (John Meacham, apfelmus) examples: - Okasaki: Breath first numbering - lessons from a small exercise in graph theory view Queue a = Empty | Cons a (Queue a) - ByteStrings view ByteString = [] | Word8 : ByteString - M. Erwig: Inductive Graphs and functional graph algorithms view Graph a b = Empty | Context a b :& Graph a b f (empty?) = ... f (match node? (in,x,out) :& g) = ... - compositing and decomposing Data.Map / Data.Set insert k a (remove k? _ :& map) = (k,a) :& map insert k a (empty?) = (k,a) :& Empty * composable parsing (Stefan Monnier, (SPJ ?)) examples: - parsing bit-streams parsePacket (bits 3 -> n (bits n -> val bs)) = ... * both - magic numbers view Int = Error | Succeded where project 4 = Error project _ = Succeded Features: * value input feature * projection to Maybe VS projection to custom algebraic data type * compositional patterns (Claus Reinke) Subfeatures: * exhaustive pattern matches (David Roundy) probably subsumed by: projection to custom algebraic data type Regards, apfelmus
Simon Peyton-Jones <simonpj@microsoft.com> wrote:
I have finally written up a proposal for adding "view patterns" to Haskell. http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns
I have taken the liberty of correcting a couple of mistakes in your example code (on the wiki). To add to the bikeshed discussion of syntax, did you consider and reject the obvious use of '<-' rather than '->', which would more closely match the pattern guard syntax? For example, f ((name,rest) <- regexp "[a-z]*") = ... does not seem so bad, especially when compared with the equivalent f v | Just (name,rest) <- regexp "[a-z]*" v = ... The form (pat <- expr) would seem to lend itself more naturally to the idea that the 'expr' is applied to an (anonymous) value, yielding a pattern. In contrast, the (expr -> pat) form looks too much like a lambda abstraction, whose form is confusingly opposite: (\pat -> expr). I concur with Claus that one of the major differences between this proposal and pattern guards is the ability to nest view patterns, just like all other existing patterns can be nested. This is perhaps its most interesting feature. Using the '<-' arrow does not seem to obscure this feature too much: parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... vs parsePacket (bits 3 -> (n, (bits n -> val bs))) = ... Possible extension 1: multi-argument view patterns. This looks nasty. The pain of introducing lots of extra types, (which will not appear literally in user code in any case, but that are arbitrarily bounded in number), does not balance against the minor saving of a couple of brackets. Tuples already exist for that purpose. Indeed, the user may wish their particular view to package up the multiple return values in a different data structure, for further pattern deconstruction, e.g. last_two :: [Int] -> (Int,Int) last_two ((x:y:_) <- snoc) = (x,y) Why treat tuples as more special than other ways of packaging multiple values? Possible extension 2: no implicit Maybe. Making the Maybe constructors explicit would even more clearly show how view patterns relate to pattern guards. Indeed, it would be wonderful not to need to wrap the result of the view in a Maybe! Rather than writing a special 'snoc' function with type [a] -> Maybe (a,[a]), I could just use the normal existing 'reverse' function: last_two (Just (x:y:_) <- snoc) = (x,y) === last_two ((x:y:_) <- reverse) = (x,y) Now the semantics of view patterns would be even simpler! In (pat <- expr), after applying the expression to a value, if the inner pattern matches, then the whole pattern matches. That's it. No complications, no implicit monads. Nice. Regards, Malcolm
On Wed, 2007-01-24 at 14:58 +0000, Malcolm Wallace wrote:
To add to the bikeshed discussion of syntax, did you consider and reject the obvious use of '<-' rather than '->', which would more closely match the pattern guard syntax?
Using the '<-' arrow does not seem to obscure this feature too much: parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... vs parsePacket (bits 3 -> (n, (bits n -> val bs))) = ...
The main drawback to this is that we don't get the left to right binders and uses. That is we use 'n' as a variable binder when we extract the 3 bits and then use that later to decide how many bits to extract. With the '<-' form the flow is all back and forth rather than left to right. In Erlang they have these bit/byte patterns: parseIpPacket << version: 4, ihl: 4, tos: 8, ... , optionsAndPadding: tos*5-32, data >> = ... See: "Applications, Implementation and Performance. Evaluation of Bit Stream Programming in Erlang", http://user.it.uu.se/~kostis/Papers/padl07.pdf The point is that it's common for things matched earlier to get used later. Simon's original suggestion allows the left-to-right match & usage that makes this kind of pattern neat. On the other hand I do see the problem with the use of '->' in views and in lambda abstractions. My first thought after seeing the erlang bit/bytestring patterns was something like a mix of pattern guards but with some monad syntax: parseIpPacket packet | do version <- bits 4 ihl <- bits 4 tos <- bits 8 ... optionsAndPadding <- bits (tos*5-32) data <- remainder(?!) = ... The idea is that it looks much like a monad, monadic fail makes the pattern match fail (just like pattern gaurds) and the variables bound in the LHS are available for subsequent patterns (just like pattern gaurds) and also bound in the RHS. However it really is a monad and so can carry some state along (in this case the current bit offset and/or the tail of the bitstring). I guess that means the RHS has to be in the monad. What's different from an ordinary do is that failure in the monad somehow becomes pattern match failure. Don't ask me exactly how that works! :-) It's just what I felt was a reasonably Haskelly translation of the Erlang example. It's not nested patterns of course. I'm not convinced that deeply nested (->) or (<-) style view patterns would make the Erlang bit matching examples look very nice. Afterall it only works for lists in Haskell because of infix patterns and data constructors. Nobody would like writing: foo (Cons x1 (Cons x2 (Cons x3 Nil))) vs foo (x1:x2:x3:[]) Duncan
Duncan Coutts <duncan.coutts@worc.ox.ac.uk> wrote:
Using the '<-' arrow does not seem to obscure this feature too much: parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... vs parsePacket (bits 3 -> (n, (bits n -> val bs))) = ...
The main drawback to this is that we don't get the left to right binders and uses.
Actually, in _both_ forms, the 'n' is bound as a variable to the left of ("before") its usage in a view expression. (But I agree that the '<-' form does not flow as nicely when reading from left to right.)
I guess that means the RHS has to be in the monad. What's different from an ordinary do is that failure in the monad somehow becomes pattern match failure.
I think the proposed extension 2 is really nice, primarily because no monads are required at all. Pattern match failure remains almost exactly as it is in Haskell'98, with no extra Maybe type or MonadPlus context or anything. It is really simple and straightforward. Regards, Malcolm
Let me urge everyone, once more, to conduct this interesting discussion on the haskell-prime mailing list. It's quite open --- anyone can subscribe --- and we'll avoid spamming the main Haskell list. I'll send responses there. Simon | -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Duncan Coutts | Sent: 24 January 2007 15:25 | To: Malcolm Wallace | Cc: haskell@haskell.org | Subject: Re: [Haskell] Views in Haskell | | On Wed, 2007-01-24 at 14:58 +0000, Malcolm Wallace wrote: | | > To add to the bikeshed discussion of syntax, did you consider and reject | > the obvious use of '<-' rather than '->', which would more closely match | > the pattern guard syntax? | | > Using the '<-' arrow does not seem to obscure | > this feature too much: | > parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... | > vs | > parsePacket (bits 3 -> (n, (bits n -> val bs))) = ... | | The main drawback to this is that we don't get the left to right binders | and uses. That is we use 'n' as a variable binder when we extract the 3 | bits and then use that later to decide how many bits to extract. With | the '<-' form the flow is all back and forth rather than left to right. ...etc...
Hello, Is this really a good idea? This seems a lot more relevant to the Haskell mailing list then haskell-prime (at least to me)---it is a language extension that is not implemented, there are a number of different ways to implement it, and we have no significant experience using it. As such, it seems that it is not relevant to haskell-prime, at least in my understanding of the goals of Haskell'. On the other hand, the proposal would probably benefit from the input of the wider audience of the Haskell mailing list, after all, this is an extension to Haskell. Despite the fact that haskell-prime is an open mailing list, there are a number of people who are not subscribed to it because they are not interested in the standardization effort. -Iavor On 1/24/07, Simon Peyton-Jones <simonpj@microsoft.com> wrote:
Let me urge everyone, once more, to conduct this interesting discussion on the haskell-prime mailing list. It's quite open --- anyone can subscribe --- and we'll avoid spamming the main Haskell list.
I'll send responses there.
Simon
| -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Duncan Coutts | Sent: 24 January 2007 15:25 | To: Malcolm Wallace | Cc: haskell@haskell.org | Subject: Re: [Haskell] Views in Haskell | | On Wed, 2007-01-24 at 14:58 +0000, Malcolm Wallace wrote: | | > To add to the bikeshed discussion of syntax, did you consider and reject | > the obvious use of '<-' rather than '->', which would more closely match | > the pattern guard syntax? | | > Using the '<-' arrow does not seem to obscure | > this feature too much: | > parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... | > vs | > parsePacket (bits 3 -> (n, (bits n -> val bs))) = ... | | The main drawback to this is that we don't get the left to right binders | and uses. That is we use 'n' as a variable binder when we extract the 3 | bits and then use that later to decide how many bits to extract. With | the '<-' form the flow is all back and forth rather than left to right.
...etc...
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
I don't mind whether discussion is on Haskell-prime or on Haskell-cafe (I read both). But I don't think it should be on the main Haskell mailing list, which is advertised as relatively low-bandwidth. It's an excellent place to start discussions but if we carried them all though there, a bunch of people would unsubscribe. I think anyway. (That's why we started Haskell-cafe in the first place.) Simon | -----Original Message----- | From: Iavor Diatchki [mailto:iavor.diatchki@gmail.com] | Sent: 24 January 2007 17:50 | To: Simon Peyton-Jones | Cc: Duncan Coutts; Malcolm Wallace; haskell@haskell.org | Subject: Re: [Haskell] Views in Haskell | | Hello, | Is this really a good idea? This seems a lot more relevant to the | Haskell mailing list then haskell-prime (at least to me)---it is a | language extension that is not implemented, there are a number of | different ways to implement it, and we have no significant experience | using it. As such, it seems that it is not relevant to haskell-prime, | at least in my understanding of the goals of Haskell'. On the other | hand, the proposal would probably benefit from the input of the wider | audience of the Haskell mailing list, after all, this is an extension | to Haskell. Despite the fact that haskell-prime is an open mailing | list, there are a number of people who are not subscribed to it | because they are not interested in the standardization effort. | -Iavor | | On 1/24/07, Simon Peyton-Jones <simonpj@microsoft.com> wrote: | > Let me urge everyone, once more, to conduct this interesting discussion on the haskell-prime | mailing list. It's quite open --- anyone can subscribe --- and we'll avoid spamming the main Haskell | list. | > | > I'll send responses there. | > | > Simon | > | > | -----Original Message----- | > | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Duncan | Coutts | > | Sent: 24 January 2007 15:25 | > | To: Malcolm Wallace | > | Cc: haskell@haskell.org | > | Subject: Re: [Haskell] Views in Haskell | > | | > | On Wed, 2007-01-24 at 14:58 +0000, Malcolm Wallace wrote: | > | | > | > To add to the bikeshed discussion of syntax, did you consider and reject | > | > the obvious use of '<-' rather than '->', which would more closely match | > | > the pattern guard syntax? | > | | > | > Using the '<-' arrow does not seem to obscure | > | > this feature too much: | > | > parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... | > | > vs | > | > parsePacket (bits 3 -> (n, (bits n -> val bs))) = ... | > | | > | The main drawback to this is that we don't get the left to right binders | > | and uses. That is we use 'n' as a variable binder when we extract the 3 | > | bits and then use that later to decide how many bits to extract. With | > | the '<-' form the flow is all back and forth rather than left to right. | > | > | > ...etc... | > | > _______________________________________________ | > Haskell mailing list | > Haskell@haskell.org | > http://www.haskell.org/mailman/listinfo/haskell | >
Malcolm Wallace wrote:
Simon Peyton-Jones <simonpj@microsoft.com> wrote:
I have finally written up a proposal for adding "view patterns" to Haskell. http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns
I have taken the liberty of correcting a couple of mistakes in your example code (on the wiki).
To add to the bikeshed discussion of syntax, did you consider and reject the obvious use of '<-' rather than '->', which would more closely match the pattern guard syntax? For example,
f ((name,rest) <- regexp "[a-z]*") = ...
Yes, I'd prefer that too. However, note that while the right arrow syntax looks confusing when used on the left of a case alternative: case e of (regexp "[a-z]*" -> (name,rest)) -> ... the left arrow syntax looks strange when used in a statement: do ((name,rest) <- regexp "[a-z]*") <- readFile "foo" ... although on balance, "pattern on the left of <-" is a better rule than "pattern on the left of -> when it is preceded by \, but on the right otherwise" :-) Being able to distinguish binding from bound occurrences of variables quickly is very important for reading code, I'm worried that there won't be a good syntax for view patterns that gets this right. Personally I remain to be convinced by view patterns. All these examples can be rewritten using either auxiliary functions, pattern guards, monads, or a combination of these. Too much choice is counter-productive.
parsePacket ((n, (val,bs) <- bits n) <- bits 3) = ... vs parsePacket (bits 3 -> (n, (bits n -> val bs))) = ...
are these significantly better than parsePacket p = parseBits p $ do n <- bits 3; val <- bits n; ... given a simple bit-parsing monad? (I just noticed that Duncan posted something similar while I was writing this, oh well). Cheers, Simon
Simon Marlow <simonmarhaskell@gmail.com> wrote:
To add to the bikeshed discussion of syntax, did you consider and reject the obvious use of '<-' rather than '->'
note that while the right arrow syntax looks confusing when used on the left of a case alternative:
case e of (regexp "[a-z]*" -> (name,rest)) -> ...
the left arrow syntax looks strange when used in a statement:
do ((name,rest) <- regexp "[a-z]*") <- readFile "foo" ...
Actually, I don't really find either of those examples confusing - the sense seems to flow nicely. E.g. "first read the file, then apply the regex, then match the resulting pair". What would perhaps be more confusing would be if the arrows were contrary to each other, e.g. do (regexp "[a-z]*" -> (name,rest)) <- readFile "foo" Now that is ugly!
Personally I remain to be convinced by view patterns.
Me too. It is a nice observation of a particular point in the design space, but it is so similar to pattern guards that I would not want to have both in the language. Pattern guards win for me, because there is no implicit Maybe, and computation sharing is explicit. Regards, Malcolm
On Fri, 26 Jan 2007, Malcolm Wallace wrote:
Me too. It is a nice observation of a particular point in the design space, but it is so similar to pattern guards that I would not want to have both in the language. Pattern guards win for me, because there is no implicit Maybe, and computation sharing is explicit.
I'm tempted to suggest this may be akin to issues like let vs where or patterns in bindings vs explicit lambdas - examples where having both adds human-expressibility to the language. -- flippa@flippac.org A problem that's all in your head is still a problem. Brain damage is but one form of mind damage.
Malcolm:
Me too. It is a nice observation of a particular point in the design space, but it is so similar to pattern guards that I would not want to have both in the language. Pattern guards win for me, because there is no implicit Maybe, and computation sharing is explicit.
pattern guards and view patterns are incremental steps on the way from simple patterns to more general ones, from concrete constructors and patterns to abstract ones. I doubt either of them is the final word, so it seems to make sense to have several overlapping intermediate stages available while we figure out what works and what doesn't. At least, I'd give such an incremental, informed-by-practice approach better chances of success than the various paper-only complete redesigns we've seen (or not) in the past. I'm always in two minds about whether or not to use pattern guards, but with view patterns added to the picture, I'd have to do two levels of translation to make do without them (view patterns to pattern guards, pattern guards to MonadPlus). and pattern guards do have an implicit Maybe, just that the embedding/ return/Just is also implicit.. without something at least as structured as Maybe, pattern match failure could only give rise to exceptions. perhaps you are mostly thinking of flat patterns, where the pain of adding explicit Maybes wouldn't be as great as for nested abstract patterns? Philippa:
I'm tempted to suggest this may be akin to issues like let vs where or patterns in bindings vs explicit lambdas - examples where having both adds human-expressibility to the language.
instead of let vs where, I think the situation is more like declarative vs imperative construction of data structures. Imagine some abstract binary list type with cons/nil constructors and consP/nilP pattern functions: - construction (declarative vs imperative) cons 1 (cons 2 nil) vs do { x <- mkNil; y <- mkCons 2 x; z <- mkCons 1 y; return z } - deconstruction/matching (view patterns vs pattern guards) f (consP -> (1, consP -> (2, nilP) )) = True vs f z | (1,y) <- consP z, (2,x) <- consP l, nilP x = True I prefer the nested versions over the linearized ones.. and while pattern guards are easy to replace, the combination of nesting and variable binding is difficult to achieve without syntactic sugar. so my intuition tells me that view patterns are a step in the right direction. as a guess, use of pattern guards will decline, but remain for matching tasks that involve multiple parameters (one could simulate pattern guards via view patterns and extra parameters, but that seems awkward;-). Claus
Hi Simon, (I'm sending this email to the main Haskell list because the discussion continues on it, I haven't seen it moved to the cafe) Below are some comments on the goodness of view patterns in relation to Palao's active patterns, and especially to their "@" combinator. A few people have replied that there's not a lot of "pattern matching" in view patterns. In (expr -> pat), pattern matching occurs in the observer function expr and, when it returns a Just w value, w is matched against pat. But in most cases w is a single value or a tuple of values. In the extension with JustN (N=1..?), w is often just a list of variables, not much of a pattern. Of course, this is so because view patterns are syntactic sugar for observation, that is, optional discrimination (guard) followed by selection of values that are bound to variables. The "failure" case is hidden and nested observation can be expressed more neatly. In other words, expr -> pat is [discriminate + ] select -> variables One problem with this is that discrimination may take place multiple times and selections may be discarded after matching, and both operations could involve elaborate computations. It may be possible for the compiler to optimise when the same function appears in the expr cases (your g function in the very first examples), yet I doubt this can be generalised when the functions are different. A concrete example: the length function for FIFO queues. lengthQ :: Queue q => q a -> Int lengthQ (isEmpty ->) = 0 lengthQ (split -> _ q) = 1 + lengthQ q Function split has been added to the queue interface: class Queue q where empty :: q a isEmpty :: q a -> Bool snoc :: a -> q a -> q a head :: q a -> a tail :: q a -> q a split :: q a -> Maybe2 a (q a) The code for split is given below. Assume a Physicist's implementation of queues (cf. Okasaki's "Purely Functional Data Structures", page 187). Function tail invokes a "check" function that maintains the representation invariant. It makes sense to reuse head and tail in the implementation of split and avoid duplicating work (otherwise split's body would repeat tail's). We'd have: data PhysicistQueue a = PQ [a] Int [a] Int [a] instance Queue PhysicistQueue where ... isEmpty (PQ w lenf f lenr r) = (lenf == 0) ... split q | isEmpty q = Nothing2 otherwise = Just2 (head q) (tail q) Typically, selectors (head, tail) are partial, and a combination of selectors into one, such as split, should be partial. However, to account for pattern-matching failure we make it total (Nothing2 case). Discrimination may take place several times in views: for non-empty queues lengthQ performs an emptiness test twice. There are overlapping cases, and we give up statically checking this cause to the left of the arrow there are different functions. [ASIDE: is it okay that pattern matching failure is represented by so many types: Bool, Maybe, Maybe1, etc? And that it is reified to a value?]. Another problem is that selected stuff may be discarded: for non-empty queues, split calculates a head value (computation), but it is discarded by lengthQ. The compiler cannot help us even if underscores appear to the right of the arrow because computation takes place before matching. Laziness will be of help, but some evaluations to WHNF may take place. In contrast, Palao's "@" combinator is quite handy: lengthQ Empty = 0 lengthQ (Tail t) = 1 + lengthQ t show :: Queue q => q a -> String show Empty = "" show ((Head h)@(Tail t)) = show h ++ show t The Tail active constructor is like invoking tail, and when the head is needed we compose it with the Head active constructor. Head and Tail are partial, the assumption is that pattern matching starts at the Empty case, just like it happens with ordinary pattern matching. The failure is not reified to a value.
Below are some comments on the goodness of view patterns in relation to Palao's active patterns, and especially to their "@" combinator.
The generalization of "@" from as-patterns (var@pat) to and-patterns (pat@pat) seems to be a useful step, especially in combination with using views mostly as observers/selectors - for instance, if views for record selections were defined, one would want to be able to match against/observe several fields without having to match against all of them. The wiki page has a definition of an "@" combinator that works in the pattern functions/data parsing framework, and can be used with view patterns. I don't find it all that clumsy, but it does highlight a limitation of view patterns (view -> pat): they are not first-class entities. The view parts are, and can be composed dynamically (that is what the "@" combinator given there does), but the pattern parts are not, so their composition has to be constructed statically.
A few people have replied that there's not a lot of "pattern matching" in view patterns. In (expr -> pat), pattern matching occurs in the observer function expr and, when it returns a Just w value, w is matched against pat. But in most cases w is a single value or a tuple of values. In the extension with JustN (N=1..?), w is often just a list of variables, not much of a pattern.
I have seen several votes against JustN, none in favour. And if many examples only have a tuple of variables in the pattern part, that is a case of non-exhaustive examples, not a characteristic of view patterns. I was misled by this, too, at first, which is why I have tried to emphasize the value of nested view patterns since. view pattern can be used as observers, in which case the pattern merely binds the observation results to variables, but they can also be used as transformers, in which case the pattern describes a full match of a transformed parameter (or of its subexpressions). in both cases, nested view patterns are likely to arise in practice. Also, there are at least two fractions, one which would like the expr part of view patterns to be nothing but a transformation, with all matching limited to the pattern part, and one which would like the expr part to describe a pattern function with possible match failure, with the pattern part limited to describing matches and variable bindings for the subexpressions (I am in this latter camp;-).
Of course, this is so because view patterns are syntactic sugar for observation, that is, optional discrimination (guard) followed by selection of values that are bound to variables. The "failure" case is hidden and nested observation can be expressed more neatly. In other words,
expr -> pat ... [discriminate + ] select -> variables
while view pattern can be used in this mode, the more general form seems to be: [discriminate abstract constructor +] extract subexpressions -> match subexpressions (more general because the observation form simply ignores some subexpressions and often needs no further matching on the rest)
One problem with this is that discrimination may take place multiple times and selections may be discarded after matching, and both operations could involve elaborate computations.
repeated discrimination arises because pattern functions tend to define refutable patterns, and the compiler may not be able to determine mutual exclusion when the discriminators involve arbitrary boolean expressions. it is, however, quite possible to define pattern functions for irrefutable patterns (no discrimination, only selection) - it would just be up to the programmer to use them wisely.. (ie, irrefutable split *after* refutable empty, but not vice-versa). discarding selections or, more generally, common computations, before going to repeat them in the next match alternative, is a different issue, already mentioned on the wiki page. I suspect it can be dealt with be restructuring the code to expose the sharing, but I am not sure yet about whether that would be so detrimental to readability as to negate the advantages of using view patterns in such cases. Claus
participants (13)
-
apfelmus＠quantentunnel.de -
Benjamin Franksen -
Claus Reinke -
David Roundy -
Duncan Coutts -
Iavor Diatchki -
John Meacham -
Malcolm Wallace -
Pablo Nogueira -
Philippa Cowderoy -
Simon Marlow -
Simon Peyton-Jones -
Stefan Monnier