Haskell - 使用 Reader monad 的二叉树中每个节点的深度

Question

我写了下面的代码。它正在工作并使用 Reader monad。

你能给我一些关于 Haskell 代码风格的提示吗？我主要指的是单子(monad)——我是新手。

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

Answer 1

我想向您展示您的想法是一个更一般概念的实例 - 压缩。这是您的程序的一个版本，它采用了更简单、更实用的风格。

应用仿函数

这是 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 应用程序

一种制作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 instance与我们的树非常相似:

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 ，和<*>以锁步方式消耗其参数。

如果您愿意的话，典型的 zippy 应用程序是“阅读器”应用程序 (->) r ，它通过将所有函数应用于固定参数并收集结果来组合函数。所以所有 Representable 仿函数承认(至少)有活力 Applicative实例。

使用some Applicative machinery ，我们可以概括 Prelude 的 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

通过丢弃原始标签来重新标记树，如您最初指定的 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')

您可以通过改变压缩的树来设计不同的标签方案。这是告诉您到达节点所采取的路径:

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

(上面对 ++ 调用的低效嵌套可以使用 difference lists 来缓解。)

labelPath :: Tree a -> Tree (Path, a)
labelPath = zipA paths

<小时/>

随着您继续学习 Haskell，您将能够更好地发现程序何时是更深层次概念的示例。设置一般结构，就像我对 Applicative 所做的那样上面的例子，在代码重用方面很快就会带来红利。