Re: GHC *is* resource hungry

> 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