5

我写了以下代码。它正在工作并使用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
4

2 回答 2

9

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

应用函子

这是 的定义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 af b

活泼的应用程序

制作Tree应用函子的一种方法是<*>同步遍历两棵树，就像处理列表一样将它们压缩在一起。zip每次遇到Node函数树中的 aNode和参数树中的 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生成 s 的无限树x。这很好用，因为 Haskell 是一种惰性语言。

     +-----x-----+
     |           |
  +--x--+     +--x--+
  |     |     |     |
+-x-+ +-x-+ +-x-+ +-x-+
|   | |   | |   | |   |
          etc

所以树的形状和 的形状t <*> pure x是一样的t：只有遇到 a 时才停止遍历Empty，而 in 中没有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函子都承认（至少）一个活泼的Applicative实例。

使用一些Applicative机制，我们可以将 Prelude 推广zip到任何应用函子（尽管它只会在本质zip上是 zippy 时表现得完全一样Applicative- 例如，使用常规Applicative实例 for[] zipA会给你它的论点的笛卡尔积）。

zipA :: Applicative f => f a -> f b -> f (a, b)
zipA = liftA2 (,)

标记为 Zipping

计划是将输入树与包含每个级别深度的无限树一起压缩。输出将是一棵与输入树形状相同的树（因为深度树是无限的），但每个节点都将标有其深度。

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上面的实例中所做的那样，很快就会在代码重用方面带来好处。

于 2016-04-07T15:01:21.757 回答
2

无需在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，但不一定使用其一元接口。

于 2016-04-07T12:34:57.460 回答