Changes between Version 2 and Version 3 of ViewPatternsNew


Ignore:
Timestamp:
Jul 18, 2007 3:53:35 PM (7 years ago)
Author:
danl
Comment:

a bunch of text

Legend:

Unmodified
Added
Removed
Modified
  • ViewPatternsNew

    v2 v3  
    1 make page now 
     1[[PageOutline]] 
     2= View patterns: lightweight views for Haskell = 
     3 
     4This page describes a lightweight proposal for adding views to Haskell. '''We are about to begin prototyping this extension in GHC, so speak now if you have comments or suggestions!''' 
     5 
     6== Basic view patterns ==  
     7 
     8View 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: 
     9 
     10{{{ 
     11   type Typ 
     12  
     13   data TypView = Unit 
     14                | Arrow Typ Typ 
     15 
     16   view :: Type -> TypeView 
     17 
     18   -- additional operations for constructing Typ's ... 
     19}}} 
     20 
     21The representation of `Typ` is held abstract, permitting implementations to use a fancy representation (e.g., hash-consing to managage sharing). 
     22 
     23In current Haskell, using this signature a little inconvenient: 
     24{{{ 
     25   size :: Typ -> Integer 
     26   size t = case t of 
     27     Unit -> 1 
     28     Arrow t1 t2 -> size t1 + size t2 
     29}}} 
     30It 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. 
     31In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against. 
     32 
     33View patterns permit calling the view function inside the pattern and matching against the result: 
     34{{{ 
     35   size (view -> Unit) = 1 
     36   size (view -> Arrow t1 t2) = size t1 + size t2 
     37}}} 
     38 
     39That is, we add a new form of pattern, written  
     40{{{ 
     41   expression -> pattern 
     42}}} 
     43that 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. 
     44 
     45=== Semantics === 
     46 
     47'''Scoping''' for ''expr `->` ''pat: 
     48* The variables bound by the view pattern are the variables bound by ''pat''. 
     49* Any variables in ''expr'' are bound occurrences. 
     50** In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments. 
     51{{{ 
     52   example :: (String -> Integer) -> String -> Bool 
     53   example f (f -> 4) = True 
     54}}} 
     55 
     56** However, pattern variables do not scope over the pattern in which they are bound. 
     57{{{ 
     58   -- doesn't work 
     59   example :: (String -> Integer, String) -> Bool 
     60   example (f, f -> 4) = True 
     61}}} 
     62 
     63'''Typing''' 
     64If ''expr'' has type ''t1'' `->` ''t2'' and  ''pat'' matches a ''t2'',  then the whole view pattern has type ''t1''. 
     65 
     66'''Evaluation''' 
     67To match a value ''v'' against a pattern (''expr'' `->` ''pat''), evaluate ''(expr v)'' and match the result against ''pat''.   
     68 
     69=== Examples ===  
     70 
     71We discuss some examples of pattern-matching abstract types and of other  uses of view patterns here. 
     72 
     73==== Join lists ==== 
     74The requisite join-list example: 
     75{{{ 
     76   data JList a = Empty  
     77                | Single a 
     78                | Join (JList a) (JList a) 
     79  
     80   data JListView a = Nil 
     81                    | Cons a (JList a) 
     82}}} 
     83Here 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---but that's of course up to the programmer.   
     84 
     85The implementation of the view: 
     86{{{ 
     87  view :: JList a -> JListView a 
     88  view Empty = Nil 
     89  view (Single a) = Cons a Empty 
     90  view (Join (view -> Cons xh xt) y) = Cons xh $ Join xt y 
     91  view (Join (view -> Nil) y) = view y 
     92}}} 
     93Note the recursive uses of the view function in view patterns within its own definition. 
     94 
     95An example of using it: 
     96{{{ 
     97  length :: JList a -> Integer 
     98  length (view -> Nil) = 0 
     99  length (view -> Cons x xs) = 1 + length xs 
     100}}} 
     101 
     102For more general sequences, `Data.Sequence` already defines the views from the left and from the right 
     103{{{ 
     104   data ViewL a 
     105   = EmptyL 
     106   | (:<) a (Seq a) 
     107 
     108   viewl :: Seq a -> ViewL a 
     109 
     110   data ViewR a 
     111   = EmptyR 
     112   | (:>) (Seq a) a 
     113 
     114   viewr :: Seq a -> ViewR a 
     115}}} 
     116that now may be used in view patterns. 
     117 
     118=== Partial views === 
     119 
     120Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections inverting each constructor: 
     121 
     122{{{ 
     123   type Typ 
     124 
     125   outUnit  : Typ -> Maybe () 
     126   outArrow : Typ -> Maybe (Typ, Typ) 
     127 
     128   -- additional operations for constructing Typ's ... 
     129}}} 
     130 
     131This view is used as follows: 
     132 
     133{{{ 
     134   size (outUnit -> Just _) = 1 
     135   size (outArrow -> Just (t1, t2)) = size t1 + size t2 
     136}}} 
     137 
     138This 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). 
     139 
     140==== Sets ==== 
     141 
     142Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby. 
     143 
     144{{{ 
     145module Set(Set, empty, insert, delete, has) where 
     146 
     147  newtype Set a = S [a] 
     148   
     149  has :: Eq a => a -> Set a -> Maybe (Set a) 
     150  has x (S xs) | x `elem` xs = Just (xs \\ x) 
     151               | otherwise   = Nothing 
     152   
     153  delete :: a -> Set a -> Set a 
     154  delete x (has x -> Just s) = s 
     155  delete x s                 = s 
     156   
     157  insert :: a -> Set a -> Set a 
     158  insert x s@(has x -> _) = s 
     159  insert x (S xs)         = S (x:xs) 
     160}}} 
     161 
     162Note the use of the previous argument `x` in later view patterns. 
     163 
     164==== Erlang-style parsing ==== 
     165 
     166Sagonas 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: 
     167{{{ 
     168  bits :: Int -> ByteString -> Maybe (Word, ByteString) 
     169  -- (bits n bs) parses n bits from the front of bs, returning 
     170  -- the n-bit Word, and the remainder of bs 
     171}}} 
     172Then we could write patterns like this: 
     173{{{ 
     174  parsePacket :: ByteString -> ... 
     175  -- FIXME: requires scoping inside the same pattern. 
     176  parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ... 
     177}}} 
     178This parses 3 bits to get the value of `n`, and then parses `n` bits to get the value of `val`. 
     179 
     180==== N+k patterns ==== 
     181 
     182`(n+k)` patterns use the following view function: 
     183{{{ 
     184   np :: Num a => a -> a -> Maybe a 
     185   np k n | k <= n = Just (n-k) 
     186           | otherwise = Nothing 
     187}}} 
     188 
     189They are used as follows: 
     190{{{ 
     191   fib :: Num a -> a -> a 
     192   fib 0 = 1 
     193   fib 1 = 1 
     194   fib (np 2 -> Just n) = fib (n + 1) + fib n 
     195}}} 
     196Note 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). 
     197 
     198`n+k` patterns are another a good opportunity for passing view data at run-time, as in: 
     199{{{ 
     200   example k (np k -> Just n) = ... 
     201}}} 
     202 
     203==== Named constants ==== 
     204 
     205View patterns can be used to pattern match against named constants: 
     206{{{ 
     207    errorVal :: Int -> Bool 
     208    errorVal = (== 4) 
     209    f (errorVal -> True) =  ... 
     210}}} 
     211 
     212==== Both patterns ==== 
     213 
     214A "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: 
     215{{{ 
     216   both : a -> (a,a) 
     217   both x = (x,x) 
     218}}} 
     219 
     220And used as follows: 
     221{{{ 
     222   f (both -> (xs, h : t)) = h : (xs ++ t) 
     223}}} 
     224 
     225-- FIXME: loss of sharing? 
     226 
     227==== Iterator Style ==== 
     228 
     229View 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.: 
     230{{{ 
     231   length [] = [] 
     232   length (x : length -> xs) = x + xs 
     233    
     234   map f [] = [] 
     235   map f (x : map f -> xs) = x : xs 
     236    
     237   foldr f z [] = z 
     238   foldr f z (x : foldr f z -> xs) =  x `f` xs 
     239}}} 
     240 
     241== Further Syntactic Extensions == 
     242 
     243Next, we describe two syntactic extensions that we may implement.   
     244 
     245=== Implicit Maybe === 
     246 
     247Above, we saw several examples of view functions that return a `Maybe`, including: 
     248{{{ 
     249   np :: Num a => a -> a -> Maybe a 
     250   np k n | k <= n = Just (n-k) 
     251           | otherwise = Nothing 
     252}}} 
     253which were used as follows: 
     254{{{ 
     255   fib (np 2 -> Just n) = fib (n + 1) + fib n 
     256}}} 
     257 
     258We may implement a special syntax that makes the `Just` implicit, using ''expr'' `=>` ''pat'' for ''expr'' `-> Just` ''pat''.  An example use:  
     259{{{ 
     260   fib (np 2 => n) = fib (n + 1) + fib n 
     261}}} 
     262 
     263This syntax works very nicely with partial views: 
     264{{{ 
     265   size (outUnit => _) = 1 
     266   size (outArrow => (t1, t2)) = size t1 + size t2 
     267}}} 
     268 
     269==== Implicit Tupling ==== 
     270 
     271A further syntactic extension would be to have implcit Maybes with implicit tupling, so that multiple patterns after the `=>` are implicitly tupled.  Then you could write: 
     272{{{ 
     273   size (outArrow => t1 t2) = size t1 + size t2 
     274}}} 
     275 
     276=== Implicit View Functions === 
     277 
     278Total views have one syntactic disadvantage relative to the iterated case 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.   
     279 
     280The idea is that we distinguish a particular type class as a hook into the pattern compiler.  The class has the following interface: 
     281{{{ 
     282   class View a b where 
     283      view :: a -> b 
     284}}} 
     285 
     286Then, you can leave off the expresion in a view pattern, writing `->` ''pat'', to mean `view -> ` ''pat''.  For example: 
     287{{{ 
     288   size (-> Unit) = 1 
     289   size (-> Arrow t1 t2) = size t1 + size t2 
     290}}} 
     291 
     292means  
     293 
     294{{{ 
     295   size (view -> Unit) = 1 
     296   size (view -> Arrow t1 t2) = size t1 + size t2 
     297}}} 
     298 
     299for the overloaded `view`.   
     300 
     301To use this mechanism, you add instances to `view`, as in: 
     302 
     303{{{ 
     304   instance View Typ TypView where 
     305     view = (the view function from above) 
     306}}} 
     307 
     308This 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.   
     309 
     310==== Functional dependencies ==== 
     311The above implementation of `size` is given the following type: 
     312{{{ 
     313   size :: View a TypView -> a -> Int 
     314}}} 
     315which 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.)   
     316 
     317Thus, it may be better to make one parameter of the type class determine the other (using associated type synonyms): 
     318{{{ 
     319   class View a where 
     320      type View a  
     321      view :: a -> View a 
     322}}} 
     323or  
     324{{{ 
     325   class View b where 
     326      type Hidden b  
     327      view :: Hidden b -> a 
     328}}} 
     329 
     330Of 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.