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

Question

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.

  Bryan 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?

Answer 1

This problem can be broken into two pieces, how you represent the data type and how you compose them together.

Data types

The styles you listed use only 2 styles of data types, the "normal" style and the continuation passing style. They differ in which objects are chosen as the primitives of the language.

In the normal style data types and their constructors are chosen as primitive. The data types are sums (having multiple constructors) of products (holding multiple values)

data Sum a b = Left a | Right b
data Product a b = Product a b

The main objects of the language are these data types and functions; the functions deconstruct the data to look inside it and see what it does.

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l _ (Left a)  = l a
either _ r (Right b) = r b

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry f (Product a b) = f a b

You can make an equivalent language where universally quantified types are treated as primitive instead of data types. In this case you can define the data types in terms of universal quantification. Sums are represented by their either function, universally quantified over the return type. Products are represented by their uncurry function, universally quantified over the return type. The need for a language extension (RankNTypes) to represent data types this way hints at why you'd call the first style "normal".

{-# LANGUAGE RankNTypes #-}

newtype Product a b = Product (forall r. (a -> b -> r) -> r)

product :: a -> b -> Product a b
product a b = Product (\f -> f a b)

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry both (Product f) = f both

newtype Sum a b = Sum (forall r. (a -> r) -> (b -> r) -> r)

left :: a -> Sum a b
left a = Sum (\l r -> l a)

right :: b -> Sum a b
right b = Sum (\l r -> r b)

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l r (Sum f) = f l r

This gives rise to one of the main differences between the two styles. In the universally quantified style there aren't any constructors. All of the structure of the data must be stored in closures to functions, which is exactly where the replacements for constructors left, right, and product put it. In the universally quantified style you can't construct any unnecessary intermediate objects; no object exists for you to construct. You can still construct unnecessary intermediate closures. At the very least you'll trick the profiler into telling you that you don't have a bunch of objects hanging around.

Your FooM data type, repeated here, can also be represented in continuation passing style.

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

It will be represented by its matchFoo function, which I've defined.

matchFoo :: ((i -> FooM i o a) -> r) -> (o -> FooM i o a -> r) -> (a -> r) -> r
matchFoo a _ _ (Await f) = a f
matchFoo _ y _ (Yield o next) = y o next
matchFoo _ _ d (Done a) = d a

The universally quantified FooM identifies a FooM with its matchFoo function, universally qualified over its return type.

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

await :: (i -> FooCPS i o a) -> FooCPS i o a
await f = FooCPS (\a _ _ -> a f)

yield :: o -> FooCPS i o a -> FooCPS i o a
yield o next = FooCPS (\_ y _ -> y o next)

done :: a -> FooCPS i o a
done a = FooCPS (\_ _ d -> d a)

Breaking the problem in 2

To use the same data type for all the ways of composing them back together we're going to replace FooM with its base functor. The base functor is the normal data type with recursions replaced by a type variable.

data FooF i o a next
  = Await (i -> next)
  | Yield o next
  | Done a
    deriving (Functor)

You can equivalently define a base functor in continuation passing style.

newtype FooFCPS i o a next = FooFCPS
  { runFooCPS
      :: forall r.
         ((i -> next) -> r)
      -> (o -> next -> r)
      -> (a -> r)
      -> r
  }
  deriving (Functor)

Composing them back together

1. Normal

We can immediately recover FooM by defining

newtype FooM i o a = FooM (FooF i o a (FooM i o a))

If you've already defined the fixed point of a functor:

newtype Fix f = Fix (f (Fix f))

Then FooM can be recovered by

newtype FooM i o a = FooM (Fix (FooF i o a))

2. Continuation Passing Style

Continuation passing style can be immediately recovered from the universally quantified FooFCPS

newtype FooCPS i o a = FooCPS (Fix (FooFCPS i o a))

3. Codensity

The codensity transformer works with either FooM or FooCPS.

4. Reflection without Remorse

We can define reflection without remorse in terms of base functors without reproducing the data type FooM in FooRWR.

newtype RWR f a = RWR { runRWR :: f (RWRExplicit f a) }

newtype RWRExplicit f a = RWRExplicit (forall x. FTCQueue (RWR f) x a)

And then recover FooRWR with

newtype FooRWR i o a = FooRWR {runFooRWR :: RWR (FooF i o a) a}

Bonus observations

Free

Both Free and F will work with either of the base functors FooF or FooFCPS.

Monad Transformers

The base functor can also be used to build a monad transformer. There's a detailed discussion of building the MachineT transformer (which is closely related to FooM) in this question and answer.

---

The claim that par can't be written in CPS without first converting back to normal style needs some qualification, since all data types can be replaced with universally quantified continuation-passing style types.