Blogging site
Type Families in Haskell is a large and complex topic with many applications. In this post, i am going to share with you an aspect of this technique which allows me to write more generalized functions and higher types; the general idea is to associate a type with the set of methods/functions in a type-class.
Before you read on, i assume you have some understanding of what type-classes are; if not then i strongly recommend you understand that before proceeding so that it would be more productive for you.
Let us assume a fictitious problem where i wish to define some functions for a
“Closet” and i want to say retrieve items and store items (i.e. shoes, presents
etc) to this closet. A way to model this is to define a type-class (i call it Closet)
and a few functionalities that allows me to get, put and start a new closet
(naturally, my home does not allow me to inject a closet at will ☺, but that’s
immaterial for now):
class Closet closet where
newClosetIO :: a -> IO (closet a)
getClosetIO :: closet a -> IO a
putClosetIO :: closet a -> a -> IO ()
The next natural thing to do is to start putting in the implementations and i want this closet to be safe from concurrent access (if you ever had to fight over precious items with a sibling, you’ll know what i’m referring to) and here’s how i might implement it.
import Control.Concurrent.MVar
instance Closet MVar where
newClosetIO = newMVar
getClosetIO = readMVar
putClosetIO closet a = modifyMVar_ closet (return . const a)
You don’t have to worry about what MVars actually are, for now, and to speak of it
briefly of them is that they are synchronization primitives which allows the
programmer to sequence actions in a safe manner in an concurrent environment
(i.e. where multiple threads are executing). Read more about MVars.
Next, let’s look at how this can be applied when i wish to store presents into
this closet & the algorithm in the function storeCloset leverages the functions
in the Closet type-class.
import Control.Monad (forM_)
-- i like to know who gave me the presents and what kind of present it is.
data Present = Present { donorName :: String, presentName :: String } deriving Show
storeCloset :: Closet closet => [Present] -> IO (closet [Present])
storeCloset xs = do
closet <- newClosetIO []
forM_ xs $ \x -> do
old <- getClosetIO closet
putClosetIO closet (x : old)
return closet
-- 'main' is the entrypoint to any haskell program, fyi.
main :: IO ()
main = do
let presents = [ Present{ donorName = "Tim" , presentName = "Toaster" },
Present{ donorName = "Tim" , presentName = "Ironing Board" },
Present{ donorName = "John", presentName = "Vase" }]
ys <- (storeCloset presents) :: IO (MVar [Present])
_ys <- readMVar ys
putStrLn . show $ _ys
return ()
This demonstrates that the program works fine and i am able to store and retrieve all the presents in the closet without troubles; the part where i have to help the haskell compiler is to hint to it which instance of the type-class did i wish to use.
There is, unfortunately, another problem and that is this implementation made
sure that i can operate only in the MVar. Honestly, there is absolutely nothing
wrong if you ever are going to operate in the MVar monad and it would be a
little clunky if i were to start providing more instances of the Closet
type-class to account for every scenario.
A way to mitigate this is to leverage Type Families once again, the benefits includes allowing us to not only extend the existing type class functionality, but also we can leverage it to make sure we are not always stuck in the IO monad and instead a Monad of our desire, for which the instance can cater to.
If you are curious as to what is meant by ”..not always stuck in the IO
Monad..”, then the solution is to generalise what used to be the IO monad and
represent it with a kind signature : * → * and in the code snippet i called it
ClosetMonad.
-- The following GHC extensions are needed
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
class Closet closet where
type ClosetMonad closet :: * -> *
new :: a -> (ClosetMonad closet) (closet a)
get :: closet a -> (ClosetMonad closet) a
put :: closet a -> a -> (ClosetMonad closet) ()
The key insight here is that ClosetMonad is now a type-family and that means we have
the ability of defining the environments we would operate in (e.g. IO, STM etc) and
the container preference (e.g. IORef, TVar). Below are the 2 type-instances of
the type-family just defined.
instance Closet IORef where
type ClosetMonad IORef = IO
new = newIORef
get = readIORef
put ioref a = modifyIORef ioref (const a)
instance Closet TVar where
type ClosetMonad TVar = STM
new = newTVar
get = readTVar
put ioref a = modifyTVar ioref (const a)
storeCloset :: (Closet closet, Monad (ClosetMonad closet)) => [Present] -> ClosetMonad closet (closet [Present])
storeCloset xs = do
closet <- new []
forM_ xs $ \x -> do
old <- get closet
put closet (x : old)
return closet
With this new approach, i can annotate the types (which the compiler will
resolve to their proper instances) and the program has greater extensibilities
since i can now extend beyond the type of the Closet but also the
side-effecting monad we can be operate in. To see what i mean, the code below
demonstrates both IO and STM scenarios.
main :: IO ()
main = do
let presents = [ Present{ giverName = "Tim", name = "Toaster" },
Present{ giverName = "Tim", name = "Ironing Board" },
Present{ giverName = "John", name = "Vase" }]
ys <- (storeCloset presents) :: IO (IORef [Present])
_ys <- readIORef ys
putStrLn . show $ _ys
ys <- atomically $ ((storeCloset presents) :: STM (TVar [Present]))
_ys <- readTVarIO ys
putStrLn . show $ _ys
return ()
This manner of writing generalised is just one aspect of what Type Families are capable of. What was interesting, for me, is that it allowed me another perspective or freedom to express generalised code beyond what a type-class might provide in its canonical form - maybe there are other forms of writing generalised code via type-classes which i am not aware of (Remind to self: to correct this observation when it chanced upon me). But so far, this looks really close to what i was looking for !
Coming back, there are a few resources written by many researchers over the years on the topic including Richard Eisenberg, Jan Stolarek, M Chakravarty and others; one of the papers i read is entitled Promoting Functions to Type Families in Haskell.
Hope you had enjoyed this post!
The complete listing is here:
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
import Control.Concurrent.STM
import Control.Concurrent.MVar
import Data.Foldable (forM_)
import Data.IORef
data Present = Present { donorName :: String, presentName :: String } deriving Show
class Closet closet where
type ClosetMonad closet :: * -> *
new :: a -> (ClosetMonad closet) (closet a)
get :: closet a -> (ClosetMonad closet) a
put :: closet a -> a -> (ClosetMonad closet) ()
instance Closet IORef where
type ClosetMonad IORef = IO
new = newIORef
get = readIORef
put ioref a = modifyIORef ioref (const a)
instance Closet TVar where
type ClosetMonad TVar = STM
new = newTVar
get = readTVar
put ioref a = modifyTVar ioref (const a)
storeCloset :: (Closet closet, Monad (ClosetMonad closet)) => [Present] -> ClosetMonad closet (closet [Present])
storeCloset xs = do
closet <- new []
forM_ xs $ \x -> do
old <- get closet
put closet (x : old)
return closet
main :: IO ()
main = do
let presents = [ Present{ donorName = "Tim" , presentName = "Toaster" },
Present{ donorName = "Tim" , presentName = "Ironing Board" },
Present{ donorName = "John", presentName = "Vase" }]
-- Here's how you can leverage IORef
ys <- (storeCloset presents) :: IO (IORef [Present])
_ys <- readIORef ys
putStrLn . show $ _ys
-- Here's how you can leverage Software Transactional Memory i.e. STM
ys <- atomically $ ((storeCloset presents) :: STM (TVar [Present]))
_ys <- readTVarIO ys
putStrLn . show $ _ys
return ()