Knot-tying monad transformer for recursive graph building.

Some operations, such as building a graph, are inherently self-recursive; consider the following graph:

a -> b
b -> a

To construct in Haskell, we might want to use the following type:

data Node = Node
  { nodeName :: Text
  , nodeNeighbours :: [Node]
  }

To construct our trivial graph, we need a to know about b and b to know about a: this is fine as long as we can build them both at the same time:

graph = [nodeA, nodeB]
  where
    nodeA = Node "a" [nodeB]
    nodeB = Node "b" [nodeA]

But this falls apart as soon as building the nodes becomes more complicated; for instance, if it becomes monadic. This causes an infinite recursion:

graph = do
  a <- buildA
  b <- buildB
  pure [a,b]
  where
    buildA = do
      b <- buildB
      pure $ Node "a" [b]
    buildB = do
      a <- buildA
      pure $ Node "b" [a]

The reason why the non-monadic version works is laziness; and there is a way to retrieve this laziness in a monadic context: it's what MonadFix is for. (https:/wiki.haskell.orgMonadFix)

However, MonadFix is both powerful and unintuitive; the goal of this module is to use its power, but to give it a more restricted interface, to make it easier to use. Using CircularT, the graph above can be built monadically like so:

graph = runCircularT do
  a <- buildA
  b <- buildB
  pure [a,b]
  where
    buildA = withCircular "a" do
      b <- buildB
      pure $ Node "a" [b]
    buildB = withCircular "b" do
      a <- buildA
      pure $ Node "b" [a]

It allows each part of a recursive process to be given a name (the type of which is of the user's choosing), and it automatically breaks cycles. The only caveat is that we cannot violate temporal causality: if we attempt to make a cache-building decision based on the value obtained from the cache, then no amount of laziness can save us:

broken = runCircularT go
  where
    go = withCircular () do
      x <- go
      pure $ if odd x then 1 else 0

CircularT is somewhat similar to TardisT from Control.Monad.Tardis and SchemaT from Hasura.GraphQL.Parser.Monad, but simpler than both.