在树上映射

Question

我是 Haskell 的新手，为了练习，我一直在使用 foldr 和 [=19] 实现一堆函数（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 []])

returns 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 []])

应该return

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

Answer 1

你不需要 treeFold 来写类似 treeMap 的东西。

treeMap f (Node a xs) = Node (f a) (map (treeMap f) xs)

对应相同思路的基础类是Foldable和Functor。基础中的所有 Foldable 都已经是 Functor；能够独立于 treeFold.

定义 treeMap 是很自然的

Answer 2

分解树木的方法通常是使用不同种类的褶皱（由于某些我不知道的范畴论原因，通常称为变形）。你有 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 class 而不是专门的 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

Mapping over a Tree