Mutable Branches

The MutPart abstraction lets us "zoom into" a smaller part of a piecewise-mutable product type. But what about sum types?

Let's look at Data.Mutable.Branches to tackle this.

Conceptually, mutable sum types are a completely different beast. A mutable product type is just a (pure) tuple of its mutable fields.

A mutable sum type is actually a mutable reference to one of its possible branches.

For example, let's consider a simple sum type:

data IntOrBool = IBInt  Int
               | IBBool Bool

Its mutable version would be:

newtype IntOrBoolRef s = IBR
    { getIBR :: MutVar s (Either (MutVar s Int) (MutVar s Bool))
    }

It's a mutable reference to either a mutable Int or a mutable Bool.

This is probably most useful when thinking about recursive types, like lists:

data List a = Nil | Cons a (List a)
  deriving (Show, Generic)

instance Mutable s a => Mutable s (List a) where
    type Ref s (List a) = GRef s (List a)

The GRef s (List a) is now a mutable linked list --- the good old fashioned data type that people learn to implement in Java or C++ or what have you. It's a reference to a cell that is either a Nil cell or a Cons cell with a reference to an a and a reference to another list cell.

The main tool to work with mutable branches is to use the MutBranch data type, from Data.Mutable.Branches, which specifies which "branch" on mutable sum type to work with. In the case of IntOrBool, it we might have a MutBranch s IntOrBool Int for the Int case and a MutBranch s IntOrBool Bool for the Bool case. In the case of List, since it has a Generic instance, we can use constrMB to create a MutBranch based on the constructor name.

nilBranch
    :: Mutable s a
    => MutBranch s (List a) ()
nilBranch = constrMB #_Nil

consBranch
    :: Mutable s a
    => MutBranch s (List a) (a, List a)
consBranch = constrMB #_Cons

nilBranch represents the Nil constructor (containing nothing, ()), and consBranch represents the Cons constructor (containing a mutable (a, List a)).

Note that due to limitations in OverloadedLabels, we're required to add that underscore before the constructor name. (If your constructor is an operator, you'd have to do something like constrMB (CLabel @":")).

The simplest way to use a MutBranch is to check if a reference is currently on that branch, with hasBranch:

-- | Check if a mutable linked list is currently empty
isEmpty
    :: (Mutable s a, PrimMonad m, PrimState m ~ s)
    => Ref s (List a)
    -> m Bool
isEmpty = hasBranch nilBranch

Using the API of Data.Mutable.Branches, we can write a function to "pop" a mutable linked list, giving us the first value and shifting the rest of the list up.

popStack
    :: (Mutable s a, PrimMonad m, PrimState m ~ s)
    => Ref s (List a)
    -> m (Maybe a)
popStack xs = do
    c <- projectBranch consBranch xs
    forM c $ \(y, ys) -> do
      o <- freezeRef y
      moveRef xs ys
      pure o

And here is a function to concatenate a second linked list to the end of a first one.

concatLists
    :: (Mutable s a, PrimMonad m, PrimState m ~ s)
    => Ref s (List a)
    -> Ref s (List a)
    -> m ()
concatLists l1 l2 = do
    c <- projectBranch consBranch l1
    case c of
      Nothing      -> moveRef l1 l2
      Just (_, xs) -> concatLists xs l2

The main benefit of using this library --- with GRef and MutBranch, are a set of automatically generated type-safe tools for dealing with mutable options.