UserPreferences

StateMonad


State Monads

The state monad hides state from us (if it needs to be passed as an extra parameter).

if we were to transform a tree so that each of the leaves were numbered

 > data Tree a = Leaf a | Branch (Tree a) (Tree a)
we could either write
 > number :: Int -> Tree a -> (Tree (a,Int) , Int)
 > number seed (Leaf a) = (Leaf (a,seed),seed + 1)
 > number seed (Branch left right)
 >  = let (left',lseed) = number seed left
 >        (right',rseed) = number lseed right
 >    in
 >        (Branch left' right', rseed)
or we could encapsulate the whole shabang in a state monad
 > numberST :: Tree a -> ST (Tree (a,Int) )
 > numberST (Leaf a) = do
 >                         next <- getNext
 >                         return Leaf (a,next)
 > 
 > numberST (Branch l r) = do
 >                            left <- numberST l
 >                            right <- numberST r
 >                            return (Branch left right)
-- ChrisAngus

Control.Monad.State

The base libraries for GHC provide such a construct, see the [WWW]documentation for Control.Monad.State.

A function to increment a counter. Taken from the paper Generalising Monads to Arrows, John Hughes (http://www.math.chalmers.se/~rjmh/), November 1998.

> tick :: State Int Int
> tick = do n <- get
>           put (n+1)
>           return n
Add one to the given number using the state monad.
> plusOne :: Int -> Int
> plusOne n = execState tick n
A contrived addition example. Works only with positive numbers.
> plus :: Int -> Int -> Int
> plus n x = execState (sequence $ replicate n tick) x

An example from The Craft of Functional Programming, Simon Thompson (http://www.cs.ukc.ac.uk/people/staff/sjt/), Addison-wesley 1999: \"Given an arbitrary tree, transform it to a tree of integers in which the original elements are replaced by natural numbers, starting from 0. The same element has to be replaced by the same number at every occurrence, and when we meet an as-yet-unvisited element we have to find a 'new' number to match it with."

> data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
> type Table a = [a]
> testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil

> numTree :: (Eq a) => Tree a -> Tree Int
> numTree t = evalState (numberTree t) []
>
> numberTree :: Eq a => Tree a -> State (Table a) (Tree Int)
> numberTree Nil = return Nil
> numberTree (Node x t1 t2) 
>     =  do num <- numberNode x
>           nt1 <- numberTree t1
>           nt2 <- numberTree t2
>           return (Node num nt1 nt2)
>     where
>     numberNode :: Eq a => a -> State (Table a) Int
>     numberNode x
>       = do table <- get
>            (newTable, newPos) <- return (nNode x table)
>            put newTable
>            return newPos
>     nNode::  (Eq a) => a -> Table a -> (Table a, Int)
>     nNode x table
>       = case (findIndexInList (== x) table) of
>         Nothing -> (table ++ [x], length table)
>         Just i  -> (table, i)
>     findIndexInList :: (a -> Bool) -> [a] -> Maybe Int
>     findIndexInList = findIndexInListHelp 0
>     findIndexInListHelp _ _ [] = Nothing
>     findIndexInListHelp count f (h:t)
>        = if (f h)
>          then Just count
>          else findIndexInListHelp (count+1) f t

So for example:

numTree testTree => Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil


There is also a construct in Control.Monad.State for encapsulating one monad inside a State monad, its called StateT. In this example by MarkCarroll, the IO state is nested inside a state monad that carries information about our computation:

> module NestedMonad where

> import Control.Monad.State
> import Data.List
                                                                                               
> get_length :: String -> IO Int
                                                                                               
> get_length name =
>     do contents <- readFile name
>        return (length (lines contents))
                                                                                               
> update_best_with :: (String, Int) -> StateT (String, Int) IO ()
                                                                                               
> update_best_with (current_name, current_count) =
>     do (best_name, best_count) <- get
>        if current_count > best_count
>           then put (current_name, current_count)
>           else return ()
                                                                                               
> do_next :: String -> StateT (String, Int) IO ()
                                                                                               
> do_next name =
>     do count <- lift $ get_length name
>        update_best_with (name, count)
                                                                                               
> longest_file :: [String] -> IO (String, Int)
                                                                                               
> longest_file names =
>     execStateT (sequence_ (map do_next names)) ("none", 0)

> main = do (name, count) <- longest_file ["/etc/hostname", "/etc/ntp.conf", "/etc/timezone"]
>           putStrLn ("Longest file is " ++ name ++ " which is " ++ show count ++ " lines long")

Note: Perhaps this can be added to the StateT documentation? Does anyone have a better example? Is there a better way to describe the standardness of the Control.Monad.State module?

-- IsaacJones


CategoryMonad