Mutually recursive bindings

[Tom Pledger]

Tom Pledger writes:
 > Mark P Jones writes:
 >  > [...]
 >  > 
 >  > In general, I think you need to know the types to determine what
 >  > transformation is required ... but you need to know the
 >  > transformation before you get the types.  Unless you break this
 >  > loop (for example, by supplying explicit type signatures, in which
 >  > case the transformation isn't needed), then I think you'll be in a
 >  > catch-22 situation.
 >  > 
 >  > Why do you need the type to determine the transformation?  Here's
 >  > another example to illustrate the point:
 >  > 
 >  >     h x = (x==x) || h True || h "hello"
 > 
 > Before looking at this example, I was gearing up to protest that the
 > transformation was cued simply by scope, but now I see that it was
 > cued by scope *and* not foiled by type.
 > 
 > So, I withdraw the transformation idea, [...]

But wait!  There's life in the transformation idea yet.  After
dependency analysis but before type checking, we have enough
information to transform this:

    f x = x==x || f True || f (f "hello")

which would be illegal without an explicit type signature, into this:

    f x =      f' f1 f2 f3 x where
        f1 x = f' f1 f2 f3 x
        f2 x = f' f1 f2 f3 x
        f3 x = f' f1 f2 f3 x
        f'        f1 f2 f3 x = x==x || f1 True || f2 (f3 "hello")

for which Haskell infers the desirable type Eq a => a -> Bool.

The loop (type checking before transformation, and transformation
before type checking) is broken by defining one sacrificial function
for each recursive reference, regardless of the possibility that some
of them may end up with the the same types (f1 and f2 in the above
example both have type Bool -> Bool).  A keen compiler could detect
and coalesce the duplicate decls and parameters after type checking.

Regards,
Tom