If you are reading this, you are probably aware that the blogosphere is littered with HMTs. The progression usually goes like this:
A programmer...
- undertakes to learn Haskell,
- struggles for some period of time with understanding Monads,
- suddenly has that "ah-ha" moment, and
- writes a tutorial (convinced that they can finally explain it to the beginner better than anyone else who has gone before could).
I...
- took it upon myself to learn Haskell
- struggled with Monads for some time
- kind of slowly and grudgingly eventually "got" monads, but not with any kind of dramatic "eureka!", more like a "oh... right... ok" kind of feeling (which was remarkably anti-climactic considering how much hair I'd pulled out over this), and
- am writing not so much a tutorial as a: "Here's what I did to understand it. Hope it helps."
If this helps you, great. I wrote this to help me, and it served that purpose. It's called "learn by doing" (practical, rather than theoretical). I therefore must also suggest that you try this yourself, rather than just expect to get it by reading this. I'm willing to concede that there are probably serious problems with these definitions, given that I am not a schooled Haskell programmer, and don't know a lot about the conventions that serious people follow.
I'd like to start by throwing down a few references which were helpful to me in my understanding:
- Brian Beckman: Don't Fear the Monads (video)
- Greg Meredith: Intro to Monads (video)
- Learn You a Haskell for Great Good (best "book" for beginners)
- James Iry's blog: One Div Zero
The two examples I implemented: the identity monad (the simplest of all!), and the state monad (because I really wanted to understand this for a project that I'm working on). Implementing the identity monad really helped me, because it's just so simple, yet has all the necessary properties of a "real" monad. State was far more difficult, mainly because of the fact that the monad wraps a function, rather than a value (although we know that these are the same thing in Haskell!), but once I cracked this, it really did "all make sense."
The Identity Monad
First, we need a type and type constructor (by Haskell convention I will use the same expression for both, which for this example is "Id").
newtype Id a = Id a deriving Show
Note: the "deriving Show" bit is there just in case I want to print these to the console. It could have just been:
Then I'm going to need a function to extract the value from the "Id" thingy:
runId :: Id a -> a
runId (Id x) = x
Simple enough, so far?
Note: this could also have been acheived using Haskell's "record syntax" as follows (saving the trouble of writing the extra function):
newtype Id a = Id { runId :: a } deriving Show
Now, the Monad bit. Don't blink, or you might miss it!
instance Monad Id where
return a = Id a
m >>= f = f (runId m)
Identity monad... done!
I'm not going to explain this in any great detail. You've probably read about "return" and "bind (>>=)" elsewhere. In bind: "m" is the monadic value, "f" is a function (a -> mb) and the bit on the right of the equals just says "run f on the value inside of m."
Some functions that operate on Id thingies:
idPlusBar :: Id String -> Id String
idPlusBar x = do
y <- x
z <- Id (y ++ "bar")
return z
This function operates on Id Strings appends "bar" to the value.
Note: the function above could be written more simply as:
idPlusBar x = Id $ (runId x) ++ "bar"
but I included it in long form for illustration purposes.
Here are a couple that operate on Id Ints:
idPlusTwo :: Id Int -> Id Int
idPlusTwo x = Id $ (runId x) + 2
idTimesThree :: Id Int -> Id Int
idTimesThree x = Id $ (runId x) * 3
idComposed :: Id Int -> Id Int
idComposed = idPlusTwo . idTimesThree
Now, here's a function ("main" in this case, as I can run this from the command line), which uses HUnit (you'll need to "import Test.HUnit") to test some assumptions:
main = do
putStrLn "running tests"
-- Id String tests
let x = Id "foo"
let test1 = TestCase $ assertEqual "String foo" "foo" $ runId x
let test2 = TestCase $ assertEqual "String foobar" "foobar" $ runId $ idPlusBar x
-- Id Int tests
let y = Id 3 :: Id Int
let test3 = TestCase $ assertEqual "Int 3" 3 $ runId y
let test4 = TestCase $ assertEqual "Int 5" 5 $ runId $ idPlusTwo y
let test5 = TestCase $ assertEqual "Int 11" 11 $ runId $ idComposed y
-- run tests
let tests = TestList [ TestLabel "foo" test1
,TestLabel "foobar" test2
,TestLabel "int 3" test3
,TestLabel "int 5" test4
,TestLabel "int + *" test5
]
runTestTT tests
So far, none of this is too challenging. You may have noticed that there's absolutely no point to any of it, however. That's OK! The idea was just to get used to wrapping stuff up and operating on it. The first version of "idPlusBar" is interesting because it illustrates how things work in "do-notation."
If you've got this monad loaded up into ghci, you can see this, too:
*Main> let x = Id "foo"
*Main> x
Id "foo"
*Main> idPlusBar x
Id "foobar"
*Main> let f x = x >>= \a -> Id (a ++ "bar")
*Main> f x
Id "foobar"
where "f" doesn't use "do", but rather "bind" directly.
Now, if you're still with me, we shall leave the tidy, simple world of identity, and enter the mysterious wonderment that is "state."
The first part of this excercise involved coming up with a super simple case where I needed to have a state parameter of some kind and a bunch of functions that depended on it. I elected to make the State an "Int" and the value the functions operate on a List of Ints. The key is that in order to be sequenced correctly the state would have to be passed from one function to the next. The functions use the state int to transform the lists, and to add complication (and make it easy to prove it's working properly) I will increment the state with each function that gets executed.
As you probably know, you can do it by "threading the state" and not using monads at all. Let's try that first:
addS :: Int -> [Int] -> [Int]
addS s xs = map (+ s) xs
timesSminus1 :: Int -> [Int] -> [Int]
timesSminus1 s xs = map (* (s-1)) xs
addStimes2 :: Int -> [Int] -> [Int]
addStimes2 s xs = map (+ (s*2)) xs
where s::Int is the 'state' and the list is the thing to be transformed
Now we can sequence these functions, and "manually" increment the state:
allS :: Int -> [Int] -> [Int]
allS s xs = let as = addS s xs;
s' = s+1;
as' = timesSminus1 s' as;
s'' = s'+1;
in addStimes2 s'' as'
It's already easy to see, even with this simple example, that this has the potential to become quite cumbersome. It's also obvious that the incrementing of the state is going to get awfully repetitive and should be abstracted in some way.
Enter the state monad...
type S = Int
newtype St s a = St { runState :: S -> (S, a) }
instance Monad (St s) where
return value = St $ \state -> (state, value)
monadSt >>= func = St $ \state->let (state', value) = runState monadSt state
in runState (func value) (state'+1)
Note: this is not a generic state monad, but one which works exclusively on Ints and increments the state with each function execution (in "bind").
Here are our functions again, using the monad:
addS' :: [Int] -> St Int [Int]
addS' xs = St $ \state -> (state,map (+ state) xs)
timesSminus1' :: [Int] -> St Int [Int]
timesSminus1' xs = St $ \state -> (state,map (* (state-1)) xs)
addStimes2' :: [Int] -> St Int [Int]
addStimes2' xs = St $ \state -> (state,map (+ (state*2)) xs)
allS' :: [Int] -> St Int [Int]
allS' xs = do
as <- addS' xs
as' <- timesSminus1' as
as'' <- addStimes2' as'
return as''
The last function in particular is quite clean compared to its non-monadic cousin.
Once again, we'll use HUnit to test some assumptions...
main = do
putStrLn "running tests"
-- set up some values to use
let xs = [1,2,3]
let state1 = 3
let state2 = 4
let state3 = 5
-- threading state tests
let test1 = TestCase $ assertEqual "increment by s" [4,5,6] $ addS state1 xs
let test2 = TestCase $ assertEqual "times (s-1)" [3,6,9] $ timesSminus1 state2 xs
let test3 = TestCase $ assertEqual "increment by s*2" [11,12,13] $ addStimes2 state3 xs
-- put it together in allS
let test4 = TestCase $ assertEqual "the lot" [22,25,28] $ allS state1 xs
-- state monad tests
let test1' = TestCase $ assertEqual "m increment by s" [4,5,6] $ snd $ (runState $ addS' xs) state1
let test2' = TestCase $ assertEqual "m times (s-1)" [3,6,9] $ snd $ (runState $ timesSminus1' xs) state2
let test3' = TestCase $ assertEqual "m increment by s*2" [11,12,13] $ snd $ (runState $ addStimes2' xs) state3
-- monadic state passing in allS'
let test4' = TestCase $ assertEqual "m the lot" [22,25,28] $ snd $ (runState $ allS' xs) state1
-- run tests
let tests = TestList [ TestLabel "test1" test1
,TestLabel "test2" test2
,TestLabel "test3" test3
,TestLabel "test4" test4
,TestLabel "m test1'" test1'
,TestLabel "m test2'" test2'
,TestLabel "m test3'" test3'
,TestLabel "m test4'" test4'
]
runTestTT tests
The real eye-opening thing here is that allS' doesn't take a state parameter at all. That's because allS' is returning a state monad (a function from state to state,value). So, we pass the state to the function (or value) which is returned by this function. This is the trick... and it is a little bit like magic!
So,
allS' takes the list ("xs") and returns the monad. runState extracts the function from the monad (\s -> (s,a)), and we pass the initial state to that. That in turn returns the state,value pair, so we take the "snd" value of the tuple.
This is it again:
snd $ (runState $ allS' xs) state1
Nice, huh?
So, our function doesn't have to mess around with state at all. It's all handled in the monad's bind function, including the incrementing of the state's value with each function call.
Once again, I would just add that the most striking thing in all this is its simplicity (a trait I've come to expect from Haskell). It seems that monads weren't that complicated after all.
Now, what are these Monad Transformer things?
I'd like to point out that there's a significant difference between these, as far as monads go:
ReplyDeletedata Id a = Id a
newtype Id a = Id a
In particular, with one of them, "undefined >> return 5" explodes at runtime. With the other, it does not.
Understanding which has which behavior, and why, is an important part of understanding evaluation in Haskell.
The title should be: "Ceci n'est pas un Haskell monad totorial"
ReplyDelete