在树上映射

Question

我是新来的Haskell和实践我一直在执行一组函数(map,length使用等)foldr和foldl.现在我想搬到树上!

我的树数据结构:

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)

Hokay？所以现在(使用标准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

Answer 2

您无需treeFold编写类似的内容treeMap。

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

与相同想法对应的基类是Foldable和Functor。基础上的一切都Foldable已经是Functor; 能够treeMap独立于进行定义是很自然的treeFold。