Changes between Version 18 and Version 19 of ViewPatterns


Ignore:
Timestamp:
Jan 25, 2007 11:23:17 AM (9 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-------------------------