Monomorphize, was: Re: Proposal for generalized function partitionin List-library

[Lennart Augustsson]

Josef Svenningsson wrote:

> John,
>
> On Thu, 17 May 2001, John Meacham wrote:
>
> [..]
> > namely that you don't necisarilly know all of the types of polymorphic
> > functions when they are in a module that is compiled seperately from the
> > rest of the program. the solution used by many C++ compilers is to
> > inline all polymorphic code in place (this is why templates are in
> > header files). there is no reason this won't work in haskell and give
> > back all of the speed benefits of base types everwhere (as it would in
> > this example) but has the unfortunate side effect of causing worst case
> > exponential code bloat as every function is re-written for every type
> > combination it is used with.
> >
> This is true in ML but not in Haskell. Haskell has polymorphic recursion
> which makes it impossible to predict statically at what types a function
> will be called. So trying to inline away polymorphism would lead to
> infinite unwindings.

This is true in theory, but in practice most polymorphism can be removed
by inlining.  I'm sure some pragmatic solution with limited inlining would
work quite well.  You'd still need to be able to handle polymorphism without
inlining, of course, so you could cope with the exceptional cases.

Mark Jones did some experiments with this kind of inlining that worked very well.

    -- Lennart