{-# LANGUAGE UnicodeSyntax #-}
module StateData where



data State s a = State {runState ∷ s → (a,s)}

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Show

labelTree ∷ Tree a → Tree Int
labelTree t = fst $ runState (labelTreeW t) 0 -- evalState = fst . runState

labelTreeW ∷ Tree a → State Int (Tree Int)
labelTreeW Leaf = return Leaf
labelTreeW (Node l _ r) =
	labelTreeW l       >>= \l'       →
	get                >>= \counterN →
	put (counterN + 1) >>= \_        →
	labelTreeW r       >>= \r'       →
	return $ Node l' counterN r'

get ∷ State s s
get = State $ \s → (s,s)

put ∷ s → State s ()
put s = State $ \_ → ((),s)

(>>-) ∷ State s a → (a → State s b) → State s b
State f >>- g = State $ \s → let (fs, s) = f s in runState (g fs) s

instance Monad (State s) where
	return v = State $ \s → (v,s)
	(>>=) = (>>-)