Changes between Version 1 and Version 2 of ViewPatternsAlternative


Ignore:
Timestamp:
Jun 12, 2011 8:57:56 AM (3 years ago)
Author:
augustss
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatternsAlternative

    v1 v2  
    3838That is, we add a new form of pattern, written  
    3939{{{ 
    40    pattern | qual1, ..., qualn 
     40   pattern | qual,,1,, , ..., qual,,n,, 
    4141}}} 
    4242This has the same meaning as pattern guard at the top level, but here they are allowed to be part of a pattern, and thus nested inside other patterns. 
    43 So first the pattern is matched, then the qualifiers are matched in order.  An expression qualifier has to evaluate to `True`, and for a "pat `<-` exp" the pattern must match the expression. 
     43So first the pattern is matched, then the qualifiers are matched in order.  An expression qualifier has to evaluate to `True`, and for a ''pat `<-` exp'' the pattern must match the expression. 
    4444 
    4545The key feature of this proposal is its modesty, rather than its ambition: 
     
    5050It is essentially some simple syntactic sugar for patterns. 
    5151However, 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. 
     52 
     53=== Semantics === 
     54 
     55'''Scoping''' for ''pat `|` quals'': 
     56 * The variables bound by the view pattern are the variables bound by ''pat'' and ''quals''. 
     57 * Variables bound by patterns to the left of a view pattern expression are in scope.  For example: 
     58   * In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments. 
     59{{{ 
     60   example :: (String -> Integer) -> String -> Bool 
     61   example f (x | f x == 4) = True 
     62}}} 
     63   * Variables can be bound to the left in tuples and data constructors: 
     64{{{ 
     65   example :: ((String -> Integer,Integer), String) -> Bool 
     66   example ((f,_), x | f x == 4) = True 
     67}}} 
     68 
     69'''Typing''' 
     70If ''pat `|` quals'' has same type as ''pat'', and the "quals" must be well typed in the same way as for pattern guards. 
     71 
     72'''Evaluation''' 
     73To match a value ''v'' against a pattern (''pat'' `|` ''quals''), match "v" against ''pat'' and then match the ''quals''. 
     74 
     75=== Examples ===  
     76 
     77We discuss some examples of pattern-matching abstract types and of other uses of view patterns here. 
     78 
     79==== Join lists ==== 
     80The requisite join-list example: 
     81{{{ 
     82   data JList a = Empty  
     83                | Single a 
     84                | Join (JList a) (JList a) 
     85  
     86   data JListView a = Nil 
     87                    | Cons a (JList a) 
     88}}} 
     89Here 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.   
     90 
     91The implementation of the view: 
     92{{{ 
     93  view :: JList a -> JListView a 
     94  view Empty = Nil 
     95  view (Single a) = Cons a Empty 
     96  view (Join (l | Cons xh xt <- view l) y) = Cons xh $ Join xt y 
     97  view (Join (l | Nil <- view) l) = view y 
     98}}} 
     99Note the recursive uses of the view function in view patterns within its own definition. 
     100 
     101An example of using it: 
     102{{{ 
     103  length :: JList a -> Integer 
     104  length (l | Nil <- view l) = 0 
     105  length (l | Cons x xs <- l) = 1 + length xs 
     106}}} 
     107 
     108For more general sequences, `Data.Sequence` already defines the views from the left and from the right 
     109{{{ 
     110   data ViewL a 
     111   = EmptyL 
     112   | (:<) a (Seq a) 
     113 
     114   viewl :: Seq a -> ViewL a 
     115 
     116   data ViewR a 
     117   = EmptyR 
     118   | (:>) (Seq a) a 
     119 
     120   viewr :: Seq a -> ViewR a 
     121}}} 
     122that now may be used in view patterns. 
     123 
     124==== Partial views ==== 
     125 
     126Here'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: 
     127 
     128{{{ 
     129   type Typ 
     130 
     131   outUnit  : Typ -> Maybe () 
     132   outArrow : Typ -> Maybe (Typ, Typ) 
     133 
     134   -- additional operations for constructing Typ's ... 
     135}}} 
     136 
     137This view is used as follows: 
     138 
     139{{{ 
     140   size (t | Just _ <- outUnit t) = 1 
     141   size (t | Just (t1, t2) <- outArrow t) = size t1 + size t2 
     142}}} 
     143 
     144This 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). 
     145 
     146==== Sets ==== 
     147 
     148Here is a small module that allows to decompose sets with respect to a given element, deleting it hereby. 
     149 
     150{{{ 
     151module Set(Set, empty, insert, delete, has) where 
     152 
     153  newtype Set a = S [a] 
     154   
     155  has :: Eq a => a -> Set a -> Maybe (Set a) 
     156  has x (S xs) | x `elem` xs = Just (xs \\ x) 
     157               | otherwise   = Nothing 
     158   
     159  delete :: a -> Set a -> Set a 
     160  delete x (r | Just s <- has r) = s 
     161  delete x s                     = s 
     162   
     163  insert :: a -> Set a -> Set a 
     164  insert x (s | Just _ <- has x s) = s 
     165  insert x (S xs)                = S (x:xs) 
     166}}} 
     167 
     168Note the use of the previous argument `x` in later view patterns. 
     169 
     170==== Erlang-style parsing ==== 
     171 
     172Sagonas 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: 
     173{{{ 
     174  bits :: Int -> ByteString -> Maybe (Word, ByteString) 
     175  -- (bits n bs) parses n bits from the front of bs, returning 
     176  -- the n-bit Word, and the remainder of bs 
     177}}} 
     178Then we could write patterns like this: 
     179{{{ 
     180  parsePacket :: ByteString -> ... 
     181  parsePacket (p1 |  Just (n, (p2 | Just (val, bs) <- bits n p2)) <- bits 3 p1) = ... 
     182}}} 
     183This 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. 
     184 
     185==== N+k patterns ==== 
     186 
     187`(n+k)` patterns use the following view function: 
     188{{{ 
     189   np :: Num a => a -> a -> Maybe a 
     190   np k n | k <= n = Just (n-k) 
     191           | otherwise = Nothing 
     192}}} 
     193 
     194They are used as follows: 
     195{{{ 
     196   fib :: Num a -> a -> a 
     197   fib 0 = 1 
     198   fib 1 = 1 
     199   fib (n2 | Just n <- np 2 n2) = fib (n + 1) + fib n 
     200}}} 
     201Note 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). 
     202 
     203Alternatively it can be written without an auxiliary function 
     204{{{ 
     205   fib :: Num a -> a -> a 
     206   fib 0 = 1 
     207   fib 1 = 1 
     208   fib (n2 | let n = n2-2, n >= 0) = fib (n + 1) + fib n 
     209}}} 
     210 
     211`n+k` patterns are another a good opportunity for passing view data at run-time, as in: 
     212{{{ 
     213   example k (m | m > k) = ... 
     214}}} 
     215 
     216==== Named constants ==== 
     217 
     218View patterns can be used to pattern match against named constants: 
     219{{{ 
     220    errorVal :: Int -> Bool 
     221    errorVal = (== 4) 
     222    f (x | errorVar x) =  ... 
     223}}} 
     224 
     225==== Both patterns ==== 
     226 
     227A "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: 
     228 
     229And used as follows: 
     230{{{ 
     231   f (x | xs <- x, h : t <- x) = h : (xs ++ t) 
     232}}} 
     233 
     234 
     235== Comparison with existing view patterns == 
     236There are straightforward translations between old and new style view patterns: 
     237[[BR]] 
     238''pat'' `<-` ''exp''  
     239[[BR]] 
     240translates to 
     241[[BR]] 
     242''x `|` pat `<-` exp x''  where ''x'' is a fresh variable. 
     243