我想要一些用于处理树木的通用工具。我正在使用JavaScript，所以我可以施加的很少，而且我正在使用我无法改变的现有数据结构。我设法定义了以下内容：
reduceTree :: (T a -> [T a]) -> (b -> T a -> b) -> b -> T a -> b
reduceTree(getChildren, f, accumulator, tree)
（我正在使用Haskell类型签名，因为它们更容易阅读）
这个getChildren函数是必需的，因为我的树是任意的，我对它的构造方式一无所知。
reduceTree效果很好。但我也希望有一个mapTree功能，最好重用我的reduceTree功能，但我卡住了。有些不对劲，但我无法弄清楚是什么。
我的reduceTree实施：
export function reduceTree(getChildren, f, accumulator, tree) {
const children = getChildren(tree);
if (!children || children.length === 0) {
return f(accumulator, tree)
} else {
const childrenResult = children.reduce(
(accumulator, subTree) => reduceTree(getChildren, f, accumulator, subTree),
accumulator
);
return f(childrenResult, tree)
}
}
它经过测试和运作。
（我用来构建/证明上面的javascript的伪Haskell实现：
reduceTree f a (Node val []) = f a val
reduceTree f a (Node val xs) = f (fold (reduceTree f) acc) val
)
我看到你的树数据结构定义如下：
data T a = Node a [T a]
如果是这种情况，那么树数据结构的折叠将是：
reduceTree :: (a -> [b] -> b) -> T a -> b
reduceTree f = let g (Node a xs) = f a (map g xs) in g
您现在可以使用mapTree定义reduceTree，如下所示：
mapTree :: (a -> b) -> T a -> T b
mapTree f = reduceTree (Node . f)
将它全部转换为JavaScript：
const Node = (a, xs) => ({a, xs});
const reduceTree = (f, node) => {
const g = node => f(node.a, node.xs.map(g));
return g(node);
};
const mapTree = (f, node) => reduceTree((a, xs) => Node(f(a), xs), node);
const tree = Node(2, [ Node(3, [ Node(11, [])
, Node(13, []) ])
, Node(5, [])
, Node(7, [ Node(17, [])
, Node(19, []) ]) ]);
console.log(mapTree(x => 2 * x, tree));希望有所帮助。
TL; DR：您的伪代码被破坏了。解决它的一种方法是
reduceTree :: (b -> a -> b) -> b -> T a -> b
reduceTree f acc (Node val []) = f acc val
reduceTree f acc (Node val ts) =
Data.List.foldl (\acc tree -> reduceTree f acc tree) (f acc val) ts
这意味着你的Javascript应该是
export function reduceTree(getChildren, f, accumulator, tree) {
const children = getChildren(tree);
if (!children || children.length === 0) {
return f(accumulator, tree)
} else {
const childrenResult = children.reduce(
(accumulator, subTree) => reduceTree(getChildren, f, accumulator, subTree),
f(accumulator,tree) // referring to `tree` only for its stored node value, yes?
);
return childrenResult;
}
}
据推测，Javascript在列表中的reduce是左侧折叠（根据维基百科，它是如此）。
它执行预订树遍历，相当于本文底部的tfoldl函数。用它实现map虽然不太有用，
tmap f t = reduceTree (\acc val -> Node (f val) ???) ??? t
因为Node :: a -> [T a] -> T a的类型不合适，不能使其适合上面的减速器类型，b -> a -> b（它需要类型a -> [b] -> b）。
这是因为这种线性折叠基本上使结构变平，将其视为线性序列。
随后进行了一些无关的阐述。
Haskell has it the exact same way作为reduceTree中的Aadit's answer函数。
约翰休斯在他的着名论文“为什么功能编程很重要”中也有同样的方式，如同
foldTree :: (a -> b -> r) -> (r -> b -> b) -> b -> Tree a -> r
foldTree f g z (Node x t) = f x . foldr g z . map (foldTree f g z) $ t
他使用了一种等同的，但更冗长的配方，他称之为redtree，用于“减少树”。它认为
foldTree f g z = reduceTree (\a rs -> f a (foldr g z rs))
所以两者几乎相同。然后，
map h = reduceTree (Node . h)
= reduceTree (\a rs -> Node (h a) rs)
= foldTree (Node . h) (:) []
没有“零”即初始累加器值来自数据定义中没有第二个子句，data T a = Node a [T a]而不是List a = Nil | Cons a (List a)，列表。
后者的倍数减少函数需要Nil或Cons a r到r，因此它必须具有“零”，即提供给它的defult值;而对于前者，它需要Node a [r]到r，所以没有Nil案件来处理（参见recursion-schemes）。
在评论中跟随a hint的user Bergi之后，Haskell包containers定义了这种类型的a Foldable instance，
data T a = Node a [T a]
相当于foldr（为方便起见，使用翻转参数），是
tfoldr :: (a -> b -> b) -> T a -> b -> b
tfoldr f (Node x ts) z = f x $ Data.List.foldr ($) z [tfoldr f t | t <- ts]
确实穿过状态/累加器！它也可以写成
tfoldr :: (a -> b -> b) -> T a -> b -> b
tfoldr f (Node x ts) z = f x . Data.List.foldr (.) id [tfoldr f t | t <- ts] $ z
以较容易实现的方式。这是实现后序树遍历;对于通常的预订遍历使用
tfoldl :: (a -> b -> b) -> T a -> b -> b
tfoldl f (Node x ts) z = Data.List.foldr (>>>) id [tfoldl f t | t <- ts] $ f x z
-- // = tfoldl f tn (... (tfoldl f t2 (tfoldl f t1 (f x z))) ...)
其中(f >>> g) x = g (f x)，或
tfoldl :: (b -> a -> b) -> T a -> b -> b
tfoldl f (Node x ts) z = Data.List.foldr (>>>) id [tfoldl f t | t <- ts] $ f z x
-- // = tfoldl f tn (... (tfoldl f t2 (tfoldl f t1 (f z x))) ...)
这相当于本文开头的代码，直到参数的顺序。