[Haskell-cafe] Re: [Haskell] View patterns in GHC: Request for feedback

[apfelmus]

Benjamin Franksen wrote:
> apfelmus wrote:
>>
>> In other words, case-expressions are as powerful as any view pattern may
>> be in the single-parameter + no-nesting case.
>
> This is how I do it, no pattern guards, no view patterns:
> 
> zip :: Seq a -> Seq b -> Seq (a,b)
> zip xs ys = case (viewl xs,viewl ys) of
>   (EmptyL,  _      ) -> empty
>   (_,       EmptyL ) -> empty
>   (x :< xt, y :< yt) -> (x,y) <| zip xt yt
> 
> This is IMHO a lot clearer than any of the alternatives you listed, except
> your 'dream' (which is exactly what 'real' views would give us).

Splendid! That lifts the single-parameter restriction. Let's also lift
the no-nesting restriction with an audacious use of rank-2-polymorphism!
The idea is that we may match a polymorphic type (forall a . a) against
as many different pattern types as we wish. In other words, the definition

  foo :: (forall a . a) -> String
  foo x = case x of
      "eek" -> ...
      13    -> ...
      (x,y) -> ...

should be just fine. Of course we need a class context like (forall a .
View b a => a) for a polymorphic type to be useful.

Here's (almost) a demonstration for sequence types, the code works with
hugs -98.

    class View a b | b -> a where
        view :: a -> b

    data Queue a = ...

    instance View (Queue a) (Queue a) where
        view = id

The view from the left is

    data ViewL seq a = EmptyL | a :< (forall b . View (seq a) b => b)

where the key trick is to make the second component of :< polymorphic.

    instance View (Queue a) (ViewL Queue a) where
        view q = if null q then EmptyL else head q :< view (tail q)

The  zip  function can be defined just like before

    zip :: Queue a -> Queue b -> Queue (a,b)
    zip xs ys = case (view xs, view ys) of
        (EmptyL,  _      ) -> empty
        (_,       EmptyL ) -> empty
        (x :< xt, y :< yt) -> (x,y) `cons` zip xt yt

But now, we can even nest patterns

    pairs :: Queue a -> Queue (a,a)
    pairs xs = case view xs of
        x :< ys -> case ys of
            y :< zs -> (x,y) `cons` pairs zs
            _       -> empty
        _              -> empty

Well, that's no true nesting since we'd like to write

    pairs xs = case view xs of
        x :< (y :< zs) -> (x,y) `cons` pairs zs
        _              -> empty

but note that we were able to write  case ys of  instead of the
otherwise obligatory  case (view ys) of . With pattern matching on
polymorphic types, real nesting would come in reach. The point is to be
able to define both  zip  and  pairs  with one and the same operator :< .


Regards,
apfelmus
Long live the we-want-real-views-or-nothing-at-all movement! :)