Haskell - 使用 Reader monad 对二叉树中每个节点的深度 [英] Haskell - depth for each node in binary tree using Reader monad
问题描述
我写了以下代码.它正在工作并使用 Reader monad.
I wrote the following code. It is working and using the Reader monad.
你能给我一些关于 Haskell 代码风格的提示吗?主要是，我的意思是单子——我是新手.
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
推荐答案
我想向您展示您的想法是一个更一般概念的实例 - zipping.这是您的程序的一个版本，它采用了更简单、更实用的风格.
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.
这是<的定义代码>适用:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
你可以说类型fx是一个结构 f 包含一些值 x.函数 <*> 采用函数结构 (f (a -> b)) 并将其应用于参数结构 (fa) 生成结果结构 (fb).
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).
使 Tree 成为应用函子的一种方法是使 <*> 以锁步方式遍历两棵树，压缩它们在一起就像 zip 处理列表.每次遇到函数树中的 Node 和参数树中的 Node 时，都可以将函数拉出并将其应用于参数.当你到达任何一棵树的底部时，你必须停止遍历.
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 生成 x 的无限树.这很好用，因为 Haskell 是一种惰性语言.
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
所以树的形状 t <*>pure x和t的形状一样:遇到Empty才停止遍历，pure中没有x.(同样适用于 pure x <*> t.)
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.)
这是使数据结构成为Applicative 实例的常用方法.例如，标准库包括 <代码>ZipList，其Applicative 实例 与我们的树非常相似:
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)
再一次，pure 生成一个无限的 ZipList，并且 <*> 在锁步中使用它的参数.
Once again, pure generates an infinite ZipList, and <*> consumes its arguments in lock-step.
典型的 zippy Applicative，如果你喜欢，是阅读器"Applicative (->) r，它通过将所有函数应用于固定参数并收集结果来组合函数.所以所有 Representable 函子承认(至少)一个 zippy Applicative 实例.
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.
使用一些Applicative 机制，我们可以将 Prelude 的 zip 推广到任何 applicative functor(尽管当 Applicative 本质上是 zippy - 例如，对于 [] zipA 的常规 Applicative 实例将为您提供笛卡尔积它的论点).
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
这是depths的样子:
+-----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
快速测试:
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
<小时>
随着您继续学习 Haskell，您会更好地发现程序何时是更深层次概念的示例.设置通用结构，就像我在上面的 Applicative 实例中所做的那样，很快就能在代码重用方面带来好处.
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屋！
