treeFold函数中的递归

Question

我有树数据类型:

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

Answer 1

不幸的是,术语"折叠"有点过载.

结构递归

如果你想让你的fold函数捕获一些结构递归的概念,我不认为,对于这种类型的树,你希望它采用两个参数(除了树参数).

类型

这种折叠函数的类型遵循数据类型的构造函数的类型.

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

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

只有一个构造函数:

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

因此,除了要折叠的树之外,折叠函数只需要一个参数.这个参数的类型是通过用Tree a一个新的类型变量替换构造函数类型中的所有实例来获得的,例如b:

           a  -> [Tree a] -> Tree a

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

           a  -> [   b  ] ->   b

类型变量b也构成函数的返回类型.也就是说,你得到了

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

履行

此函数的实现也来自数据类型的定义.b通过递归地将折叠函数应用于a的Tree a-typed部分,可以获得必须传递给折叠的第一个参数的-typed值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的函数的应用程序替换树值中构造函数的所有应用程序.ftreeFold

例子

例如,您现在可以使用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和foldlPrelude:

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, (+))