[Haskell] Re: Views in Haskell

[apfelmus at quantentunnel.de]

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