Haskell puzzles!

Jan-Willem Maessen jmaessen@alum.mit.edu
Tue, 19 Mar 2002 10:44:26 -0500

Daan Leijen writes:
> 1) Are e1 and e2 equal?
> > f (x:xs) y  = x
> > g (x:xs)    = \y -> x
> >
> > e1 = seq (f []) 1
> > e2 = seq (g []) 1
> ...
> 1) 
> answer: 
>   "e1" equals the value 1, while "e2" is undefined.
> ...
> opinion:
>   I think that the pattern matching translation rules
>   are wrong here and we shouldn't push the "case" through
>   the lambda's. However, the current rules are potentially
>   more efficient since all arguments can be collected
>   before matching.

On the contrary, I far prefer the way things are now.  Matching
arguments as they arrive makes programs far too eager about pattern
matching.  Consider the following minor variation on your example
(which happily also avoids using "seq"):

Q) Are e1 and e2 both defined?

> f (x:xs) y z = x
> g (x:xs)     = \y -> \z -> x
> e1 = f [] 1
> e2 = g [] 1

A) No, e1 is defined---pattern matching happens only when all the
arguments have arrived.  This is nice and lazy---we don't do any work
until we know we have to.  By contrast, e2 performs the matching as
soon as (g []) is applied to 1.  We've matched eagerly, and our
program fails.

  In practice, pattern matches are much more complicated than f and g.
  There is no easy and convenient way to get the behavior of e1 if
  matching always works as in e2.  Indeed, it's not even clear how to
  do complex multiple-argument pattern matches if we proceed this way.
  Meanwhile, there's a simple way to turn f into g if that's what is

-Jan-Willem Maessen
And I've implemented *Eager* Haskell, too.