Thu Mar 21 14:35:29 JST 2013

Stateモナド、大体使い方分かったつもり StateTも大体同じみたいだし

import Control.Monad.State

data Tree = Nil | Node Int Tree Tree deriving Show

push_t tr n =
    case tr of
      Nil -> Node n Nil Nil
      Node m l r | n < m -> Node m (push_t l n) r
                 | True  -> Node m l (push_t r n)

pop_t tr =
    case tr of
      Node n Nil r
          -> (n , r)
      Node n (Node m Nil r2) r
          -> (m , Node n r2 r)
      Node n l r
          -> let (m, tr) = pop_t l in
               (m, Node n tr r)

push :: Int -> State Tree Int
push n = get >>= put.(\tr -> push_t tr n) >> return n

pop :: State Tree Int
pop = get >>= (\(n,tr) -> put tr >> return n).pop_t
*Main Control.Monad.State> runState (push 0) Nil
(0,Node 0 Nil Nil)
*Main Control.Monad.State> runState (push 0 >> push 1 >> push 2) Nil
(2,Node 0 Nil (Node 1 Nil (Node 2 Nil Nil)))
*Main Control.Monad.State> runState (push 0 >> push 1 >> push 2 >> pop) Nil
(0,Node 1 Nil (Node 2 Nil Nil))
*Main Control.Monad.State> runState (push 2 >> push 1 >> push 0 >> pop) Nil
(0,Node 2 (Node 1 Nil Nil) Nil)