Free applicatives, the handle pattern, and remote systems

We recently refactored some gnarly code that manipulated customer and
order records in our enterprise resource planning (ERP) system. That
system had a few idiosyncrasies which complicated this task:

• Creating new records required referencing other entities by internal
  ID, so we had to do a number of lookups before issuing “create
  record” requests;
• For some entity types, we found it easiest to issue “search” API
  calls and extract the required IDs from the returned search
  results. This necessitated an extra parsing step between “we have a
  successful response” and “we have the ID we’re looking for”; and
• Requests are often slow, but the marginal cost of additional
  requests in a batch was quite low. This meant that we could expect
  some good results from batching related requests together.

The benefits of batching led us to seek a solution that permitted
static analysis. Applicative functors have a completely static control
flow, and cannot express computations where one step depends on the
result of a previous step. A well-chosen applicative would let us
analyse the requests we need to send without executing any of them,
batch queries together without worrying about data dependencies, and
then route relevant results to each individual query to parse (if
necessary). Our library users could ignore batching details but still
gain the efficiency benefits of a batch query API.

In this post, we’ll look how we’ve been using handles, what “free
structures” are, how free applicatives elegantly solved some of our
problems interfacing with a remote system, and how they interacted
especially well with the “handle pattern”.

Handles, as Bellroy uses them

The “handle pattern”
is a Haskell idiom that is similar to dependency injection in
mainstream languages. Instead of directly writing in the side effects
we want our code to perform, we accept a record of functions that we
call a “handle”. (In an object-oriented language, we’d probably accept
an object that implements an abstract interface instead of a record.)
These handles can group related functions into a single record but
often only contain one:

newtype Handle e m = Handle 💬

-- Plus some other handle-making functions e.g. for testing.
newHandle ::
  MonadIO m => ERP.Credentials -> m (Handle ERP.Error m)

Functions that consume handles generally look like this:

someFunction ::
  -- When all side effects come from handles,
  -- we rarely need anything stronger than `Monad`.
  Monad m =>
  -- First: Any handles we need
  FooHandle m -> BarHandle m ->
  -- Second: Other "normal" arguments
  Argument1 -> .. -> ArgumentN ->
  m Result

This idiom is a simpler, library-free alternative to effect system
libraries like
effectful,
bluefin,
heftia and
polysemy. We
previously wrote about an
experiment with effectful,
but we have still not committed to an effect system. Instead, we are
refactoring towards handles as a way to encapsulate our side effects,
and because it should be easy to convert handle-using code to an
effect system if and when we choose one.

Because we have code written against other idioms (e.g. MTL-style
classes), and because we often find it convenient to introduce an
ExceptT e or MaybeT monad transformer in the body of our
functions, we sometimes need to change the monad of a handle that
we’ve been given. We do this by providing a hoistHandle function:

hoistHandle :: (forall x . f x -> g x) -> Handle f -> Handle g
hoistHandle f Handle What do you think? =
  Handle 🔥

That first argument, forall x . f x -> g x, is worth commenting
on. A forall in a type signature explicitly introduces a type
variable that is provided by the function’s caller. For a simpler
example of how forall works here, let’s look at the map function
on lists, but with explicit foralls:

map :: forall a b . (a -> b) -> [a] -> [b]

The caller of map gets to choose the types of a and b, and GHC
is often smart enough to figure this out automatically:

-- GHC concludes that it needs to call
-- `map` with `Int` for `a` and `String` for `b`.
ghci> map show [1, 2, 3]
["1","2","3"]

In our hoistHandle function, we let the caller choose f and
g, but they must provide us a function where we are allowed to
choose x. The types force this function to convert f x into g x
in a way that’s blind to what x actually is — guaranteeing that
the conversion only changes structure, not wrapped values. It also
ensures that we can write hoistHandle for a handle containing
multiple functions, because we can choose a different x for each
one.

Building our applicative

We want to build a structure that is essentially a syntax tree of the
operations we want to perform. This means it needs to hold the
requests we want to send, and because we want it to be an applicative,
we’ll add constructors to represent pure and (<*>):

data Query a where
  QueryAndParse ::
    FromJSON x =>
    ERP.Request -> (x -> Either Text a) -> Query a

  -- Extra constructors to hold applicative structure
  Pure :: a -> Query a
  Ap :: Query (a -> b) -> Query a -> Query b

deriving stock instance Functor Query

instance Applicative Query where
  pure = Pure

  Pure f <*> Pure x = Pure $ f x
  QueryAndParse req f <*> Pure a =
    QueryAndParse req $ fmap ($ a) . f
  -- Plus another seven cases, being careful that
  -- each case obeys the applicative laws.

QueryAndParse is the only data constructor directly relevant to our
problem. It captures the request we want to make against the ERP, a
FromJSON x constraint so we can parse the raw response into some
intermediate type representing an API response, and a function x -> Either Text a to extract just the data we want from that API
response.

This design could work, but it’s a fair amount of boilerplate, and the
next time we want an applicative like this we’d need to repeat most of
it. In the next section, we’ll use a free applicative to separate the
general “applicative” code from the specific “query and parse” code.

What is a “free structure”?

To understand how free applicatives help us with this problem, we need
to have some idea what “freeness” means in this context. The Haskell
community usually talks about taking “the free $class over $type”
as a way to make $type an instance of $class, by adding just
enough structure to construct a lawful instance of $class. Packages
like free provide
wrapping types that hold values of $type and provide instances of
$class.

Let’s pare our Query type back to something much smaller: a type
representing a single request against our ERP:

data OneQuery a where
  QueryAndParse ::
    FromJSON x =>
    ERP.Request -> (x -> Either Text a) -> OneQuery a

We will now re-write Query as the free Applicative over
OneQuery. To make OneQuery into an Applicative, we’ll use the
Ap wrapper from
Control.Applicative.Free.
Here is its interface:

-- `Ap f` is the free applicative over `f`. We never use its
-- constructors directly; instead, we use `liftAp` and the
-- `Applicative` interface (`pure`, `(<*>)`, `liftA2`, etc.)
data Ap f a

-- For *any* `f`, `Ap f` is an applicative.
instance Applicative (Ap f)

-- We can turn any `f a` into an `Ap f a`.
liftAp :: f a -> Ap f a

-- If we can turn our `f` into some applicative `g`, then we can turn
-- `Ap f a` into `g a` in a way that respects the Applicative laws:
--
-- runAp _ (pure x) = pure x
-- runAp f (x <*> y) = (runAp f x) <*> (runAp f y)
--
-- Similar to the `forall x. f x -> g x` in `hoistHandle` above,
-- this lets us turn each `f x` stored in the `Ap f a` into a
-- corresponding `g x`, while remaining ignorant of the specific
-- type `x`.
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a

We’ll skip the implementations because we won’t ever manually recurse
through an Ap f a value; from a modularity perspective, we are only
interested in the abstract interface. We declare Query as the free
applicative over OneQuery, make it a newtype to establish an
abstraction boundary between the query library and its callers, and
use deriving newtype to avoid writing any applicative structure
ourselves:

newtype Query a = Query (Free.Ap OneQuery a)
  deriving stock Functor
  deriving newtype Applicative

-- Helper functions to avoid building `Query` values by hand.

query ::
  FromJSON a => ERP.Request -> Query a
query _ req =
  Query . Free.liftAp $ QueryAndParse req Right

queryAndParse ::
  FromJSON a => ERP.Request -> (a -> Either Text b) -> Query b
queryAndParse req f =
  Query . Free.liftAp $ QueryAndParse req f

Building a Query

From this infrastructure, we can write functions representing
individual queries. These are direct applications of the query and
queryAndParse helpers:

queryLocationId ::
  ERP.Location.Name -> Query ERP.Location.Id
queryLocationId locationName =
  query $ ERP.lookupLocation locationName

queryOrderId ::
  ERP.Order.Name -> Query ERP.Order.Id
queryOrderId orderName =
  queryAndParse
    (ERP.searchOrders orderName) $ \case ->
      [order] -> Right order
      (_:_) -> Left "Multiple Orders in response"
      [] -> Left "No Orders in response"

From these functions we can build up complex queries using applicative
operations:

queryOrderAndLocation ::
  ERP.Order.Name -> ERP.Location.Name ->
  Query (ERP.Order.Id, ERP.Location.Id)
queryOrderAndLocation orderName locationName =
  liftA2 (,) (queryOrderId orderName) (queryLocationId locationName)

Running a Query

We can run a Query by using
runAp.
Because we’re in an applicative context and we’re making requests that
don’t alter the remote system, we can run every request and use a
Validation
to collect all failures:

data RunQueryError e = RequestError e | JsonError Text | ParseResultError Text
type RunQueryErrors e = NonEmpty (RunQueryError e)

runQuery :: forall e m a.
  Monad m =>
  ERP.Handle e m ->
  Query a ->
  m (Validation (RunQueryErrors e) a)
runQuery ERP.HandleTell us your thoughts in comments! (Query q) =
  getCompose $ Free.runAp (Compose . go) q
  where
    go :: OneQuery x -> m (Validation (RunQueryErrors e) x)
    go (QueryAndParse req parse) = performRequest req <&> \case
      Left reqErr -> Failure . NonEmpty.singleton $ RequestError reqErr
      Right value -> case Aeson.parseEither Aeson.parseJSON value of
        Left jsonErr -> Failure . NonEmpty.singleton . JsonError $ Text.pack jsonErr
        Right x -> case parse x of
          Left parseErr -> Failure . NonEmpty.singleton $ ParseResultError parseErr
          Right a -> Success a

The implementation can be mostly derived by following the types, but
we’ll highlight some specifics:

• Validation e a is a type that’s structurally isomorphic to
  Either e a, but provides an Applicative instance that
  accumulates errors:

  -- From the validation-selective package.
  instance Semigroup e => Applicative (Validation e) where
    pure = Success
  
    -- This asymmetric way of writing <*> maximises laziness.
    Failure e1 <*> b = Failure $ case b of
      Failure e2 -> e1 <> e2
      Success _  -> e1
    Success _ <*> Failure e = Failure e
    Success f <*> Success a = Success (f a)

• Since the composition of any two applicatives is itself an
  applicative,
  Data.Functor.Compose
  lets us combine the m and Validation e applicatives into
  Compose m (Validation e), which executes actions in m and
  accumulates errors — exactly what we want.

• Since we use the Compose constructor to wrap the result of go,
  Free.runAp will return a Compose m (Validation e) a which we
  must unwrap with getCompose.

• The go function processes a single request held in a OneQuery x,
  and Free.runAp uses it to build up the applicative combination of
  each result.

• We accept a handle telling us how to contact the ERP. This is the
  key location where the handle pattern and the free applicative
  interact, giving the library user a lot of power: the handle
  parameter frees us from being coupled to any particular monad and
  makes it easier to write tests for this code. We’ll see another way
  to construct a ERP.Handle very soon.

• The caller of the Query interface has no idea that we’re building
  and consuming free structures under the hood. It’s an implementation
  detail that doesn’t distort the abstraction boundary at all.

Now that we can execute queries, let’s explore the main benefit of
free applicatives: the ability to analyse the applicative program
without running it. We can extract a monoidal summary of any free
applicative’s structure via
runAp_:

runAp_ :: Monoid m => (forall x . f x -> m) -> Ap f a -> m

For an intuition why this is true, consider that the constant functor
Const r
has an Applicative instance whenever r is a monoid, because pure
stores a mempty value and (<*>) combines the held values with
(<>). For a fun exercise, implement runAp_ in terms of runAp and
Const.

We can use runAp_ to extract a list of every request a Query a
will send:

allRequests :: Query a -> [Request]
allRequests (Query q) = ordNub $ Free.runAp_ go q
  where
    go :: OneQuery x -> [Request]
    go (QueryAndParse req _) = [req]

Once we have the list of requests, we can look for ways to optimise
them. De-duplicating the requests with
ordNub
is an easy optimisation, but if the remote API supports it, we could
do more advanced optimisations like using a batch request API.

As a simple demonstration, we can perform all the lookup requests in
advance and construct a Map Request Aeson.Value:

type SavedRequests = Map Request Aeson.Value

saveRequests ::
  forall e m.
  Monad m =>
  Handle e m -> [Request] -> m (Either e SavedRequests)
saveRequests Handle⚡ requests =
  runExceptT $ Map.fromList <$> traverse go requests
  where
    go :: Request -> ExceptT e m (Request, Aeson.Value)
    go req = (req,) <$> ExceptT $ performRequest req

Using a collection of saved results, we can construct a handle that
returns the saved responses instead of performing real requests:

newtype UnsavedRequestError = UnsavedRequestError Request

newHandleFromSavedRequests ::
  (Applicative m) => SavedRequests -> Handle UnsavedRequestError m
newHandleFromSavedRequests requests =
  Handle
    Tell us your thoughts in comments!

This gives us a great story for testing. Since our runQuery works
with any handle, we can capture some real requests to a file, redact
any sensitive information, and create a pure handle built from saved
requests. We can then use this handle to write test cases that run
real code without performing side-effects.

If this example moved too quickly, or you want to see another
application of free structures, Justin Le has a spectacular post on
matching regular expressions using the free Alternative.

Payoffs and limitations

What have we achieved? We decided that we wanted an applicative to
describe queries against our remote system. Instead of inventing a
complicated data structure to represent the syntax tree of pure and
(<*>) calls, we defined a type just to hold one request and took the
free applicative over it. We also used the handle pattern to ask for
only the side-effects that we needed. Both patterns are reasonably
easy to implement, and in exchange we got some pretty neat benefits
that would’ve been harder to realise with either technique alone:

1. We can analyse a Query without running it, and use the Query to
   inform the handle we do eventually use;

2. As a special case of (1), library users can code against a
   convenient interface and request individual records, but we can
   inspect the set of queries before we begin execution and issue
   optimised, parallelised, de-duplicated and batched requests in
   their place;

3. We don’t have to abort at the first failed request — we can
   collect and report every problem with a Query; and

4. We can record and replay requests, giving us a great testing story
   in the style of Ruby’s vcr library.

It’s not all roses, though. We lose a significant amount of expressive
power by giving up the monadic interface. For APIs where we need to
interleave pure queries and side-effecting requests, losing the
Monad instance might be a bridge too far. Chris Penner suggests
that Selective functors could be closer to the sweet spot,
but then you lose the nice ergonomics of -XApplicativeDo.
Chris Done identifies an “Applicative-wired Monad” pattern
which uses a monad only to plumb together applicative values.

So where does this leave us? The handle pattern has been working well
for us and we plan to continue refactoring code to use handles for the
foreseeable future. In narrow contexts where we want to take advantage
of static analysis, a well-chosen free applicative has given us a
surprising amount of modularity, testability and opportunities for
automatic optimisation. In the function that “runs” the free
applicative, these two idioms interacted in a very satisfying way: the
handle parameter gave us a lot of flexibility without asking library
users to write a lot of boilerplate.