Applicative-wired monad pattern

Oh sure. Essentially a relative monad in Haskell is a type constructor with the following operations:

-- f is a functor, but not necessarily an endofunctor
class Relative f g where
  rPure :: g a -> f a
  rBind :: (g a -> f b) -> f a -> f b

with some laws (which are essentially the same as those for regular monads):

rBind rPure = id -- left unit
rBind f . rPure = f -- right unit
rBind f . rBind g = rBind (rBind f . g) -- associativity

Every monad is a relative monad if you pick g to be Identity. But non-trivial examples include the type for well-scoped lambda terms where rBind performs parallel substitution:

type data Nat = Zero | Succ Nat

data Fin :: Nat -> Type where
  FZ :: Fin (Succ n)
  FS :: Fin n -> Fin (Succ n)

data Term :: Nat -> Type where
  Var :: Fin n -> Term n
  Lam :: Term (Succ n) -> Term n
  App :: Term n -> Term n -> Term n

as well as arrows (see page 13. of this pdf).

Additionally if we take any monad f and a functor g, Compose f g is a relative monad on g (see page 14. of this pdf):

instance Monad f => Relative (Compose f g) g where
  rPure = Compose . pure
  rBind k x = Compose (getCompose x >>= getCompose . k)

It seems like the core idea of the Applicative Wired pattern is using relative monads under the hood. Functions taking Value a and returning Action (Value b) are rPure-like and functions that use >>= for Action must return Action (Value a) to interface with the rest of the API.

Jane Street’s Bonsai library uses a similar pattern to provide a nicer interface for arrows and Leo White gave a talk called “Arrows as applicatives in a monad” on the same idea.

10 Likes