Simon Peyton-Jones wrote:
http://hackage.haskell.org/trac/haskell-prime/wiki/ViewPatterns
I'm thinking of implementing it in GHC, so I'd be interested in feedback of the form - how desirable is it to have a feature of this general form? - can this particular proposal be improved?
I have several arguments, conveniently structured into sections. Most of them are not in favor of the current proposal, but I'd really like to have views. 1. *Look and feel* The most important feature of views is that they have the same look and feel as ordinary pattern matches. 1.1. *Against "->", pro "?"* With the "->" syntax, f (singleton -> n) does not have the same look and feel as f (Singleton n) The main problem is that in lambda expressions, "->" already expects the free variables on the left. I think that something along the lines of f ($snoc x xs) = ... g ($(bits 3) x bs) = ... is much better. I'd propose to use a simple question mark "?" either before f (?snoc x xs) = ... g (?(bits 3) x xs) = ... , as delimiter f (snoc? x xs) = ... g (bits 3? x xs) = ... or after f (snoc? x xs) = ... g ((bits 3)? x xs) = ... the view function. I currently favor before. The main argument for a question mark is its mnemonic value: eff (why not match snoc? x x-es) is equal to
From now on, this post will use postfix question marks, although my true preference currently fluctuates like the quantum vacuum.
1.2. *View functions are not interchangeable with ordinary pattern matches* This hinders changing a concrete representation to an abstract data type. Of course, the solution is to anticipate the change beforehand and do all pattern matches with view functions: type Stack a = [a] f :: Stack a f (null?) = .. f (pop? x xs) = .. This certainly discourages ordinary pattern matching. In other words, implementing the proposal has considerable impact on ordinary pattern matching (not in semantics but in use). The extension #2 illustrates this: the canonical ordinary pattern match form for (f :: Product -> ...) would be f SmallProd = ... f MediumProd = ... f BigProd = ... With view functions, the canonical form would become f (smallProd?) = f (medProd?) = f (bigProd?) = But because we are used to capital letters, f (prodSize? SmallProd) = f (prodSize? MediumProd) = f (prodSize? BigProd) = suddenly becomes feasible. Due to the tedious repetition of a long identifier (prodSize), I for one will invariable write it out as a case expression f prod = case prodSize prod of SmallProd -> ... MediumProd -> ... BigProd -> ... This can already be done in Haskell98. 2. *Projection to Maybe invariably looses sharing of expensive computations* This is a strong argument against view functions that project everything to Maybe a. Unfortunately, projecting things to Maybe is very compositional. Suppose that data Graph represents a graph and that we want a function g :: Graph -> [...] g (forest? xs) = concatMap g xs g (tree?) = ... g (dag?) = ... These three properties are expensive to calculate but all three only depend on the result of a single depth first search. By projecting teh disjoint sum to several Maybes, the depth first search has to be repeated every time. There is *no way* for the compiler to optimize this because this would mean common subexpression elimination across functions. The proposals from Wadler and Burton et.al. avoid this problem by projecting to a possibly larger sum. In fact, the three view functions arise from function commondfs :: Graph -> (Maybe Forest, Maybe Tree, Maybe DAG) by forest = (\(x,_,_) -> x) . commondsf tree = (\(_,x,_) -> x) . commondsf dag = (\(_,_,x) -> x) . commondsf While it is true that commondfs == forest ** tree ** dag with some join function (**) from category theory, the difference in computational complexity already shows up in the type of the three-fold join: join3 :: forall a b c d . (a -> b, a -> c, a -> d) -> (a -> (b,c,d)) join3 (b,c,d) = b ** c ** d The observation is that the type a does not appear linearly in the triple. 3. *Haskell98 can emulate patterns with view functions, at least as case expressions* Yesterday, i stumbled on the fact that we can have at least case expressions with arbitrary view functions in Haskell98. The trick is to pass from snoc :: [a] -> Maybe ([a],a) to its case expression (dual; continuation passing style; System F inductive type) snoc :: [a] -> forall b . ([a] -> a -> b) -> b -> b Interchanging the first two arguments gives us snoc :: ([a] -> a -> b) -> [a] -> (b -> b) which is perfectly suited for use as higher order pattern because the variables to be bound are only a lambda away. To unleash do-syntax abuse, we need some monad magic newtype Case a b c = Case (a -> b -> b) instance Monad (Case a b) where return x = undefined (~Case x) >>= f = Case $ \a -> (x a) . (y a) where Case y = f undefined Here are two higher order patterns: snoc :: ([a] -> a -> b) -> Case [a] b c snoc f = Case $\xs -> if null xs then id else const $ f (init xs) (last x) empty :: b -> Case [a] b c empty b = Case $\xs -> if null xs then const b else id Our new "case of"-statement is caseof :: a -> Case a b c -> b caseof x (Case c) = c x $ error "match: failed pattern match" Et voilà, defining last in terms of snoc and empty: last' :: [a] -> a last' xs = caseof xs $do snoc $ \ xs x -> x empty $ error "last: empty list" Of course, we have to use "$ \" instead of "?" or "->". 4. *People have different views about views* Judging from the replies so far, everybody seems to expect something completely different from views :) I think we should collect a lot of examples, attribute them to the particular intentions and map the intension to the set of features views might provide. Here is an attempt to start such a list. Intentions: "I need views for ..." * pattern matching on abstract data types (John Meacham, apfelmus) examples: - Okasaki: Breath first numbering - lessons from a small exercise in graph theory view Queue a = Empty | Cons a (Queue a) - ByteStrings view ByteString = [] | Word8 : ByteString - M. Erwig: Inductive Graphs and functional graph algorithms view Graph a b = Empty | Context a b :& Graph a b f (empty?) = ... f (match node? (in,x,out) :& g) = ... - compositing and decomposing Data.Map / Data.Set insert k a (remove k? _ :& map) = (k,a) :& map insert k a (empty?) = (k,a) :& Empty * composable parsing (Stefan Monnier, (SPJ ?)) examples: - parsing bit-streams parsePacket (bits 3 -> n (bits n -> val bs)) = ... * both - magic numbers view Int = Error | Succeded where project 4 = Error project _ = Succeded Features: * value input feature * projection to Maybe VS projection to custom algebraic data type * compositional patterns (Claus Reinke) Subfeatures: * exhaustive pattern matches (David Roundy) probably subsumed by: projection to custom algebraic data type Regards, apfelmus