Basically reprint from https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State and https://hackage.haskell.org/package/transformers-0.5.2.0/docs/Control-Monad-Trans-State-Lazy.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import Control.Monad
import System.Random
import Control.Monad.Trans.State.Lazy
import qualified Data.Map.Strict as M

-- pseudo-random generator
roll_dice_io :: IO (Int, Int)
roll_dice_io = liftM2 (,) (randomRIO (1,6)) (randomRIO (1,6))

roll_n_dice_io :: Int -> IO [Int]
roll_n_dice_io n = replicateM n $ randomRIO (1,6)

seed :: Int -> StdGen
seed = mkStdGen 

roll_die :: State StdGen Int
roll_die = state $ randomR (1,6)

roll_dice :: State StdGen (Int, Int)
roll_dice = liftM2 (,) roll_die roll_die

roll_n_dice :: Int -> State StdGen [Int]
roll_n_dice n = replicateM n $ roll_die
  
-- counting
tick :: State Int ()
tick = do
  n <- get
  put $ n+1
  return ()

plus_one :: Int -> Int
plus_one seed = execState tick seed

plus_n :: Int -> Int -> Int
plus_n seed n = execState (replicateM n tick) seed

-- labelling tree
data Tree a = Nil
  | Node a (Tree a) (Tree a)
  deriving (Eq, Show)

type Table a = M.Map a Int

number_tree :: (Ord a, Eq a) => Tree a -> State (Table a) (Tree Int)
number_tree Nil = return Nil
number_tree (Node x t1 t2) = do
  num <- number_node x
  nt1 <- number_tree t1
  nt2 <- number_tree t2
  return $ Node num nt1 nt2
  where
    number_node :: (Ord a, Eq a) => a -> State (Table a) Int
    number_node x = do
      table <- get
      case M.lookup x table of
        Just index -> return index
        Nothing ->
          let
            size = M.size table
            table' = M.insert x size table
          in
            put table' >> return size

convert_tree :: (Ord a, Eq a) => Tree a -> Tree Int
convert_tree t = evalState (number_tree t) M.empty

test_tree = Node "Zero" (Node "One" (Node "Two" Nil Nil)
                         (Node "One" (Node "Zero" Nil Nil) Nil))
                       Nil
main :: IO ()
main = do
  roll_dice_io >>= print
  roll_n_dice_io 5 >>= print
  print $ evalState roll_die (seed 0)
  print $ evalState roll_dice (seed 0)
  print $ evalState (roll_n_dice 10) $ seed 0

  print $ plus_one 3
  print $ plus_n 2 7

  print $ convert_tree test_tree