Изменение значения листьев дерева к упорядоченной последовательности, сохраняя при этом структура

Question

дерева Учитывая это рекурсивная древовидную структуру

data Tree = Leaf Int | Node Tree Tree deriving Show 

Я хотел бы, чтобы нормализовать его таким образом, что сохраняет структуру дерева, но делает целые числа в листья последовательны в глубинах - первый порядок. Как я могу это достичь? Мой текущий код настройки выглядит следующим образом:

myTree = Node (Leaf 3) (Node (Leaf 5) (Leaf 2)) 

myTree' = normalize myTree 

-- preserve tree structure, but make Ints sequential in depths-first traversal 
normalize :: Tree -> Tree 
normalize = id -- todo: implement 

main = do 
    print myTree -- prints  : Node (Leaf 3) (Node (Leaf 5) (Leaf 2)) 
    print myTree' -- should print: Node (Leaf 1) (Node (Leaf 2) (Leaf 3)) 

Answer 1

Без использования монады, вы можете написать одно отображение функции деревьев проведения определенного состояния

mapLRS :: (s -> Int -> (s, Int)) -> s -> Tree -> (Tree, s) 
mapLRS f s (Leaf x ) = 
    let (s', x') = f s x 
    in (Leaf x', s')     -- the mapped leaf and the new state 
mapLRS f s (Node l r) = 
    let (l', s') = mapLRS f s l  -- the mapped left branch and the new state 
     (r', s'') = mapLRS f s' r  -- the mapped right branch and the new state 
    in (Node l' r', s'') 

Теперь

normalize :: Tree -> Tree 
normalize = fst . mapWithStateLeftRight (\s _ -> (s + 1, s)) 1 

Использование монады может быть более удобным для чтения (f не то же самое для простоты с использованием state)

import Control.Monad.State 

mapLRS :: (s -> (Int, s)) -> Tree -> State s Tree 
mapLRS f (Leaf x) = Leaf <$> state f 
mapLRS f (Node l r) = Node <$> mapLRS f l <*> mapLRS f r 

normalize :: Tree -> Tree 
normalize tree = evalState (mapLRS (\s -> (s, s + 1)) tree) 1 

Answer 2

Стандартный способ сделать это, чтобы записать текущую метку в государственной монаде:

import Control.Monad.State 

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

normalize :: Tree -> Tree 
normalize t = evalState (go t) 1 where 

    go :: Tree -> State Int Tree 
    go (Leaf _) = Leaf <$> (get <* modify (+1)) 
    go (Node l r) = Node <$> go l <*> go r 

Это решение инициализирует состояние в 1, затем обходит дерево и каждый встречается Leaf он помещает текущую метку в возвращаемом Leaf и увеличивает метку.

В качестве альтернативы, можно получить экземпляр Traversable для Tree:

{-# language DeriveFunctor, DeriveFoldable, DeriveTraversable #-} 

import Control.Monad.State 

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Show, Functor, Foldable, Traversable) 

normalize :: Tree a -> Tree Int 
normalize = (`evalState` 1) . traverse (\_ -> get <* modify (+1)) 

Это работает точно так же, но это к сведению, что она опирается на тот факт, что полученный Traversable экземпляр имеет правильный порядок обхода. Конечно, если бы мы захотели получить какой-то другой заказ, нам пришлось бы писать собственные обходы.