Changes between Version 6 and Version 7 of ViewPatternsNew

Jul 18, 2007 4:56:36 PM (8 years ago)



  • ViewPatternsNew

    v6 v7  
    333333Of 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.
     335== Compilation ==
    335337== Features views can have ==
    359361Our proposal ''integrates with type classes'': a single "view" can decompose multiple different data types. 
     363== Related work ==
     365=== Uses of Views ===
     367The observations from [ 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.
     369The abstractional power views offer can also be put to good use when designing data structures, as the following papers show
     371  * [ R.Hinze: A fresh look on binary search trees].
     372  * [ R.Hinze:  A Simple Implementation Technique for Priority Search Queues]
     373  * The the key idea of [ 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.
     375=== [ Wadler's original paper (POPL 1987)] ===
     377Wadler's paper was the first concrete proposal.  It proposed a top-level view
     378declaration, together with functions ''in both directions'' between the view type
     379and the original type, which are required to be mutually inverse. 
     380This allows view constructors to be used in expressions
     381as well as patterns, which seems cool. Unfortunately this dual role proved
     382problematic for equational reasoning, and every subsequent proposal restricted
     383view constructors to appear in patterns only.
     385=== [ Burton et al views (1996)] ===
     387This proposal is substantially more complicated than the one above; in particular it
     388requires new form of top-level declaration for a view type. For example:
     390  view Backwards a of [a] = [a] `Snoc` a | Nil
     391     where
     392     backwards [] = Nil
     393     backwards (x:[]) = [] `Snoc` x
     394     backwards (x1:(xs `Snoc` xn)) = (x1:xs) `Snoc` xn
     396Furthermore, it is in some ways less expressive than the proposal here;
     397the (n+k) pattern, Erlang `bits` pattern, and `regexp` examples are not
     398definable, because all rely on the value input feature.
     400I think this proposal is substantially the same as "Pattern matching and
     401abstract data types", Burton and Cameron, JFP 3(2), Apr 1993.
     403=== [ Okasaki: views in Standard ML] ===
     405Okasaki's design is very similar to Burton et al's, apart from differences due
     406to the different host language.  Again, the value input feature is not supported.
     408=== [ Erwig: active patterns] ===
     410Erwig's proposal for active patterns renders the Set example like this:
     412data Set a = Empty | Add a (Set a)
     414pat Add' x _ =
     415  Add y s => if x==y then Add y s
     416             else let Add' x t = s
     417                  in Add x (Add y t)
     419delete x (Add' x s) = s
     420delete x s          = s
     422This requires a new top-leven declaration form `pat`; and I don't think it's nearly
     423as easy to understand as the current proposal.  Notably, in the first equation for
     424`delete` it's ahrd to see that the second `x` is a bound occurrence; this somehow
     425follows from the `pat` declaration.
     427Still the proposal does support the value input feature.
     429=== [ Palao et al: active destructors (ICFP'96)] ===
     431Active Desctructors (ADs) are defined by a new form of top-level declaration.  Our
     432singleton example would look like this:
     434  Sing x match [x]
     436Here '''match''' is the keyword, and `Sing` is the AD.  ADs are quite like view patterns:
     437the can do computation, and can fail to match.  But they are definitely not normal
     438Haskell functions, and need their own form of top-level declaration.  They even have
     439a special form of type to describe them.
     441The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the
     442new form of type.
     444They also introduce a combining form for ADs, to make a kind of and-pattern.  For
     445example, suppose we had
     447  Head x match (x:_)
     448  Tail x match (_:xs)
     450  f :: [a] -> [a]
     451  f ((Head x)@(Tail ys)) = x:x:ys
     453Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)`
     454against the argument, binding `x` and `ys` respectively.  We can model that with view patterns:
     456  headV (x:xs) = Just x
     457  headV []     = Nothing
     459  tailV (x:xs) = Just xs
     460  tailV []     = Nothing
     462  f (both -> (headV => x, tailV => ys)) = x:x:ys
     465An to duplicating the value is to compose the functions:
     467  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c)
     468  (f @ g) x = do { b <- f x; c <- g x; return (b,c) }
     470  f :: [a] -> [a]
     471  f (headV @ tailV -> (x,ys)) = x:x:ys
     473This is a little clumsier: the "`@`" combines functions, with a kind of positional
     474binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear
     475that `headV` binds `x` and `tailV` binds `y`.
     477=== [ Erwig/Peyton Jones: transformational patterns] ===
     479This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although
     480it is joint-authored, the transformational-pattern idea is Martin's.)  Transformational patterns
     481are very close to what we propose here.  In particular, view functions are ordinary Haskell functions,
     482so that the only changes are to patterns themselves.
     484There are two main differences (apart from syntax).
     485First, transformational patterns didn't have the value input feature, althought it'd be easy
     486to add (indeed that's what we've done). Second, transformational patterns as described by
     487Erwig do no stripping of the `Maybe` (see "Possible extension 2" above).
     489=== [ F# Active Patterns] ===
     491Simon 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.
     493Here is [ a full paper describing the design], by Don Syme, Gregory Neverov, and James Margetson (April 2007).
     495The feature is implemented in F# 1.9. Some code snippets are below.
     497    let (|Rect|) (x:complex) = (x.RealPart, x.ImaginaryPart)
     498    let (|Polar|) (x:complex) = (x.Magnitude , x.Phase)
     500    let mulViaRect c1 c2 =
     501        match c1,c2 with
     502        | Rect(ar,ai), Rect(br,bi) -> Complex.mkRect(ar*br - ai*bi, ai*br + bi*ar)
     504    let mulViaPolar c1 c2 =
     505        match c1,c2 with
     506        | Polar (r1,th1),Polar (r2,th2) -> Complex.mkPolar(r1*r2, th1+th2)
     508    let mulViaRect2  (Rect(ar,ai))   (Rect(br,bi))   = Complex.mkRect(ar*br - ai*bi,
     509                                                                      ai*br + bi*ar)
     510    let mulViaPolar2 (Polar(r1,th1)) (Polar(r2,th2)) = Complex.mkPolar(r1*r2, th1+th2)
     512And for views:
     514    open System
     516    let (|Named|Array|Ptr|Param|) (typ : System.Type) =
     517        if typ.IsGenericType        then Named(typ.GetGenericTypeDefinition(),
     518                                               typ.GetGenericArguments())
     519        elif not typ.HasElementType then Named(typ, [| |])
     520        elif typ.IsArray            then Array(typ.GetElementType(),
     521                                               typ.GetArrayRank())
     522        elif typ.IsByRef            then Ptr(true,typ.GetElementType())
     523        elif typ.IsPointer          then Ptr(false,typ.GetElementType())
     524        elif typ.IsGenericParameter then Param(typ.GenericParameterPosition,
     525                                               typ.GetGenericParameterConstraints())
     526        else failwith "MSDN says this can't happen"
     528    let rec freeVarsAcc typ acc =
     529        match typ with
     530        | Named (con, args) -> Array.fold_right freeVarsAcc args acc
     531        | Array (arg, rank) -> freeVarsAcc arg acc
     532        | Ptr (_,arg)       -> freeVarsAcc arg acc
     533        | Param(pos,cxs)    -> Array.fold_right freeVarsAcc cxs (typ :: acc)
     536=== [ Emir, Odersky, Williams: Matching objects with patterns] ===
     538Scala is an OO language with lots of functional features.  It has algebraic data types and
     539pattern matching.  It also has a form of view called '''extractors''', which are
     540pretty similar to view patterns, albeit in OO clothing.  Notably, by packaging a constructor
     541and an extractor in a class, they can use the same class name in both expressions and terms,
     542implicitly meaning "use the constructor in expressions, and use the extractor in patterns".
     544The paper does a comparative evaluation of various OO paradigms for matching, and
     545concludes that case expressions and extractors work pretty well.
     547=== Pattern synonyms  ===
     549[ Pattern synonyms]
     550are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see
     551[ Abstract value constructors],
     552Reppy & Aiken, TR 92-1290, Cornell, June 1992.
     554The one way in which pattern synonyms are better than view patterns is that
     555they define by-construction bi-directional maps.  Example
     557  data Term = Var String | Term String [Term]
     559  -- 'const' introduces a pattern synonym
     560  const Plus a b = Term "+" [a,b]
     562  f :: Term -> Term
     563  f (Plus a b) = Plus (f a) (f b)
     564  f ... = ...
     566With pattern views, we'd have to write two functions for the "plus" view:
     568  plus :: Term -> Term -> Term
     569  plus a b = Term "+" [a,b]
     571  isPlus :: Term -> Maybe2 Term Term
     572  isPlus (Term "+" [a,b]) = Just2 a b
     573  isPlus other            = Nothing
     575  f :: Term -> Term
     576  f (isPlus -> a b) = plus (f a) (f b)
     578But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration;
     579and are much more limited than view patterns (by design they cannot do computation).
     581=== [ Tullsen: First Class Patterns] ===
     583First Class Patterns is an approach that attempts to
     584add the minimum of syntax to the language which---in combination with
     585pattern combinators written within the language---can achieve everything
     586and more that Haskell patterns can do.  They have the value-input feature.
     588The advantages are  1) They are simpler than Haskell's patterns;  2) Patterns are first class.
     5893) The binding mechanism (the pattern binder) is orthogonal to the the pattern combinators:
     590the hope is that one can stop changing the syntax/semantics of patterns and concentrate on writing the
     591combinators (as Haskell functions).
     593The disadvantages are as follows: 1) An extra syntactic construct that binds variables, the pattern binder, is required.
     5942) Even with pattern binders, simple patterns look clunkier than Haskell's patterns.
     5953) No attempt is made to check for exhaustiveness of patterns.
     5964) 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.
     598The examples at the top of this page would look like this with first class patterns:
     600  f = {%sing n} .-> n+1
     601                |>> 0
     603  g =  {%sing True}  .-> 0
     604    .| {%sing False} .-> 1
     605                     |>> 2 
     607=== First class abstractions ===
     609Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.  By a "first class abstraction" I mean a value of type
     610(''something'' `->` ''something'')
     611with a syntax something like
     612(`\` ''pattern'' `->` ''result'').
     613The abstraction includes both the pattern and the result.  In contrast, view patterns tackle only the syntax of patterns; the pattern of a first-class abstraction. 
     615Here are the ones I know of
     617 * [ Claus Reinke's lambda-match proposal]
     618 * [ Matthias Blume: Extensible programming with first-class cases] (ICFP06)
     620All these proposals are more or less orthogonal to this one. For example, Reinke
     621proposes a compositional syntax for lambda abstractions
     622`(\p -> e)` where pattern matching failure on `p` can be caught and composed
     623with a second abstraction. Thus
     625   (| Just x -> x+1 ) +++ (| Nothing -> 0 )
     627combines two abstractions, with failure from the first falling through to the seoond. 
     629None of these proposals say
     630anything about the patterns themselves, which in turn is all this
     631proposal deals with.  Hence orthgonal.
     633=== Barry Jay: First class patterns ===
     635A 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 [ home page] has more info.