Haskell

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

不需要像这里那样进出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 中运行的事实，但不一定使用其 monadic 接口。

Answer 2

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

应用函子

这里是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 的无限树。这很好用，因为 Haskell 是一种惰性语言。

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

所以树的形状t <*> pure x和t的形状是一样的：只有遇到一个Empty才停止遍历，里面没有pure x。（同样适用于pure x <*> t。）

这是使数据结构成为 Applicative 实例的常用方法。例如，标准库包含 ZipList, whose 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 Applicative 是 "reader" Applicative (->) r，它通过将函数全部应用于固定参数并收集结果来组合函数。所以所有 Representable 函子都承认（至少）一个活泼的 Applicative 实例。

使用 some Applicative machinery，我们可以将 Prelude 的 zip 泛化到任何应用仿函数（尽管它只会在 Applicative 是 zippy in 时表现得像 zip性质 - 例如，[] zipA 的常规 Applicative 实例将为您提供其参数的笛卡尔积）。

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 实例所做的那样，可以在代码重用方面迅速获得回报。

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

Haskell - depth for each node in binary tree using Reader monad

monads

reader-monad

应用函子

Zippy 应用程序

标记为压缩