[Haskell-cafe] MultiCase alternative

[ok at cs.otago.ac.nz]

"Baa" <aquagnu at gmail.com> wrote:

> view patterns are "active" too, sure while they are callable :)
> Unfortunately I am not so familiar with both to compare them in detail.
> Are they equal in capacity/in general or only partially? I mean, can
> Haskell view patterns cover all possibilities of Active Patterns of F#?

I'm not sure.  The idea of something like views has been around
for a while.  For all I know, F# might have got there first.
There were quite a few proposals before all the warts got
frozen off and we were blessed with the present deceptively
simple scheme.  I have a bit of trouble trying to make sense of
some of Microsoft's F# documentation, though.

Let's compare them!

Do you use an ordinary function definition or some weird syntax?

Haskell: you use an ordinary function that can be used like an
ordinary function AND can be used in (view -> pattern) form

F# : weird syntax, not usable as an ordinary function.

Is the classification result an ordinary data type that can be
used by multiple views, or does each user-defined classifier
have to have a different result type?

Haskell: it's an ordinary type.

F# : if I've understood correctly, no, each active pattern
defines its own union type (with parts of the definition
scattered).

Is it obvious to a human reader when we're doing a plain old
"what constructor is this" match and when something fancy is
happening?

Haskell: yes, with pretty minimal overhead.

F# : no, by design.

Can the two approaches do the same things?

Based on my present wholly inadequate understanding of F# active
patterns, Haskell view patterns can do everything they do, but
not the other way around.  But I must stress that I regard my
understanding of F# active patterns as inadequate.

Let's take the ABCD example.
data ABCD a b c = A a | B b | C c | D c
data ABC  a b c = A' A | B' b | C c Bool

abc :: ABCD a b c -> ABC a b c
abc (A a) = A' a
abc (B b) = B' b
abc (C c) = C' c False
abc (D c) = C' c True

f (abc -> A' a)   = ...
f (abc -> B' b)   = ...
f (abc -> C' c _) = ...

This will be compiled as if it read
f x = case abc x of {A' a -> ... ; B' b -> ... ; C' c _ -> ...}

You define an ordinary type, you define an ordinary function,
and you call that ordinary function inside patterns.

type abcd<'a,'b,'c> = A of 'a | B of 'b | C of 'c | D of 'c;;

let (|A1|B1|C1|) x =
 match x with
  | A a -> A1(a)
  | B b -> B1(b)
  | C c -> C1(c,false)
  | D c -> C1(c,true);;

let f x =
 match x with
  | A1 a -> 1
  | B1 b -> 2
  | C1 (c,_) -> 3;;

This F# code has been tested in fsi 4.1.

You define an anonymous ADT with the constructors on one side
of the = and their arguments on the other, you define an
anonymous function, which is basically the same as the view
function, and you call the anonymous function inside pattern
matching.
>> Generally speaking, before proposing language changes, it's
>> always a good idea to see if you can solve your problem by
>> factoring out common stuff into a new function (or type, or
>> typeclass) first.
>>
>
> Sure, but there is another point of view here. Alternative is to have
> flexible but elegant syntax embedded in language, instead of many-many
> extensions for any possibility - they "fragment" language. But of course
> this is controversial and ambiguous :-)

I agree 100%.  That's why I prefer Haskell to F#.
View patterns are indeed flexible but elegant.
However, in this particular example, they are not
actually needed.

<quote>
SML/NJ has also extended the syntax of patterns to
allow ``or-patterns.'' The  basic syntax is:

  (apat1 | ... | apatn)

where the apati are atomic patterns. The other
restriction is that the variables bound in each
apati must be the same, and have the same type.
</quote>
The MLton compiler also (optionally) supports this.

There has been a certain amount of pressure in the Erlang
community to add a similar feature to Erlang.  In fact,
respected Erlang people have claimed to see a lot of
repeated cases that OR patterns would avoid.

Sometimes pain is Nature's way of telling you you're doing
it wrong.  If you find two cases in a data type being
handled the same way in one place, is this a rare thing,
or are they handled very similarly in many places?  If so,
why are they TWO cases instead of one with a subcase?

There's a big problem with F# active patterns, which is
shared by view patterns to a lesser degree.  That is that
a call to an active or view pattern may do arbitrary
amounts of work, whereas (after forcing such evaluation as
may be needed) ordinary pattern matching does an amount
of work proportional to the size of the pattern.
In Haskell, view pattern match syntax at least warns you
that you *might* have a problem.

What evil lurks in the heart of OR-patterns?

Let Pi be the pattern (i,_) | (_,i)

f P1 ... Pn (0,0) = True
f _  ... _  _     = False

g = f (1,1) (2,2) ... (n,n) (1,1)

What stops this taking time exponential in n to decide
which clause to use?  And you certainly don't want the
compiler to process this by expanding the alternatives out.
(So far it has taken 3 minutes on a fast machine to not
finish compiling these 3 lines of code...  I fear the worst.)

I have reluctantly come to the conclusion that OR-patterns
fill a much-needed gap.