[Haskell] Re: Views in Haskell
apfelmus at quantentunnel.de
apfelmus at quantentunnel.de
Wed Jan 24 06:55:22 EST 2007
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
More information about the Haskell
mailing list