[Haskell-cafe] Announcement: Bang, a drum DSL for Haskell

[Bertram Felgenhauer]

Tom Ellis wrote:
> On Wed, Jun 11, 2014 at 01:25:48AM +0200, Bertram Felgenhauer wrote:
> > begin cont = cont (return ())
> > a m cont = cont (m >> putStrLn "a")
> > b m cont = cont (m >> putStrLn "b")
> > c m cont = cont (m >> putStrLn "c")
> > end m = m
> > 
> > main = begin a b c a b a end
> 
> This is fantastic!

Unfortunately this causes performance problems with ghc's type
checker:

  main = begin a a a a a a a a a a a a a a a a a end

takes more than a second to type-check under ghc 7.8.2, and every
additional 'a' adds a factor of two. Interestingly, ghc 7.6.3 does
not show this behaviour.

Note that the instantiated types of 'a' grow exponentially:
The first 'a' in 'begin a end' and 'begin a a end' have types

  M -> (M -> M) -> M

and

  M -> (M -> (M -> M) -> M) -> (M -> M) -> M

respectively, where 'M' abbreviates IO (), and each additional 'a'
turns M -> r into M -> (M -> r) -> r, doubling the type's size.

Cheers,

Bertram

P.S. a related way for causing bad type checking performance is
the innocent looking

  main = id id id id id id id id id id id
         id id id id id id id id id id id (return ())

where again, the type of the first 'id' grows exponentially in
the number of 'id' calls. In this case, ghc-7.6.3 performs just
as badly as ghc-7.8.2.