Changes between Version 18 and Version 19 of ViewPatterns


Ignore:
Timestamp:
Jan 25, 2007 11:23:17 AM (7 years ago)
Author:
guest
Comment:

agglomerating the lightweight proposal

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatterns

    v18 v19  
    1919solution for this problem.   (See the end for a comparison with related work.) 
    2020 
    21 == The proposal informally == 
     21--------------------------- 
     22== The lightweight view proposal == 
     23=== Informally === 
    2224 
    2325The proposal introduces a new form of pattern, called a '''view pattern''' 
     
    5355of `sing` might not have intended it to be used in pattern matching.   
    5456 
    55 --------------------------- 
    56 == The proposal more formally == 
     57=== More formally === 
    5758 
    5859The only special stuff is in the pattern.   
     
    7980whole pattern (''expr'' `->` ''pat'') has type ''t1''. 
    8081 
    81 === Nesting === 
    82  
    83 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 
    84 {{{ 
    85   f (sing -> x, True) = ... 
    86   g (Just (sing -> x)) = ... 
    87   h (Just (sing -> Just x)) = ... 
    88 }}} 
    89 And by the same token, view patterns nest inside each other: 
    90 {{{ 
    91   k :: [[a]] -> a 
    92   k (sing -> sing -> x) = x 
    93 }}} 
    94 This convenient nesting is perhaps the biggest practical  
    95 difference between view patterns and pattern guards. 
    96  
    97  
    98 === The value input feature === 
    99  
    100 Note that the ''expr'' is an arbitrary Haskell expression. For example, suppose you wrote 
    101 a regular expression matching function: 
    102 {{{ 
    103   regexp :: String -> String -> Maybe (String, String) 
    104   -- (regexp r s) parses a string matching regular expression r  
    105   --    the front of s, returning the matched string and remainder of s 
    106 }}} 
    107 then you could use it in patterns thus: 
    108 {{{ 
    109   f :: String -> String 
    110   f (regexp "[a-z]*" -> (name, rest)) = ... 
    111 }}} 
    112 Of course, the argument does not need to be a constant as it is here. 
    113  
    114 '''This ability to pass arguments to the view function, to guide its matching 
    115 behaviour, is a key feature of this proposal,''' shared by some, but by no means 
    116 all view proposals.  I'll call it the '''value input feature'''.   
    117  
    118 Indeed, in a sense, patterns become first class.  For example, one could pass a pattern 
    119 as an argument to a function thus: 
    120 {{{ 
    121   g :: (Int -> Maybe Int) -> Int -> ... 
    122   g p (p -> x) = ... 
    123 }}} 
    124 Here the first argument `p` can be thought of as a pattern passed to `g`, which 
    125 is used to match the second argument of `g`.  
    126  
    127 Here is another rather cute example: 
    128 {{{ 
    129 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]  
    130 unfoldr f (f -> (a, b)) = a : unfoldr f b 
    131 unfoldr f other         = [] 
    132 }}} 
     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 
    13390 
    13491=== Possible extension 1: multi-argument view patterns === 
     
    199156}}} 
    200157(Note the tiresome `Just2`.) 
    201 The benefit of not having the implicit matching is that you can write functions that are, perhaps, 
    202 more view-like.  Example: 
    203 {{{ 
    204 data Product = ....some big data type... 
    205  
    206 data Size = Small | Medium | Big        -- View type 
    207 prodSize :: Product -> Size 
    208 prodSize = .... 
    209  
    210 f :: Product -> ... 
    211 f (prodSize -> Small)  = ... 
    212 f (prodSize -> Medium) = ... 
    213 f (prodSize -> Big)    = ... 
    214 }}} 
    215 With the built-in `Maybe` proposal, you'd instead write something like this: 
    216 {{{ 
    217 smallProd, medProd, bigProd :: Product -> Bool 
    218 smallProd p = ... 
    219 medProd   p = ... 
    220 bigProd   p = ... 
    221  
    222 f :: Product -> ... 
    223 f (smallProd ->) = ... 
    224 f (medProd   ->) = ... 
    225 f (bigProd   ->) = ... 
    226 }}} 
    227 This is not obviously worse, except that the first version is more 
    228 obviously exhaustive.  Incidentally, both should generate the same 
    229 code. 
     158 
     159For more one the consequences of removing the implicit `Maybe`, see the [[ref(Implicit `Maybe` feature)]] 
    230160 
    231161I can think of three alternatives: 
     
    235165    * ''(expr `->` pat)'' for the built-in `Maybe` story 
    236166    * ''(expr `=>` pat)'' with no bulit-in `Maybe` 
    237   
    238 == Efficiency == 
    239  
    240 View patterns can do arbitrary computation, perhaps expensive.  So 
    241 it's good to have a syntactically-distinct notation that reminds the 
    242 programmer that some computation beyond ordinary pattern matching may 
    243 be going on. 
    244  
    245 It's reasonable to expect the compiler to avoid repeated computation when 
    246 pattern line up in a column: 
    247 {{{ 
    248   f (snoc -> x xs) True  = ... 
    249   f (snoc -> x xs) False = ... 
    250 }}} 
    251 In pattern-guard form, common sub-expression should achieve the same 
    252 effect, but it's quite a bit less obvious.  We should be able to give 
    253 clear rules for when the avoidance of repeat computation is 
    254 guaranteed. 
     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 
    255239 
    256240--------------------------- 
     
    408392 
    409393The majority of the proposals allow nesting. 
     394 
     395 
     396--------------------------- 
     397== Efficiency of Views == 
     398 
     399View patterns can do arbitrary computation, perhaps expensive. 
     400 
     401It's reasonable to expect the compiler to avoid repeated computation when 
     402pattern line up in a column: 
     403{{{ 
     404  f (snoc -> x xs) True  = ... 
     405  f (snoc -> x xs) False = ... 
     406}}} 
     407In pattern-guard form, common sub-expression should achieve the same 
     408effect, but it's quite a bit less obvious.  We should be able to give 
     409clear rules for when the avoidance of repeat computation is 
     410guaranteed. 
    410411 
    411412--------------------------- 
     
    487488}}} 
    488489 
    489 == Concrete syntax == 
    490 A disadvantage of the arrow syntax is that it looks a bit confusing 
    491 when it appears in a case expression: 
    492 {{{ 
    493   last xs = case xs of 
    494                 (snoc -> x xs) -> x 
    495 }}} 
    496 (Also that "x xs" looks a bit like `x` applied to `xs`.) 
    497  
    498 Here are some other possible syntax choices I've considered: 
    499 {{{ 
    500   f ($snoc x xs) = ...          -- Use prefix "$" 
    501   g ($(bits 3) x bs) = ...      -- Extra parens for the value input feature 
    502  
    503   f (%snoc x xs) = ...          -- Or use prefix "%" instead 
    504  
    505   f (.snoc x xs) = ...          -- Or use prefix "." instead 
    506  
    507   f (snoc | x xs) = ..          -- Use "|" instead of "->" 
    508   g (bits 3 | b bs) = ... 
    509 }}} 
    510 Another possibility is to use a backward arrow, more like pattern guards: 
    511 {{{ 
    512   f ((x,xs) <- snoc) = ...  -- More like pattern guards 
    513 }}} 
    514 But that messes up the left-to-right flow that is useful in some cases. 
    515 For example, compare these: 
    516 {{{ 
    517   parsePacket1 (bits 3 -> n (bits n -> val bs)) = ... 
    518  
    519   parsePacket2 (n (val bs <- bits n) <- bits 3) = ... 
    520 }}} 
    521  
    522 I also thought about infix view patterns, where the view function 
    523 appears between its (pattern) arguments, but I could not think of a 
    524 nice syntax for it, so it is not provided by this proposal. 
    525  
    526 == Remarks == 
    527  
    528 The key feature of this proposal is its modesty, rather than its ambition: 
    529   * There is no new form of declaration (e.g. 'view' or 'pattern synonym').   
    530   * The functions used in view patterns are ordinary Haskell functions, and can be called from ordinary Haskell code.  They are not special view functions. 
    531   * Since the view functions are ordinary Haskell functions, no changes are needed to import or export mechanisms. 
    532   * Both static and dynamic semantics are extremely simple. 
    533 It is essentially some simple syntactic sugar for patterns. 
    534 However, sometimes modest syntactic sugar can have profound consequences. 
    535 In this case, it's possible that people would start routinely hiding 
    536 the data representation and exporting view functions instead, which might 
    537 be an excellent thing. 
    538  
    539 All this could be done with pattern guards.  For example `parsePacket` could be written 
    540 {{{ 
    541   parsePacket bs | Just (n, bs')    <- bits 3 bs 
    542                  | Just (val, bs'') <- bits n bs' 
    543                  = ... 
    544 }}} 
    545 Indeed, one might ask whether the extra syntax for view patterns is worth 
    546 it when they are so close to pattern guards.   
    547 That's a good question.  I'm hoping that support for view patterns 
    548 might encourage people to export view functions (ones with `Maybe` 
    549 return types, and encouage their use in patten matching).  That is, 
    550 just lower the barrier for abstraction a bit. 
    551  
    552 '''Completeness'''.  It is hard to check for completeness of pattern matching; and likewise for 
    553 overlap.  But guards already make both of these hard; and GADTs make completness hard too. 
    554 So matters are not much worse than before. 
    555  
    556490 
    557491-------------------------