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

Question

我写了以下代码.它正在使用Readermonad.

你能给我一些关于Haskell代码风格的提示吗？主要是我的意思是monads - 我是新手.

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是包含某些值的结构 .该函数采用函数()的结构并将其应用于arguments()的结构以生成结果()的结构.f x<*>f (a -> b)f af b

Zippy Applicatives

制作Tree应用程序仿函数的一种方法是通过<*>锁定步骤遍历两棵树,将它们拉到一起就像zip列表一样.每次遇到Node函数Node树和参数树中的a 时,都可以拉出函数并将其应用于参数.当你到达任一树的底部时,你必须停止遍历.

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是一种懒惰的语言.

     +-----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,并<*>以锁步方式使用其参数.

原型zippy Applicative,如果你愿意,是"读者"Applicative (->) r,它通过将所有功能应用于固定参数并收集结果来组合功能.所以所有的Representable仿函数都承认(至少)一个zippy 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上面的实例中所做的那样,很快就会在代码重用中获得回报.