Как преобразовать тип данных в MonadState

Question

У меня есть эти типы:

data Tree a = Branch (Tree a) a (Tree a) | Leaf 
    deriving (Eq, Ord, Show) 

newtype State' s a = State' { runState' :: (s, Counts) -> (a, s, Counts) } 

С этих случаях:

instance Monad (State' s) 
instance MonadState (State' s) s 

И мне нужно сделать функцию

label :: MonadState m Int => Tree a -> m (Tree (Int, a)) 

Но Я не знаю, как я могу преобразовать дерево в State'.

Answer 1

Вам не нужно преобразовывать Tree в ваше состояние, для которого необходимо использовать значение состояния Int на каждом этапе процесса маркировки. Для этого, вы, вероятно, извлечь выгоду из чего-то вроде

getLabelAndIncr :: MonadState m Int => m Int 
getLabelAndIncr = do 
    current <- get 
    put $ current + 1 
    return current 

Тогда в вашей label функции вы можете сделать что-то вроде

label :: MonadState m Int => Tree a -> m (Tree (Int, a)) 
label Leaf = return Leaf 
label (Branch left node right) = do 
    l <- getLabelAndIncr 
    let newNode = (l, node) 
    newLeft <- ??? 
    newRight <- ??? 
    return $ Branch newLeft newNode newRight 

Вы должны выяснить, что происходит в ???, я не собираюсь решать все это для вас, но это должно быть довольно простое упражнение. Здесь происходит то, что getLabelAndIncr получает текущее значение метки для использования, а затем сохраняет это значение, увеличивающееся в состоянии. Затем создается новое значение узла, которое помечено этой меткой, левая и правая ветви получают свои теги, и возвращается новое дерево, которое теперь имеет метки. Тип состояния остается неизменным каждый раз, это фиксируется MonadState m Int, в котором говорится, что m - это монашеская монада, которая всегда имеет значение состояния, которое является Int.

Answer 2

Вы не должны преобразовать Tree в состояние, m (Tree (Int, a)) часть сигнатуры типа просто означает, что результат будет Tree, содержащие tupels из Int с и a с, которая сама находится внутри государственной монады. Это даже не должно быть монадой State'.