{"id":292,"date":"2007-01-29T08:00:01","date_gmt":"2007-01-29T08:00:01","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/01\/29\/more-monads-stateful-programming\/"},"modified":"2007-01-29T08:00:01","modified_gmt":"2007-01-29T08:00:01","slug":"more-monads-stateful-programming","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/01\/29\/more-monads-stateful-programming\/","title":{"rendered":"More Monads: Stateful Programming"},"content":{"rendered":"

Time for more monads. In this article, I’m going to show you how to implement a very simple
\nstate monad<\/em> – it’s a trivial monad which allows you to use a mutable state
\nconsisting of a single integer. Then we’ll expand it to allow a more interesting
\nnotion of state.<\/p>\n

<\/p>\n

Let’s get the trivial stuff out of the way. To start off, we’ll use a simple fixed
\nstate type which is just a wrapper for a single integer<\/p>\n

\n>data State = State Int deriving (Show)\n<\/pre>\n
 A monad over that would be written:<\/p>\n
\n>data SimpleStateMonad a = SSMon (State -> (a,State))\n<\/pre>\n
 To understand that, just remember that the monad is really a transition function<\/em> for
\nexecuting a sequence of computations that use a state. In fact, we’ll describe the sequence of steps
\nchained together that way as a single monad operation as a monadic sequence<\/em>. In a monadic sequence, each step of the computation is going to take the current state, do something with it, and return both a value and an updated state.<\/p>\n
 Given the monad type – the basic type of the step function for the sequences we want to build – the first thing that we need to do is implement the fundamental monadic operators. There are two of them: the sequencing operator (>>=)<\/code>, and the return<\/code> function that brings a non-monadic value into a monad.<\/p>\n
 We’ll implement the (>>=)<\/code> operator, which we’ll implement as a function named chain<\/em>:<\/p>\n
\n>chain :: (SimpleStateMonad a) -> (a -> SimpleStateMonad b)\n>          -> SimpleStateMonad b\n>chain (SSMon state) stepfun =\n>      SSMon (s -> let (carried, stateBefore) = state s\n>                       SSMon stateMonadAfter = stepfun carried\n>                   in stateMonadAfter stateBefore)\n<\/pre>\n
 The way that chain<\/code> works is crucial, and so we’ll take some time and tease it apart. Chain is a function that takes the result of the previous computation step of the sequence, and
\nchains it into the next step of the sequence. The way to understand the code is to look at the basic
\npieces, and how they’re put together:<\/p>\n
    \n
  •  The first binding of the let: (carried,stateBefore) = state s<\/code>. This looks
    \nmysterious – so we’ll take the time to look at it carefully. state<\/code> is the
    \nfunction inside of the monad that carries hidden monadic state and the result of the previous
    \nstep. So all we’re really doing here is unwrapping the results of the previous<\/em> step – extracting the state and the return values, and binding them to separate variables. carried<\/code> is the result of the previous step, and stateBefore<\/code> is the
    \nstate returned by the previous step – that is, the state before<\/em> we chain in
    \nthe next step of the monadic sequence.<\/li>\n
  •  The second binding of the let: SSMon stateMonadAfter = stepfun carried<\/code>. Again,
    \nit looks mysterious, but it’s really pretty simple. The monad is a step function – we’re
    \ncreating a step function from<\/em> the result of the previous step, so that we can
    \nuse that to run the next step. stepfun carried<\/code> is just a function which
    \npasses the state and return value of the first step into the second step of our
    \nchain.<\/li>\n
  •  The main expression of the let: stateMonadAfter stateBefore<\/code>. This just
    \nruns the step function we generated on the result of the previous step.<\/li>\n
  •  The λ wrapping the whole shebang: monads are a bit of a trap – you don’t
    \nget to get out of them without using a type-specific operation that isn’t part of the
    \nmonad class. The monadic chain operator needs to result in a monad value – the wrapping
    \nlambda expression just encapsulates the stepping sequence we’ve built into a monadic
    \nfunction wrapper.<\/li>\n<\/ul>\n
     Return is trivial, so we’ll just write it inline in the declaration of our monad type as an instance of the monad typeclass. The typeclass declaration looks like:<\/p>\n
    \n>instance Monad SimpleStateMonad where\n>    statemonad >>= statefun = chain statemonad statefun\n>    return nonMonadValue = SSMon (state -> (nonMonadValue, state))\n<\/pre>\n
     Nothing complicated there. The next thing we need to do is to write some functions usable
    \ninside<\/em> of a monadic computation to access and update the state hidden inside the
    \nmonad. Let’s start with retrieving the state value:<\/p>\n
    \n>getState :: SimpleStateMonad Int\n>getState = SSMon (s@(State i) -> (i,s))\n<\/pre>\n
     That’s it! It’s just a monadic step function that takes the value hidden in the state,
    \nand puts it into the “return value” slot of the monad result. So the monadic state is
    \nunmodified, and the result passed to the next state is the value that was wrapped up in the monad.<\/p>\n
     Updating is almost as easy:<\/p>\n
    \n>putState ::  (Int -> Int) -> SimpleStateMonad ()\n>putState updateFun =\n>     let stateUpdateFun = ((State i)  -> State (updateFun i))\n>     in SSMon (s -> ((), stateUpdateFun s))\n<\/pre>\n
     putState<\/code> takes a function that performs a modification of the state value. Since
    \nwe want people to treat the state as an integer, we do a little bit of wrapping, to translate an Int -> Int<\/code> function to a State -> State<\/code> function. The real meat is just
    \nexecuting the state update function to produce the new state value, and wrapping it up in a monad
    \nthat returns the unit value and the updated state.<\/p>\n
     Finally, we need a function that takes an initial state value, and a monadic sequence of operations, and executes the monadic sequence starting with the state value.<\/p>\n
    \n>runWithState :: Int -> SimpleStateMonad a ->  (a,State)\n>runWithState f (SSMon c) = c (State f)\n<\/pre>\n
     And voila! We have a state monad. Let’s try a simple test of it. Here’s
    \na monadic sequence that plays with the state a bit.<\/p>\n
    \n>testState :: SimpleStateMonad Int\n>testState = do\n>\t           putState (3*)\n>\t           putState (1+)\n>\t           i \t           return (i+2)\n<\/pre>\n
     Running that in GHCI gives us:<\/p>\n
     *Main> runWithState 3 testState\n(12,State 10)\n*Main> runWithState 10 testState (33,State 31)\n*Main>\n<\/pre>\n
     I ran it twice, with different values for the initial state. The code takes whatever the initial
    \nstate is, multiplies it by three, and adds one. That’s the final value of the state. And then the do
    \nblock finishes with a value of the current state plus two. What’s actually returned at the end of the
    \ndo block is a pair of the return value of the last statement in the block, and the final state. As  you can see, it does exactly the right thing. It looks almost like a piece of imperative code,
    \nexcept that the “assignment” operator, putState<\/code> takes a function on the current
    \nvalue of the state instead of just a new value.<\/p>\n
     So, now we’ve seen the basic method that we can use t make a monad that can encapsulate a kind of
    \nstate. But so far, it’s a pretty trivial kind of state: how much good is one integer? Suppose we
    \nwanted something more than that. In fact, suppose we wanted an arbitrary set of named variables
    \nencapsulated in a state. We do almost the same thing as the simple state monad; we just use a more
    \ncomplicated value inside the monad, and a different set of functions for working with the value in
    \nthe state. We’ll start by just building a trivial non-monadic<\/em> implementation of a name\/value
    \nlist.<\/p>\n
    \n>type NameValueMap = [(String,Int)]\n>\n>getValueFromList :: NameValueMap -> String -> Int\n>getValueFromList ((n,v):rest) name\n>             | n == name = v\n>              otherwise = getValueFromList rest name\n>getValueFromList [] name = -1\n>\n>setValueInList :: NameValueMap -> String\n-> Int -> [(String,Int)]\n>setValueInList ((n,v):rest) name newval\n>          | n == name = ((n,newval):rest)\n>          | otherwise = ((n,v):(setValueInList rest name newval))\n>setValueInList [] name newval = [(name,newval)]\n<\/pre>\n
     Now, we’re going to wrap that as a monad. The declaration of the monad type
    \nand the chain and return functions are going to be essentially identical to the integer
    \nstate monad.<\/p>\n
    \n>data MapStateMonad a = MapMon (NameValueMap -> (a,NameValueMap))\n>\n>mchain :: (MapStateMonad a) ->\n>          (a -> MapStateMonad b) ->\n>          MapStateMonad b\n>mchain (MapMon state) stepfun =\n>        MapMon (s -> let (carried, stateBefore) = state s\n>                          MapMon stateMonadAfter = stepfun carried\n>                      in stateMonadAfter stateBefore)\n>\n>\n>instance Monad MapStateMonad where\n>    statemonad >>= statefun = mchain statemonad statefun\n>    return nonMonadValue =\n>            MapMon (state -> (nonMonadValue, state))\n<\/pre>\n
     Here’s where we do something a little bit different. Instead of having “getState” and “putState” functions for working on the state in the monad, we need operations that fit the new name-map state.<\/p>\n
    \n>getFromState :: String -> MapStateMonad Int\n>getFromState name =\n>      MapMon (statemap -> (getValueFromList statemap name,\n>                            statemap))\n>\n>setInState :: String -> Int -> MapStateMonad ()\n>setInState  name newval =\n>       MapMon (statemap ->\n>                   ((),\nsetValueInList statemap name newval))\n<\/pre>\n
     And, just as in the case of the simple integer state monad, we need a way of running a monadic sequence with a particular initial state. And while we’re at it, we’ll write a test sequence.<\/p>\n
    \n>runWithMapState :: NameValueMap ->\n>                   MapStateMonad a ->\n>                   (a,NameValueMap)\n>runWithMapState f (MapMon c) = c f\n>\n>testMapMonad = do\n>                  setInState \"x\" 3\n>                  setInState \"y\" 5\n>                  z                   x                   return (x*z)\n<\/pre>\n
     Now, aside from a bit of syntax, that<\/em> looks like an imperative program, doesn’t it? Except that we’ve implemented it in a pure functional way – using a hidden state parameter. That’s the basic idea of what we do with monads – they allow us to create mini-languages with different
    \nsemantics based on the idea of chaining things together into monadic sequences. We write most of the program in the general functional language; but when we need to, we have multiple custom languages at our disposal in the form of the monad system. We can easily use monads for IO, for imperative programming, for Prolog-style backtracking, for non-determinism… All there,  in Monads.<\/p>\n
     Next up, we’ll look at the theory of monads: what they are in category theory, and how that relates to  what we’ve seen in programming, and what rules are required by the monadic semantics to make a new monad work correctly.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Time for more monads. In this article, I’m going to show you how to implement a very simple state monad – it’s a trivial monad which allows you to use a mutable state consisting of a single integer. Then we’ll expand it to allow a more interesting notion of state.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[89],"tags":[],"class_list":["post-292","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4I","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/292","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=292"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/292\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=292"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=292"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=292"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}