Monday, November 16, 2009

Reviewing View Patterns

View Patterns are an interesting extension to the pattern matching capabilities of Haskell, implemented in GHC 6.10 and above. After using view patterns in real world programs, including HLint, I've come to like them. I use view patterns in 10 of the 27 modules in HLint.

View Pattern Overview

My intuitive understanding of view patterns is given in my Approaches and Applications of Inductive Programming 2009 paper, which describes the view pattern translation as:


f (sort -> min:ascending) = ...
==
f v_1 | min:ascending <- sort v_1 = ...
==
f v_1 | case v_2 of _:_ -> True ; _ -> False = ...
where v_2 = sort v_1 ; min:ascending = v_2


The view pattern on the first line sorts the list elements, then binds the lowest element to min and the remaining elements to ascending. If there are no elements in the list then the pattern will not match. This can be translated to a pattern guard, which can then be translated to a case expression. This translation does not preserve the scoping behaviour of the variables, but is sufficient for all my uses of view patterns. It is important to note that the translation from view patterns to pattern guards is fairly simple, and mainly eliminates one redundant intermediate variable. However, the translation from pattern guards to case expressions and guards is substantially harder.

How I Use View Patterns

My uses of view patterns seem to fall into a few distinct categories. Here are some example code snippets (mainly from HLint), along with explanation.

1) Complex/Nested Matching


uglyEta (fromParen -> App f (fromParen -> App g x)) (fromParen -> App h y) = g == h


Every operation/match pair in a pattern guard requires a separate pattern guard, whereas view patterns can be nested very naturally. Here the abstract syntax tree for expressions has brackets, and the fromParen function unwraps any brackets to find the interesting term inside. View patterns allow us to perform nested matches, which would have required three separate pattern guards.

2) Matching on a Different Structure


isAppend (view -> App2 op _ _) = op ~= "++"


The expression tree I use in HLint has lots of expressions which apply a function to two arguments - for example App (App (Var f) x) y and InfixOp x f y. I have a type class View that maps expressions into the data type data App2 = NoApp2 | App2 String Exp Exp, allowing easy matching on a range of expressions.

3) Safe Normalisation


dismogrify (simplify -> x) = .... x ....


While working with Yhc Core for the Catch and Supero tools I often wanted to process a syntax tree after simplifying it. If you name the original tree x, and the simplified tree y, then it's an easy (and type-safe) mistake to use x instead of y. To avoid this I wrote:


dismogrify bad_x = .... x ....
where x = simplify bad_x


Using bad_x in the expression makes the mistake easy for a human to spot. Using a view pattern makes the mistake impossible.

4) Mapping


classify (Ident (getRank -> x)) = ...


Sometimes I want to take a variable in one domain, and work with it in another. In the above example getRank converts a String to a Rank enumeration. Within the classify function I only wish to work with the rank as an enumeration, so it's convenient to never bind the string. This pattern is similar to safe normalisation, but it's purpose isn't safety - just making things a little neater.

5) Abstraction

The view pattern example in the GHC manual is all about abstraction. I have mainly used HLint in programs which don't use abstract data types, just algebraic data types which are intended to be manipulated directly. I don't think there are many data types which are both abstract and have a structural view, so I suspect this use will be less common (Data.Sequence is the only type that comes to mind).

Improvements I Suggest

I think there are three improvements that should be made to the view patterns in GHC 6.10.4:

1) Warnings

In GHC 6.10 all view patterns are incorrectly considered overlapping (see bug #2395), so all users of view patterns need to supply -fno-warn-overlapping-patterns. This problem has been fixed in GHC 6.12, which is great news.

2) Scoping

The current scoping behaviour seems undesirable:


apply (f -> y) = ...
where f = ...


Here the f in the view pattern isn't the f bound at the where. I suggest that the lhs of the -> can use variables from the where, in a similar manner to pattern guards. (It's possible this suggestion is misguided, as the scoping rules can be quite subtle.)

3) Implicit Patterns

The original view patterns wiki document asks what should become of (-> ...), and proposes it become (view -> ...). I like this idea as HLint already contains 12 instances of (view -> ...). The only question is which view should be used? I think there are two possible answers:

a) The view currently in scope

If the desugaring is simply to view, then people can select their imports appropriately to choose their view function. This proposal is similar to the rebindable syntax already supported, but in this case may be a legitimate default, due to several possible view interpretations. If one day everyone starts using Data.View.view, then the default could be switched. As an example (in combination with proposal 2) we could have:


uglyEta (-> App f (-> App g x)) (-> App h y) = g == h
where view = fromParen


b) Data.View.view

In HLint I have used:


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


I haven't needed any functional dependencies, as the matching always constrains the types sufficiently. I have mapped one source type (i.e. Exp) to several matching types (App2 and App1), but never mapped multiple source types onto one matching type. If I was to add a dependency it should be that b uniquely determines a, as usually b will have a pattern on the RHS which will constrain b already.

I think my preference is for using Data.view.view, primarily because all other Haskell syntax is bound to a fixed name, rather than using the name currently in scope. However, my opinions on functional dependencies should be taken with skepticism - I'm not normally a user of functional dependencies.

4) Rejected Suggestions

I do not support the idea of implicit view patterns without some leading syntax (see bug 3583) - view patterns are nice, but I don't think they are important enough to be first-class, like they are in F# (note that F# interoperates with OO languages, so first-class view patterns are much more reasonable there).

I also do not support the idea of implicit Maybe in view patterns - Maybe should not be special, and this suggestion doesn't seem to fit with the rest of Haskell.

Conclusion

View patterns are a nice enhancement to pattern guards, increasing their compositionality and reducing the need for redundant intermediate variables. I could live without view patterns, but I don't think I should have to - the design is good, and they fit in nicely with the language. As for pattern guards, I consider them an essential part of the Haskell language that really makes a substantially difference to some pieces of code that would otherwise be rather ugly.

Edit: Fix as per Christophe's comment.

6 comments:

Dan said...

Glad to hear that view patterns are getting some use!

Regarding the suggestions:

1) The warnings were ridiculous because we thought were were going to rewrite the exhaustiveness checker, but then that never happened. I guess it has been taken care of now, though I wonder what they did: do you want your compiler warnings to be sound (if there's a potential overlap, you get a warning), complete (if there is a warning, then there is definitely an overlap), or neither?

2) One tricky thing is that the viewed variables could also appear in the RHS of the 'where' binding, and what do you do with:

apply (f -> y) = e where f = y

?

The translation as

apply x =
(case f x of y -> e)
where f = y

doesn't make sense.

3) We thought about this but never did it, mostly because we couldn't make up our minds about the fundeps on the view class. If people get some experience and decide what the fundeps should be, it would be easy to implement.

Martijn said...

I understand that (-> pat) would be convenient but I don't like the implicit use of a bound name. It feels very unlike Haskell: nowhere else in the language are names used implicitly.

Neil Mitchell said...

Dan - thanks for implementing the feature in the first place, my comments on your comments are:

1) I want my compiler warnings to be complete - otherwise they are impossible to shut up.

2) Yes, the scoping is trick, but I'm sure it could be done.

Martijn: 1 in Haskell means Prelude.fromInteger 1, there are loads of places where functions are implicitly inserted. I think I probably agree with you though that it should be a predefined name, rather than the name in scope.

Christophe Poucet said...

Small comment:
f v_1 | case v_2 of _:_ -> True ; _ -> False = ...
where v_2 = f v_1 ; min:ascending = v_2

You probably mean 'where v_2 = sort v_1'.

Neil Mitchell said...

Christophe: Indeed I did, I was adapting from an example in terms of f/g trying to make it more meaningful, and added a typo. Now fixed.

Reid said...

True story: I was writing bindings to a C library and I had some code like this:

> do
>   ...
>   let Blah n x y = ...
>   ...

when the compiler informed me that n was a CInt but I was using it later as an Int.

"No problem," I thought, "I'll just use a view pattern (Blah (fromIntegral -> n) x y), like I learned from Neil's blog post."

"But then, this is library code. Do I really want a dependency on that language feature? And there's that annoying warning in GHC 6.10..."

And so I promptly wrote

> do
>   ...
>   let Blah n0 x y = ...
>         n = fromIntegral n
>   ...

(sigh)