Changes between Version 28 and Version 29 of ViewPatterns


Ignore:
Timestamp:
Jul 23, 2007 9:01:00 AM (8 years ago)
Author:
danl
Comment:

import new text

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatterns

    v28 v29  
    1 [[PageOutline]] 
    21= View patterns: lightweight views for Haskell = 
    32 
    4 This page describes a rather lightweight proposal for adding views to  
    5 Haskell Prime.  I'm thinking of prototyping the idea in GHC, so I'm looking 
    6 for feedback. 
    7  
    8 This page is open to editing by anyone.  (Chase the "Wiki notes" link in the sidebar to find out how.) 
    9  
    10 == The problem ==  
    11  
    12 We are keen on abstraction, but pattern matching is so convenient that 
    13 we break abstractions all the time.  It's our dirty little secret. 
    14 Looked at this way, object-oriented folk are much more obsessive  
    15 about abstraction than we are: everything (including field access  
    16 these days) is a method. 
    17  
    18 Views have, in one form or another, repeatedly been proposed as a 
    19 solution for this problem.   (See the end for a comparison with related work.) 
    20  
    21 --------------------------- 
    22 == The lightweight view proposal == 
    23 === Informally === 
    24  
    25 The proposal introduces a new form of pattern, called a '''view pattern''' 
    26 Here are some function definitions using view patterns. 
    27 To read these definitions, imagine that `sing` is 
    28 a 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 }}} 
    44 So what is `sing`?  It is just an ordinary Haskell function that 
    45 returns a `Maybe` type: 
    46 {{{ 
    47   sing :: [a] -> Maybe a 
    48   sing [x]   = Just x 
    49   sing other = Nothing 
    50 }}} 
    51 So `sing` simply identifies singleton lists, and returns the payload (that is, 
    52 the singleton element; otherwise it returns `Nothing`. 
    53 It is very important that '''there is nothing special about `sing`'''.  It is 
    54 not declared to be a view; it can be called as a normal Haskell function; the author 
    55 of `sing` might not have intended it to be used in pattern matching.   
    56  
    57 === More formally === 
    58  
    59 The only special stuff is in the pattern.   
    60 The sole change is this: add a single new sort of pattern, of the  
    61 form 
    62         (''expr'' `->` ''pat'') 
    63  
    64 where ''expr'' is an arbitrary Haskell expression.   I'll call a pattern 
    65 of this form a '''view pattern'''.  
    66  
    67 From a '''scoping''' point of view, the variables bound by the pattern (''expr'' `->` ''pat'') 
    68 are simply the variables bound by ``pat``. 
    69 Any variables in ``expr`` are bound occurrences. 
    70  
    71 The rule for '''pattern-matching''' is this: 
    72 To 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  
    77 The '''typing rule''' is similarly simple.   
    78 The expression ''expr'' must have type 
    79 ''t1 `-> Maybe` t2''. Then the pattern ''pat'' must have type ''t2'', and the 
    80 whole pattern (''expr'' `->` ''pat'') has type ''t1''. 
    81  
    82 === Features === 
    83  
    84 For the different features this proposal (and others) have, see [[ref(Features views can have)]]. 
    85 The 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  
    93 It would be quite useful to allow more than one sub-pattern in a view 
    94 pattern.  To do this we'd need a `Maybe` data type that returns more than 
    95 one 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 }}} 
    101 With this in hand we can extend the views story to have multiple sub-patterns. 
    102 Example: 
    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 }}} 
    114 It is tiresome that we need types `Maybe2`, `Maybe3` etc, but we already have  
    115 that in Haskell; consider `zip3`, `zip4` and so on. 
    116 We could always get away without it, by sticking to unary view patterns and 
    117 using 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 }}} 
    129 But the tuple looks a bit clumsy. 
    130  
    131 Under this proposal, the number of sub-patterns in the view pattern determines 
    132 which return type the view function should have.  E.g. in the pattern '(e -> p1 p2 p3)', 
    133 'e' should return a `Maybe3`. 
    134  
    135 If 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 }}} 
    143 Here `even` is used as a nullary view pattern, with no sub-patterns 
    144 following the `->`. 
    145  
    146 Another 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  
    150 Thus far, the view function is required to return a `Maybe` type, with `Nothing` to indicate match 
    151 failure.  An alternative, presented in the Erwig paper on transformational patterns (see Related work below),  
    152 this implicit matching is not performed; instead, the sub-pattern is matched against 
    153 whatever the view function returns.  So you'd have to write: 
    154 {{{ 
    155 f (snoc -> Just2 xs x) = ... 
    156 }}} 
    157 (Note the tiresome `Just2`.) 
    158  
    159 For more one the consequences of removing the implicit `Maybe`, see the [[ref(Implicit `Maybe` feature)]] 
    160  
    161 I 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  
    170 A disadvantage of the arrow syntax is that it looks a bit confusing 
    171 when 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  
    178 Here 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 }}} 
    193 Another possibility is to use a backward arrow, more like pattern guards: 
    194 {{{ 
    195   f ((x,xs) <- snoc) = ...  -- More like pattern guards 
    196 }}} 
    197 But that messes up the left-to-right flow that is useful in some cases. 
    198 For 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  
    205 I also thought about infix view patterns, where the view function 
    206 appears between its (pattern) arguments, but I could not think of a 
    207 nice syntax for it, so it is not provided by this proposal. 
    208  
    209 === Remarks === 
     3[[PageOutline(2-3,,inline)]] 
     4 
     5'''We are about to begin prototyping this extension in GHC, so speak now if you have comments or suggestions!''' 
     6This page has been revised to reflect what we're going to implement.  For the previous discussion, see ViewPatternsArchive. 
     7 
     8== Basic view patterns ==  
     9 
     10View patterns are a convenient way of pattern-matching against values of abstract types.  For example, in a programming language implementation, we might represent the syntax of the types of the language as follows: 
     11 
     12{{{ 
     13   type Typ 
     14  
     15   data TypView = Unit 
     16                | Arrow Typ Typ 
     17 
     18   view :: Type -> TypeView 
     19 
     20   -- additional operations for constructing Typ's ... 
     21}}} 
     22 
     23The representation of `Typ` is held abstract, permitting implementations to use a fancy representation (e.g., hash-consing to managage sharing). 
     24 
     25In current Haskell, using this signature a little inconvenient: 
     26{{{ 
     27   size :: Typ -> Integer 
     28   size t = case t of 
     29     Unit -> 1 
     30     Arrow t1 t2 -> size t1 + size t2 
     31}}} 
     32It is necessary to iterate the case, rather than using an equational function definition.  And the situation is even worse when the matching against `t` is buried deep inside another pattern. 
     33In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against. 
     34 
     35View patterns permit calling the view function inside the pattern and matching against the result: 
     36{{{ 
     37   size (view -> Unit) = 1 
     38   size (view -> Arrow t1 t2) = size t1 + size t2 
     39}}} 
     40 
     41That is, we add a new form of pattern, written  
     42{{{ 
     43   expression -> pattern 
     44}}} 
     45that means "apply the expression to whatever we're trying to match against, and then match the result of that application against the pattern".  The expression can be any Haskell expression of function type, and view patterns can be used wherever patterns are currently used. 
    21046 
    21147The key feature of this proposal is its modesty, rather than its ambition: 
    21248  * 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. 
     49  * The functions used in view patterns are ordinary Haskell functions, and can be called from ordinary Haskell code. 
     50  * No changes are needed to import or export mechanisms. 
    21551  * Both static and dynamic semantics are extremely simple. 
    21652It is essentially some simple syntactic sugar for patterns. 
    217 However, sometimes modest syntactic sugar can have profound consequences. 
    218 In this case, it's possible that people would start routinely hiding 
    219 the data representation and exporting view functions instead, which might 
    220 be an excellent thing. 
    221  
    222 All 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 }}} 
    228 Indeed, one might ask whether the extra syntax for view patterns is worth 
    229 it when they are so close to pattern guards.   
    230 That's a good question.  I'm hoping that support for view patterns 
    231 might encourage people to export view functions (ones with `Maybe` 
    232 return types, and encouage their use in patten matching).  That is, 
    233 just lower the barrier for abstraction a bit. 
    234  
    235 '''Completeness'''.  It is hard to check for completeness of pattern matching; and likewise for 
    236 overlap.  But guards already make both of these hard; and GADTs make completness hard too. 
    237 So matters are not much worse than before. 
    238  
    239  
    240 --------------------------- 
    241 == Features views can have == 
    242  
    243 The 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  
    247 This 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 }}} 
    254 Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc. 
    255  
    256 Of 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  
    262 In 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 }}} 
    268 then you could use it in patterns thus: 
    269 {{{ 
    270   f :: String -> String 
    271   f (regexp "[a-z]*" -> (name, rest)) = ... 
    272 }}} 
    273 Of course, the argument does not need to be a constant as it is here. 
    274  
    275 With 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 }}} 
    280 Here the first argument `p` can be thought of as a pattern passed to `g`, which 
    281 is used to match the second argument of `g`. 
    282  
    283 Here is another rather cute example: 
    284 {{{ 
    285 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]  
    286 unfoldr f (f -> (a, b)) = a : unfoldr f b 
    287 unfoldr f other         = [] 
    288 }}} 
    289  
    290 === Implicit `Maybe` feature === 
    291  
    292 In 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  
    298 Some 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  
    300 By 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  
    316 Projection 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 }}} 
    327 Using a fixed set of multiple alternatives makes it more obvious whether the match is exhaustive or not. 
    328  
    329 While 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 }}} 
    334 represents 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 }}} 
    341 These three properties are expensive to calculate but all three only 
    342 depend on the result of a single depth first search. By projecting the 
    343 disjoint sum to several `Maybe`s, the depth first search has to be 
    344 repeated every time. More importantly, there is *no way* for the compiler to optimize this because that would mean common subexpression elimination across 
    345 functions. 
    346  
    347 Some 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 {{{ 
    349 map f [] = [] 
    350 map f (x: map f -> xs) = x:xs 
    351  
    352 foldr f z [] = z 
    353 foldr f z (x: foldr f z -> xs) =  x `f` xs 
    354 }}} 
    355  
    356 === Transparent ordinary Patterns === 
    357  
    358 The 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 }}} 
    366 This certainly discourages ordinary pattern matching. In other words, 
    367 implementing the proposal has considerable impact on ordinary pattern 
    368 matching (not in semantics but in use). 
    369  
    370 The problem that needs to be solved is to introduce abstraction "after the fact". 
    371  
    372 On 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  
    376 In 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 }}} 
    382 And by the same token, view patterns nest inside each other: 
    383 {{{ 
    384   k :: [[a]] -> a 
    385   k (sing -> sing -> x) = x 
    386 }}} 
    387 This convenient nesting is perhaps the biggest practical  
    388 difference between view patterns and pattern guards. 
    389  
    390 The majority of the proposals allow nesting. 
    391  
    392  
    393 === Integration with type classes === 
    394  
    395 A view mechanism that integrates nicely with type classes would allow 
    396 a single "view" to decompose multiple different data types.  For 
    397 example, a view might work on any type in class Num, or in class Sequence. 
    398  
    399 A good example is Haskell's existing (n+k) patterns.  Here is how they 
    400 can be expressed using the view pattern proposed in this page (with different  
    401 syntax, 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 }}} 
    418 Here a single, overloaded view, `np`, can be used  
    419 in `g`, and `h` to match against values of different types and, 
    420 in `f`'s case, any type in class Num. (Notice too the use of the value  
    421 input feature.) 
    422  
    423 This feature falls out very nicely from view patterns, but  
    424 not from all other proposals. 
    425  
    426 --------------------------- 
    427 == Efficiency of Views == 
    428  
    429 View patterns can do arbitrary computation, perhaps expensive. 
    430  
    431 It's reasonable to expect the compiler to avoid repeated computation when 
    432 pattern line up in a column: 
    433 {{{ 
    434   f (snoc -> x xs) True  = ... 
    435   f (snoc -> x xs) False = ... 
    436 }}} 
    437 In pattern-guard form, common sub-expression should achieve the same 
    438 effect, but it's quite a bit less obvious.  We should be able to give 
    439 clear rules for when the avoidance of repeat computation is 
    440 guaranteed. 
    441  
    442 --------------------------- 
    443 == Use cases and examples == 
    444  
    445 Whether 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  
    449 Lists, 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 
     53However, sometimes modest syntactic sugar can have profound consequences. In this case, it's possible that people would start routinely hiding the data representation and exporting view functions instead, which would be an excellent thing. 
     54 
     55=== Semantics === 
     56 
     57'''Scoping''' for ''expr `->` ''pat: 
     58 * The variables bound by the view pattern are the variables bound by ''pat''. 
     59 * Any variables in ''expr'' are bound occurrences.  Variables bound by patterns to the left of a view pattern expression are in scope.  For example: 
     60   * In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments. 
     61{{{ 
     62   example :: (String -> Integer) -> String -> Bool 
     63   example f (f -> 4) = True 
     64}}} 
     65   * Variables can be bound to the left in tuples and data constructors: 
     66{{{ 
     67   example :: ((String -> Integer,Integer), String) -> Bool 
     68   example ((f,_), f -> 4) = True 
     69}}} 
     70 
     71'''Typing''' 
     72If ''expr'' has type ''t1'' `->` ''t2'' and  ''pat'' matches a ''t2'',  then the whole view pattern has type ''t1''. 
     73 
     74'''Evaluation''' 
     75To match a value ''v'' against a pattern (''expr'' `->` ''pat''), evaluate ''(expr v)'' and match the result against ''pat''.   
     76 
     77=== Examples ===  
     78 
     79We discuss some examples of pattern-matching abstract types and of other  uses of view patterns here. 
     80 
     81==== Join lists ==== 
     82The requisite join-list example: 
     83{{{ 
     84   data JList a = Empty  
     85                | Single a 
     86                | Join (JList a) (JList a) 
     87  
     88   data JListView a = Nil 
     89                    | Cons a (JList a) 
     90}}} 
     91Here 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.   
     92 
     93The implementation of the view: 
     94{{{ 
     95  view :: JList a -> JListView a 
     96  view Empty = Nil 
     97  view (Single a) = Cons a Empty 
     98  view (Join (view -> Cons xh xt) y) = Cons xh $ Join xt y 
     99  view (Join (view -> Nil) y) = view y 
     100}}} 
     101Note the recursive uses of the view function in view patterns within its own definition. 
     102 
     103An example of using it: 
     104{{{ 
     105  length :: JList a -> Integer 
     106  length (view -> Nil) = 0 
     107  length (view -> Cons x xs) = 1 + length xs 
     108}}} 
     109 
     110For more general sequences, `Data.Sequence` already defines the views from the left and from the right 
    450111{{{ 
    451112   data ViewL a 
     
    461122   viewr :: Seq a -> ViewR a 
    462123}}} 
    463  
    464 Thus, 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  
    466 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. 
    467  
    468 === Designing data structures === 
    469  
    470 The 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  
    477 Having 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. 
     124that now may be used in view patterns. 
     125 
     126==== Partial views ==== 
     127 
     128Here'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: 
     129 
     130{{{ 
     131   type Typ 
     132 
     133   outUnit  : Typ -> Maybe () 
     134   outArrow : Typ -> Maybe (Typ, Typ) 
     135 
     136   -- additional operations for constructing Typ's ... 
     137}}} 
     138 
     139This view is used as follows: 
     140 
     141{{{ 
     142   size (outUnit -> Just _) = 1 
     143   size (outArrow -> Just (t1, t2)) = size t1 + size t2 
     144}}} 
     145 
     146This style should be discouraged when the view is in fact a total operation, as it moves the documentation of this fact out of the type system, making it harder for both people and the compiler to check exhaustiveness.  However, it may be a useful idiom for defining a partial matching function with several constructors (e.g., in XML processing). 
     147 
     148==== Sets ==== 
    478149 
    479150Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby. 
    480 {{{ 
    481 module Set( Set, empty, insert, delete, has) where 
     151 
     152{{{ 
     153module Set(Set, empty, insert, delete, has) where 
    482154 
    483155  newtype Set a = S [a] 
     
    488160   
    489161  delete :: a -> Set a -> Set a 
    490   delete x (has x -> s) = s 
    491   delete x s            = s 
     162  delete x (has x -> Just s) = s 
     163  delete x s                 = s 
    492164   
    493165  insert :: a -> Set a -> Set a 
     
    495167  insert x (S xs)         = S (x:xs) 
    496168}}} 
    497 Notice 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  
    501 The expression to the left of the `->` can mention variables bound in earlier patterns. 
    502 For 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 
     169 
     170Note the use of the previous argument `x` in later view patterns. 
     171 
     172==== Erlang-style parsing ==== 
     173 
     174Sagonas 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: 
     175{{{ 
     176  bits :: Int -> ByteString -> Maybe (Word, ByteString) 
    505177  -- (bits n bs) parses n bits from the front of bs, returning 
    506178  -- the n-bit Word, and the remainder of bs 
     
    509181{{{ 
    510182  parsePacket :: ByteString -> ... 
    511   parsePacket (bits 3 -> n (bits n -> val bs)) = ... 
    512 }}} 
    513 This parses 3 bits to get the value of `n`, and then parses `n` bits to get 
    514 the value of `val`.   
    515  
    516 === N+k patterns === 
    517  
    518 You can test for values.  For example here's a view function that tests for values  
    519 greater than or equal to n: 
     183  parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ... 
     184}}} 
     185This 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. 
     186 
     187==== N+k patterns ==== 
     188 
     189`(n+k)` patterns use the following view function: 
    520190{{{ 
    521191   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 }}} 
    530 You 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 
    532 that its use in a view pattern gives rise to a type-class constraint (in this case, 
    533 that in turn makes `f` overloaded). 
    534  
    535 === Naming constants in one place === 
    536  
    537 We are always taught to write magic numbers, or constants, in one place only. 
    538 In C you can write 
    539 {{{ 
    540   #define ERRVAL 4 
    541 }}} 
    542 and then use `ERRVAL` in `switch` labels.  You can't do that in Haskell, which is tiresome. 
    543 But with view pattern you can: 
    544 {{{ 
    545   errVal :: Int -> Bool 
    546   errVal = (== 4) 
    547  
    548   f (errVal ->) = ... 
    549 }}} 
    550  
    551  
    552 ------------------------- 
     192   np k n | k <= n = Just (n-k) 
     193           | otherwise = Nothing 
     194}}} 
     195 
     196They are used as follows: 
     197{{{ 
     198   fib :: Num a -> a -> a 
     199   fib 0 = 1 
     200   fib 1 = 1 
     201   fib (np 2 -> Just n) = fib (n + 1) + fib n 
     202}}} 
     203Note the integration with type classes: the view function can be overloaded, and its use in a view pattern gives rise to a type-class constraint (in this case, that in turn makes `fib` overloaded). 
     204 
     205`n+k` patterns are another a good opportunity for passing view data at run-time, as in: 
     206{{{ 
     207   example k (np k -> Just n) = ... 
     208}}} 
     209 
     210==== Named constants ==== 
     211 
     212View patterns can be used to pattern match against named constants: 
     213{{{ 
     214    errorVal :: Int -> Bool 
     215    errorVal = (== 4) 
     216    f (errorVal -> True) =  ... 
     217}}} 
     218 
     219==== Both patterns ==== 
     220 
     221A "both pattern" `pat1 & pat2` matches a value against both `pat1` and `pat2` and succeeds only when they both succeed.  A special case is as-patterns, `x@p`, where the first pattern is a variable.  Both patterns can be programmed using view patterns: 
     222{{{ 
     223   both : a -> (a,a) 
     224   both x = (x,x) 
     225}}} 
     226 
     227And used as follows: 
     228{{{ 
     229   f (both -> (xs, h : t)) = h : (xs ++ t) 
     230}}} 
     231 
     232(However, this might cause a loss of sharing.) 
     233 
     234==== Iterator Style ==== 
     235 
     236View patterns permit programming in an iterator style, where you name the result of a recursive call but not the term the call was made on.  E.g.: 
     237{{{ 
     238   length [] = [] 
     239   length (x : length -> xs) = x + xs 
     240    
     241   map f [] = [] 
     242   map f (x : map f -> xs) = x : xs 
     243    
     244   foldr f z [] = z 
     245   foldr f z (x : foldr f z -> xs) =  x `f` xs 
     246 
     247   unfoldr :: (b -> Maybe (a, b)) -> b -> [a]  
     248   unfoldr f (f -> Just (a, unfoldr f -> b)) = a : b 
     249   unfoldr f other         = [] 
     250}}} 
     251 
     252== Further Syntactic Extensions == 
     253 
     254Next, we describe two further syntactic extensions that we will implement.   
     255 
     256=== Implicit Maybe === 
     257 
     258Above, we saw several examples of view functions that return a `Maybe`, including: 
     259{{{ 
     260   np :: Num a => a -> a -> Maybe a 
     261   np k n | k <= n = Just (n-k) 
     262           | otherwise = Nothing 
     263}}} 
     264which were used as follows: 
     265{{{ 
     266   fib (np 2 -> Just n) = fib (n + 1) + fib n 
     267}}} 
     268 
     269We may implement a special syntax that makes the `Just` implicit, using ''expr'' `=>` ''pat'' for ''expr'' `-> Just` ''pat''.  An example use:  
     270{{{ 
     271   fib (np 2 => n) = fib (n + 1) + fib n 
     272}}} 
     273 
     274This syntax works very nicely with partial views: 
     275{{{ 
     276   size (outUnit => _) = 1 
     277   size (outArrow => (t1, t2)) = size t1 + size t2 
     278}}} 
     279 
     280==== Implicit Tupling ==== 
     281 
     282A further syntactic extension would be to have implcit Maybes with implicit tupling: multiple patterns after the `=>` are implicitly tupled.  Then you could write: 
     283{{{ 
     284   size (outArrow => t1 t2) = size t1 + size t2 
     285}}} 
     286 
     287=== Implicit View Functions === 
     288 
     289Total 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.   
     290 
     291The idea is that we distinguish a particular type class as a hook into the pattern compiler.  The class has the following interface: 
     292{{{ 
     293   class View a b where 
     294      view :: a -> b 
     295}}} 
     296 
     297Then, you can leave off the expresion in a view pattern, writing (`->` ''pat''), to mean `view -> ` ''pat''.  For example: 
     298{{{ 
     299   size (-> Unit) = 1 
     300   size (-> Arrow t1 t2) = size t1 + size t2 
     301}}} 
     302 
     303means  
     304 
     305{{{ 
     306   size (view -> Unit) = 1 
     307   size (view -> Arrow t1 t2) = size t1 + size t2 
     308}}} 
     309 
     310for the overloaded `view`.   
     311 
     312To use this mechanism, you add instances to `view`, as in: 
     313 
     314{{{ 
     315   instance View Typ TypView where 
     316     view = (the view function from above) 
     317}}} 
     318 
     319This 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.   
     320 
     321Of 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. 
     322 
     323==== Functional dependencies ==== 
     324The above implementation of `size` is given the following type: 
     325{{{ 
     326   size :: View a TypView -> a -> Int 
     327}}} 
     328which may or may not be what you want.  (For example, with nested view patterns, you can get into situations where the middle type connecting two view patterns is not determined.)   
     329 
     330Thus, it may be better to make one parameter of the type class determine the other (using associated type synonyms): 
     331{{{ 
     332   class View a where 
     333      type View a  
     334      view :: a -> View a 
     335}}} 
     336or  
     337{{{ 
     338   class View b where 
     339      type Hidden b  
     340      view :: Hidden b -> a 
     341}}} 
     342 
     343Of 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. 
     344The 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. 
     345 
     346== Compilation == 
     347 
     348'''Efficiency'''  View patterns can do arbitrary computation, perhaps expensive. 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. 
     349 
     350'''Exhaustiveness/Redundancy.'''  It is hard to check for completeness of pattern matching; and likewise for overlap.  But guards already make both of these hard; and GADTs make completness tricky too. So matters are not much worse than before. 
     351 
     352== Features views can have == 
     353 
     354In comparing the different views proposals below, it will be useful to have terminology for some features of views. 
     355 
     356==== Value input feature ==== 
     357 
     358Our 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. 
     359 
     360==== Implicit `Maybe` feature ==== 
     361 
     362Our proposal has the ''implicit `Maybe`'' feature: the syntax ''expr'' `=>` ''pat'' permits the programmer to elide the `Just`, for example when using partial views.   
     363 
     364==== Transparent ordinary Patterns ==== 
     365 
     366Our proposal does not have the ''transparent ordinary patterns'' feature: view patterns are written differently than ordinary patterns. 
     367There are pros and cons both ways: 
     368The 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.   
     369 
     370==== Nesting ==== 
     371 
     372Our 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. 
     373 
     374==== Integration with type classes ==== 
     375 
     376Our 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.   
     377 
    553378== Related work == 
    554379 
    555 === Wadler's original paper (POPL 1987) === 
     380==== [http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps Wadler's original paper (POPL 1987)] ==== 
    556381 
    557382Wadler's paper was the first concrete proposal.  It proposed a top-level view 
     
    563388view constructors to appear in patterns only. 
    564389 
    565 === [http://haskell.org/development/views.html Burton et al views (1996)] === 
     390==== [http://haskell.org/development/views.html Burton et al views (1996)] ==== 
    566391 
    567392This proposal is substantially more complicated than the one above; in particular it 
     
    581406abstract data types", Burton and Cameron, JFP 3(2), Apr 1993. 
    582407 
    583 === [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] === 
     408==== [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] ==== 
    584409 
    585410Okasaki's design is very similar to Burton et al's, apart from differences due 
    586411to the different host language.  Again, the value input feature is not supported. 
    587412 
    588 === [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] === 
     413==== [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] ==== 
    589414 
    590415Erwig's proposal for active patterns renders the Set example like this: 
     
    607432Still the proposal does support the value input feature. 
    608433 
    609 === [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] === 
    610  
    611 Active Desctructors (ADs) are defined by a new form of top-level declaration.  Our 
    612 singleton example would look like this: 
     434==== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM Palao et al: active destructors (ICFP'96)] ==== 
     435 
     436Active Destructors (ADs) are defined by a new form of top-level declaration.   
     437 
     438Where we'd write 
     439{{{ 
     440   sing :: [a] -> a option 
     441   sing [x] = x  
     442}}} 
     443The equivalent active destructor would be 
    613444{{{ 
    614445  Sing x match [x] 
     
    619450a special form of type to describe them. 
    620451 
    621 The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the 
    622 new form of type. 
     452The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the new form of type. 
    623453 
    624454They also introduce a combining form for ADs, to make a kind of and-pattern.  For 
     
    631461  f ((Head x)@(Tail ys)) = x:x:ys 
    632462}}} 
    633 Here `(Head x)@(Tail ys)` is a pattern that matches ''both'' `(Head x)` and `(Tail ys)` 
    634 against the argument, binding `x` and `ys` respectively.  We can model that with view patterns, 
    635 only a bit more clumsily: 
     463Here `(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: 
    636464{{{ 
    637465  headV (x:xs) = Just x 
     
    641469  tailV []     = Nothing 
    642470 
     471  f (both -> (headV => x, tailV => ys)) = x:x:ys 
     472}}} 
     473 
     474An alternative to duplicating the value is to compose the functions: 
     475{{{ 
    643476  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c) 
    644477  (f @ g) x = do { b <- f x; c <- g x; return (b,c) } 
     
    647480  f (headV @ tailV -> (x,ys)) = x:x:ys 
    648481}}} 
    649 The clumsiness is that the "`@`" combines functions, with a kind of positional 
    650 binding; the pattern `(x,ys)` is separated from the combiner so that it's less clear 
    651 that `headV` binds `x` and `tailV` binds `y`. 
    652  
    653 In exchange, although view patterns are a bit less convenient here, they  
    654 are a much, much smaller language change than ADs. 
    655  
    656 === [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] === 
     482This 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`. 
     483 
     484==== [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] ==== 
    657485 
    658486This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although 
     
    661489so that the only changes are to patterns themselves. 
    662490 
    663 There are two main differences (apart from syntax). 
     491There are two main differences (apart from syntax).  
    664492First, transformational patterns didn't have the value input feature, althought it'd be easy  
    665493to add (indeed that's what we've done). Second, transformational patterns as described by 
    666494Erwig do no stripping of the `Maybe` (see "Possible extension 2" above). 
    667495 
    668 === [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] === 
     496==== [http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx F# Active Patterns] ==== 
    669497 
    670498Simon 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. 
     
    713541}}} 
    714542 
    715 === [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] === 
     543==== [http://lambda-the-ultimate.org/node/1960 Emir, Odersky, Williams: Matching objects with patterns] ==== 
    716544 
    717545Scala is an OO language with lots of functional features.  It has algebraic data types and 
     
    724552concludes that case expressions and extractors work pretty well. 
    725553 
    726 === Pattern synonyms  === 
     554==== Pattern synonyms  ==== 
    727555 
    728556[http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms]  
     
    731559Reppy & Aiken, TR 92-1290, Cornell, June 1992. 
    732560 
    733 The one way in which pattern synonyms are better than view patterns is that 
    734 they define by-construction bi-directional maps.  Example 
     561The one way in which pattern synonyms are better than view patterns is thatn they define by-construction bi-directional maps.  Example 
    735562{{{ 
    736563  data Term = Var String | Term String [Term] 
     
    755582  f (isPlus -> a b) = plus (f a) (f b) 
    756583}}} 
    757 But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration; 
    758 and 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] === 
     584But 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). 
     585 
     586==== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] ==== 
    761587 
    762588First Class Patterns is an approach that attempts to 
     
    7756014) 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. 
    776602 
    777 The examples at the top of this page would look like this with first class patterns: 
     603The singleton example above would like this: 
    778604{{{ 
    779605  f = {%sing n} .-> n+1 
     
    784610                     |>> 2   
    785611}}} 
    786 === First class abstractions === 
     612 
     613==== First class abstractions ==== 
    787614 
    788615Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.  By a "first class abstraction" I mean a value of type 
     
    810637proposal deals with.  Hence orthgonal. 
    811638 
    812 === Barry Jay: First class patterns === 
     639==== Barry Jay: First class patterns ==== 
    813640 
    814641A 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. 
     642 
     643==== Uses of Views ==== 
     644 
     645The 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. 
     646 
     647The abstractional power views offer can also be put to good use when designing data structures, as the following papers show 
     648 
     649  * [http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz R.Hinze: A fresh look on binary search trees]. 
     650  * [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf R.Hinze:  A Simple Implementation Technique for Priority Search Queues] 
     651  * 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. 
     652 
     653