Changes between Version 11 and Version 12 of ViewPatternsNew


Ignore:
Timestamp:
Jul 19, 2007 10:32:38 AM (8 years ago)
Author:
danl
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatternsNew

    v11 v12  
    1 [[PageOutline]]
    21= View patterns: lightweight views for Haskell =
    32
    43This page describes a lightweight proposal for adding views to Haskell. '''We are about to begin prototyping this extension in GHC, so speak now if you have comments or suggestions!'''
     4
     5[[PageOutline(2-3,,inline)]]
    56
    67== Basic view patterns ==
     
    352353In comparing the different views proposals below, it will be useful to have terminology for some features of views.
    353354
    354 === Value input feature ===
     355==== Value input feature ====
    355356
    356357Our 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.
    357358
    358 === Implicit `Maybe` feature ===
     359==== Implicit `Maybe` feature ====
    359360
    360361Our proposal has the ''implicit `Maybe`'' feature: the syntax ''expr'' `=>` ''pat'' permits the programmer to elide the `Just`, for example when using partial views. 
    361362
    362 === Transparent ordinary Patterns ===
     363==== Transparent ordinary Patterns ====
    363364
    364365Our proposal does not have the ''transparent ordinary patterns'' feature: view patterns are written differently than ordinary patterns.
     
    366367The 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. 
    367368
    368 === Nesting ===
     369==== Nesting ====
    369370
    370371Our 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.
    371372
    372 === Integration with type classes ===
     373==== Integration with type classes ====
    373374
    374375Our proposal ''integrates with type classes'': an single view function can decompose multiple different data types, and the type class constraints are propagated to the user of the view. 
     
    376377== Related work ==
    377378
    378 === [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] ===
     379==== [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] ====
    379380
    380381Wadler's paper was the first concrete proposal.  It proposed a top-level view
     
    386387view constructors to appear in patterns only.
    387388
    388 === [http://haskell.org/development/views.html Burton et al views (1996)] ===
     389==== [http://haskell.org/development/views.html Burton et al views (1996)] ====
    389390
    390391This proposal is substantially more complicated than the one above; in particular it
     
    404405abstract data types", Burton and Cameron, JFP 3(2), Apr 1993.
    405406
    406 === [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] ===
     407==== [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] ====
    407408
    408409Okasaki's design is very similar to Burton et al's, apart from differences due
    409410to the different host language.  Again, the value input feature is not supported.
    410411
    411 === [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] ===
     412==== [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] ====
    412413
    413414Erwig's proposal for active patterns renders the Set example like this:
     
    430431Still the proposal does support the value input feature.
    431432
    432 === [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] ===
     433==== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] ====
    433434
    434435Active Destructors (ADs) are defined by a new form of top-level declaration. 
     
    480481This 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`.
    481482
    482 === [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] ===
     483==== [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] ====
    483484
    484485This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although
     
    492493Erwig do no stripping of the `Maybe` (see "Possible extension 2" above).
    493494
    494 === [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] ===
     495==== [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] ====
    495496
    496497Simon started this design discussion after talking to Don Syme about F#'s '''active patterns''', which serve a very similar purpose. These combine both “total” discrimination (views) and “partial” discrimination (implicit maybe) into one mechanism. It does this by embedding the names of discriminators in the names of matching functions, via “values with structured names”.  Sample uses include matching on .NET objects and XML.
     
    539540}}}
    540541
    541 === [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] ===
     542==== [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] ====
    542543
    543544Scala is an OO language with lots of functional features.  It has algebraic data types and
     
    550551concludes that case expressions and extractors work pretty well.
    551552
    552 === Pattern synonyms  ===
     553==== Pattern synonyms  ====
    553554
    554555[http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms]
     
    582583But 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).
    583584
    584 === [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] ===
     585==== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] ====
    585586
    586587First Class Patterns is an approach that attempts to
     
    608609                     |>> 2 
    609610}}}
    610 === First class abstractions ===
     611
     612==== First class abstractions ====
    611613
    612614Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.  By a "first class abstraction" I mean a value of type
     
    634636proposal deals with.  Hence orthgonal.
    635637
    636 === Barry Jay: First class patterns ===
     638==== Barry Jay: First class patterns ====
    637639
    638640A 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.
    639641
    640 === Uses of Views ===
     642==== Uses of Views ====
    641643
    642644The 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.