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

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.