用于有状态树转换的Haskell习语

html5 • • 问答 

data Tree a b = Leaf a | Branch b [Tree a b]

给定一对函数f :: a -> a'，g :: b -> b'我可以轻松地将 aTree a b转换为 a Tree a' b'。

type Transform a b = a -> b
treeTransform :: Transform leaf leaf' ->
                 Transform branch branch' ->
                 Tree leaf branch ->
                 Tree leaf' branch'
treeTransform f _ (Leaf a) = Leaf (f a)
treeTransform f g (Branch b ts) = Branch (g b) (map (treeTransform f g) ts)

这棵树是一个bifunctor，上面的treeTransform只是一个bimap。没什么特别的。

现在当我需要通过fand线程状态时会发生什么g？

type StatefulTransform s a a' = s -> a -> (s, a')

statefulTreetransform :: StatefulTransform state leaf leaf' ->
                         StatefulTransform state branch branch' ->
                         state ->
                         Tree leaf branch ->
                         Tree leaf' branch'

现在有不止一种方法来实现这个功能，因为有不同的方法来遍历树。

我可以使用深度优先遍历来实现转换，但广度优先遍历是一个绊脚石。从树中提取数据到列表广度优先相对容易。转换提取的数据也很简单。但是如何将转换后的数据弯曲回原来的树形？

回答

即使您不尝试做二元函数，也有多个遍历命令！我将讨论如何为一个无聊的老函子做这件事；额外的类型参数也可以处理，但这样做会分散核心思想的注意力。所以这是我的无聊函子树类型：

data Tree x = Node x [Tree x]

进行广度优先遍历的传统方法是，作为中间步骤，生成一个列表列表。对于外部列表，树的每一层都有一个元素。像这样：

notQuiteBF :: Tree x -> [[x]]
notQuiteBF (Node x children) = [x] : (map concat . transpose . map notQuiteBF) children

那么实际的广度优先遍历只是这些列表的串联。

bf :: Tree x -> [x]
bf = concat . notQuiteBF

好的一点[x]是它有足够的信息来迭代树中的值。不幸的是，知道如何对来自多个孩子的遍历重新排序的信息还不够：我们知道第一个孩子的节点和第二个孩子的节点的广度优先排序，但我们不知道每个元素的深度是多少，所以我们不能把它们编织在一起。

一些聪明的人问了这个问题：如果我们只记得那个深度信息呢？所以在 中notQuiteBF，我们使用了更丰富的结构。好的一点[[x]]是它有足够的信息来重新排序元素，即使我们从树节点的深度优先访问来构造它。不幸的是，如果我们需要的话，重建树的形状的信息并不足够：我们知道每个级别的元素序列是什么，但我们不知道这些元素中的每一个与哪个父元素相关联。

所以现在我问：如果我们只记得那些额外的信息呢？方法如下：[[x]]我们将[[[x]]]作为中间结构返回，而不是。和以前一样，外部列表每个深度有一个元素。下一层在上一层深度的每个节点有一个元素；最后一层具有与该父级关联的子级。

让我们看一个例子：

                       a
                      / 
                     /   
                    /     
                   b       c
                  /       |
                 d   e     f
                     |    / 
                     g   h   i

对于这棵树，我们得到以下列表列表，带有提示性空格：

[[[a                    ]]
,[ [b        ,c        ]]
,[  [d ,e   ],[f      ]]
,[   [],[g ],  [h ,i ]]
,[       [],    [],[]]
]

Wellllll... 要重新构建树，我们实际上更喜欢以相反的顺序使用它。

[[[],[],[]]
,[[],[g],[h,i]]
,[[d,e],[f]]
,[[b,c]]
,[[a]]
]

我们先写重构算法。

rebuild :: [[[x]]] -> [Tree x]
rebuild = concat . go [] where
    go trees [] = trees
    go trees (xss:xsss) = go (weirdZipWith Node xss trees) xsss

weirdZipWith :: (x -> y -> z) -> [[x]] -> [y] -> [[z]]
weirdZipWith f [] _ = []
weirdZipWith f ([]:xss) ys = [] : weirdZipWith f xss ys
weirdZipWith f _ [] = []
weirdZipWith f ((x:xs):xss) (y:ys)
    = let (b, e) = splitAt 1 (weirdZipWith f (xs:xss) ys)
      in map (f x y:) b ++ e

在 ghci 中尝试一下：

> rebuild [["","",""],["","g","hi"],["de","f"],["bc"],["a"]]
[Node 'a' [Node 'b' [Node 'd' [],Node 'e' [Node 'g' []]],Node 'c' [Node 'f' [Node 'h' [],Node 'i' []]]]]

看起来挺好的。现在另一个方向。这是notQuiteBF上面的一个非常小的变化。

bf :: Tree x -> [[[x]]]
bf (Node x children) = [[x]] : [concat (concat b)] : e where
    (b, e) = splitAt 1 . map concat . transpose . map bf $ children

我们可以仔细检查我们的工作：

> quickCheck (t -> (rebuild . reverse . bf) t == [t :: Tree Int])
+++ OK, passed 100 tests.

有了这些工具，就可以很容易地编写Applicative遍历：我们只需按照正确的顺序构建元素列表，在f保留列表结构的同时调用它们中的每一个，然后重建树。所以：

bfTraverse :: Applicative f => (x -> f y) -> Tree x -> f (Tree y)
bfTraverse f = id
    . fmap (head . rebuild . reverse)
    . traverse (traverse (traverse f))
    . bf

（可能需要相当微妙的论证才能确信head这里是安全的！）在 ghci 中尝试一下：

> bfTraverse (x -> putStrLn [x] >> pure (toUpper x)) (Node 'a' [Node 'b' [Node 'd' [],Node 'e' [Node 'g' []]],Node 'c' [Node 'f' [Node 'h' [],Node 'i' []]]])
a
b
c
d
e
f
g
h
i
Node 'A' [Node 'B' [Node 'D' [],Node 'E' [Node 'G' []]],Node 'C' [Node 'F' [Node 'H' [],Node 'I' []]]]

以上是用于有状态树转换的Haskell习语的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>