3

我有树数据类型：

data Tree a = Node
  { rootLabel :: a,        -- label value
    subForest :: [Tree a]  -- zero or more child trees
  }

{-- Node (a) [] ..or...  Node (a1) [ Node (a2) [..], Node (a3) [..] ] --}

我需要编写 treeFold 函数，我认为我需要第一个函数来制作带有标签值的东西，第二个函数需要 func1 的两个结果并产生一些最终结果等等。我开始编写递归函数 treeFold，为具有 0 个子树的最小树编写函数，但由于子树列表不为空，我无法完成我的函数。

我需要获取第一个孩子和其他孩子的列表并从中制作新树以使用这棵新树进行递归调用吗？ 

treeFold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
treeFold func1 _ (Node a1 []) = func1 a1   
treeFold func1 func2 (Node a1 [y]) = func2 (func1 a1) (treeFold func1 func2 y) 
treeFold func1 func2 (Node a1 [y1,y2]) = func2 (func1 a1) (treeFold func1 func2 (y1
4

1 回答 1

8

不幸的是，“折叠”这个词有点过分了。

结构递归

如果您希望您的 fold 函数捕获一些结构递归的概念，我认为对于这种类型的树，您不希望它采用两个参数（除了树参数）。

类型

这种折叠函数的类型来自数据类型的构造函数的类型。

在您的情况下，您的数据类型

data Tree a = Node {rootLabel :: a, subForest :: [Tree a]}

只有一个构造函数：

Node :: a -> [Tree a] -> Tree a

因此，除了要折叠的树之外，您的 fold 函数将只接受一个参数。此参数的类型是通过将Tree a构造函数类型中所有出现的 替换为新的类型变量来获得的，例如b：

           a  -> [Tree a] -> Tree a

           |        |          |
           |        |          |
          \ /      \ /        \ /
           -        -          -

           a  -> [   b  ] ->   b

类型变量b也构成函数的返回类型。也就是说，你得到

treeFold :: (a -> [b] -> b) -> Tree a -> b

执行

此函数的实现也遵循数据类型的定义。b通过递归地将 fold 函数应用于a 的Tree a类型化部分，您可以获得必须传递给 fold 的第一个参数的类型化值Node。这里有点棘手的是这些部分存储在一个列表中，因此您还需要映射该列表：

treeFold f (Node x xss) = f x (map (treeFold f) xss)

或者，可以说更好一点：

treeFold f = h
  where
    h (Node x xss) = f x (map h xss)

关键思想是，您将Node树值中的构造函数的所有应用程序替换f为作为第一个参数传递给的函数的应用程序treeFold。

例子

例如，您现在可以使用treeFold定义一个对树中所有元素求和的函数：

total :: Num a => Tree a -> a
total =  treeFold (\n ns -> n + sum ns)

或者一个简单地返回树包含多少元素的函数：

size :: Tree a -> Int
size =  treeFold (\_ ns -> 1 + sum ns)

减少

另一个品牌的折叠是那些对数据结构进行（左偏或右偏）归约的折叠。这些折叠确实通常需要两个额外的参数：

treeFoldr :: (a -> b -> b) -> b -> Tree a -> b
treeFoldl :: (b -> a -> b) -> b -> Tree a -> b

例如，您可以根据辅助功能来实现这些功能flatten

flatten :: Tree a       -> [a]
flatten    (Node x xss) =  x : concatMap flatten xss

并通过重用列表函数foldr和foldl前奏：

treeFoldr :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr    op               e =  foldr op e . flatten

treeFoldl :: (b -> a -> b) -> b -> Tree a -> b
treeFoldl    op               e =  foldl op e . flatten

例如：

total = treeFoldl (+) 0
size  = treeFoldr (const succ) 0

更多变化

根据您想要概括的概念，还有更多变体。例如，有人可能会争辩说，为了捕获结构递归，不需要/不希望在子森林上进行映射，最终会得到类似的东西

treeFold' :: (a -> c -> b) -> (c, b -> c -> c) -> Tree a -> b
treeFold' node (nil, cons) = h
  where
    h (Node x xss) = node x (foldr (cons . h) nil xss)

接着

total = treeFold' (+) (0, (+))
size  = treeFold' (const succ) (0, (+))
于 2013-05-22T21:09:19.797 回答