Haskell наклеивает двоичное дерево через сквозной сквозной ход по глубине

Question

Мне нужно пометить двоичное дерево через обход первого порядка по глубине, и я подумал, что мне нужно сначала пройти через левые ветви дерева и назовите их, затем сделайте то же самое для правильных ветвей. Моя бинарное дерево хранит только значения на внутренних узлах (не конечных узлов/листьев):

label :: MonadState m Int => Tree a -> m (Tree (Int, a)) 
label (Branch l x r) = do n <- get 
          l' <- label l 
          r' <- label r 
          return (Branch l' (n, x) r') 
label (Leaf) = return Leaf 

* EDIT: Необходимо использовать государство Монадой однако я действительно не схватывая использование этого. Мой текущий код показан выше, но не работает должным образом.

EDIT: желаемый результат, например. для:

Branch (Branch Leaf (-2) Leaf) 1 Leaf 

должно быть:

Branch (Branch Leaf (0,-2) Leaf) (1,1) Leaf 

Кроме того, я не знаю, как я должен использовать государство Монада для него, я еще совсем запутался для его использования:

instance Monad (State' s) where 

    -- return :: a -> State' s a 
    return x = State' (\(s,c) -> (x, s, (c <> oneReturn))) 

    -- (>>=) :: State' s a -> (a -> State' s b) -> State' s b 
    st >>= k = State' $ \(s,c) -> let (a, s', c') = runState' st (s,c) 
            in runState' (k a) (s',(c' <> oneBind)) 

instance MonadState (State' s) s where 

    -- get :: State' s s 
    get = State' $ \(s,c) -> (s,s, (c <> oneGet)) 

    -- put :: s -> State' s() 
    put s = State' $ \(_,c) -> ((),s, (c <> onePut)) 

Answer 1

Вам не нужны функции label_l, label_r. Вам не нужны монады. (Вы можете использовать этот пример для изучения состояния монады, но вы не должны.)

Просто используйте (стандартный трюк) обогащая спецификации от

Tree a -> Tree (Int, a) 

в

f :: Int -> Tree a -> (Tree (Int a), Int) 

функция получает начальную метку (первый аргумент) и возвращает помеченное дерево и следующую метку для использования (во втором компоненте результата).

Е.Г.,

f 8 (Branch (Branch Leaf (-2) Leaf) 1 Leaf) 
    == (Branch (Branch Leaf (8,-2) Leaf) (9,1) Leaf), 10) 

Это может быть осуществлено легко, без каких-либо передовых концепций.

f s0 t = case t of 
    Branch l k r -> let (l', s1) = f s0 l 
         (r', s2) = f s1 r 
        in ... 

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

Answer 2

Один из способов структурирования вашей функции с государственной монадой:

label :: MonadState m Int => Tree a -> m (Tree (Int, a)) 
label t = do 
    -- Fetch the next label number from the state monad with "get". 
    -- Increase the label number by one and store it back in the state with "put". 
    -- Pattern match on "t" and call "label" recursively. 

Я предполагаю, что вы уже знакомы с do -syntax? Попробуйте написать указанную выше функцию, а затем обновите вопрос с помощью нового кода, если вам нужно больше советов.

Answer 3

Боюсь, что ваша проблема легче решить, чем предлагаемые ответы, если только вы видите, как использовать структуру, которую вы определяете, когда делаете определения типа. Вот как это происходит.

{-# LANGUAGE DeriveTraversable, FlexibleContexts #-} 

module LBT where 

import Control.Monad.State 

data Tree x 
    = Leaf 
    | Branch (Tree x) x (Tree x) 
    deriving (Functor, Foldable, Traversable) 

Это много делает traverse операцию работу влево-вправо, то есть в порядке, как вам требуется.

Теперь объясните, что делать с одним элементом.

next :: MonadState Int m => m Int 
next = do x <- get ; modify (+ 1) ; return x 

labelElt :: MonadState Int m => x -> m (Int, x) 
labelElt x = (,) <$> next <*> pure x 

next операция дает следующее значение и обновляет счетчик. Операция labelElt затем украшает одно значение своим счетчиком. А теперь

label :: MonadState Int m => Tree x -> m (Tree (Int, x)) 
label = traverse labelElt 

Вы получаете программу, которую вы уже заплатили, когда определили свой тип. Когда вы знаете, что делать с одним элементом, вы можете управлять всей структурой. Бесплатно. Здесь нет специальной рекурсии! Структура вашего типа обеспечивает структуру вашей программы. Хаскелл сделает это за вас, если вы позволите.