Changes between Version 2 and Version 3 of ViewPatternsNew

Timestamp:

07/18/07 08:53:35 (6 years ago)

Author:

danl

Comment:

a bunch of text

ViewPatternsNew

@@ -1 @@
-make page now
+[[PageOutline]]
+= View patterns: lightweight views for Haskell =
+
+This 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!'''
+
+== Basic view patterns == 
+
+View 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:
+
+{{{
+   type Typ
+ 
+   data TypView = Unit
+                | Arrow Typ Typ
+
+   view :: Type -> TypeView
+
+   -- additional operations for constructing Typ's ...
+}}}
+
+The representation of `Typ` is held abstract, permitting implementations to use a fancy representation (e.g., hash-consing to managage sharing).
+
+In current Haskell, using this signature a little inconvenient:
+{{{
+   size :: Typ -> Integer
+   size t = case t of
+     Unit -> 1
+     Arrow t1 t2 -> size t1 + size t2
+}}}
+It 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.
+In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against.
+
+View patterns permit calling the view function inside the pattern and matching against the result:
+{{{
+   size (view -> Unit) = 1
+   size (view -> Arrow t1 t2) = size t1 + size t2
+}}}
+
+That is, we add a new form of pattern, written 
+{{{
+   expression -> pattern
+}}}
+that 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.
+
+=== Semantics ===
+
+'''Scoping''' for ''expr `->` ''pat:
+* The variables bound by the view pattern are the variables bound by ''pat''.
+* Any variables in ''expr'' are bound occurrences.
+** In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments.
+{{{
+   example :: (String -> Integer) -> String -> Bool
+   example f (f -> 4) = True
+}}}
+
+** However, pattern variables do not scope over the pattern in which they are bound.
+{{{
+   -- doesn't work
+   example :: (String -> Integer, String) -> Bool
+   example (f, f -> 4) = True
+}}}
+
+'''Typing'''
+If ''expr'' has type ''t1'' `->` ''t2'' and  ''pat'' matches a ''t2'',  then the whole view pattern has type ''t1''.
+
+'''Evaluation'''
+To match a value ''v'' against a pattern (''expr'' `->` ''pat''), evaluate ''(expr v)'' and match the result against ''pat''.  
+
+=== Examples === 
+
+We discuss some examples of pattern-matching abstract types and of other  uses of view patterns here.
+
+==== Join lists ====
+The requisite join-list example:
+{{{
+   data JList a = Empty 
+                | Single a
+                | Join (JList a) (JList a)
+ 
+   data JListView a = Nil
+                    | Cons a (JList a)
+}}}
+Here 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.  
+
+The implementation of the view:
+{{{
+  view :: JList a -> JListView a
+  view Empty = Nil
+  view (Single a) = Cons a Empty
+  view (Join (view -> Cons xh xt) y) = Cons xh $ Join xt y
+  view (Join (view -> Nil) y) = view y
+}}}
+Note the recursive uses of the view function in view patterns within its own definition.
+
+An example of using it:
+{{{
+  length :: JList a -> Integer
+  length (view -> Nil) = 0
+  length (view -> Cons x xs) = 1 + length xs
+}}}
+
+For more general sequences, `Data.Sequence` already defines the views from the left and from the right
+{{{
+   data ViewL a
+   = EmptyL
+   | (:<) a (Seq a)
+
+   viewl :: Seq a -> ViewL a
+
+   data ViewR a
+   = EmptyR
+   | (:>) (Seq a) a
+
+   viewr :: Seq a -> ViewR a
+}}}
+that now may be used in view patterns.
+
+=== Partial views ===
+
+Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections inverting each constructor:
+
+{{{
+   type Typ
+
+   outUnit  : Typ -> Maybe ()
+   outArrow : Typ -> Maybe (Typ, Typ)
+
+   -- additional operations for constructing Typ's ...
+}}}
+
+This view is used as follows:
+
+{{{
+   size (outUnit -> Just _) = 1
+   size (outArrow -> Just (t1, t2)) = size t1 + size t2
+}}}
+
+This 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).
+
+==== Sets ====
+
+Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby.
+
+{{{
+module Set(Set, empty, insert, delete, has) where
+
+  newtype Set a = S [a]
+  
+  has :: Eq a => a -> Set a -> Maybe (Set a)
+  has x (S xs) | x `elem` xs = Just (xs \\ x)
+               | otherwise   = Nothing
+  
+  delete :: a -> Set a -> Set a
+  delete x (has x -> Just s) = s
+  delete x s                 = s
+  
+  insert :: a -> Set a -> Set a
+  insert x s@(has x -> _) = s
+  insert x (S xs)         = S (x:xs)
+}}}
+
+Note the use of the previous argument `x` in later view patterns.
+
+==== Erlang-style parsing ====
+
+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:
+{{{
+  bits :: Int -> ByteString -> Maybe (Word, ByteString)
+  -- (bits n bs) parses n bits from the front of bs, returning
+  -- the n-bit Word, and the remainder of bs
+}}}
+Then we could write patterns like this:
+{{{
+  parsePacket :: ByteString -> ...
+  -- FIXME: requires scoping inside the same pattern.
+  parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ...
+}}}
+This parses 3 bits to get the value of `n`, and then parses `n` bits to get the value of `val`.
+
+==== N+k patterns ====
+
+`(n+k)` patterns use the following view function:
+{{{
+   np :: Num a => a -> a -> Maybe a
+   np k n | k <= n = Just (n-k)
+           | otherwise = Nothing
+}}}
+
+They are used as follows:
+{{{
+   fib :: Num a -> a -> a
+   fib 0 = 1
+   fib 1 = 1
+   fib (np 2 -> Just n) = fib (n + 1) + fib n
+}}}
+Note 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).
+
+`n+k` patterns are another a good opportunity for passing view data at run-time, as in:
+{{{
+   example k (np k -> Just n) = ...
+}}}
+
+==== Named constants ====
+
+View patterns can be used to pattern match against named constants:
+{{{
+    errorVal :: Int -> Bool
+    errorVal = (== 4)
+    f (errorVal -> True) =  ...
+}}}
+
+==== Both patterns ====
+
+A "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:
+{{{
+   both : a -> (a,a)
+   both x = (x,x)
+}}}
+
+And used as follows:
+{{{
+   f (both -> (xs, h : t)) = h : (xs ++ t)
+}}}
+
+-- FIXME: loss of sharing?
+
+==== Iterator Style ====
+
+View 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.:
+{{{
+   length [] = []
+   length (x : length -> xs) = x + xs
+   
+   map f [] = []
+   map f (x : map f -> xs) = x : xs
+   
+   foldr f z [] = z
+   foldr f z (x : foldr f z -> xs) =  x `f` xs
+}}}
+
+== Further Syntactic Extensions ==
+
+Next, we describe two syntactic extensions that we may implement.  
+
+=== Implicit Maybe ===
+
+Above, we saw several examples of view functions that return a `Maybe`, including:
+{{{
+   np :: Num a => a -> a -> Maybe a
+   np k n | k <= n = Just (n-k)
+           | otherwise = Nothing
+}}}
+which were used as follows:
+{{{
+   fib (np 2 -> Just n) = fib (n + 1) + fib n
+}}}
+
+We may implement a special syntax that makes the `Just` implicit, using ''expr'' `=>` ''pat'' for ''expr'' `-> Just` ''pat''.  An example use: 
+{{{
+   fib (np 2 => n) = fib (n + 1) + fib n
+}}}
+
+This syntax works very nicely with partial views:
+{{{
+   size (outUnit => _) = 1
+   size (outArrow => (t1, t2)) = size t1 + size t2
+}}}
+
+==== Implicit Tupling ====
+
+A 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:
+{{{
+   size (outArrow => t1 t2) = size t1 + size t2
+}}}
+
+=== Implicit View Functions ===
+
+Total 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.  
+
+The idea is that we distinguish a particular type class as a hook into the pattern compiler.  The class has the following interface:
+{{{
+   class View a b where
+      view :: a -> b
+}}}
+
+Then, you can leave off the expresion in a view pattern, writing `->` ''pat'', to mean `view -> ` ''pat''.  For example:
+{{{
+   size (-> Unit) = 1
+   size (-> Arrow t1 t2) = size t1 + size t2
+}}}
+
+means 
+
+{{{
+   size (view -> Unit) = 1
+   size (view -> Arrow t1 t2) = size t1 + size t2
+}}}
+
+for the overloaded `view`.  
+
+To use this mechanism, you add instances to `view`, as in:
+
+{{{
+   instance View Typ TypView where
+     view = (the view function from above)
+}}}
+
+This 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.  
+
+==== Functional dependencies ====
+The above implementation of `size` is given the following type:
+{{{
+   size :: View a TypView -> a -> Int
+}}}
+which 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.)  
+
+Thus, it may be better to make one parameter of the type class determine the other (using associated type synonyms):
+{{{
+   class View a where
+      type View a 
+      view :: a -> View a
+}}}
+or 
+{{{
+   class View b where
+      type Hidden b 
+      view :: Hidden b -> a
+}}}
+
+Of 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.