Haskell - глубина для каждого узла в двоичном дереве, используя монаду Reader
Я написал следующий код. Это работает и использует Reader монада.
Не могли бы вы дать мне несколько советов о стиле кода в Haskell? В основном я имею в виду монады - я новичок.
import Control.Monad.Reader
data Tree a = Node a (Tree a) (Tree a)
| Empty
renumberM :: Tree a -> Reader Int (Tree Int)
renumberM (Node _ l r) = ask >>= (\x ->
return (Node x (runReader (local (+1) (renumberM l)) x)
(runReader (local (+1) (renumberM r)) x)))
renumberM Empty = return Empty
renumber'' :: Tree a -> Tree Int
renumber'' t = runReader (renumberM t) 0
2 ответа
Я хочу показать вам, что ваша идея является примером более общего понятия - молнии. Вот версия вашей программы, которая использует более простой и функциональный стиль.
Аппликативные функторы
Вот определение Applicative:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Вы могли бы сказать, что тип f x это структура f содержащий некоторые значения x, Функция <*> принимает структуру функций (f (a -> b)) и применяет его к структуре аргументов (f a) создать структуру результатов (f b).
Zippy Applicatives
Один из способов сделать Tree аппликативный функтор, делая <*> пройти через два дерева в замке шаг, объединяя их так же, как zip делает со списками. Каждый раз, когда вы сталкиваетесь с Node в дереве функций и Node в дереве аргументов вы можете вытащить функцию и применить ее к аргументу. Вы должны прекратить движение, когда достигнете нижней части любого из деревьев.
instance Applicative Tree where
pure x = let t = Node x t t in t
Empty <*> _ = Empty
_ <*> Empty = Empty
(Node f lf rf) <*> (Node x lx rx) = Node (f x) (lf <*> lx) (rf <*> rx)
instance Functor Tree where
fmap f x = pure f <*> x -- as usual
pure x генерирует бесконечное дерево x s. Это прекрасно работает, потому что Haskell - ленивый язык.
+-----x-----+
| |
+--x--+ +--x--+
| | | |
+-x-+ +-x-+ +-x-+ +-x-+
| | | | | | | |
etc
Итак, форма дерева t <*> pure x такой же, как форма t: вы прекращаете движение, только когда сталкиваетесь с Empty и нет ни одного в pure x, (То же самое относится к pure x <*> t.)
Это распространенный способ сделать структуру данных экземпляром Applicative, Например, стандартная библиотека включает ZipList, чья Applicative Экземпляр очень похож на экземпляр нашего дерева:
newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
pure x = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)
Снова, pure генерирует бесконечное ZipList, а также <*> потребляет свои аргументы в lock-step.
Прототип молниеносного Applicative, если хотите, является "читательским" Applicative. (->) r, который объединяет функции, применяя их все к фиксированному аргументу и собирая результаты. Итак все Representable функторы признают (по крайней мере) молнию Applicative пример.
Используя некоторые Applicative машины, мы можем обобщить прелюдии zip к любому аппликативному функтору (хотя он будет вести себя так же, как zip когда Applicative молния в природе - например, с регулярным Applicative экземпляр для []zipA даст вам декартово произведение своих аргументов).
zipA :: Applicative f => f a -> f b -> f (a, b)
zipA = liftA2 (,)
Маркировка как молнии
План состоит в том, чтобы сжать входное дерево вместе с бесконечным деревом, содержащим глубину каждого уровня. Результатом будет дерево с той же формой, что и у входного дерева (потому что дерево глубин бесконечно), но каждый узел будет помечен своей глубиной.
depths :: Tree Integer
depths = go 0
where go n = let t = go (n+1) in Node n t t
Это то, что depths похоже:
+-----0-----+
| |
+--1--+ +--1--+
| | | |
+-2-+ +-2-+ +-2-+ +-2-+
| | | | | | | |
etc
Теперь, когда мы настроили структуры, которые нам нужны, пометить дерево очень просто.
labelDepths :: Tree a -> Tree (Integer, a)
labelDepths = zipA depths
Повторная маркировка дерева путем отбрасывания оригинальных ярлыков, как вы изначально указали, также проста.
relabelDepths :: Tree a -> Tree Integer
relabelDepths t = t *> depths
Быстрый тест:
ghci> let myT = Node 'x' (Node 'y' (Node 'z' Empty Empty) (Node 'a' Empty Empty)) (Node 'b' Empty Empty)
ghci> labelDepths myT
Node (0,'x') (Node (1,'y') (Node (2,'z') Empty Empty) (Node (2,'a') Empty Empty)) (Node (1,'b') Empty Empty)
+--'x'-+ +--(0,'x')-+
| | labelDepths | |
+-'y'-+ 'b' ~~> +-(1,'y')-+ (1,'b')
| | | |
'z' 'a' (2,'z') (2,'a')
Вы можете придумать разные схемы маркировки, изменяя дерево, по которому вы движетесь. Вот тот, который говорит вам путь, который вы выбрали для достижения узла:
data Step = L | R
type Path = [Step]
paths :: Tree Path
paths = go []
where go path = Node path (go (path ++ [L])) (go (path ++ [R]))
+--------[ ]--------+
| |
+---[L]---+ +---[R]---+
| | | |
+-[L,L]-+ +-[L,R]-+ +-[R,L]-+ +-[R,R]-+
| | | | | | | |
etc
(Неэффективная вложенность вызовов в ++ выше может быть смягчено, используя списки различий.)
labelPath :: Tree a -> Tree (Path, a)
labelPath = zipA paths
Продолжая изучать Haskell, вы лучше поймете, когда программа является примером более глубокой концепции. Настройка общих структур, как я сделал с Applicative пример выше, быстро платит дивиденды при повторном использовании кода.
Там нет необходимости входить и выходить из Reader как вы делаете это здесь, используя runReader; вместо этого вы можете переписать его как
renumberR :: Tree a -> Reader Int (Tree Int)
renumberR (Node _ l r) = do
x <- ask
l' <- local (+1) (renumberR l)
r' <- local (+1) (renumberR r)
return (Node x l' r')
renumberR Empty = return Empty
Тем не менее, вы можете написать это еще лучше, просто используя аппликативный интерфейс Reader:
renumberR (Node _ l r) =
Node <$> ask <*> local (+1) (renumberR l) <*> local (+1) (renumberR r)
renumberR Empty = pure Empty
Обратите внимание, что я переименовал вашу функцию в renumberR подчеркнуть тот факт, что он работает в Reader, но не обязательно используя его монадический интерфейс.