How does this state code work?

Question

This code is from this article.

I was able to follow him to this part.

module Test where

type State = Int

data ST a = S (State -> (a, State))

apply        :: ST a -> State -> (a,State)
apply (S f) x = f x

fresh =  S (\n -> (n, n+1))

instance Monad ST where
    -- return :: a -> ST a
    return x   = S (\s -> (x,s))

    -- (>>=)  :: ST a -> (a -> ST b) -> ST b
    st >>= f   = S (\s -> let (x,s') = apply st s in apply (f x) s')

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


mlabel  :: Tree a -> ST (Tree (a,Int))
-- THIS IS THE PART I DON'T UNDERSTAND:
mlabel (Leaf x) = do n <- fresh
                     return (Leaf (x,n))
mlabel (Node l r) =  do l' <- mlabel l
                        r' <- mlabel r
                        return (Node l' r')

label t = fst (apply (mlabel t) 0)

tree = Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c')

And label treeproduces:

Node (Node (Leaf ('a',0)) (Leaf ('b',1))) (Leaf ('c',2))

I see that the operator >>=is a tool for a "chain" of functions that return monads (or something like that).

And although I think I understand this code, I do not understand how this particular code works.

In particular do n <- fresh. We didn't pass any arguments fresh, right? What produces n <- freshin this case? I absolutely do not understand this. Maybe this has something to do with curry?

Answer 1

With a monolithic "pipeline" insert, your code becomes

fresh state = (state, state + 1)

mlabel (Leaf x) state =                   --  do
  let (n, state') = fresh state           --    n <- fresh
  in  (Leaf (x,n), state')                --    return (Leaf (x,n))

mlabel (Node l r) state =                 -- do
  let (l', state') = mlabel l state       --    l' <- mlabel l
  in let (r', state'') = mlabel r state'  --    r' <- mlabel r
     in  (Node l' r', state'')            --    return (Node l' r') 

main = let (result, state') = mlabel tree 0  
       in  print result                         

{- Or with arrows,

mlabel (Leaf x)   = Leaf . (x ,)  &&&  (+ 1)
mlabel (Node l r) = mlabel l >>> second (mlabel r)
                              >>> (\(a,(b,c)) -> (Node a b,c))
main              = mlabel tree >>> fst >>> print  $ 0
-}

Or in an imperative pseudo-code:

def state = unassigned

def fresh ():
    tmp = state 
    state := state + 1     -- `fresh` alters the global var `state`
    return tmp             -- each time it is called

def mlabel (Leaf x):       -- a language with pattern matching
    n = fresh ()           -- global `state` is altered!
    return (Leaf (x,n))  

def mlabel (Node l r):
    l' = mlabel l          -- affects the global
    r' = mlabel r          --    assignable variable
    return (Node l' r')    --    `state`

def main:
    state := 0             -- set to 0 before the calculation!
    result = mlabel tree
    print result

result state; snd Haskell (a, State). fst - , .

.

, , catch " ". : " ", , , , , .

, ( , , Prolog), , . "" , , , , (, , ...).

, , , . .

Answer 2

, n < - fresh. , ?

. , fresh, , , - apply (mlabel someTree) 5. , , , - mlabel (>>=) do-notation, (>>=) return , Monad .

Answer 3

The main thing is to understand that notation dotranslates into functions Monad, therefore

do n <- fresh
   return (Leaf (x,n))

not suitable for

fresh >>= (\n -> 
           return (Leaf (x,n))  )

and

do l' <- mlabel l
   r' <- mlabel r
   return (Node l' r')

not suitable for

mlabel l >>= (\l' -> 
              mlabel r >>= (\r' ->
                            return (Node l' r') ))

This will hopefully allow you to continue defining the meaning of the code, but for more help you should read the notation dofor Monads.