Changes between Version 1 and Version 2 of ViewPatterns


Ignore:
Timestamp:
Jan 22, 2007 2:39:45 PM (9 years ago)
Author:
anonymous
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatterns

    v1 v2  
    1 = Lightweigtht Views in Haskell =
     1= View patterns: lightweight views for Haskell =
    22
    3 This page describes a rather lightweight proposal for adding views to
    4 Haskell Prime.  I'm thinking of prototyping the idea in GHC, so I'm looking
    5 for feedback.
    6 
    7 == The problem ==
    8 
    9 We are keen on abstraction, but pattern matching is so convenient that
    10 we break abstractions all the time.  It's our dirty little secret.
    11 Looked at this way, object-oriented folk are much more obsessive
    12 about abstraction than we are: everything (including field access
    13 these days) is a method.
    14 
    15 Views have, in one form or another, repeatedly been proposed as a
    16 solution for this problem.   (See the end for a comparison with related work.)
    17 
    18 == The proposal informally ==
    19 
    20 The proposal introduces a new form of pattern, called a '''view pattern'''
    21 Here are some function definitions using view patterns.
    22 To read these definitions, imagine that `$sing` is
    23 a sort of constructor that matches singleton lists.
    24 {{{
    25   f :: [Int] -> Int
    26   f (sing -> n) = n+1   -- Equiv to: f [x] = ...
    27   f other     = 0
    28 
    29   g :: [Bool] -> Int
    30   g (sing -> True)  = 0         -- Equiv to: g [True] = ...
    31   g (sing -> False) = 1         -- Equiv to: g [False] = ...
    32   g other           = 2
    33 
    34   h :: [[Int]] -> Int   
    35   h ($sing -> x : $sing -> y : _) = x+y
    36                         -- Equiv to: h ([x]:[y]:_) = ...
    37   h other = 0
    38 }}}
    39 So what is `sing`?  It is just an ordinary Haskell function that
    40 returns a `Maybe` type:
    41 {{{
    42   sing :: [a] -> Maybe a
    43   sing [x]   = Just x
    44   sing other = Nothing
    45 }}}
    46 So `sing` simply identifies singleton lists, and returns the payload (that is,
    47 the singleton element; otherwise it returns `Nothing`.
    48 It is very important that '''there is nothing special about `sing`'''.  It is
    49 not declared to be a view; it can be called as a normal Haskell function; the author
    50 of `sing` might not have intended it to be used in pattern matching. 
    51 
    52 ---------------------------
    53 == The proposal more formally ==
    54 
    55 The only special stuff is in the pattern. 
    56 The sole change is this: add a single new sort of pattern, of the
    57 form
    58         (''expr'' `->` ''pat'')
    59 
    60 where ''expr'' is an arbitrary Haskell expression.   I'll call a pattern
    61 of this form a '''view pattern'''.
    62 
    63 From a '''scoping''' point of view, the variables bound by the pattern (''expr'' `->` ''pat'')
    64 are simply the variables bound by ``pat``.
    65 Any variables in ``expr`` are bound occurrences.
    66 
    67 The rule for '''pattern-matching''' is this:
    68 To match a value ''v'' against a pattern ''($expr -> p)'',
    69   * Evaluate ''(expr v)''
    70   * If the result is ''(`Just` w)'', match ''w'' against ''p''
    71   * If the result is `Nothing`, the match fails.
    72 
    73 The '''typing rule''' is similarly simple. 
    74 The expression ''expr'' must have type
    75 ''t1 `-> Maybe` t2''. Then the pattern ''pat'' must have type ''t2'', and the
    76 whole pattern (''expr'' `->` ''pat'') has type ''t1''.
    77 
    78 === The value input feature ===
    79 
    80 Note that the ''expr'' is an arbitrary Haskell expression. For example, suppose you wrote
    81 a regular expression matching function:
    82 {{{
    83   regexp :: String -> String -> Maybe (String, String)
    84   -- (regexp r s) parses a string matching regular expression r
    85   --    the front of s, returning the matched string and remainder of s
    86 }}}
    87 then you could use it in patterns thus:
    88 {{{
    89   f :: String -> String
    90   f (regexp "[a-z]*" -> (name, rest)) = ...
    91 }}}
    92 Of course, the argument does not need to be a constant as it is here.
    93 
    94 '''This ability to pass arguments to the view function, to guide its matching
    95 behaviour, is a key feature of this proposal,''' shared by some, but by no means
    96 all view proposals.  I'll call it the '''value input feature'''. 
    97 
    98 Indeed, in a sense, patterns become first class.  For example, one could pass a pattern
    99 as an argument to a function thus:
    100 {{{
    101   g :: (Int -> Maybe Int) -> Int -> ...
    102   g p (p -> x) = ...
    103 }}}
    104 Here the first argument `p` can be thought of as a pattern passed to `g`, which
    105 is used to match the second argument of `g`.
    106 
    107 === A possible extension ===
    108 
    109 It would be quite useful to allow more than one sub-pattern in a view
    110 pattern.  To do this we'd need a `Maybe` data type that returns more than
    111 one result, thus:
    112 {{{
    113   data Maybe2 a b   = Nothing2 | Just2 a b
    114   data Maybe3 a b c = Nothing3 | Just3 a b c
    115         -- ..etc..., up to 8 perhaps (sigh)
    116 }}}
    117 With this in hand we can extend the views story to have multiple sub-patterns.
    118 Example:
    119 {{{
    120   snoc :: [a] -> Maybe2 [a] a
    121   snoc [] = Nothing2
    122   snoc (x:xs) = case snoc xs of
    123                   Nothing2   -> Just2 [] x
    124                   Just2 ys y -> Just2 (x:ys) y
    125 
    126   last :: [Int] -> Int
    127   last (snoc -> xs x) = x
    128   last other = error "empty list"
    129 }}}
    130 It is tiresome that we need types `Maybe2`, `Maybe3` etc, but we already have
    131 that in Haskell; consider `zip3`, `zip4` and so on.
    132 We could always get away without it, by sticking to unary view patterns and
    133 using tuples, thus:
    134 {{{
    135   snoc :: [a] -> Maybe2 ([a], a)
    136   snoc [] = Nothing
    137   snoc (x:xs) = case snoc xs of
    138                   Nothing     -> Just ([], x)
    139                   Just (ys,y) -> Just (x:ys, y)
    140 
    141   last :: [Int] -> Int
    142   last (snoc -> (xs, x)) = x
    143   last other = error "empty list"
    144 }}}
    145 But the tuple looks a bit clumsy.
    146 
    147 Under this proposal, the number of sub-patterns in the view pattern determines
    148 which return type the view function should have.  E.g. in the pattern '(e -> p1 p2 p3)',
    149 'e' should return a `Maybe3`.
    150 
    151 If n=0, then we want `Maybe0`, which is called `Bool`.  Thus
    152 {{{
    153   even :: Int -> Bool
    154   even n = n `div` 2 == 0
    155 
    156   f (even ->) = ...     -- Matches even numbers
    157   f other     = ...
    158 }}}
    159 Here `even` is used as a nullary view pattern, with no sub-patterns
    160 following the `->`.
    161 
    162 == Efficiency ==
    163 
    164 View patterns can do arbitrary computation, perhaps expensive.  So
    165 it's good to have a syntactically-distinct notation that reminds the
    166 programmer that some computation beyond ordinary pattern matching may
    167 be going on.
    168 
    169 It's reasonable to expect the compiler to avoid repeated computation when
    170 pattern line up in a column:
    171 {{{
    172   f (snoc -> x xs) True  = ...
    173   f (snoc -> x xs) False = ...
    174 }}}
    175 In pattern-guard form, common sub-expression should achieve the same
    176 effect, but it's quite a bit less obvious.  We should be able to give
    177 clear rules for when the avoidance of repeat computation is
    178 guaranteed.
    179 
    180 
    181 ---------------------------
    182 == More examples ==
    183 
    184 === Erlang-style parsing ===
    185 
    186 The expression to the left of the `->` can mention variables bound in earlier patterns.
    187 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:
    188 {{{
    189   bits :: Int -> ByteString -> Maybe2 Word ByteString
    190   -- (bits n bs) parses n bits from the front of bs, returning
    191   -- the n-bit Word, and the remainder of bs
    192 }}}
    193 Then we could write patterns like this:
    194 {{{
    195   parsePacket :: ByteString -> ...
    196   parsePacket (bits 3 -> n (bits n -> val bs)) = ...
    197 }}}
    198 This parses 3 bits to get the value of `n`, and then parses `n` bits to get
    199 the value of `val`. 
    200 
    201 === Sets as lists ===
    202 
    203 Here is a module implementing sets as lists:
    204 {{{
    205 module Set( Set, empty, insert, delete, has) where
    206 
    207   newtype Set a = S [a]
    208  
    209   has :: Eq a => a -> Set a -> Maybe (Set a)
    210   has x (S xs) | x `elem` xs = Just (xs \\ x)
    211                | otherwise   = Nothing
    212  
    213   delete :: a -> Set a -> Set a
    214   delete x (has x -> s) = s
    215   delete x s            = s
    216  
    217   insert :: a -> Set a -> Set a
    218   insert x s@(has x -> _) = s
    219   insert x s              = s
    220 }}}
    221 Notice that in the left-hand side `delete x (has x -> s)`, the first `x` is a binding occurrence,
    222 but the second is merely an argument to `has` and is a bound occurrence.
    223 
    224 === N+k patterns ===
    225 
    226 You can test for values.  For example here's a view function that tests for values
    227 greater than or equal to n:
    228 {{{
    229    np :: Num a => a -> a -> Maybe a
    230    np k n | k <= n    = Just (n-k)
    231           | otherwise = Nothing
    232 
    233    f :: Num a => a -> Int
    234    f (np 10 -> n) = 0           -- Matches values >= 10
    235    f (np 4  -> n) = 1           -- Matches values >= 4
    236    f other        = 2
    237 }}}
    238 You will recognise these as (n+k) patterns, albeit with slightly different syntax.
    239 (Incidentally, this example shows that the view function can be overloaded, and
    240 that its use in a view pattern gives rise to a type-class constraint (in this case,
    241 that in turn makes `f` overloaded).
    242 
    243 === Naming constants in one place ===
    244 
    245 We are always taught to write magic numbers, or constants, in one place only.
    246 In C you can write
    247 {{{
    248   #define ERRVAL 4
    249 }}}
    250 and then use `ERRVAL` in `switch` labels.  You can't do that in Haskell, which is tiresome.
    251 But with view pattern you can:
    252 {{{
    253   errVal :: Int -> Bool
    254   errVal = (== 4)
    255 
    256   f (errVal ->) = ...
    257 }}}
    258 
    259 == Remarks ==
    260 
    261 '''Note 0'''.  A key feature of this proposal is its modesty. 
    262   * There is no new form of declaration (e.g. 'view' or 'pattern synonym'). 
    263   * The functions used in view patterns are ordinary Haskell functions, and can be called from ordinary Haskell code.  They are not special view functions.
    264   * Since the view functions are ordinary Haskell functions, no changes are needed to import or export mechanisms.
    265   * Both static and dynamic semantics are extremely simple.
    266 
    267 '''Note 1'''.  All this could be done with pattern guards.  For example `parsePacket` could be written
    268 {{{
    269   parsePacket bs | Just (n, bs')    <- bits 3 bs
    270                  | Just (val, bs'') <- bits n bs'
    271                  = ...
    272 }}}
    273 But it's a bit more clumsy.  I'm hoping that support for view patterns might encourage people to export
    274 view functions (ones with `Maybe` return types, and encouage their use in patten matching).  That is,
    275 just lower the barrier for abstraction a bit.
    276 
    277 '''Note 2'''.  It is hard to check for completeness of pattern matching; and likewise for
    278 overlap.  But guards already make both of these hard; and GADTs make completness hard too.
    279 So matters are not much worse than before.
    280 
    281 == Concrete syntax ==
    282 
    283 Here are some other possible syntax choices I've considered:
    284 {{{
    285   f ($snoc x xs) = ...          -- Use prefix "$"
    286   g ($(bits 3) x bs) = ...      -- Extra parens for the value input feature
    287 
    288   f (%snoc x xs) = ...          -- Or use prefix "%" instead
    289 
    290   f (.snoc x xs) = ...          -- Or use prefix "." instead
    291 
    292   f (snoc | x xs) = ..          -- Use "|" instead of "->"
    293   g (bits 3 | b bs) = ...
    294 }}}
    295 
    296 I also thought about infix view patterns, where the view function
    297 appears between its (pattern) arguments, but I could not think of a
    298 nice syntax for it, so it is not provided by this proposal.
    299 
    300 -------------------------
    301 == Related work ==
    302 
    303 === Wadler's original paper (POPL 1987)] ===
    304 
    305 Wadler's paper was the first concrete proposal.  It proposed a top-level view
    306 declaration, together with functions ''in both directions'' between the view type
    307 and the original type, which are required to be mutually inverse. 
    308 This allows view constructors to be used in expressions
    309 as well as patterns, which seems cool. Unfortunately this dual role proved
    310 problematic for equational reasoning, and every subsequent proposal restricted
    311 view constructors to appear in patterns only.
    312 
    313 === [http://haskell.org/development/views.html Burton et al views (1996)] ===
    314 
    315 This proposal is substantially more complicated than the one above; in particular it
    316 rquires new form of top-level declaration for a view type. For example:
    317 {{{
    318   view Backwards a of [a] = [a] `Snoc` a | Nil
    319      where
    320      backwards [] = Nil
    321      backwards (x:[]) = [] `Snoc` x
    322      backwards (x1:(xs `Snoc` xn)) = (x1:xs) `Snoc` xn
    323 }}}
    324 Furthermore, it is in some ways less expressive than the proposal here;
    325 the (n+k) pattern, Erlang `bits` pattern, and `regexp` examples are not
    326 definable, because all rely on the value input feature.
    327 
    328 I think this proposal is substantially the same as "Pattern matching and
    329 abstract data types", Burton and Cameron, JFP 3(2), Apr 1993.
    330 
    331 === [http://citeseer.ist.psu.edu/okasaki98view.html Okasaki: views in Standard ML] ===
    332 
    333 Okasaki's design is very similar to Burton et al's, apart from differences due
    334 to the different host language.  Again, the value input feature is not supported.
    335 
    336 === [http://citeseer.ist.psu.edu/erwig96active.html Erwig: active patterns] ===
    337 
    338 Erwig's proposal for active patterns renders the Set example like this:
    339 {{{
    340 data Set a = Empty | Add a (Set a)
    341 
    342 pat Add' x _ =
    343   Add y s => if x==y then Add y s
    344              else let Add' x t = s
    345                   in Add x (Add y t)
    346 
    347 delete x (Add' x s) = s
    348 delete x x          = s
    349 }}}
    350 This requires a new top-leven declaration form `pat`; and I don't think it's nearly
    351 as easy to understand as the current proposal.  Notably, in the first equation for
    352 `delete` it's ahrd to see that the second `x` is a bound occurrence; this somehow
    353 follows from the `pat` declaration.
    354 
    355 Still the proposal does support the value input feature.
    356 
    357 === [http://citeseer.ist.psu.edu/erwig00pattern.html Erwig/Peyton Jones: transformational patterns] ===
    358 
    359 This paper describes pattern guards, but it also introduces '''transformational patterns'''.  (Although
    360 it is joint-authored, the transformational-pattern idea is Martin's.)  Transformational patterns
    361 are very close to what we propose here.  In particular, view functions are ordinary Haskell functions,
    362 so that the only changes are to patterns themselves.
    363 
    364 There are two main differences (apart from syntax).
    365 First, transformational patterns didn't have the value input feature, althought it'd be easy
    366 to add (indeed that's what we've done). Second, : in the current
    367 proposal the view function is expected to return a `Maybe` type, with `Nothing` to indicate match
    368 failure.  In the transformational pattern paper, this implicit matching is not performed. So,
    369 using the new syntax, you'd have to write
    370 {{{
    371 f (snoc -> Just2 xs x) = ...
    372 }}}
    373 The benefit of not having the implicit matching is that you can write functions that are, perhaps,
    374 more view-like.  Example:
    375 {{{
    376 data Product = ....some big data type...
    377 
    378 data Size = Small | Medium | Big        -- View type
    379 prodSize :: Product -> Size
    380 prodSize = ....
    381 
    382 f :: Product -> ...
    383 f (prodSize -> Small)  = ...
    384 f (prodSize -> Medium) = ...
    385 f (prodSize -> Big)    = ...
    386 }}}
    387 With the current proposal, you'd instead write something like this:
    388 {{{
    389 smallProd, medProd, bigProd :: Product -> Bool
    390 smallProd p = ...
    391 medProd   p = ...
    392 bigProd   p = ...
    393 
    394 f :: Product -> ...
    395 f (smallProd ->) = ...
    396 f (medProd   ->) = ...
    397 f (bigProd   ->) = ...
    398 }}}
    399 This is not obviously worse, except that the first version is more
    400 obviously exhaustive.  Incidentally, both should generate the same
    401 code.
    402 
    403 While I think the implicit Maybe-stripping is a real win, it's an open
    404 design choice.  Perhaps a different arrow could suppress the
    405 stripping?
    406 
    407 === Pattern synonyms  ===
    408 
    409 [http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms]
    410 are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see
    411 [http://people.cs.uchicago.edu/~jhr/papers/1992/tr-sml-const.pdf Abstract value constructors],
    412 Reppy & Aiken, TR 92-1290, Cornell, June 1992.
    413 
    414 The one way in which pattern synonyms are better than view patterns is that
    415 they define by-construction bi-directional maps.  Example
    416 {{{
    417   data Term = Var String | Term String [Term]
    418  
    419   -- 'const' introduces a pattern synonym
    420   const Plus a b = Term "+" [a,b]
    421 
    422   f :: Term -> Term
    423   f (Plus a b) = Plus (f a) (f b)
    424   f ... = ...
    425 }}}
    426 With pattern views, we'd have to write two functions for the "plus" view:
    427 {{{
    428   plus :: Term -> Term -> Term
    429   plus a b = Term "+" [a,b]
    430 
    431   isPlus :: Term -> Maybe2 Term Term
    432   isPlus (Term "+" [a,b]) = Just2 a b
    433   isPlus other            = Nothing
    434 
    435   f :: Term -> Term
    436   f (isPlus -> a b) = plus (f a) (f b)
    437 }}}
    438 But perhaps that is not so bad.  Pattern synonyms also require a new form of top level declaration;
    439 and are much more limited than view patterns (by design they cannot do computation).
    440 
    441 === First class abstractions ===
    442 
    443 Several proposals suggest first class ''abstractions'' rather that first-class ''patterns''.
    444 Here are the ones I know of
    445 
    446  * [http://hackage.haskell.org/trac/haskell-prime/ticket/114 Claus Reinke's lambda-match proposal]
    447  * [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: first class patterns]
    448  * [http://ttic.uchicago.edu/~blume/pub-cat.html Matthias Blume: Extensible programming with first-class cases] (ICFP06)
    449 
    450 All these proposals are more or less orthogonal to this one. For example, Reinke
    451 proposes a compositional syntax for lambda abstractions
    452 `(\p -> e)` where pattern matching failure on `p` can be caught and composed
    453 with a second abstraction. Thus
    454 {{{
    455    (| Just x -> x+1 ) +++ (| Nothing -> 0 )
    456 }}}
    457 combines two abstractions, with failure from the first falling through to the seoond. 
    458 
    459 Blume and Tullsen have a similar flavour.  None of these proposals say
    460 anything about the patterns themselves, which in turn is all this
    461 proposal deals with.  Hence orthgonal.
    462 
     3Thi