[Haskell-cafe] Re: [Haskell] View patterns in GHC: Request for
feedback
apfelmus
apfelmus at quantentunnel.de
Wed Jul 25 11:27:00 EDT 2007
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! :)
More information about the Haskell-Cafe
mailing list