Как работает этот код монады State?

Со встроенной монадической «конвейерной обработкой» ваш код становится

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
-}

Или в императивном псевдокоде:

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 в кортеже (a, State) языка Haskell. А поле fst кортежа — это только что построенное дерево, несущее нумерацию вместе с данными в своих листьях.

Эти варианты функционально эквивалентны.

Возможно, вы слышали крылатую фразу о том, что монадическая привязка является "программируемой точкой с запятой". Здесь смысл его ясен: он определяет так сказать "протокол вызова функции", что мы используем первое возвращаемое значение как вычисляемый результат, а второе возвращаемое значение как обновленное состояние, которое мы передаем в следующий расчет , поэтому он увидит состояние updated.

Это стиль программирования с передачей состояния (важный, например, для Пролога), делающий изменение состояния явным, но вручную заботящийся о передаче правильного обновленного состояния. Монады позволяют нам абстрагировать эту «проводку» состояний, переходя от одного вычисления к другому, так что это делается автоматически за нас, ценой необходимости мыслить в императивном стиле и того, что это состояние снова становится скрытым, неявным (как изменение состояния подразумевается в императивном программировании, от которого мы хотели отказаться в первую очередь при переходе к функциональному программированию...).

Таким образом, все, что делает монада State, — это поддерживает для нас это скрытое состояние и передает его обновленным между последовательными вычислениями. Так что ничего важного в конце концов нет.

Конкретно делайте ‹- свежее. Мы не передали никаких аргументов свежему, верно?

Точно. Мы пишем для аргумента, который будет передаваться fresh, когда мы, например, делаем что-то вроде apply (mlabel someTree) 5. Хорошее упражнение, которое поможет вам более четко увидеть, что происходит, это сначала написать mlabel с явным (>>=) вместо do-нотации, а затем заменить (>>=) и return тем, что говорит экземпляр Monad.

Главное, что нужно понять, это то, что нотация do преобразуется в функции Monad, поэтому

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

сокращение от

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

и

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

сокращение от

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

Мы надеемся, что это позволит вам продолжить разбираться в значении кода, но для получения дополнительной помощи вам следует прочитать о нотации do для монад.