Changes between Version 9 and Version 10 of ViewPatternsNew
- Timestamp:
- 07/19/07 03:11:03 (6 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
ViewPatternsNew
v9 v10 31 31 In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against. 32 32 33 To make programming with such interfaces more convenient, we add a new kind of pattern called a ''view pattern''.View patterns permit calling the view function inside the pattern and matching against the result:33 View patterns permit calling the view function inside the pattern and matching against the result: 34 34 {{{ 35 35 size (view -> Unit) = 1 … … 37 37 }}} 38 38 39 In general, a view pattern is written 39 That is, we add a new form of pattern, written 40 40 {{{ 41 41 expression -> pattern … … 47 47 '''Scoping''' for ''expr `->` ''pat: 48 48 * The variables bound by the view pattern are the variables bound by ''pat''. 49 * Any variables in ''expr'' are bound occurrences. 49 * Any variables in ''expr'' are bound occurrences. Variables bound by patterns to the left of a view pattern expression are in scope. For example: 50 50 * In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments. 51 51 {{{ … … 53 53 example f (f -> 4) = True 54 54 }}} 55 * However, pattern variables do not scope over the pattern in which they are bound. 56 {{{ 57 -- doesn't work 58 example :: (String -> Integer, String) -> Bool 59 example (f, f -> 4) = True 55 * Variables can be bound to the left in tuples and data constructors: 56 {{{ 57 example :: ((String -> Integer,Integer), String) -> Bool 58 example ((f,_), f -> 4) = True 60 59 }}} 61 60 … … 80 79 | Cons a (JList a) 81 80 }}} 82 Here we've chosen that the view type only exposes the cons/nil structure one level at a time: the second argument to `Cons` is a join-list ---but that's of course up to the programmer.81 Here we've chosen that the view type only exposes the cons/nil structure one level at a time: the second argument to `Cons` is a join-list, not a view of it---but that's of course up to the programmer. 83 82 84 83 The implementation of the view: … … 117 116 ==== Partial views ==== 118 117 119 Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections inverting each constructor:118 Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections optionally inverting each constructor: 120 119 121 120 {{{ … … 172 171 {{{ 173 172 parsePacket :: ByteString -> ... 174 -- FIXME: requires scoping inside the same pattern.175 173 parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ... 176 174 }}} 177 This parses 3 bits to get the value of `n`, and then parses `n` bits to get the value of `val`. 175 This parses 3 bits to get the value of `n`, and then parses `n` bits to get the value of `val`. Note that this example uses the left-to-right scoping in the inner tuple: the first component is jused in the view expression in the second. 178 176 179 177 ==== N+k patterns ==== … … 222 220 }}} 223 221 224 -- FIXME: loss of sharing? 222 (However, this might cause a loss of sharing.) 225 223 226 224 ==== Iterator Style ==== … … 238 236 239 237 unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 240 unfoldr f (f -> Just (a, b)) = a : unfoldr fb238 unfoldr f (f -> Just (a, unfoldr f -> b)) = a : b 241 239 unfoldr f other = [] 242 240 }}} … … 244 242 == Further Syntactic Extensions == 245 243 246 Next, we describe two syntactic extensions that we mayimplement.244 Next, we describe two further syntactic extensions that we will implement. 247 245 248 246 === Implicit Maybe === … … 272 270 ==== Implicit Tupling ==== 273 271 274 A further syntactic extension would be to have implcit Maybes with implicit tupling , so thatmultiple patterns after the `=>` are implicitly tupled. Then you could write:272 A further syntactic extension would be to have implcit Maybes with implicit tupling: multiple patterns after the `=>` are implicitly tupled. Then you could write: 275 273 {{{ 276 274 size (outArrow => t1 t2) = size t1 + size t2 … … 279 277 === Implicit View Functions === 280 278 281 Total views have one syntactic disadvantage relative to the iterated casethat we started with: you have to repeat the name of the view function in each clause! We now describe a method for eliding the name of the view function.279 Total views have one syntactic disadvantage relative to the iterated-case style definition that we started with: you have to repeat the name of the view function in each clause! We now describe a method for eliding the name of the view function. 282 280 283 281 The idea is that we distinguish a particular type class as a hook into the pattern compiler. The class has the following interface: … … 287 285 }}} 288 286 289 Then, you can leave off the expresion in a view pattern, writing `->` ''pat'', to mean `view -> ` ''pat''. For example:287 Then, you can leave off the expresion in a view pattern, writing (`->` ''pat''), to mean `view -> ` ''pat''. For example: 290 288 {{{ 291 289 size (-> Unit) = 1 … … 310 308 311 309 This way, you don't have to write the name of the view function in each case. However, there is a still a syntactic marker saying that the case isn't an ordinary pattern match, which may be useful in understanding the performance of the code. 310 311 Of course, you can only use one view function for each hidden-type/view-type pair this way, since you can only have one instance of the class. 312 312 313 313 ==== Functional dependencies ==== … … 332 332 333 333 Of course, a programmer can always use all three type classes explicitly; it's just a question of which one should be the default. We plan to try them out before deciding. 334 The downside of these versions is that you can only have one view for a type (when `a` determines `View a`) or you can only use a type as a view of one type (when `b` determines `Hidden b`) with the implicit syntax. 334 335 335 336 == Compilation == 336 337 337 338 View patterns can do arbitrary computation, perhaps expensive. 338 339 339 It's reasonable to expect the compiler to avoid repeated computation when pattern line up in a column, as in `size` at the top of the page. In pattern-guard form, common sub-expression should achieve the same effect, but it's quite a bit less obvious. We should be able to give clear rules for when the avoidance of repeat computation is guaranteed. 340 340 … … 345 345 === Value input feature === 346 346 347 Our proposal has the ''value input'' feature: the view function can be passed parameters; in a function definition, those parameters can mention previous arguments. For example, this permits a view function itself to be passed as an argument, so patterns, in a sense, become first class.347 Our proposal has the ''value input'' feature: the view function can be passed parameters; and those those parameters can mention variables bound by patterns to the left. For example, this permits a view function itself to be passed as an argument, so patterns, in a sense, become first class. 348 348 349 349 === Implicit `Maybe` feature === … … 355 355 Our proposal does not have the ''transparent ordinary patterns'' feature: view patterns are written differently than ordinary patterns. 356 356 There are pros and cons both ways: 357 The advantage of having transparent ordinary patterns is that you can replace a concrete datatype with an abstract type and a view without changing client code. A disadvantage is that view patterns can do arbitrary computation, perhaps expensive, so it's good to have a syntactic marker that some computation beyond ordinary pattern matching may be going on. Another disadvantage is that transparent ordinary patterns require a larger language extension than just a new form of pattern, so that certain names may be declared to be view constructors for a type. We consider our proposal's implicit view syntax `(-> e)` to be a nice compromise between the two alternatives.357 The advantage of having transparent ordinary patterns is that you can replace a concrete datatype with an abstract type and a view without changing client code. A disadvantage is that view patterns can do arbitrary computation, perhaps expensive, so it's good to have a syntactic marker that some computation beyond ordinary pattern matching may be going on. Another disadvantage is that transparent ordinary patterns require a larger language extension than just a new form of pattern, so that certain names may be declared to be view constructors for a type. We consider our proposal's implicit-view-function syntax `(->` ''pat''`)` to be a nice compromise between the two alternatives. 358 358 359 359 === Nesting === 360 360 361 Our proposal has the ''nesting'' feature: view patterns nest inside other patterns, and other patterns nest inside them. Ne xting is perhaps the biggest practical difference between view patterns and pattern guards.361 Our proposal has the ''nesting'' feature: view patterns nest inside other patterns, and other patterns nest inside them. Nesting is perhaps the biggest practical difference between view patterns and pattern guards. 362 362 363 363 === Integration with type classes === … … 366 366 367 367 == Related work == 368 369 === Uses of Views ===370 371 The observations from [http://citeseer.ist.psu.edu/356396.html Okasaki: Breadth-First Numbering - Lessons ... ] suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of.372 373 The abstractional power views offer can also be put to good use when designing data structures, as the following papers show374 375 * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees].376 * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze: A Simple Implementation Technique for Priority Search Queues]377 * The the key idea of [http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz M.Erwig: Inductive Graphs and Functional Graph Algorithms] is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch.378 368 379 369 === [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] === … … 433 423 === [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] === 434 424 435 Active Desctructors (ADs) are defined by a new form of top-level declaration. Our 436 singleton example would look like this: 425 Active Destructors (ADs) are defined by a new form of top-level declaration. 426 427 Where we'd write 428 {{{ 429 sing :: [a] -> a option 430 sing [x] = x 431 }}} 432 The equivalent active destructor would be 437 433 {{{ 438 434 Sing x match [x] … … 443 439 a special form of type to describe them. 444 440 445 The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the 446 new form of type. 441 The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the new form of type. 447 442 448 443 They also introduce a combining form for ADs, to make a kind of and-pattern. For … … 455 450 f ((Head x)@(Tail ys)) = x:x:ys 456 451 }}} 457 Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)` 458 against the argument, binding `x` and `ys` respectively. We can model that with view patterns: 452 Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)` against the argument, binding `x` and `ys` respectively. We can model that with view patterns: 459 453 {{{ 460 454 headV (x:xs) = Just x … … 467 461 }}} 468 462 469 An to duplicating the value is to compose the functions:463 An alternative to duplicating the value is to compose the functions: 470 464 {{{ 471 465 (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c) … … 475 469 f (headV @ tailV -> (x,ys)) = x:x:ys 476 470 }}} 477 This is a little clumsier: the "`@`" combines functions, with a kind of positional 478 binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear 479 that `headV` binds `x` and `tailV` binds `y`. 471 This is a little clumsier: the "`@`" combines functions, with a kind of positional binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear that `headV` binds `x` and `tailV` binds `y`. 480 472 481 473 === [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] === … … 556 548 Reppy & Aiken, TR 92-1290, Cornell, June 1992. 557 549 558 The one way in which pattern synonyms are better than view patterns is that 559 they define by-construction bi-directional maps. Example 550 The one way in which pattern synonyms are better than view patterns is thatn they define by-construction bi-directional maps. Example 560 551 {{{ 561 552 data Term = Var String | Term String [Term] … … 580 571 f (isPlus -> a b) = plus (f a) (f b) 581 572 }}} 582 But perhaps that is not so bad. Pattern synonyms also require a new form of top level declaration; 583 and are much more limited than view patterns (by design they cannot do computation). 573 But perhaps that is not so bad. Pattern synonyms also require a new form of top level declaration; and are much more limited than view patterns (by design they cannot do computation). 584 574 585 575 === [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] === … … 600 590 4) No attempt is made to integrate with Haskell's patterns, the idea is a proposal for an alternative when one needs more than simple patterns. 601 591 602 The examples at the top of this page would look like this with first class patterns:592 The singleton example above would like this: 603 593 {{{ 604 594 f = {%sing n} .-> n+1 … … 639 629 A yet more ambitious scheme is to treat patterns themselves as first class, even though they have free (binding) variables. This is the approach that Barry Jay has taken in his very interesting project on the ''pattern calculus''. His [http://www-staff.it.uts.edu.au/~cbj home page] has more info. 640 630 631 === Uses of Views === 632 633 The observations from [http://citeseer.ist.psu.edu/356396.html Okasaki: Breadth-First Numbering - Lessons ... ] suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of. 634 635 The abstractional power views offer can also be put to good use when designing data structures, as the following papers show 636 637 * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. 638 * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze: A Simple Implementation Technique for Priority Search Queues] 639 * The the key idea of [http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz M.Erwig: Inductive Graphs and Functional Graph Algorithms] is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch. 640
