Changes between Version 11 and Version 12 of ViewPatternsNew


Ignore:
Timestamp:
Jul 19, 2007 10:32:38 AM (7 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.