用fold函数映射任意n元树

Question

用fold函数映射任意n元树

javascripthaskelltreefunctional-programmingfold

4

我希望拥有一些用于处理树形结构的通用工具。我正在使用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)
  }
}

经过测试，它可以正常工作。

以下是我伪造的 Haskell 实现，用于构建/证明上述 JavaScript 代码：

reduceTree f a (Node val []) = f a val
reduceTree f a (Node val xs) = f (fold (reduceTree f) acc) val

)

- Luftzig

你已经弄清楚mapTree的签名了吗？ - Bergi

请问您能展示一下 reduceTree 的实现吗？我猜它目前并没有调用 f - 除非你把 getChildren 改成类似于 getContents :: T a -> (a, [T a]) 这样的形式。 - Bergi

啊，没错 - 但是你的 f 应该接受一个 a 参数，而不是一个 T a。 - Bergi

@Bergi我通过创建“f :: b -> T a -> b”来避免处理节点结构本身。请记住，我实际上是使用JavaScript，所以一切都很松散。 - Luftzig

@WillNess，@Bergi 我添加了我的 reduceTree 实现和伪代码。请注意，我的“树”只有一些值的节点和（可能为空的）子节点列表。 - Luftzig

2个回答

3

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中的reduceTree函数与Aadit的答案中的函数完全相同。约翰·休斯在他的著名论文“为什么函数式编程很重要”中也几乎是这样的。

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，因此必须提供“零”即默认值；而前者的归约器将 Node a [r] 转化为 r，因此没有需要处理的 Nil 情况（参见 recursion-schemes）。

根据评论中用户Bergi提供的线索，Haskell包containers为此类型定义了可折叠实例。

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))) ...)

这句话的意思是：它与本帖开头的代码等价，只是参数的顺序不同。

参见：Haskell树上的折叠变体

- Will Ness

谢谢！那是非常有帮助的解释，它对我很有帮助。最终我使用了Aadit的解决方案，但在阅读您的答案之前我并不理解它。 - Luftzig

@Luftzig 谢谢，我也是在写之前想到的。:) 有趣的是，一种折叠方式可以让你轻松地重新创建结构，而另一种则会破坏它。在使用右折叠实现 tail 时，有一些类似的情况，这很难做到，如果使用参数形式，则非常简单。这里肯定有一些更深层次的东西... - Will Ness

关于线性度的问题，它意味着在将树转换为列表时，很容易对节点值映射一个函数。只是在这个过程中，树结构会丢失。也许可以通过以某种“标记”装饰规约函数的输出类型，并在之后重新创建结构来恢复它。---相反的问题可能是，是否可能使用Aadit的折叠将树展平为列表。 - Will Ness

@WillNess 也许你的 foldTree 或 redtree 太平凡了，但我认为它是一个函数式珍珠。与 Aadit 的 catamorphism 的等价性对我来说并不明显，因为它包括了一个右折叠，因此失去了非线性结构。但由于 foldTree 有两个不同的函数，它可以在某种程度上检索结构。这是一个惊人的组合子，感谢你从论文中挖掘出来。 - user5536315

1

@scriptum John Hughes 的 foldTree，我只是在语法上进行了微调。 :) 这篇论文用一种更详细的方式介绍了它，我为自己能够识别出这个模式并将递归调用放入组合链中而感到非常自豪。 :) 它也在这里中被提到。顺便说一句，我记得写过这篇答案，但不记得所有细节。 :) 我想你已经明白了，这两个函数之间的区别。 - Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aadit M Shah · Accepted Answer

我看到你的树形数据结构定义如下：

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

现在你可以使用reduceTree来定义mapTree，如下所示：

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));

希望这能帮到您。