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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
51 messages Options
123
Reply | Threaded
Open this post in threaded view
|

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

Simon Marlow-5
Dan Licata wrote:

> Simon PJ and I are implementing view patterns, a way of pattern matching
> against abstract datatypes, in GHC.  Our design is described here:
>
> http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns
>
> If you have any comments or suggestions about this design, we'd love to
> hear them.  You can respond to this list (and we can take it to
> haskell-cafe if the thread gets long) or, if you prefer, directly to me.

At the risk of being a spoil-sport, I have a somewhat negative take on view
patterns.  Not because I think they're particularly bad, but because I
don't think they're significantly useful enough to warrant adding to the
language, at least if we also have pattern guards.

All of the examples on the wiki page can be written in the same number of
lines, sometimes with fewer characters, using pattern guards or some other
existing Haskell idiom (e.g. the bit parsing example is much more nicely
expressed using a bit-parsing monad).  I believe adding yet another idiom
will be detrimental: too much choice is bad.

To my eyes, mixing bound and binding occurrences of variables in patterns
in an arbitrarily nested way is sure to lead to confusion.  The existing
idioms all have a one-level deep notion of bound/binding scope, and in
order to get more nesting you have to start naming things: this is good,
IMO.  Not that I think we should omit a language feature because it *could*
be used to write obfuscated code; no, in this case I think nesting more
than one level deep will *always* lead to obfuscated code.

The use of the right-arrow is confusing, especially on the left of a case
alternative or in a lambda expression.

The main argument in favour of view patterns is:

 > it's possible that people would start routinely hiding the data
 > representation and exporting view functions instead, which would be an
 > excellent thing.

My impression is that most of the time a data structure has a clever
internal representation that you don't want to expose anyway.  This is
supported by the data structures we have in the base package, all these are
abstract:

   Data.Set, Data.IntSet, Data.Map, Data.IntMap
   Data.Graph, Data.Sequence, Data.Bytestring, Data.Array,
   Data.HashTable, Data.Ratio(Rational)

and most export view-like things (e.g. Data.Set.toList).

The modules I found that export non-abstract types that should really be
abstract:

   Data.Complex, Data.Tree

So I don't think there's an overwhelming amount of stuff that would change
if we had view patterns.  In GHC itself most of our data structures are
already abstract too.

The View class is nice, even with just pattern guards.  I'd be in favour of
  making it standard and actively encouraging its use.

Cheers,
        Simon
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Jon Harrop
On Monday 23 July 2007 16:57:08 Simon Marlow wrote:

> Dan Licata wrote:
> > Simon PJ and I are implementing view patterns, a way of pattern matching
> > against abstract datatypes, in GHC.  Our design is described here:
> >
> > http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns
> >
> > If you have any comments or suggestions about this design, we'd love to
> > hear them.  You can respond to this list (and we can take it to
> > haskell-cafe if the thread gets long) or, if you prefer, directly to me.
>
> At the risk of being a spoil-sport, I have a somewhat negative take on view
> patterns...

F# already has active patterns and there are OCaml macros implementing views.
I have used F#'s active patterns extensively and find them to be extremely
useful. I can only assume that they will remain similarly useful in Haskell.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Heinrich Apfelmus
In reply to this post by Simon Marlow-5
Simon Marlow wrote:

> Dan Licata wrote:
>> Simon PJ and I are implementing view patterns, a way of pattern matching
>> against abstract datatypes, in GHC.  Our design is described here:
>>
>> http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns
>>
>> If you have any comments or suggestions about this design, we'd love to
>> hear them.  You can respond to this list (and we can take it to
>> haskell-cafe if the thread gets long) or, if you prefer, directly to me.
>
> At the risk of being a spoil-sport, I have a somewhat negative take on
> view patterns.  Not because I think they're particularly bad, but
> because I don't think they're significantly useful enough to warrant
> adding to the language, at least if we also have pattern guards.
>
> All of the examples on the wiki page can be written in the same number
> of lines, sometimes with fewer characters, using pattern guards or some
> other existing Haskell idiom (e.g. the bit parsing example is much more
> nicely expressed using a bit-parsing monad).  I believe adding yet
> another idiom will be detrimental: too much choice is bad.

I agree that only few examples from the wiki page are that compelling.
Nevertheless, I like view patterns since they can be put to really good use

  http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns#UsesofViews

Views are especially useful for Data.Graph. Also, I favor views instead
of pattern guards.

However, I don't like the current proposal, mainly because it doesn't
have the "Transparent ordinary Patterns"-feature. Also, I consider
definitions like

   foldr f z [] = z
   foldr f z (x : foldr f z -> xs) =  x `f` xs

abuse.

>   Data.Set, Data.IntSet, Data.Map, Data.IntMap
>   Data.Graph, Data.Sequence, Data.Bytestring, Data.Array,
>   Data.HashTable, Data.Ratio(Rational)
>
> So I don't think there's an overwhelming amount of stuff that would
> change if we had view patterns.  In GHC itself most of our data
> structures are already abstract too.

While the implementation of the abstract data structures themselves is
unlikely to change, views make it much easier to use them. I think it
would be a big win to have ByteStrings or Data.Sequence pattern matched
like ordinary lists and I think that Data.Graph will blossom with proper
view patterns.

Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] View patterns in GHC: Request forfeedback

Rene de Visser
In reply to this post by Simon Marlow-5
>> Simon PJ and I are implementing view patterns, a way of pattern matching
>> against abstract datatypes, in GHC.  Our design is described here:
>>
>> http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns
>>
>> If you have any comments or suggestions about this design, we'd love to
>> hear them.  You can respond to this list (and we can take it to
>> haskell-cafe if the thread gets long) or, if you prefer, directly to me.
>
I find the => operator excessive. GHC Haskell seems to be growing too
rapidly syntax wise in my opinion.
The important features of code are correctness, maintainability and
readibility (IMHO), and I think => is working against these.

=> uses up more syntax. Buys very little. Equivalent to "-> Just _ " or "->
Just x " as far as I can see.
I would prefer to type the extra 6 characters rather than having the hidden
Maybe.
It is also one more thing to learn. One more confusing type error when you
mix them up.

Rene.





_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: [Haskell] View patterns in GHC: Request forfeedback

Jonathan Cast
On Monday 23 July 2007, Rene de Visser wrote:

> >> Simon PJ and I are implementing view patterns, a way of pattern matching
> >> against abstract datatypes, in GHC.  Our design is described here:
> >>
> >> http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns
> >>
> >> If you have any comments or suggestions about this design, we'd love to
> >> hear them.  You can respond to this list (and we can take it to
> >> haskell-cafe if the thread gets long) or, if you prefer, directly to me.
>
> I find the => operator excessive.

I want to voice my complete agreement.  At least -> is already a binding
operator in GHC, with semantics analogous to those being introduced; since
when is => a binding operator?  Thus far, neither => nor <= has been used for
anything of the sort, so it's an entirely new entry in the semantic space ---
and => /is/ already a keyword in GHC, which makes it worse.

<snip>

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

RE: [Haskell] View patterns in GHC: Request for feedback

Simon Peyton Jones
In reply to this post by Simon Marlow-5
| At the risk of being a spoil-sport, I have a somewhat negative take on
| view patterns.  Not because I think they're particularly bad, but
| because I don't think they're significantly useful enough to warrant
| adding to the language, at least if we also have pattern guards.

Syntactic sugar is always like this.  It's always a judgement call: is the extra expressiveness worth the extra cost?  One could ask that about list comprehensions, or pattern guards, or as-patterns, or records.  Yet syntactic sugar can sometimes have quite a powerful effect -- think of do-notation for example.

The other question is about cost.  Syntactic sugar that can be readily explained, is easy to implement, and involves only localized changes (to the spec and to the compiler) are cheap.  The views that Dan and I propose are specifically crafted to be minimally invasive and cheap in this sense.

I swing to and fro on this one.  On one day I think that view patterns are OK but just not quite worth it.  On the next I think that perhaps they'll lower the barrier to allowing us to combine *abstraction* and *pattern matching*.  The answer probably differs from one person to another. At the moment we're faced with this tension; pattern guards (also arguably superfluous) make it a bit easier but not easy enough.

Views have been the subject of rather inconclusive debate for a long time, certainly since the inception of Haskell.  I'm thinking of pattern views as a way to break the logjam by implementing something that is a reasonable stab, and seeing whether it "sticks".  I thought of pattern guards in the same way, and they certainly seem to have stuck.  But we can only find out by trying it out.

That said, I'm keen to do it as well as possible -- so the more comments the better.

Simon

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Heinrich Apfelmus
Simon Peyton-Jones wrote:
> Views have been the subject of rather inconclusive debate for a long time,
> certainly since the inception of Haskell. I'm thinking of pattern
views as a way
> to break the logjam by implementing something that is a reasonable stab,
> and seeing whether it "sticks". I thought of pattern guards in the
same way,
> and they certainly seem to have stuck. But we can only find out by
trying it out.

What I fear the most is exactly that this proposal "sticks" and becomes
the de-facto standard :(

IMHO, the long-time debate about views is not whether they're useful (I
think they are!) but which concrete form to choose. Unfortunately, all
of the proposals so far are somehow like Dr. Jekyll and Mr. Hyde: one
side is nice but the other is rather ugly.

In the end, I might end up using the currently proposed pattern views,
not because I'm fond of the proposal but simply because they're
implemented and the pain of not using views is too big.

Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Jules Bean
apfelmus wrote:
> IMHO, the long-time debate about views is not whether they're useful (I
> think they are!) but which concrete form to choose. Unfortunately, all
> of the proposals so far are somehow like Dr. Jekyll and Mr. Hyde: one
> side is nice but the other is rather ugly.
>
> In the end, I might end up using the currently proposed pattern views,
> not because I'm fond of the proposal but simply because they're
> implemented and the pain of not using views is too big.

Maybe it would be helpful if Simon M would give a bit more flesh to the
bones of his suggestion that all the examples in the proposal can be
done more concisely without them.

apfelmus: Have you tried using pattern guards for views?

f s | y <: ys <- viewl s = ....
     | EmptyL  <- viewl s = ....

(did I get that right? :)

Personally I thought the basic proposal is quite nice, but the extra
sugar for Maybes and tuples looked a bit ugly...

Jules
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Heinrich Apfelmus
Jules Bean wrote:
> Have you tried using pattern guards for views?
>
> f s | y :< ys <- viewl s = ....
>     | EmptyL  <- viewl s = ....

Hm, I'd simply use a plain old case-expression here

  f s = case viewl s of
     y :< ys -> ...
     EmptyL  -> ...

In other words, case-expressions are as powerful as any view pattern may
be in the single-parameter + no-nesting case.


A better example is probably  zip  for sequences (Data.Sequence.Seq):

  zip :: Seq a -> Seq b -> Seq (a,b)
  zip xs ys = case viewl xs of
     x :< xt -> case viewl ys of
         y :< yt -> (x,y) <| zip xt yt
         EmptyL  -> empty
     EmptyL  -> empty

Pattern guards

  zip xs ys
    | EmptyL <- viewl xs = empty
    | EmptyL <- viewl ys = empty
    | x :< xt <- viewl xs, y :< yt <- viewl ys = (x,y) <| zip xt yt

Pattern guards variant

  zip xs ys
    |  EmptyL <- xs'                 = empty
    |                  EmptyL <- ys' = empty
    | x :< xt <- xs', y :< yt <- ys' = (x,y) <| zip xt yt
    where
    xs' = viewl xs; ys' = viewl ys

View patterns

  zip (viewl -> EmptyL) _  = empty
  zip _  (viewl -> EmptyL) = empty
  zip (viewl -> x :< xs) (viewl -> y :< ys) = (x,y) <| zip xs ys

My dream

  zip EmptyL  _       = empty
  zip _       EmptyL  = empty
  zip (x:<xs) (y:<ys) = (x,y) <| zip xs ys


Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Conor McBride
Hi

Ok, I'm not quite under my rock yet,,,

On 25 Jul 2007, at 10:28, apfelmus wrote:

> Jules Bean wrote:
>> Have you tried using pattern guards for views?
>>
>> f s | y :< ys <- viewl s = ....
>>     | EmptyL  <- viewl s = ....

This is annoying because the intermediate computation gets repeated. I
don't think view patterns fix this even if they sometimes hide it. I  
worry
that the good behaviour of this feature depends on a compiler  
noticing that
a repetition can be shared: this design makes the sharing harder to  
express.

Of course,

> Hm, I'd simply use a plain old case-expression here
>
>   f s = case viewl s of
>      y :< ys -> ...
>      EmptyL  -> ...

which is fine if you're ready to commit to the right-hand side at  
this point,
but what if the result of the intermediate computation tells you what
patterns to look for next?

Epigram's "with"-notation was never implemented in Epigram, but it  
has been
implemented in Agda 2. At the moment, we'd write

   f s with viewl s      -- adds a new column to the left
   f s | y :< ys  = ...  -- so you can now match whatever you like
   f s | EmptyL   = ...

Inside a "with-block", the patterns left of | must refine the original
patterns left of the "with". When you're fed up looking at the new
information, you can exit the block, drop the column and carry on as  
normal
(see zip, below).

I'd hope that we might ultimately be able to elide the repeated lefts
if they are unchanged, but that's not implemented at the moment.

   f s with viewl s      -- adds a new column to the left
       | y :< ys  = ...
       | EmptyL   = ...

So zip might become

   zip xs ys  with viewl xs
              | x :< xt  with viewl ys
                         | y :< yt = (x, y) <| zip xt yt
   zip _ _ = empty

or even

   zip xs ys  with viewl xs  with viewl ys
              | x :< xt      | y :< yt      = (x, y) <| zip xt yt
   zip _ _ = empty

For more entertainment, a padding zip

   pzip x' xs y' ys with viewl xs with viewl ys
                    | x :< xt     | y :< yt     = (x, y)   <| pzip x  
xt y yt
                    | x :< xt     | EmptyL      = fmap (flip (,) y') xs
                    | EmptyL      | y :< yt     = fmap ((,) x') ys
   pzip _ _ _ _ = empty

Pattern matching is much weirder in a dependently typed setting, but  
also a
lot more powerful. Inspecting the value of a pattern variable or of an
intermediate computation can leave us knowing more about (and hence
instantiate) other pattern variables. We get stuff like this

   gcd :: Positive -> Positive -> Positive
   gcd x       y with trichotomy x y
   gcd x (x + y) | LT x y = gcd x y
   gcd x       x | EQ x   = x
   gcd (y + x) y | GT x y = gcd x y

Here, matching on the result of trichotomy (with constructor  
patterns, see?)
causes the original argument patterns to become more informative
(with non-linear non-constructor forms which are *guaranteed* to match
at no run time cost).

For us, it's a bad idea to try to think of analysing one scrutinee
independently of the other data we have to hand. We're naturally pushed
towards thinking about the left-hand side as a whole, to which  
information
can be added, supporting further refinement. This is part of what James
McKinna and I were on about in "The view from the left", and it's  
happening
on real computers now.

To sum up, one-shot matching on intermediate computations, as provided
by pattern guards or view-patterns, is conspicuously nasty in a  
dependently
typed language, but for reasons which make it sometimes merely  
annoying in
Haskell.

I'm disinclined to argue thus: "don't do your thing (which probably will
happen) because it messes up my thing (which probably won't, at least in
Haskell)". I'll just chuck these observations in the air and see what  
happens.

All the best

Conor

PS Please may I have pattern synonyms anyway? They're cheap and they  
serve a
different purpose. Maybe I should say more about how their absence is
seriously nasty for the way I work, another time.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Ben Franksen-2
In reply to this post by Heinrich Apfelmus
apfelmus wrote:

> Jules Bean wrote:
>> Have you tried using pattern guards for views?
>>
>> f s | y :< ys <- viewl s = ....
>>     | EmptyL  <- viewl s = ....
>
> Hm, I'd simply use a plain old case-expression here
>
>   f s = case viewl s of
>      y :< ys -> ...
>      EmptyL  -> ...
>
> In other words, case-expressions are as powerful as any view pattern may
> be in the single-parameter + no-nesting case.
>
> A better example is probably  zip  for sequences (Data.Sequence.Seq):
>
>   zip :: Seq a -> Seq b -> Seq (a,b)
>   zip xs ys = case viewl xs of
>      x :< xt -> case viewl ys of
>          y :< yt -> (x,y) <| zip xt yt
>          EmptyL  -> empty
>      EmptyL  -> empty

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).

Cheers
Ben, member of the we-want-real-views-or-nothing-at-all movement ;-)

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Dan Licata
In reply to this post by Simon Marlow-5
[I think we should move the rest of this thread to haskell-cafe, since
it's getting long.  Note that there have already been some responses on
both lists.]

Hi Claus,

On Jul25, Claus Reinke wrote:

> >I think that the signature
> >
> >>   type Typ
> >>
> >>   unit :: Typ -> Maybe ()
> >>   arrow :: Type -> Maybe (Typ,Typ)
> >
> >is *wrong* if what you really mean is
> >
> >>   type Typ
> >>
> >>   data TypView = Unit | Arrow Typ Typ
> >>   view :: Typ -> TypView
>
> different =/= wrong !-)

No, of course not.  All I meant to say is that sometimes you want a
total view, and that a total view should be given a type that says as
much.  The latter says this better than the former.  On the other hand,
there are lots of circumstances in which you want a partial view, and I
think the (... -> Maybe _) types for those are perfectly appropriate.

> >That is, if what you mean is that every Typ is either Unit or an Arrow
> >*and nothing else* then the latter signature should be preferred, as it
> >makes this fact explicit in the type system.  
>
> but that is not what you're saying there at all! you're saying that -within
> view 'view' of Typ- Typ is mapped to either Unit or Arrow, if the mapping
> is successfull. there can be other views of Typ,

Right, but the only issue here is whether this particular view function
is total or not.

> and the types do not guarantee that 'view' itself is exhaustive over
> Typ (there can be variants of Typ that 'view' fails to map to
> TypView).
> in the abstract deconstructor variant, this partiality is explicit in the
> types,
> in the concrete view type variant, it is hidden from the types, implicit in
> the implementation of 'view'.

But by this reasoning, every expression you write should have a Maybe
type, since there's always the possibility of match failure or
non-termination.  In Haskell, these effects are always implicit in a
type, so there's no need to add extra summands to account for them.
If you think about the *values* of the returned type, then (1 + Typ *
Typ) is what you want, not ((1 + 1) + (1 + Typ * Typ)).    


> btw, it might be useful to permit association of abstract types
> with abstract deconstructors, so that an extended abstract type
> (export) declaration somewhat like
>
>    type Typ as unit -> () | arrow -> (Typ,Typ)
>
> tells us (and the compiler) that the abstract patterns in the size
> function are exhaustive (or at least as exhaustive as clients of
> the abstract type Typ are supposed to be). the proof obligation
> would be on the exporter of the abstract type, and any pattern
> match failures relating to this should be reported as view failures.
>
> doing so would declare a virtual view type, similar to the concrete
> view types used in other examples, so there might be several 'as'
> clauses for a single abstract type, declaring separate sets of
> exhaustive abstract deconstructors.

Setting aside the "transparent ordinary patterns" feature, I think this
is exactly what you get above:
- the data declaration for TypView corresponds to this "as" declaration
- the view function of type Typ -> TypView can be analyzed for
exhaustiveness using GHC's exhaustiveness checker
- a run-time match failure of view will be reported as such

So I don't think I understand what you're going for here.  Could you
explain?

-Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: [Haskell] View patterns in GHC: Request forfeedback

Claus Reinke
Hi Dan,

> No, of course not.  All I meant to say is that sometimes you want a
> total view, and that a total view should be given a type that says as
> much.  The latter says this better than the former.  On the other hand,
> there are lots of circumstances in which you want a partial view, and I
> think the (... -> Maybe _) types for those are perfectly appropriate.

indeed. i was only argueing against the 'wrong', or against the unclear
appeal to the type system (which also appears on the wiki page):

although you could introduce a _convention_ by which all view functions
are supposed to be exhaustive over their input type, the types themselves
do not encode or check exhaustiveness. so we're talking about an informal
promise rather than a formal guarantee.

one could turn that promise into a type-checked guarantee by using
explicit sum types (and thus structural rather than name-based typing),
but that gets awkward in plain haskell.
 
> But by this reasoning, every expression you write should have a Maybe
> type, since there's always the possibility of match failure or
> non-termination.  In Haskell, these effects are always implicit in a
> type, so there's no need to add extra summands to account for them.
> If you think about the *values* of the returned type, then (1 + Typ *
> Typ) is what you want, not ((1 + 1) + (1 + Typ * Typ)).    

yes, but we were talking about the subset of partiality due to
failure to accept input, rather than the whole class of partiality
due to failure to produce results. in particular, we were talking
about a syntactically checkable subset of that: exhaustiveness
means checking for a certain set of abstract or concrete patterns
(a function with exhaustive matching can still be partial in results).

i often feel limited by the non-extensible, need-to-be-named sum
types in haskell, and since i intend to use view patterns to encode
abstract patterns, within a framework of extensible matching, i
encoded my patterns in an extensible, open fashion.

others prefer to keep the closed sum types, just use view patterns
to transform between different concrete views. as Connor said,
they will want to avoid the Maybe of treating individual patterns in
isolation, and instead treat complete sets of patterns all the time.
 
i'm not saying that one is better than the other, i'm saying that i
prefer one of them, and that the appeal to typing is misleading
in the form presented.

> Setting aside the "transparent ordinary patterns" feature, I think this
> is exactly what you get above:
> - the data declaration for TypView corresponds to this "as" declaration

> - the view function of type Typ -> TypView can be analyzed for
> exhaustiveness using GHC's exhaustiveness checker

but note that the type does not encode or guarantee whether or
not such a check has happened, let alone was successful.

> - a run-time match failure of view will be reported as such

the declaration of virtual views as sets of exhaustive abstract patterns
was indeed meant to provide the same documentation as a concrete
view declaration would give.
 
> So I don't think I understand what you're going for here.  Could you
> explain?

i just wanted to suggest that it might be possible to get the best of
both worlds: documentation of exhaustiveness and extensible matches
(see Tullsen's first-class patterns or my library support and examples
for lambda-match on the haskell-prime list for more discussion of the
latter).

claus

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Dan Licata
In reply to this post by Conor McBride
Hi Conor,

This is a really good point, especially in the presence of GADTs and
type-level functions and so on, which introduce aspects of dependency.

Why are you so fatalistic about "with" in Haskell?  Is it harder to
implement than it looks? It seems to be roughly in the same category as
our view pattern proposal, in that it's just an addition to the syntax
of pattern matching, and it has a straightforward elaboration into the
internal language.  (Well, for Haskell it's more straightforward than
for Epigram, because we don't need to construct the evidence for ruling
out contradictory branches, etc., necessary to translate to inductive
family elims.)

-Dan

On Jul25, Conor McBride wrote:

> Hi
>
> Ok, I'm not quite under my rock yet,,,
>
> On 25 Jul 2007, at 10:28, apfelmus wrote:
>
> >Jules Bean wrote:
> >>Have you tried using pattern guards for views?
> >>
> >>f s | y :< ys <- viewl s = ....
> >>    | EmptyL  <- viewl s = ....
>
> This is annoying because the intermediate computation gets repeated. I
> don't think view patterns fix this even if they sometimes hide it. I  
> worry
> that the good behaviour of this feature depends on a compiler  
> noticing that
> a repetition can be shared: this design makes the sharing harder to  
> express.
>
> Of course,
>
> >Hm, I'd simply use a plain old case-expression here
> >
> >  f s = case viewl s of
> >     y :< ys -> ...
> >     EmptyL  -> ...
>
> which is fine if you're ready to commit to the right-hand side at  
> this point,
> but what if the result of the intermediate computation tells you what
> patterns to look for next?
>
> Epigram's "with"-notation was never implemented in Epigram, but it  
> has been
> implemented in Agda 2. At the moment, we'd write
>
>   f s with viewl s      -- adds a new column to the left
>   f s | y :< ys  = ...  -- so you can now match whatever you like
>   f s | EmptyL   = ...
>
> Inside a "with-block", the patterns left of | must refine the original
> patterns left of the "with". When you're fed up looking at the new
> information, you can exit the block, drop the column and carry on as  
> normal
> (see zip, below).
>
> I'd hope that we might ultimately be able to elide the repeated lefts
> if they are unchanged, but that's not implemented at the moment.
>
>   f s with viewl s      -- adds a new column to the left
>       | y :< ys  = ...
>       | EmptyL   = ...
>
> So zip might become
>
>   zip xs ys  with viewl xs
>              | x :< xt  with viewl ys
>                         | y :< yt = (x, y) <| zip xt yt
>   zip _ _ = empty
>
> or even
>
>   zip xs ys  with viewl xs  with viewl ys
>              | x :< xt      | y :< yt      = (x, y) <| zip xt yt
>   zip _ _ = empty
>
> For more entertainment, a padding zip
>
>   pzip x' xs y' ys with viewl xs with viewl ys
>                    | x :< xt     | y :< yt     = (x, y)   <| pzip x  
> xt y yt
>                    | x :< xt     | EmptyL      = fmap (flip (,) y') xs
>                    | EmptyL      | y :< yt     = fmap ((,) x') ys
>   pzip _ _ _ _ = empty
>
> Pattern matching is much weirder in a dependently typed setting, but  
> also a
> lot more powerful. Inspecting the value of a pattern variable or of an
> intermediate computation can leave us knowing more about (and hence
> instantiate) other pattern variables. We get stuff like this
>
>   gcd :: Positive -> Positive -> Positive
>   gcd x       y with trichotomy x y
>   gcd x (x + y) | LT x y = gcd x y
>   gcd x       x | EQ x   = x
>   gcd (y + x) y | GT x y = gcd x y
>
> Here, matching on the result of trichotomy (with constructor  
> patterns, see?)
> causes the original argument patterns to become more informative
> (with non-linear non-constructor forms which are *guaranteed* to match
> at no run time cost).
>
> For us, it's a bad idea to try to think of analysing one scrutinee
> independently of the other data we have to hand. We're naturally pushed
> towards thinking about the left-hand side as a whole, to which  
> information
> can be added, supporting further refinement. This is part of what James
> McKinna and I were on about in "The view from the left", and it's  
> happening
> on real computers now.
>
> To sum up, one-shot matching on intermediate computations, as provided
> by pattern guards or view-patterns, is conspicuously nasty in a  
> dependently
> typed language, but for reasons which make it sometimes merely  
> annoying in
> Haskell.
>
> I'm disinclined to argue thus: "don't do your thing (which probably will
> happen) because it messes up my thing (which probably won't, at least in
> Haskell)". I'll just chuck these observations in the air and see what  
> happens.
>
> All the best
>
> Conor
>
> PS Please may I have pattern synonyms anyway? They're cheap and they  
> serve a
> different purpose. Maybe I should say more about how their absence is
> seriously nasty for the way I work, another time.
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Heinrich Apfelmus
In reply to this post by Ben Franksen-2
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! :)

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Jon Fairbairn
In reply to this post by Simon Marlow-5
Simon Marlow <[hidden email]> writes:

> Dan Licata wrote:
>
> > Simon PJ and I are implementing view patterns, a way of
> > pattern matching against abstract datatypes, in GHC.
>
> At the risk of being a spoil-sport, I have a somewhat
> negative take on view patterns.  Not because I think they're
> particularly bad, but because I don't think they're
> significantly useful enough to warrant adding to the
> language, at least if we also have pattern guards.

I wholeheartedly agree.

I'd rather see a slightly different question addressed: how
to permit the definition of overloaded functions using
pattern matching (and I mean pattern matching with exactly
the same syntax as anywhere else). In other words, if I write

> f [] = e
> f (a:b) g a b

I currently only get f :: [t] -> something, so if I later
discover that I need to change the input representation to
be more efficient than lists, I have to rewrite f. Wouldn't
it be so much nicer if I could simply add a declaration

> f:: Stream s => s t -> something

and get a function that works on anything in the Stream
class?

The core of the idea would be to allow classes to include
constructors (and associated destructors) so the definition
of Stream would include something for ":" and "[]" and their
inverses, though I've no real idea of the details; can
anyone come up with a plan?


* * *

It's essential to this idea that it doesn't involve any new
pattern matching syntax; the meaning of pattern matching for
overloaded functions should be just as transparent as for
non-overloaded ones.

--
Jón Fairbairn                                 [hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Jonathan Cast
On Wednesday 25 July 2007, Jon Fairbairn wrote:

> Simon Marlow <[hidden email]> writes:
> > Dan Licata wrote:
> > > Simon PJ and I are implementing view patterns, a way of
> > > pattern matching against abstract datatypes, in GHC.
> >
> > At the risk of being a spoil-sport, I have a somewhat
> > negative take on view patterns.  Not because I think they're
> > particularly bad, but because I don't think they're
> > significantly useful enough to warrant adding to the
> > language, at least if we also have pattern guards.
>
> I wholeheartedly agree.
>
> I'd rather see a slightly different question addressed: how
> to permit the definition of overloaded functions using
> pattern matching (and I mean pattern matching with exactly
> the same syntax as anywhere else). In other words, if I write
>
> > f [] = e
> > f (a:b) g a b
>
> I currently only get f :: [t] -> something, so if I later
> discover that I need to change the input representation to
> be more efficient than lists, I have to rewrite f. Wouldn't
> it be so much nicer if I could simply add a declaration
>
> > f:: Stream s => s t -> something
>
> and get a function that works on anything in the Stream
> class?
>
> The core of the idea would be to allow classes to include
> constructors (and associated destructors) so the definition
> of Stream would include something for ":" and "[]" and their
> inverses, though I've no real idea of the details; can
> anyone come up with a plan?
>
>
> * * *
>
> It's essential to this idea that it doesn't involve any new
> pattern matching syntax; the meaning of pattern matching for
> overloaded functions should be just as transparent as for
> non-overloaded ones.
I don't have a formal specification, but I think this does that:

-- | Minimal complete definition: either 'empty', 'unit', and 'append' or '[]'
-- and '(:)' + pattern matching
algebraic class Stream s where
  empty :: s t
  unit :: t -> s t
  append :: s t -> s t -> s t
  [] :: s t
  (:) :: t -> s t -> s t
  empty = []
  unit x = x : []
  append (x:xn) ys = x : (xn `append` ys)
  [] = empty
  x : xn = unit x `append` xn

De-sugars into:

data StreamView s t
  = []
  | (:) t (s t)

data Stream s = Stream{
  empty :: forall t. s t,
  unit :: forall t. t -> s t,
  append :: forall t. t -> s t,
  nil :: forall t. s t,
  cons :: forall t. t -> s t,
  viewStream :: forall t. s t -> StreamView s t}

defaultEmpty s = nil s
defaultUnit s x = cons s x (nil s)
defaultAppend s xn ys = case viewStream s xn of
  [] -> ys
  x : xn' -> cons s x (defaultAppend s xn' ys)
defaultNil s = empty s
defaultCons s x xn = append s (unit s x) xn

Case evaluation proceeds by case analysis of viewStream.

data List t
  = Nil
  | Cons t (List t)

instance Stream List where
  [] = Nil
  (:) = Cons
  Nil = []
  Cons = (:)

De-sugars into:

streamList = Stream{
  empty = defaultEmpty streamList,
  unit = defaultUnit streamList,
  append = defaultAppend streamList,
  nil = Nil,
  cons = Cons,
  viewStream = \ xn -> case xn of
    Nil -> []
    Cons x xn -> x : xn}

While

data Tsil t
  = Lin
  | Snoc (Tsil t) t

instance Stream Tsil where
  empty = Lin
  unit x = Snoc Lin x
  xn `append` Lin = xn
  xn `append` Snoc ys y = (xn `append` ys) `Snoc` y
  Lin = []
  Snoc xn x = flip fix (x, Lin, xn) $ \ loop (x, ys, xn) -> case xn of
    Lin -> x : ys
    Snoc xn' x' -> loop (x', x : ys, xn')

De-sugars into

streamTsil = Stream{
  empty = Lin,
  unit = Snoc Lin,
  append = \ xn ys -> case ys of
    Lin -> xn
    Snoc ys' y -> (append streamTsil xn ys') `Snoc` y,
  nil = defaultNil streamTsil,
  cons = defaultCons streamTsil,
  viewStream = \ xn -> case xn of
    Lin -> []
    Snoc xn' x -> flip fix (x, Lin, xn) $ \ loop (x, ys, xn) -> case xn of
      Lin -> x : ys
      Snoc xn' x' -> loop (x', cons streamTsil x ys, xn')}

The best part is that you can have multiple data types to a view and multiple
views of a data type, and the fact that pattern-matching proceeds one level
at a time; the worst part is the rather syntactic way e.g. (:) as a
view-constructor is distinguished from (:) as a class method.  They can't be
distinguished type-wise (e.g., by a dictionary passing mechanism) because
their types aren't unifiable; I think you'd have to define a tail context
within viewStream and replace (:) with the constructor there only.  Or change
the view type to

data StreamView t
  = []
  | t : StreamView t

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs
--
Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Dan Licata
In reply to this post by Heinrich Apfelmus
On Jul25, apfelmus wrote:
> The point is to be
> able to define both  zip  and  pairs  with one and the same operator :< .

There's actually a quite simple way of doing this.  You make the view
type polymorphic, but not in the way you did:

   type Queue elt
   empty :: Queue elt
   cons :: elt -> Queue elt -> Queue elt

   data ViewL elt rec = EmptyL
                      | elt :< rec

   view :: Queue elt -> ViewL elt (Queue elt)
   view2 :: Queue elt -> ViewL elt (ViewL elt (Queue elt))

That is, the result of the view type is a parameter, so you can
instantiate it with both the viewed type and another view (and so on if
you want more levels).

Then the client code looks like this:

myzip :: Queue a -> Queue b -> Queue (a,b)
myzip a b = case (view a, view b) of
              (EmptyL, _) -> empty
              (_, EmptyL) -> empty
              (h1 :< t1, h2 :< t2) -> (h1,h2) `cons` myzip a b

pairs :: Queue a -> Queue (a,a)
pairs a = case view2 a of
            h1 :< (h2 :< t) -> (h1, h2) `cons` pairs t
            _ -> empty

The only difference with view patterns is that you can do the view2
inside the pattern itself:

pairs (view2 -> h1 :< (h2 :< t)) = (h1,h2) `cons` pairs t
pairs _                          = empty

This would be useful if the thing you were viewing were deep inside
another pattern.

This is a well-known technique in the ML community; see, e.g.,
http://www.cs.cmu.edu/~tom7/papers/wizard.pdf

-Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Derek Elkins
In reply to this post by Ben Franksen-2
On Wed, 2007-07-25 at 14:12 +0200, Benjamin Franksen wrote:

> Cheers
> Ben, member of the we-want-real-views-or-nothing-at-all movement ;-)

Derek, member of the counter-culture,
we-don't-want-real-views-but-nothing-at-all-may-suffice movement.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Ben Franksen-2
In reply to this post by Dan Licata
Dan Licata wrote:

> On Jul25, apfelmus wrote:
>> The point is to be
>> able to define both  zip  and  pairs  with one and the same operator :< .
>
> There's actually a quite simple way of doing this.  You make the view
> type polymorphic, but not in the way you did:
>
>    type Queue elt
>    empty :: Queue elt
>    cons :: elt -> Queue elt -> Queue elt
>
>    data ViewL elt rec = EmptyL
>                     | elt :< rec
>
>    view :: Queue elt -> ViewL elt (Queue elt)
>    view2 :: Queue elt -> ViewL elt (ViewL elt (Queue elt))

This is cool! The more so because 'view2' can quite easily be defined in
terms of 'view'

view2 q = case view q of
  EmptyL -> EmptyL
  x :< q' -> x :< view q'

so it suffices to provide the one-level 'view' as a library function. Does
this scale to views containing multiple nestable constructors?

It would, of course, be nice to get rid of having to write view2
altogether...

Cheers
Ben

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
123