Skip to content

Missed optimization

Motivation

When compiling the function below:

myJoin :: Monad m => m (m a) -> m a
myJoin mma =
  do
    ma <- mma
    a <- ma
    return a

ghc generates two calls to the bind function (just as the code specifies). But this function is (I believe) semantically equivalent to the following:

myJoin' :: Monad m => m (m a) -> m a
myJoin' mma =
  do
    ma <- mma
    ma

which could potentially be more efficient since only one bind is performed. Perhaps ghc could be taught to perform this transformation.

For an even simpler example consider:

silly_1 :: Monad m => m a -> m a
silly_1 ma =
  do
    a <- ma
    return a

silly_2 :: Monad m => m a -> m a
silly_2 ma = do ma

silly_3 :: Monad m => m a -> m a
silly_3 ma = ma

Here ghc realizes that (2) and (3) are the same function (aka the identity function) but it compiles (1) with a call to bind.

silly_1
  = \ (@ (m_a76C :: * -> *))
      (@ a_a76D)
      ($dMonad_a76F :: Monad m_a76C)
      (ma_a5Vu :: m_a76C a_a76D) ->
      >>=
        @ m_a76C
        $dMonad_a76F
        @ a_a76D
        @ a_a76D
        ma_a5Vu
        (\ (a1_a5Vv :: a_a76D) ->
           return @ m_a76C $dMonad_a76F @ a_a76D a1_a5Vv)

silly_2
  = \ (@ (m_ankf :: * -> *))
      (@ a_ankg)
      _ [Occ=Dead]
      (ma_an0P :: m_ankf a_ankg) ->
      ma_an0P

silly_3 = silly_2

This is all with ghc 8.8.4.

Proposal

Teach ghc to perform this transformation.

Edited by Neo
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information