Haskell - 使用Reader monad在二叉树中的每个节点的深度 [英] Haskell - depth for each node in binary tree using Reader monad
问题描述
我写了下面的代码。它正在使用 Reader monad。
你可以给我一些关于Haskell代码风格的提示吗？主要是指单子 - 我是新手。
import Control.Monad.Reader
数据树a =节点a（树a）（树a）
|清空
renumberM :: Tree a - > Reader Int（Tree Int）
renumberM（Node _ lr）= ask>> =（\ x - >
return（节点x（runReader（local（+1） ）x）
（runReader（local（+1）（renumberM r））x））
renumberM Empty = return空
重新编号''：树a - > ; Tree Int
renumber''t = runReader（renumberM t）0
我想告诉你，你的想法是一个更一般概念的实例 - 压缩。这是你的程序的一个版本，它使用了一个更简单和更实用的风格。
Applicative Functors
class Functor f =>应用f其中
pure :: a - > f a
（*）:: f（a - > b） - > f a - > fb
你可以说 fx 是包含一些值 x 的结构 f 。函数<> 采用函数结构（ f（a - > b））并且适用它变成了一个参数结构（ fa ）来产生结果结构（ fb ）。
Zippy Applicatives
制作 Tree 一个应用函数的一种方法是使<> 在锁步中遍历两棵树，将它们压缩在一起，就像 zip 与名单。每次在函数树中遇到一个 Node ，并在参数树中出现一个 Node 时，您可以将运行并将其应用于参数。
实例Applicative Tree其中
pure x必须停止遍历。 = let t = t
中的节点xtt空<> _ =清空
_< *> Empty = Empty
（节点ff，ff）*< （节点x lx rx）=节点（fx）（lf * lx）（rf * rx）
实例函数树其中
fmap fx =纯f < * GT; x - 如往常一样
纯x 生成一个 x s的无限树。这很好，因为Haskell是一种懒惰的语言。
+ ----- x ----- +
| |
+ - x - + + - x - +
| | | |
+ -x- + + -x- + + -x- + + -x- +
| | | | | | | |
等
所以树的形状 t <* >纯x 与 t 的形状相同：当遇到 Empty ，并且中没有任何纯x 。 （这同样适用于纯x <*> t 。）
这是一种常见的方式数据结构是 Applicative 的一个实例。例如，标准库包含 ZipList ，其 Applicative instance 与我们的树非常相似：
newtype ZipList a = ZipList {getZipList :: [a]}
实例Applicative ZipList其中
pure x = ZipList（重复x）
ZipList fs< *> ZipList xs = ZipList（zipWith（$）fs xs）
再一次，纯会生成一个无限的 ZipList ，并且<>
$ b 如果您愿意，原型zippy应用程序是读者应用程序（ - >）r ，它将函数全部应用于一个固定的参数并收集结果。因此，所有 可表示 函子承认（至少）一个zippy Applicative 实例。
使用一些 Applicative 机器，我们可以将Prelude的 zip 推广到任何应用函子（尽管它只会像<$ c当 Applicative 本质上是zippy - 例如，使用常规 Applicative 时，$ c> zip 对于 [] zipA 的c>实例将为您提供其参数的笛卡尔乘积）。
zipA :: Applicative f => f a - > f b - > f（a，b）
zipA = liftA2（，）
标签为压缩 h2>
计划是将输入树与包含每个级别深度的无限树一起压缩。输出将是一棵与输入树形状相同的树（因为深度树是无限的），但每个节点都会标记为深度。
depths :: Tree Integer
depths = go 0
其中go n = let t = go（n + 1）in Node ntt
这就是深度的样子：
+ ----- 0 ----- +
| |
+ - 1 - + + - 1 - +
| | | |
+ -2- + + -2- + + - + - + - + +
| | | | | | | |
等
现在我们已经建立了我们需要的结构，很容易。
labelDepths :: Tree a - > Tree（Integer，a）
labelDepths = zipA深度
通过扔掉原始标签，正如您最初指定的也很简单。
relabelDepths :: Tree a - >树整数
relabelDepths t = t *>深度
快速测试：
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
类型路径= [步骤]
路径::树路径
路径= go []
其中go path =节点路径（go（path ++ [L]）） （go（path ++ [R]））
+ -------- [] -------- +
| |
+ --- [L] --- + + --- [R] --- +
| | | |
+ - [L，L] - + + - [L，R] - + + - [R，L] - + + - [R，R] - +
| | | | | | | |
等
（
labelPath :: Tree a - > Tree（Path，a）
labelPath = zipA路径
当你继续学习Haskell时，当程序是一个更深层概念的例子时，你会更好地发现它。设置一般结构，就像我上面的 Applicative 实例一样，快速支付代码重用的红利。
I wrote the following code. It is working and using the Reader monad.
Could you give me some hints about code style in Haskell ? Mainly, I mean monads -- I am newbie.
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
I want to show you that your idea is an instance of a more general concept - zipping. Here's a version of your program that employs a simpler and more functional style.
Applicative Functors
Here's the definition of Applicative:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
You could say that a type f x is a structure f containing some values x. The function <*> takes a structure of functions (f (a -> b)) and applies it to a structure of arguments (f a) to produce a structure of results (f b).
Zippy Applicatives
One way to make Tree an applicative functor is by making <*> traverse the two trees in lock-step, zipping them together just like zip does with lists. Every time you encounter a Node in the tree of functions and a Node in the tree of arguments, you can pull the function out and apply it to the argument. You have to stop traversing when you reach the bottom of either of the trees.
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 generates an infinite tree of xs. This works fine because Haskell is a lazy language.
+-----x-----+
| |
+--x--+ +--x--+
| | | |
+-x-+ +-x-+ +-x-+ +-x-+
| | | | | | | |
etc
So the shape of the tree t <*> pure x is the same as the shape of t: you only stop traversing when you encounter an Empty, and there aren't any in pure x. (The same applies to pure x <*> t.)
This is a common way to make a data structure an instance of Applicative. For example, the standard library includes ZipList, whose Applicative instance is very similar to that of our tree:
newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
pure x = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)
Once again, pure generates an infinite ZipList, and <*> consumes its arguments in lock-step.
The prototypical zippy Applicative, if you like, is the "reader" Applicative (->) r, which combines functions by applying them all to a fixed argument and collecting the results. So all Representable functors admit (at least) a zippy Applicative instance.
Using some Applicative machinery, we can generalise the Prelude's zip to any applicative functor (although it'll only behave precisely like zip when the Applicative is zippy in nature - for example, with the regular Applicative instance for [] zipA will give you the Cartesian product of its arguments).
zipA :: Applicative f => f a -> f b -> f (a, b)
zipA = liftA2 (,)
Labelling as Zipping
The plan is to zip the input tree together with an infinite tree containing the depth of each level. The output will be a tree with the same shape as the input tree (because the depths-tree is infinite), but each node will be labelled with its depth.
depths :: Tree Integer
depths = go 0
where go n = let t = go (n+1) in Node n t t
This is what depths looks like:
+-----0-----+
| |
+--1--+ +--1--+
| | | |
+-2-+ +-2-+ +-2-+ +-2-+
| | | | | | | |
etc
Now that we've set up the structures we need, labelling a tree is easy.
labelDepths :: Tree a -> Tree (Integer, a)
labelDepths = zipA depths
Relabelling a tree by throwing away the original labels, as you originally specified, is easy too.
relabelDepths :: Tree a -> Tree Integer
relabelDepths t = t *> depths
A quick test:
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')
You can devise different labelling schemes by varying the tree you zip along. Here's one which tells you the path you took to reach a node:
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
(The inefficient nesting of calls to ++ above can be mitigated using difference lists.)
labelPath :: Tree a -> Tree (Path, a)
labelPath = zipA paths
As you continue to learn Haskell, you'll get better at spotting when a program is an example of a deeper concept. Setting up general structures, like I did with the Applicative instance above, quickly pays dividends in code reuse.
这篇关于Haskell - 使用Reader monad在二叉树中的每个节点的深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
