GHC *is* resource hungry

[Ralf Hinze]

> I bet it's massive types.  Translate the program into system F and see.
> (I remember this came up when looking at Okasaki's sequences of code
> combinators.)

Ok. I didn't use System Fomega (no compiler at hand) but GHC's
data types with locally quantified fields. Here is the original
program (I added type signatures and swapped the argument of `leaf').

> type CPS a = forall ans . (a -> ans) -> ans
> begin :: CPS (a -> a)
> begin next = next id
> leaf :: Int -> (Int -> a) -> CPS a
> leaf i k next = next (k i)
> fork :: (Int -> a) -> CPS (Int -> Int -> a)
> fork k next = next (\ t u -> k (t + u))
> end :: a -> a
> end x = x
> main = print (begin fork fork fork fork fork fork fork fork fork fork (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) (leaf 0) end)

Still massive problems.

Now, if I turn the `type' into a `newtype' declaration and insert a few
identity functions (`CPS' and `#'), then GHC compiles the program like a charm.
The charm of the original program is, of course, gone.

> newtype CPS a = CPS (forall ans . (a -> ans) ->  ans)
> infixl 9 #
> CPS m # k = m k
> begin :: CPS (a -> a)
> begin = CPS (\ next -> next id)
> leaf :: Int -> (Int -> a) -> CPS a
> leaf i k = CPS (\ next -> next (k i))
> fork :: (Int -> a) -> CPS (Int -> Int -> a)
> fork k = CPS (\ next -> next (\ t u -> k (t + u)))
> end :: a -> a
> end x = x
> main = print (begin # fork # fork # fork # fork # fork # fork # fork # fork # fork # fork # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # leaf 0 # end)

Maybe this helps to identify the source of the problem.

Cheers, Ralf