when to use CPS vs codensity vs reflection without remorse in Haskell

Are there any rules of thumb for when to use continuation-passing style vs codensity vs reflection without remorse when creating monads in Haskell?

As an example, I'm going to use a simple coroutine monad. If you've never seen this before, you might want to check out the "Coroutine Pipelines" article in Monad.Reader Issue 19 or the pipes library. The full code for the following examples can be found in this repository.

1. Normal

   This is just a normal monad defined as a datatype:

   data FooM i o a
     = Await (i -> FooM i o a)
     | Yield o (FooM i o a)
     | Done a
   
   

   This style is used extensively thorought the Haskell ecosystem. One example of this style is the Proxy data type from pipes.

2. Continuation-Passing Style (CPS)

   This is similar to the normal style, but each data constructor has become an argument to a continuation:

   newtype FooCPS i o a = FooCPS
     { runFooCPS
         :: forall r.
            ((i -> FooCPS i o a) -> r)
         -> (o -> FooCPS i o a -> r)
         -> (a -> r)
         -> r
     }
   
   

   This style is used in both attoparsec and parsec.

3. Codensity

   This style uses a codensity monad transformer wrapped around a monad defined in the normal style. This gives O(1) left-associative bind.

   The codensity monad transformer looks like the following:

   newtype Codensity m a = Codensity
     { runCodensity :: forall b. (a -> m b) -> m b
     }
   
   

   Our actual monad could be defined as a newtype using the Codensity transformer. Notice how FooCodensity is using FooM internally.

   newtype FooCodensity i o a = FooCodensity
     { runFooCodensity :: Codensity (FooM i o) a
     }
   
   

   This style is used by conduit in the ConduitM type.

4. Reflection without Remorse

   This is the style discussed in the paper Reflection without Remorse.

   This is similar to the normal style, but recursive calls have become a data structure with O(1) append and amortized O(1) uncons. This gives O(1) left-associative bind and monadic-reflection to the FooRWR monad:

   data FooRWR i o a
     = AwaitRWR (forall x. i -> FooExplicit i o x a)
     | YieldRWR  o (forall x. FooExplicit i o x a)
     | DoneRWR a
   
   

   The FooExplicit type is defined as the following:

   type FooExplicit i o = FTCQueue (FooRWR i o)
   
   

   FTCQueue is a data structure with O(1) append and amortized O(1) uncons.

   This style is used by the freer-effects and extensible packages. It is available as a standalone library in monad-skeleton.

---

When should normal vs CPS vs codensity vs reflection without remorse be used? I imagine a hard and fast answer would require benchmarking a given monad and application, but are there any rules of thumb?

From my own research, I've come across the following ideas/comments:

• CPS can be faster than normal style because you may not have to do case-analysis. Although the actual speedup may vary based on how the code is compiled by GHC. Codensity and reflection without remorse have some overhead.

  Gabriel Gonzalez (the author of pipes) writes about how he sticks with normal style for pipes in both this reddit thread and this issue on Github.

  Byran O'Sullivan (the author of attoparsec) writes about how changing attoparsec from normal style to CPS gave a factor of 8 speedup. Some of the comments on that post also talk about normal style vs CPS.

• If you need deep left associative binds, normal style and CPS end up with quadratic runtime.

  Here is an example from the "Reflection without Remorse" paper that will exhibit quadratic runtime.

  data It i a = Get (i -> It i a) | Done a
  
  sumInput :: Int -> It Int Int
  sumInput n = Get (foldl (>=>) return (replicate (n - 1) f))
    where
      f x = get >>= return . (+ x)
  
  

  If sumInput is rewritten with codensity or reflection without remorse, it will run perfectly fast.

  If your application has deep left-associative binds, you should probably be using codensity or reflection without remorse.

  Michael Snoyman (author of conduit) talks about this in a blog post about speeding up conduit.

  The pipes library used to provide a codensity transformer.

• CPS and codensity don't support O(1) reflection.

  Here is a function that requires monadic reflection. This example is adapted from the "Reflection without Remorse" paper:

  data It i a = Get (i -> It i a) | Done a
  
  par :: It i a -> It i b -> It i (It i a, It i b)
  par l r
    | Done <- l = Done (l, r)
    | Done <- r = Done (l, r)
    | Get f <- l, Get g <- r = Get Done >>= \x -> par (f x) (g x)
  
  

  This method can't be written in the CPS or codensity style without first converting back to normal style. The reflection without remorse style does not have this problem.

  If you need monadic reflection, you should probably be using normal style or reflection without remorse.

• Reflection without remorse adds some overhead, but it is the only style that gives both O(1) left-associative bind and reflection.

bonus question: A similar question could be asked about Free (normal style) vs F (CPS) from the free package. When should Free be used? When should F be used?