How to model a mutable key/value map in a monad transformer stack?

Question

This is a bit of a design question.

I currently have an "App" class which is a monad transformer stack, and what I want to add to that stack is a mutable Key/Value store.

Exactly how that store is implemented I want to be able to easily change. Initially I want it to be just an in memory Map, but later on I'll probably change it to be some database based thing.

The first thing that jumped to mind was just to add a StateT to my monad transformer stack. That works fine for an in memory Map, but I don't think this will work for a database implementation, as I don't want to get/update the entire state each time, but just one key/value combination.

The second thought was writing my own monad transformer. But when I looked at existing transformers, they all have classes with instances with all other monad transformers so they work with others. I think adding my own monad transformer and allowing it to interact nicely with all other transformers would involve writing n (or maybe 2 * n instances actually) so it can poke through other transformers and other transformers can poke through it. Technically I'll only have to do this with the transformers I'm using, but that seems a bit hacky. There's probably another argument here about whether monad transformer stack is a good idea at all, but I'd rather not completely change my App architecture at this point.

So my third idea was to have a ReaderT with a record of functions (or maybe a record with a typeclass constraint like data Blah where Blah :: c => Blah) that I can replace. This I think I could get to work, but I'm not sure it's the best approach, I'd have to layer a ReaderT on top of a StateT for the in memory approach I think.

As a I guess fourth approach, I did write out a bunch of typeclasses like so:

data HadKey = KeyFound | KeyNotFound

class Monad m => LookupMapM key value m where
  lookupM :: key -> m (Maybe value)

class LookupMapM key value m => InsertMapM key value m where
  insertM :: key -> value -> m HadKey

class InsertMapM key value m => UpdateMapM key value m where
  updateM :: key -> value -> m HadKey

Which I then started implementing interfaces, like so:

instance LookupMapM key value (StateT (Map key value) m) where ...

instance (...) => LookupMapM key value IO where ...

This seemed promising, but then the second instance seems problematic... like, I can only have one IO implementation (presumably different databases should be able to have their own implementation).

I guess I could work around the above with the package tagged identity, so I could tag different implementations.

I note I'll then still need to lift my "map" transformer if it's not at the top of the stack, but that's not a big issue, I could just maintain a liftKV function that just needs an extra lift every time a layer is added to the monad transformer stack, and I don't think that's a big deal.

But maybe there's a better way of doing this than the ways I've suggested? Or maybe one of the ways I've suggested is the best way, I'm just not sure which one.

By other thought here was instead of having:

class Monad m => LookupMapM key value m where
  lookupM :: key -> m (Maybe value)

going with this style:

class Monad m => LookupMapM t m where
  type Key t
  type Value t
  lookupM :: Key t -> m (Maybe (Value t))

But I'm not sure if this solves anything or just adds extra complication for no benefit.

Any thoughts?

Answer 1

You are going to have to put IO at the bottom of your stack. Above that you will need a ReaderT with the database connection information and functions to access the database through it. Then put whatever else you need on top of that.

For an example of this kind of thing, see the Render monad in the Cairo library. It's storing a render context instead of a database connection, but the concept is the same.

Answer 2

I'd go with your custom transformer idea. Yes, you need n instances, but you can have the compiler write them for you with minimal expenditure of actual brain power -- all but the MonadState instance, since presumably you don't want to expose the fact that this happens to be implemented with StateT!

newtype KVT k v m a = KVT { runKVT :: StateT (Map k v) m a }
    deriving (Functor, Applicative, Monad) via StateT (Map k v) m
    deriving MonadTrans via StateT (Map k v)
deriving via StateT (Map k v) m instance MonadReader r m => MonadReader r (KVT k v m)
deriving via StateT (Map k v) m instance MonadWriter w m => MonadWriter w (KVT k v m)
-- etc.

instance MonadState s m => MonadState s (KVT m) where state = lift . state

I think you had the right idea with your classes, but I would make it just one class until you know for sure you need something more intense. More on the "just one instance" problem later.

class Monad m => KV k v m | m -> k v where
    lookupM :: k -> m (Maybe v)
    insertM :: k -> v -> m HadKey
    updateM :: k -> v -> m HadKey

instance Monad m => KV k v (KVT k v) where
    lookupM = KVT . gets . lookup
    insertM k = {- exercise for the reader -}
    updateM k = {- ditto -}

Again you can derive all the necessary instances, though you'll need one extra trick. This (ViaLift) may be available in a library somewhere; I haven't looked.

newtype ViaLift t m a = ViaLift (t m a)
    deriving MonadTrans via t

instance (MonadTrans t, KV k v m) => KV k v (ViaLift t m) where
    lookupM   = ViaLift . lift . lookupM
    insertM k = ViaLift . lift . insertM k
    updateM k = ViaLift . lift . updateM k

deriving via ViaLift (ReaderT r) m instance KV k v (ReaderT r m)
deriving via ViaLift (WriterT w) m instance KV k v (WriterT w m)
-- etc.

(By the way, I think these instances obviate the need for your proposed liftKV. But I'm not sure; I don't know what problem you were anticipating there.)

Now, on the "just one instance" problem. I see a few different regimes you could be living in.

1. You want to be able to swap out the implementation without users even knowing. Then it's okay that there's just one instance possible. You just hide everything behind the module boundary and swap out the one implementation for the other.
2. You want the user to be able to choose between multiple implementations statically. Make separate modules for each implementation, with a new type in each -- possibly even named the same thing in all modules.
3. You want the user to be able to choose between multiple implementations dynamically. Then it's okay that there's just one instance possible; the plan will be to make a type that holds whatever information it needs to hold to know which implementation it's going to use, and that one type is the one that has the instance.