Haskell puzzles!

[Daan Leijen]

Hi all,

I have put together some interesting Haskell puzzles!
Not many people were able to solve all three puzzles 
so don't be discouraged you don't know all the answers.

Have fun, 
 Daan.

-----------------------------------------------------
- All three puzzles are "Haskell 98"; you can solve 
  them using the Haskell 98 manual and they should be
  implementation independent.

- "equal" means that two evaluated expression denote
  the same semantical value; i.e. when typed on the
  Hugs prompt, I will see the same answer.

- All the answers are at the end of this mail.

-----------------------------------------------------
1) Are e1 and e2 equal?

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


-----------------------------------------------------
2) Are e1 and e2 equal? 
   Is one definition preferred over the other?
   (And what about "h x = nfib 30" ?)

> f  = const (nfib 30)
> g  = \x -> nfib 30
>
> e1 = f 1 + f 2
> e2 = g 1 + g 2


-----------------------------------------------------
3) Are e1 and e2 equal?
   And what if I typed them on the Hugs prompt?

> f   = \x -> x + x
> g x = x + x
>
> e1  = f 1.0 + f 2.0
> e2  = g 1.0 + g 2.0


-----------------------------------------------------
Answers at the end of this email.....








































Answers:
-----------------------------------------------------
1) 
answer: 
  "e1" equals the value 1, while "e2" is undefined.
   
explanation:
  This is due to the translation of pattern matching.
  The functions are de sugared into:

  > f x' y  = case x' of (x:xs) -> x
  > g x'    = case x' of (x:xs) -> (\y -> x)

  Now, the expression "f []" is a partial application
  and thus in weak head normal form while "g []" is
  evaluated and the pattern matching fails.

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.

-----------------------------------------------------
2)
answer:
  Yes, "e1" and "e2" are equal. However, the "f" definition
  is preferred since it potentially shares the computation 
  of "nfib 30". ("e1" will be almost twice as fast as "e2" 
  on most systems).

explanation:
  The Haskell language is only defined to be "non-strict".
  This means that there are no guarantees about sharing. However,
  all current Haskell systems use lazy semantics. This means
  that both "f" and "g" are caf's. When "g" is evaluated, the
  expression "\x -> nfib 30" is shared and on each call "nfib 30"
  is re-evaluated. When "f" is evaluated, the application node
  "const (nfib 30)" is shared and once it is applied it will be updated
  and "nfib 30" is only evaluated once. Smart compilers like GHC 
  however, will inline definitions like "g" and after common expression
  elimination we also end up with an efficient version. Same would
  hold for a full laziness transformation.

  Note that "h x = nfib 30" behaves exactly like "g" except that it's
  type is more general due to the monomorphism restriction and 
  defaulting:

  > f,g :: a -> Integer
  > h   :: Num b => a -> b

opinion:
  I believe that the operational distinction between both definitions
  is fundamentally important and should be expressible by the user.

-----------------------------------------------------
3) 
answer:
  Yes, "e1" and "e2" are equal (6.0). However, when "e1" and "e2"
  are used outside the scope of "f" and "g", for example when typed
  on the Hugs prompt, "e1" is not well-typed.

explanation:
  The type of "g" is "Num a => a -> a". One would expect the same
  type for "f" but unfortunately, the monomorphism restriction prevents
  this and defaulting tries to resolve the instance. Based on the usage
  of "f", it will default to "Double" and we get the type "Double -> Double"
  for "f". However, if we would use it from the Hugs prompt, there is
  no usage site of "f" and defaulting will resort to the "default defaulting"
  rules and set the type of "f" to "Integer -> Integer" and the expression
  "f 1.0" becomes ill typed -- that is, unless I use a "default" declaration
  in the module, as in:

  > default (Double)

opinion:
  Clearly, as puzzle 2 shows, we want to have a distinction between 
  shared values and functions. So, we need at least to be warned when
  the compiler would add a dictionary argument. I would say that an
  "overloading warning" is more appropriate than a "monomorphism restriction".
  Anyway, the real culprit here is the horrible defaulting mechanism. 
  I believe that defaulting has no place in Haskell modules and should 
  probably only be used on expressions in a top-level interpreter.