thunk-force category

A thunk-force category consists of

• a category ,
• a functor ,
• a map (“thunk”) that sends each object of to an arrow (i.e., is a “possibly unnatural transformation”), and
• a natural transformation (“force”)

satisfying the following criteria:

1. ,
2. is a natural transformation,
3. , and
4. .

Intuitively:

1. After a value has been thunked, thunking it again inside the thunk structure is the same as thunking the thunk structure itself.
2. Mapping an arrow inside a thunk and then thunking the resulting thunk is the same as thunking the original thunk and then mapping two levels down.
3. Thunking a value and then forcing that thunk gives back the original value.
4. Thunking a thunk and then forcing inside the outer thunk structure gives back the original thunk structure.

Equivalently:

• is a comonad, and
• each is an -coalgebra.

class Functor cat l => AbstractKleisli cat l where
  thunk :: cat a (l a)
  force :: cat (l a) a

It turns out that, for any monad , the Kleisli category of can be viewed as an abstract Kleisli category in a canonical way, with , , and .

instance Monad cat m => AbstractKleisli (Kleisli cat m) m where
  -- ignoring the Kleisli newtype wrapper:
  -- thunk :: cat a (m (m a))
  -- force :: cat (m a) (m a)
  thunk = Kleisli (return . return)
  force = id

Now we ask: how else can a Kleisli category be an abstract Kleisli category?

-- cat a (m (f a))
thunk' :: Kleisli a (f a)
-- cat (f a) (m a)
force' :: Kleisli (f a) a

-- Over Hask:
kthunk' :: a -> m (f a)
kforce' :: f a -> m a

In particular, we will focus on thunk-force Kleisli categories over Hask. That is, given a monad m on Hask, we consider functors f on the Kleisli category of m satisfying the thunk-force category laws. To start, we need to be able to pick out such functors.

class Monad m => KleisliFunctor m f where
  kmap :: (a -> m b) -> f a -> m (f b)

A Kleisli functor is subject to the usual functor laws (keeping in mind that it is a functor on a Kleisli category, not on Hask):

• kmap return = return
• kmap (g <=< f) = kmap g <=< kmap f

If we rephrase the second law in terms of >>=, we get

• kmap (f x >>= g) = kmap f x >>= g

class KleisliFunctor m f => ThunkForce f m where
  thunk :: a -> m (f a)
  force :: f a -> m a

data Cell s a = Thunk (ST s a) | Value a

newtype LazyRef s a = LazyRef (STRef s (Cell s a))

instance KleisliFunctor (ST s) (LazyRef s) where
  kmap f (LazyRef r) = LazyRef <$> newSTRef (Thunk (force r >>= f))

instance ThunkForce (LazyRef s) (ST s) where
  thunk x = LazyRef <$> newSTRef (Value x)
  force (LazyRef r) = readSTRef r >>= \case
    Value x -> return x
    Thunk m -> do
      x <- m
      writeSTRef r (Value x)
      return x