On Thu, 6 Jan 1994, Simon L Peyton Jones wrote:
> OK, here's my example. I hope it's right. I was writing a compiler
> pass which looked at a data type something like
>
> data Expr = Let Bind Expr
> | ...
>
> data Bind = MkBind String Expr
>
> Then I had three functions, written in continuation-passing styule, as
> follows:
>
> doBinds :: [Bind] -> [Bind]
> doBinds (b:bs) = doBindAndScope b (\b' -> b' : doBinds bs)
>
> doExpr :: Expr -> Expr
> doExpr (Let b e) = doBindAndScope b (\b' -> Let b' (doExpr e))
>
> doBindAndScope :: Bind -> (Bind -> a) -> a
> doBindAndScope (MkBind s e) cont = cont (MkBind s (doExpr e))
>
> The trouble is that the mutual recursion between
>
> doBindsAndScope doExpr
>
> means that doBindsAndScope can't be as polymorphic as its type
> signature says it should be. But if it isn't that polymorphic, the
> call in doBinds is illegal.
>
> I solved it like this (UTTERLY YUK YUK), by encapsulating the polymorphism
> in a fixed data type which simply tags the various expected types at
> which the function can be called. Not only is this really quite obscure,
> but it also is inefficient at runtime.
Hmm...very irritating. An alternative to Simon's solution would be:
doBinds (b:bs) = doBindAndScope b doExpr (\b' -> b' : doBinds bs)
doExpr (Let b e) = doBindAndScope b doExpr (\b' -> Let b' (doExpr e))
doBindAndScope :: Bind -> (Expr -> Expr) -> (Bind -> a) -> a
doBindAndScope (MkBind s e) f cont = cont (MkBind s (f e))
This works by removing the mutual recursion at the expense of
introducing an unwanted additional parameter. Maybe not UTTERLY
horrible but still not very nice.
OK - I'm convinced that allowing polymorphic recursion in the presence
of type signatures is useful, so perhaps it would be worth complicating
the type system a bit to allow it. After all, what's a bit of extra
complexity when there's so much in there already :-).
Sebastian
