Changes between Version 1 and Version 2 of ViewPatternsArchive


Ignore:
Timestamp:
Jul 23, 2007 8:57:26 AM (8 years ago)
Author:
danl
Comment:

import current text; sorry, there's no way to keep the history

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatternsArchive

    v1 v2  
    1 page coming soon 
     1[[PageOutline]] 
     2= View patterns: lightweight views for Haskell = 
     3 
     4This page describes a rather lightweight proposal for adding views to  
     5Haskell Prime.  I'm thinking of prototyping the idea in GHC, so I'm looking 
     6for feedback. 
     7 
     8This page is open to editing by anyone.  (Chase the "Wiki notes" link in the sidebar to find out how.) 
     9 
     10== The problem ==  
     11 
     12We are keen on abstraction, but pattern matching is so convenient that 
     13we break abstractions all the time.  It's our dirty little secret. 
     14Looked at this way, object-oriented folk are much more obsessive  
     15about abstraction than we are: everything (including field access  
     16these days) is a method. 
     17 
     18Views have, in one form or another, repeatedly been proposed as a 
     19solution for this problem.   (See the end for a comparison with related work.) 
     20 
     21--------------------------- 
     22== The lightweight view proposal == 
     23=== Informally === 
     24 
     25The proposal introduces a new form of pattern, called a '''view pattern''' 
     26Here are some function definitions using view patterns. 
     27To read these definitions, imagine that `sing` is 
     28a sort of constructor that matches singleton lists. 
     29{{{ 
     30  f :: [Int] -> Int 
     31  f (sing -> n) = n+1   -- Equiv to: f [n] = ... 
     32  f other     = 0 
     33 
     34  g :: [Bool] -> Int 
     35  g (sing -> True)  = 0         -- Equiv to: g [True] = ... 
     36  g (sing -> False) = 1         -- Equiv to: g [False] = ... 
     37  g other           = 2 
     38 
     39  h :: [[Int]] -> Int    
     40  h (sing -> x : sing -> y : _) = x+y 
     41                        -- Equiv to: h ([x]:[y]:_) = ... 
     42  h other = 0 
     43}}} 
     44So what is `sing`?  It is just an ordinary Haskell function that 
     45returns a `Maybe` type: 
     46{{{ 
     47  sing :: [a] -> Maybe a 
     48  sing [x]   = Just x 
     49  sing other = Nothing 
     50}}} 
     51So `sing` simply identifies singleton lists, and returns the payload (that is, 
     52the singleton element; otherwise it returns `Nothing`. 
     53It is very important that '''there is nothing special about `sing`'''.  It is 
     54not declared to be a view; it can be called as a normal Haskell function; the author 
     55of `sing` might not have intended it to be used in pattern matching.   
     56 
     57=== More formally === 
     58 
     59The only special stuff is in the pattern.   
     60The sole change is this: add a single new sort of pattern, of the  
     61form 
     62        (''expr'' `->` ''pat'') 
     63 
     64where ''expr'' is an arbitrary Haskell expression.   I'll call a pattern 
     65of this form a '''view pattern'''.  
     66 
     67From a '''scoping''' point of view, the variables bound by the pattern (''expr'' `->` ''pat'') 
     68are simply the variables bound by ``pat``. 
     69Any variables in ``expr`` are bound occurrences. 
     70 
     71The rule for '''pattern-matching''' is this: 
     72To match a value ''v'' against a pattern ''(expr -> p)'',  
     73  * Evaluate ''(expr v)'' 
     74  * If the result is ''(`Just` w)'', match ''w'' against ''p'' 
     75  * If the result is `Nothing`, the match fails. 
     76 
     77The '''typing rule''' is similarly simple.   
     78The expression ''expr'' must have type 
     79''t1 `-> Maybe` t2''. Then the pattern ''pat'' must have type ''t2'', and the 
     80whole pattern (''expr'' `->` ''pat'') has type ''t1''. 
     81 
     82=== Features === 
     83 
     84For the different features this proposal (and others) have, see [[ref(Features views can have)]]. 
     85The proposal 
     86  * has the value input feature 
     87  * has the implicit `Maybe` feature 
     88  * doesn't have the transparent ordinary patterns feature 
     89  * has the nesting feature 
     90 
     91=== Possible extension 1: multi-argument view patterns === 
     92 
     93It would be quite useful to allow more than one sub-pattern in a view 
     94pattern.  To do this we'd need a `Maybe` data type that returns more than 
     95one result, thus: 
     96{{{ 
     97  data Maybe2 a b   = Nothing2 | Just2 a b 
     98  data Maybe3 a b c = Nothing3 | Just3 a b c 
     99        -- ..etc..., up to 8 perhaps (sigh) 
     100}}} 
     101With this in hand we can extend the views story to have multiple sub-patterns. 
     102Example: 
     103{{{ 
     104  snoc :: [a] -> Maybe2 [a] a 
     105  snoc [] = Nothing2 
     106  snoc (x:xs) = case snoc xs of 
     107                  Nothing2   -> Just2 [] x 
     108                  Just2 ys y -> Just2 (x:ys) y 
     109 
     110  last :: [Int] -> Int 
     111  last (snoc -> xs x) = x 
     112  last other = error "empty list" 
     113}}} 
     114It is tiresome that we need types `Maybe2`, `Maybe3` etc, but we already have  
     115that in Haskell; consider `zip3`, `zip4` and so on. 
     116We could always get away without it, by sticking to unary view patterns and 
     117using tuples, thus: 
     118{{{ 
     119  snoc :: [a] -> Maybe ([a], a) 
     120  snoc [] = Nothing 
     121  snoc (x:xs) = case snoc xs of 
     122                  Nothing     -> Just ([], x) 
     123                  Just (ys,y) -> Just (x:ys, y) 
     124 
     125  last :: [Int] -> Int 
     126  last (snoc -> (xs, x)) = x 
     127  last other = error "empty list" 
     128}}} 
     129But the tuple looks a bit clumsy. 
     130 
     131Under this proposal, the number of sub-patterns in the view pattern determines 
     132which return type the view function should have.  E.g. in the pattern '(e -> p1 p2 p3)', 
     133'e' should return a `Maybe3`. 
     134 
     135If n=0, then we want `Maybe0`, which is called `Bool`.  Thus 
     136{{{ 
     137  even :: Int -> Bool 
     138  even n = n `div` 2 == 0 
     139 
     140  f (even ->) = ...     -- Matches even numbers 
     141  f other     = ... 
     142}}} 
     143Here `even` is used as a nullary view pattern, with no sub-patterns 
     144following the `->`. 
     145 
     146Another variation (call it "extension 1b"), which avoids the tiresome need to define new types, is this: supplying multiple sub-patterns in a view pattern is synonymous with tupling.  Thus `(f -> p1 p2)` would be synonymous with `(f -> (p1,p2))`.  Here the effect is purely syntactic, allowing you to omit parens and commas without confusion.  No new types.  The power-to-weight ratio is probably better for this alternative. 
     147 
     148=== Possible extension 2: the implicit `Maybe`  === 
     149 
     150Thus far, the view function is required to return a `Maybe` type, with `Nothing` to indicate match 
     151failure.  An alternative, presented in the Erwig paper on transformational patterns (see Related work below),  
     152this implicit matching is not performed; instead, the sub-pattern is matched against 
     153whatever the view function returns.  So you'd have to write: 
     154{{{ 
     155f (snoc -> Just2 xs x) = ... 
     156}}} 
     157(Note the tiresome `Just2`.) 
     158 
     159For more one the consequences of removing the implicit `Maybe`, see the [[ref(Implicit `Maybe` feature)]] 
     160 
     161I can think of three alternatives: 
     162 * The `Maybe` stuff is built-in. This is the main proposal, because I think it is often exactly what you want. 
     163 * No built-in `Maybe` stuff.  Arguably this is more consistent with pattern-guards. 
     164 * Both are available, with different syntax.  For example  
     165    * ''(expr `->` pat)'' for the built-in `Maybe` story 
     166    * ''(expr `=>` pat)'' with no bulit-in `Maybe` 
     167 
     168=== Concrete syntax === 
     169 
     170A disadvantage of the arrow syntax is that it looks a bit confusing 
     171when it appears in a case expression: 
     172{{{ 
     173  last xs = case xs of 
     174                (snoc -> x xs) -> x 
     175}}} 
     176(Also that "x xs" looks a bit like `x` applied to `xs`.) 
     177 
     178Here are some other possible syntax choices I've considered: 
     179{{{ 
     180  f ($snoc x xs) = ...          -- Use prefix "$" 
     181  g ($(bits 3) x bs) = ...      -- Extra parens for the value input feature 
     182 
     183  f (%snoc x xs) = ...          -- Or use prefix "%" instead 
     184  f (.snoc x xs) = ...          -- Or use prefix "." instead 
     185  f (?snoc x xs) = ...          -- Or use prefix "?" instead 
     186 
     187  f (snoc? x xs) = ...          -- Postfix "?" 
     188  g ((bits 3)? x bs) = ...      -- With parens 
     189 
     190  f (snoc | x xs) = ..          -- Use "|" instead of "->" 
     191  g (bits 3 | b bs) = ... 
     192}}} 
     193Another possibility is to use a backward arrow, more like pattern guards: 
     194{{{ 
     195  f ((x,xs) <- snoc) = ...  -- More like pattern guards 
     196}}} 
     197But that messes up the left-to-right flow that is useful in some cases. 
     198For example, compare these: 
     199{{{ 
     200  parsePacket1 (bits 3 -> n (bits n -> val bs)) = ... 
     201 
     202  parsePacket2 (n (val bs <- bits n) <- bits 3) = ... 
     203}}} 
     204 
     205I also thought about infix view patterns, where the view function 
     206appears between its (pattern) arguments, but I could not think of a 
     207nice syntax for it, so it is not provided by this proposal. 
     208 
     209=== Remarks === 
     210 
     211The key feature of this proposal is its modesty, rather than its ambition: 
     212  * There is no new form of declaration (e.g. 'view' or 'pattern synonym').   
     213  * The functions used in view patterns are ordinary Haskell functions, and can be called from ordinary Haskell code.  They are not special view functions. 
     214  * Since the view functions are ordinary Haskell functions, no changes are needed to import or export mechanisms. 
     215  * Both static and dynamic semantics are extremely simple. 
     216It is essentially some simple syntactic sugar for patterns. 
     217However, sometimes modest syntactic sugar can have profound consequences. 
     218In this case, it's possible that people would start routinely hiding 
     219the data representation and exporting view functions instead, which might 
     220be an excellent thing. 
     221 
     222All this could be done with pattern guards.  For example `parsePacket` could be written 
     223{{{ 
     224  parsePacket bs | Just (n, bs')    <- bits 3 bs 
     225                 | Just (val, bs'') <- bits n bs' 
     226                 = ... 
     227}}} 
     228Indeed, one might ask whether the extra syntax for view patterns is worth 
     229it when they are so close to pattern guards.   
     230That's a good question.  I'm hoping that support for view patterns 
     231might encourage people to export view functions (ones with `Maybe` 
     232return types, and encouage their use in patten matching).  That is, 
     233just lower the barrier for abstraction a bit. 
     234 
     235'''Completeness'''.  It is hard to check for completeness of pattern matching; and likewise for 
     236overlap.  But guards already make both of these hard; and GADTs make completness hard too. 
     237So matters are not much worse than before. 
     238 
     239 
     240--------------------------- 
     241== Features views can have == 
     242 
     243The main goal of views is to introduce computations into pattern matches thus introducing abstraction from hard wired constructors. To distinguish between the different proposals, we pick out the key features 
     244 
     245=== Value input feature === 
     246 
     247This features allows to introduce additional parameters into the computation. Perhaps the most basic example are (n+k) patterns 
     248{{{ 
     249  fib :: Int -> Int 
     250  fib 0 = 1 
     251  fib 1 = 1 
     252  fib (n + 2) = fib (n + 1) + fib n 
     253}}} 
     254Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc. 
     255 
     256Of course, the real power unfolds when the extra parameter can be given at runtime 
     257{{{ 
     258   f :: Int -> Int -> ... 
     259   f n (n + m) = m           -- f a b = (b - a) 
     260}}} 
     261 
     262In the proposed view pattern (''expr'' `->` ''pat''), ''expr'' is an arbitrary Haskell expression. Thus, the lightweight proposal has the '''value input feature'''. For another example, suppose you wrote a regular expression matching function: 
     263{{{ 
     264  regexp :: String -> String -> Maybe (String, String) 
     265  -- (regexp r s) parses a string matching regular expression r  
     266  --    the front of s, returning the matched string and remainder of s 
     267}}} 
     268then you could use it in patterns thus: 
     269{{{ 
     270  f :: String -> String 
     271  f (regexp "[a-z]*" -> (name, rest)) = ... 
     272}}} 
     273Of course, the argument does not need to be a constant as it is here. 
     274 
     275With the value input feature, in a sense, patterns become first class. For example, one could pass a pattern as an argument to a function thus: 
     276{{{ 
     277  g :: (Int -> Maybe Int) -> Int -> ... 
     278  g p (p -> x) = ... 
     279}}} 
     280Here the first argument `p` can be thought of as a pattern passed to `g`, which 
     281is used to match the second argument of `g`. 
     282 
     283Here is another rather cute example: 
     284{{{ 
     285unfoldr :: (b -> Maybe (a, b)) -> b -> [a]  
     286unfoldr f (f -> (a, b)) = a : unfoldr f b 
     287unfoldr f other         = [] 
     288}}} 
     289 
     290=== Implicit `Maybe` feature === 
     291 
     292In functional languages, pattern matching is used to inspect a sum types like `Either Int String` and to proceed with the matching alternative. We can always project a choice between multiple alternatives to choice between one alternative (`Just`) and failure (`Nothing`): 
     293{{{ 
     294   maybeLeft  :: Either a b -> Maybe a 
     295   maybeRight :: Either a b -> Maybe b 
     296}}} 
     297 
     298Some proposals build their patterns entirely from from such single alternative de-constructors functions of type `a -> Maybe b`, while some allow projection to multiple alternatives. 
     299 
     300By restricting de-constructors to be of type `a -> Maybe b`, the Maybe can be made implicit, it doesn't show up in the pattern. Example: 
     301{{{ 
     302    data Product = ....some big data type... 
     303    type Size = Int 
     304     
     305    smallProd, medProd, bigProd :: Product -> Maybe Size 
     306    smallProd p = ... 
     307    medProd   p = ... 
     308    bigProd   p = ... 
     309     
     310    f :: Product -> ... 
     311    f (smallProd -> s) = ... 
     312    f (medProd   -> s) = ... 
     313    f (bigProd   -> s) = ... 
     314}}} 
     315 
     316Projection to multiple alternatives requires a new (or existing) data type for every group of alternatives introduced. 
     317{{{ 
     318    data Dimensions = Small | Medium | Big      -- View type 
     319    prodSize :: Product -> Dimensions 
     320    prodSize = ... 
     321     
     322    f :: Product -> ... 
     323    f (prodSize -> Small)  = ... 
     324    f (prodSize -> Medium) = ... 
     325    f (prodSize -> Big)    = ... 
     326}}} 
     327Using a fixed set of multiple alternatives makes it more obvious whether the match is exhaustive or not. 
     328 
     329While the implicit `Maybe a` is more compositional and nicely integrates with already existing uses of the `Maybe`-type, it cannot share expensive computations across multiple alternatives. This is a strong argument against the implicit `Maybe a`. To illustrate the problem, suppose that 
     330 
     331{{{ 
     332   data Graph 
     333}}} 
     334represents a graph and that we want a function 
     335{{{ 
     336   g :: Graph -> [...] 
     337   g (forest -> xs) = concatMap g xs 
     338   g (tree ->)      = ... 
     339   g (dag  ->)      = ... 
     340}}} 
     341These three properties are expensive to calculate but all three only 
     342depend on the result of a single depth first search. By projecting the 
     343disjoint sum to several `Maybe`s, the depth first search has to be 
     344repeated every time. More importantly, there is *no way* for the compiler to optimize this because that would mean common subexpression elimination across 
     345functions. 
     346 
     347Some would argue that implicit the 'Maybe a' is ''less'' compositional than the explicit version.  If no 'Maybe' is required, then the result of the view function can be any type at all, which can be pattern-matched in the ordinary way.  Some examples of cute programming of well-known combinators: 
     348{{{ 
     349map f [] = [] 
     350map f (x: map f -> xs) = x:xs 
     351 
     352foldr f z [] = z 
     353foldr f z (x: foldr f z -> xs) =  x `f` xs 
     354}}} 
     355 
     356=== Transparent ordinary Patterns === 
     357 
     358The lightweight view proposal has different syntax for view functions and ordinary pattern matches, they are not interchangeable. To use the abstraction view functions offer, you have to anticipate whether you can stick to ordinary constructors or whether you will switch to abstract constructors at some time. For example, a stack abstraction would have to use view patterns if we want to be able to change the concrete representation of stacks later on. 
     359{{{ 
     360    type Stack a = [a] 
     361     
     362    f :: Stack a 
     363    f (null?)     = ... 
     364    f (pop? x xs) = ... 
     365}}} 
     366This certainly discourages ordinary pattern matching. In other words, 
     367implementing the proposal has considerable impact on ordinary pattern 
     368matching (not in semantics but in use). 
     369 
     370The problem that needs to be solved is to introduce abstraction "after the fact". 
     371 
     372On the other hand, view patterns can do arbitrary computation, perhaps expensive. So it's good to have a syntactically-distinct notation that reminds the programmer that some computation beyond ordinary pattern matching may be going on. 
     373 
     374=== Nesting === 
     375 
     376In the lightweight proposal, view patterns are just an extra syntactic form of pattern, and they nest inside other patterns, and other patterns nest inside them.  So one can write 
     377{{{ 
     378  f (sing -> x, True) = ... 
     379  g (Just (sing -> x)) = ... 
     380  h (Just (sing -> Just x)) = ... 
     381}}} 
     382And by the same token, view patterns nest inside each other: 
     383{{{ 
     384  k :: [[a]] -> a 
     385  k (sing -> sing -> x) = x 
     386}}} 
     387This convenient nesting is perhaps the biggest practical  
     388difference between view patterns and pattern guards. 
     389 
     390The majority of the proposals allow nesting. 
     391 
     392 
     393=== Integration with type classes === 
     394 
     395A view mechanism that integrates nicely with type classes would allow 
     396a single "view" to decompose multiple different data types.  For 
     397example, a view might work on any type in class Num, or in class Sequence. 
     398 
     399A good example is Haskell's existing (n+k) patterns.  Here is how they 
     400can be expressed using the view pattern proposed in this page (with different  
     401syntax, of course): 
     402{{{ 
     403   np :: Num a => a -> a -> Maybe a 
     404   np k n | k <= n    = Just (n-k) 
     405          | otherwise = Nothing 
     406 
     407   g :: Int -> Int 
     408   g (np 3 -> n) = n*2 
     409 
     410   h :: Integer -> Integer 
     411   h (np 9 -> n) = n*2 
     412 
     413   f :: Num a => a -> Int 
     414   f (np 10 -> n) = n           -- Matches values >= 10, f a = (a - 10) 
     415   f (np 4  -> n) = 1           -- Matches values >= 4 
     416   f other        = 2 
     417}}} 
     418Here a single, overloaded view, `np`, can be used  
     419in `g`, and `h` to match against values of different types and, 
     420in `f`'s case, any type in class Num. (Notice too the use of the value  
     421input feature.) 
     422 
     423This feature falls out very nicely from view patterns, but  
     424not from all other proposals. 
     425 
     426--------------------------- 
     427== Efficiency of Views == 
     428 
     429View patterns can do arbitrary computation, perhaps expensive. 
     430 
     431It's reasonable to expect the compiler to avoid repeated computation when 
     432pattern line up in a column: 
     433{{{ 
     434  f (snoc -> x xs) True  = ... 
     435  f (snoc -> x xs) False = ... 
     436}}} 
     437In pattern-guard form, common sub-expression should achieve the same 
     438effect, but it's quite a bit less obvious.  We should be able to give 
     439clear rules for when the avoidance of repeat computation is 
     440guaranteed. 
     441 
     442--------------------------- 
     443== Use cases and examples == 
     444 
     445Whether views are really worth it can only be decide on the base of examples. Some are situations where you programmed and thought "I wish I had a view for that". Some are those snippets of code that unexpectedly use views to good effect. 
     446 
     447=== Sequences === 
     448 
     449Lists, queues, ByteStrings and 2-3-finger trees are all implementations of sequences, but only ordinary lists can be deconstructed using pattern matching. The need for list patterns on arbitrary sequence data structures is desperate. As if to ease the pain, Data.Sequence even defines the views from the left and from the right 
     450{{{ 
     451   data ViewL a 
     452   = EmptyL 
     453   | (:<) a (Seq a) 
     454 
     455   viewl :: Seq a -> ViewL a 
     456 
     457   data ViewR a 
     458   = EmptyR 
     459   | (:>) (Seq a) a 
     460 
     461   viewr :: Seq a -> ViewR a 
     462}}} 
     463 
     464Thus, the presence of views has a direct impact on existing Haskell libraries. Arguably, a view proposal that wants to be effective for abstract data types likely has to have the transparent ordinary patterns feature. 
     465 
     466The 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. 
     467 
     468=== Designing data structures === 
     469 
     470The abstractional power views offer can also be put to good use when designing data structures, as the following papers show 
     471 
     472  * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. 
     473  * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze:  A Simple Implementation Technique for Priority Search Queues] 
     474 
     475=== Sets and Inductive Graphs === 
     476 
     477Having the value input feature, even set like data structures come in reach for pattern matching. In fact, 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. 
     478 
     479Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby. 
     480{{{ 
     481module Set( Set, empty, insert, delete, has) where 
     482 
     483  newtype Set a = S [a] 
     484   
     485  has :: Eq a => a -> Set a -> Maybe (Set a) 
     486  has x (S xs) | x `elem` xs = Just (xs \\ x) 
     487               | otherwise   = Nothing 
     488   
     489  delete :: a -> Set a -> Set a 
     490  delete x (has x -> s) = s 
     491  delete x s            = s 
     492   
     493  insert :: a -> Set a -> Set a 
     494  insert x s@(has x -> _) = s 
     495  insert x (S xs)         = S (x:xs) 
     496}}} 
     497Notice that in the left-hand side `delete x (has x -> s)`, the first `x` is a binding occurrence, but the second is merely an argument to `has` and is a bound occurrence. 
     498 
     499=== Erlang-style parsing === 
     500 
     501The expression to the left of the `->` can mention variables bound in earlier patterns. 
     502For example, Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ([http://user.it.uu.se/~kostis/Papers/index.html#Conference "Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07]).  Suppose we had a parsing function thus: 
     503{{{ 
     504  bits :: Int -> ByteString -> Maybe2 Word ByteString 
     505  -- (bits n bs) parses n bits from the front of bs, returning 
     506  -- the n-bit Word, and the remainder of bs 
     507}}} 
     508Then we could write patterns like this: 
     509{{{ 
     510  parsePacket :: ByteString -> ... 
     511  parsePacket (bits 3 -> n (bits n -> val bs)) = ... 
     512}}} 
     513This parses 3 bits to get the value of `n`, and then parses `n` bits to get 
     514the value of `val`.   
     515 
     516=== N+k patterns === 
     517 
     518You can test for values.  For example here's a view function that tests for values  
     519greater than or equal to n: 
     520{{{ 
     521   np :: Num a => a -> a -> Maybe a 
     522   np k n | k <= n    = Just (n-k) 
     523          | otherwise = Nothing 
     524 
     525   f :: Num a => a -> a 
     526   f (np 10 -> n) = 0           -- Matches values >= 10 
     527   f (np 4  -> n) = 1           -- Matches values >= 4 
     528   f other        = 2 
     529}}} 
     530You will recognise these as (n+k) patterns, albeit with slightly different syntax. 
     531(Incidentally, this example shows that the view function can be overloaded, and 
     532that its use in a view pattern gives rise to a type-class constraint (in this case, 
     533that in turn makes `f` overloaded). 
     534 
     535=== Naming constants in one place === 
     536 
     537We are always taught to write magic numbers, or constants, in one place only. 
     538In C you can write 
     539{{{ 
     540  #define ERRVAL 4 
     541}}} 
     542and then use `ERRVAL` in `switch` labels.  You can't do that in Haskell, which is tiresome. 
     543But with view pattern you can: 
     544{{{ 
     545  errVal :: Int -> Bool 
     546  errVal = (== 4) 
     547 
     548  f (errVal ->) = ... 
     549}}} 
     550 
     551 
     552------------------------- 
     553== Related work == 
     554 
     555=== Wadler's original paper (POPL 1987) === 
     556 
     557Wadler's paper was the first concrete proposal.  It proposed a top-level view 
     558declaration, together with functions ''in both directions'' between the view type 
     559and the original type, which are required to be mutually inverse.   
     560This allows view constructors to be used in expressions 
     561as well as patterns, which seems cool. Unfortunately this dual role proved 
     562problematic for equational reasoning, and every subsequent proposal restricted 
     563view constructors to appear in patterns only. 
     564 
     565=== [http://haskell.org/development/views.html Burton et al views (1996)] === 
     566 
     567This proposal is substantially more complicated than the one above; in particular it 
     568requires new form of top-level declaration for a view type. For example: 
     569{{{ 
     570  view Backwards a of [a] = [a] `Snoc` a | Nil 
     571     where 
     572     backwards [] = Nil 
     573     backwards (x:[]) = [] `Snoc` x 
     574     backwards (x1:(xs `Snoc` xn)) = (x1:xs) `Snoc` xn 
     575}}} 
     576Furthermore, it is in some ways less expressive than the proposal here; 
     577the (n+k) pattern, Erlang `bits` pattern, and `regexp` examples are not 
     578definable, because all rely on the value input feature. 
     579 
     580I think this proposal is substantially the same as "Pattern matching and 
     581abstract data types", Burton and Cameron, JFP 3(2), Apr 1993. 
     582 
     583=== [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] === 
     584 
     585Okasaki's design is very similar to Burton et al's, apart from differences due 
     586to the different host language.  Again, the value input feature is not supported. 
     587 
     588=== [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] === 
     589 
     590Erwig's proposal for active patterns renders the Set example like this: 
     591{{{ 
     592data Set a = Empty | Add a (Set a) 
     593 
     594pat Add' x _ = 
     595  Add y s => if x==y then Add y s 
     596             else let Add' x t = s 
     597                  in Add x (Add y t) 
     598 
     599delete x (Add' x s) = s 
     600delete x s          = s 
     601}}} 
     602This requires a new top-leven declaration form `pat`; and I don't think it's nearly  
     603as easy to understand as the current proposal.  Notably, in the first equation for 
     604`delete` it's ahrd to see that the second `x` is a bound occurrence; this somehow 
     605follows from the `pat` declaration. 
     606 
     607Still the proposal does support the value input feature. 
     608 
     609=== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] === 
     610 
     611Active Desctructors (ADs) are defined by a new form of top-level declaration.  Our 
     612singleton example would look like this: 
     613{{{ 
     614  Sing x match [x] 
     615}}} 
     616Here '''match''' is the keyword, and `Sing` is the AD.  ADs are quite like view patterns: 
     617the can do computation, and can fail to match.  But they are definitely not normal  
     618Haskell functions, and need their own form of top-level declaration.  They even have 
     619a special form of type to describe them. 
     620 
     621The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the 
     622new form of type. 
     623 
     624They also introduce a combining form for ADs, to make a kind of and-pattern.  For 
     625example, suppose we had 
     626{{{ 
     627  Head x match (x:_) 
     628  Tail x match (_:xs) 
     629 
     630  f :: [a] -> [a] 
     631  f ((Head x)@(Tail ys)) = x:x:ys 
     632}}} 
     633Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)` 
     634against the argument, binding `x` and `ys` respectively.  We can model that with view patterns, 
     635only a bit more clumsily: 
     636{{{ 
     637  headV (x:xs) = Just x 
     638  headV []     = Nothing 
     639 
     640  tailV (x:xs) = Just xs 
     641  tailV []     = Nothing 
     642 
     643  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c) 
     644  (f @ g) x = do { b <- f x; c <- g x; return (b,c) } 
     645 
     646  f :: [a] -> [a] 
     647  f (headV @ tailV -> (x,ys)) = x:x:ys 
     648}}} 
     649The clumsiness is that the "`@`" combines functions, with a kind of positional 
     650binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear 
     651that `headV` binds `x` and `tailV` binds `y`. 
     652 
     653In exchange, although view patterns are a bit less convenient here, they  
     654are a much, much smaller language change than ADs. 
     655 
     656=== [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] === 
     657 
     658This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although 
     659it is joint-authored, the transformational-pattern idea is Martin's.)  Transformational patterns 
     660are very close to what we propose here.  In particular, view functions are ordinary Haskell functions, 
     661so that the only changes are to patterns themselves. 
     662 
     663There are two main differences (apart from syntax). 
     664First, transformational patterns didn't have the value input feature, althought it'd be easy  
     665to add (indeed that's what we've done). Second, transformational patterns as described by 
     666Erwig do no stripping of the `Maybe` (see "Possible extension 2" above). 
     667 
     668=== [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] === 
     669 
     670Simon 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. 
     671 
     672Here is [http://blogs.msdn.com/dsyme/archive/2007/04/07/draft-paper-on-f-active-patterns.aspx a full paper describing the design], by Don Syme, Gregory Neverov, and James Margetson (April 2007). 
     673 
     674The feature is implemented in F# 1.9. Some code snippets are below. 
     675{{{ 
     676    let (|Rect|) (x:complex) = (x.RealPart, x.ImaginaryPart) 
     677    let (|Polar|) (x:complex) = (x.Magnitude , x.Phase) 
     678 
     679    let mulViaRect c1 c2 =  
     680        match c1,c2 with  
     681        | Rect(ar,ai), Rect(br,bi) -> Complex.mkRect(ar*br - ai*bi, ai*br + bi*ar) 
     682 
     683    let mulViaPolar c1 c2 =  
     684        match c1,c2 with  
     685        | Polar (r1,th1),Polar (r2,th2) -> Complex.mkPolar(r1*r2, th1+th2) 
     686 
     687    let mulViaRect2  (Rect(ar,ai))   (Rect(br,bi))   = Complex.mkRect(ar*br - ai*bi,  
     688                                                                      ai*br + bi*ar) 
     689    let mulViaPolar2 (Polar(r1,th1)) (Polar(r2,th2)) = Complex.mkPolar(r1*r2, th1+th2) 
     690}}} 
     691And for views: 
     692{{{ 
     693    open System 
     694     
     695    let (|Named|Array|Ptr|Param|) (typ : System.Type) = 
     696        if typ.IsGenericType        then Named(typ.GetGenericTypeDefinition(),  
     697                                               typ.GetGenericArguments()) 
     698        elif not typ.HasElementType then Named(typ, [| |]) 
     699        elif typ.IsArray            then Array(typ.GetElementType(),  
     700                                               typ.GetArrayRank()) 
     701        elif typ.IsByRef            then Ptr(true,typ.GetElementType()) 
     702        elif typ.IsPointer          then Ptr(false,typ.GetElementType()) 
     703        elif typ.IsGenericParameter then Param(typ.GenericParameterPosition,  
     704                                               typ.GetGenericParameterConstraints()) 
     705        else failwith "MSDN says this can't happen" 
     706 
     707    let rec freeVarsAcc typ acc = 
     708        match typ with 
     709        | Named (con, args) -> Array.fold_right freeVarsAcc args acc 
     710        | Array (arg, rank) -> freeVarsAcc arg acc 
     711        | Ptr (_,arg)       -> freeVarsAcc arg acc 
     712        | Param(pos,cxs)    -> Array.fold_right freeVarsAcc cxs (typ :: acc)  
     713}}} 
     714 
     715=== [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] === 
     716 
     717Scala is an OO language with lots of functional features.  It has algebraic data types and 
     718pattern matching.  It also has a form of view called '''extractors''', which are 
     719pretty similar to view patterns, albeit in OO clothing.  Notably, by packaging a constructor 
     720and an extractor in a class, they can use the same class name in both expressions and terms,  
     721implicitly meaning "use the constructor in expressions, and use the extractor in patterns". 
     722 
     723The paper does a comparative evaluation of various OO paradigms for matching, and  
     724concludes that case expressions and extractors work pretty well. 
     725 
     726=== Pattern synonyms  === 
     727 
     728[http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms]  
     729are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see  
     730[http://people.cs.uchicago.edu/~jhr/papers/1992/tr-sml-const.pdf Abstract value constructors],  
     731Reppy & Aiken, TR 92-1290, Cornell, June 1992. 
     732 
     733The one way in which pattern synonyms are better than view patterns is that 
     734they define by-construction bi-directional maps.  Example 
     735{{{ 
     736  data Term = Var String | Term String [Term] 
     737   
     738  -- 'const' introduces a pattern synonym 
     739  const Plus a b = Term "+" [a,b] 
     740 
     741  f :: Term -> Term 
     742  f (Plus a b) = Plus (f a) (f b) 
     743  f ... = ... 
     744}}} 
     745With pattern views, we'd have to write two functions for the "plus" view: 
     746{{{ 
     747  plus :: Term -> Term -> Term 
     748  plus a b = Term "+" [a,b] 
     749 
     750  isPlus :: Term -> Maybe2 Term Term 
     751  isPlus (Term "+" [a,b]) = Just2 a b 
     752  isPlus other            = Nothing 
     753 
     754  f :: Term -> Term 
     755  f (isPlus -> a b) = plus (f a) (f b) 
     756}}} 
     757But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration; 
     758and are much more limited than view patterns (by design they cannot do computation). 
     759 
     760=== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] === 
     761 
     762First Class Patterns is an approach that attempts to 
     763add the minimum of syntax to the language which---in combination with 
     764pattern combinators written within the language---can achieve everything 
     765and more that Haskell patterns can do.  They have the value-input feature. 
     766 
     767The advantages are  1) They are simpler than Haskell's patterns;  2) Patterns are first class. 
     7683) The binding mechanism (the pattern binder) is orthogonal to the the pattern combinators: 
     769the hope is that one can stop changing the syntax/semantics of patterns and concentrate on writing the 
     770combinators (as Haskell functions). 
     771 
     772The disadvantages are as follows: 1) An extra syntactic construct that binds variables, the pattern binder, is required. 
     7732) Even with pattern binders, simple patterns look clunkier than Haskell's patterns. 
     7743) No attempt is made to check for exhaustiveness of patterns. 
     7754) 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. 
     776 
     777The examples at the top of this page would look like this with first class patterns: 
     778{{{ 
     779  f = {%sing n} .-> n+1 
     780                |>> 0 
     781 
     782  g =  {%sing True}  .-> 0 
     783    .| {%sing False} .-> 1 
     784                     |>> 2   
     785}}} 
     786=== First class abstractions === 
     787 
     788Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.  By a "first class abstraction" I mean a value of type 
     789(''something'' `->` ''something'') 
     790with a syntax something like 
     791(`\` ''pattern'' `->` ''result''). 
     792The 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.   
     793 
     794Here are the ones I know of 
     795 
     796 * [http://hackage.haskell.org/trac/haskell-prime/ticket/114 Claus Reinke's lambda-match proposal] 
     797 * [http://ttic.uchicago.edu/~blume/pub-cat.html Matthias Blume: Extensible programming with first-class cases] (ICFP06) 
     798 
     799All these proposals are more or less orthogonal to this one. For example, Reinke 
     800proposes a compositional syntax for lambda abstractions  
     801`(\p -> e)` where pattern matching failure on `p` can be caught and composed 
     802with a second abstraction. Thus 
     803{{{ 
     804   (| Just x -> x+1 ) +++ (| Nothing -> 0 ) 
     805}}} 
     806combines two abstractions, with failure from the first falling through to the seoond.   
     807 
     808None of these proposals say 
     809anything about the patterns themselves, which in turn is all this 
     810proposal deals with.  Hence orthgonal. 
     811 
     812=== Barry Jay: First class patterns === 
     813 
     814A 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. 
     815