折叠树函数 [英] Fold Tree Function

问题描述

 数据BinaryTree a = Leaf 
 |节点（BinaryTree a）a（BinaryTree a）
导出（Eq，Ord，Show）
 
 foldTree ::（a  - > b  - > b） - > b  - > BinaryTree a  - > b 
 foldTree _ base Leaf = base 
 foldTree fn base（Node left right）= fn a（foldTree fn acc right）
 where acc = foldTree fn base left 
  

这段代码几乎可行。但并非总是如此。例如，它不会重构与原始版本完全相同的树。

解决方案

GHC善于折叠东西。您的类型的结构包含足够的信息，用于您希望的顺序遍历策略对机器来说是显而易见的。为了调用魔法，请说出派生可折叠！，GHC会为您写入函数。

  { - ＃LANGUAGE DeriveFoldable＃ - } 
 data BinaryTree a = Leaf 
 | Node（BinaryTree a）a（BinaryTree a）
派生可折叠
  

现在我们有





  foldTree = foldr 
  

这里一个有趣的推论是，你可以通过改变类型的形状来改变遍历顺序。

---

虽然我们在这里，但请注意您的要求。你想使用 foldr 来实现一个函数，这个函数将一棵树分开，并将它们放在一起，完全相同，相当于 id 。 这是不可能的。 foldr 为 Foldable 结构的元素提供 sequential 访问权限，擦除精确的信息元素在树中的位置。最好的情况是，你可以创建一个列表形状的树，元素沿着右脊柱出现：

  toListShapedTree = foldr（Node Leaf ）Leaf 
  

你想要的是变形：

  cata ::（b  - > a  - > b  - > b） - > b  - > BinaryTree a  - > b 
 cata node leaf leaf = leaf 
 cata node leaf（Node lxr）= node（cata node leaf l）x（cata node leaf r）
  pre> 
 
 
请注意节点参数的额外参数！该规范给出折叠函数访问 Node 构造函数的参数。与 Foldable 不同，结构的变形类型特定于该结构。我们不会因将所有内容视为列表而丢失信息。现在你可以这样写： 
 
 
  cataId = cata Node Leaf 
  
如果您为此设置了 foldr ，则可以采取一种策略来获取位置信息。首先用它的标签标记每个元素位置，然后在折叠中使用该数据来重建树。看起来像辛苦的工作给我。
 
I'm trying to write a fold function for a tree:
data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving (Eq, Ord, Show)

foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree _ base Leaf = base
foldTree fn base (Node left a right) = fn a (foldTree fn acc right)
         where acc = foldTree fn base left
This code nearly works. However not always. For example it won't reconstruct the tree exactly the same as the original.
解决方案
GHC is good at folding things. The very structure of your type contains enough information for your desired in-order traversal strategy to be obvious to the machine. To invoke the magic spell, utter the words "deriving Foldable!" and GHC will write your function for you.
{-# LANGUAGE DeriveFoldable #-}
data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving Foldable
Now we have
foldTree = foldr
An interesting corollary here is that you can vary the traversal order by varying the shape of the type.



While we're here, a note on your requirements. You want to implement a function, using foldr, which takes a tree apart and puts it back together exactly the same, equivalent to id. This is not possible. foldr provides sequential access to the elements of the Foldable structure, erasing information like the precise position of the element within the tree. At best, you can build a list-shaped tree, with elements appearing along the right spine:
toListShapedTree = foldr (Node Leaf) Leaf
What you want is a catamorphism:
cata :: (b -> a -> b -> b) -> b -> BinaryTree a -> b
cata node leaf Leaf = leaf
cata node leaf (Node l x r) = node (cata node leaf l) x (cata node leaf r)
Note the extra parameter to the node argument! This specification gives the folding function access to the arguments of the Node constructor. Unlike Foldable, the type of a structure's catamorphism is specific to that structure. We don't lose information by viewing everything as a list. Now you can write:
cataId = cata Node Leaf
If you're dead set on using foldr for this, one strategy could be to take the positional information with you. First label each element with its position, then in the fold use that data to reconstruct the tree. Seems like hard work to me.

                        
这篇关于折叠树函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！