haskell - 映射一棵树

Question

我是 Haskell 的新手，为了练习，我一直使用 foldr 实现了一系列函数(map、length 等)折叠。现在我想搬到树上!

我的树数据结构:

data Tree a = Node a [Tree a] deriving (Show) 

我编写了一个 Haskell 函数来折叠树:

treeFold :: (b->a->b) -> b -> Tree a -> b
treeFold f s (Node a []) = f s a
treeFold f s (Node a xs) = foldl f (f s a) (dFSList xs)

其中dFSList是树中所有节点的列表。所以做类似的事情:

treeFold (+) 0 (Node 1 [Node 2 [], Node 3 []])

返回 6。酷。

现在我想编写一个 Haskell 函数来映射树，但我想使用我的 treeFold 函数来完成它。这是我到目前为止所拥有的:

treeMap f (Node a []) = (Node (f a) [])
treeMap f (Node a (x:xs)) = (Node (f a) (a list involving foldTree somehow??))

如何完成我的treeMap功能？我希望能够做到

treeMap (+1) (Node 1 [Node 2 [], Node 3 []])

它应该返回

(Node 2 [Node 3 [], Node 4 []])

Answer 1

分解树木的方法通常是使用不同种类的折叠(由于我不知道的某些类别理论原因，通常称为变形现象)。您有data Tree a = Node a [Tree a]，因此要将其拆开，您需要制作

cat :: (a -> [b] -> b) -> Tree a -> b
cat f (Node root children) = f root (map (cat f) children)

霍凯？所以现在(使用标准的 Functor 类而不是专门的treeMap)，

instance Functor Tree where
  fmap f = cat (Node . f)

你也可以像这样写线性折叠。你的 treeFold 让我困惑，但你可以写，例如，

instance Foldable Tree where
  foldMap f = cat go where
    go root children = f root `mappend` fold children

更强，

instance Traversable Tree where
  traverse f = cat go where
    go root children = Node <$> f root <*> sequenceA children