1

给定这个定义，我如何为通用 Haskell 树编写通用的 foldr 和 foldl 函数？

data (Eq a, Show a) => Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)

treefoldr :: (Eq a, Show a) => 
   (a -> b -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c

treefoldl :: (Eq a, Show a) =>
   (b -> a -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c

即使我能理解 foldr 和 foldl 函数在 Haskell 中的工作原理，我也不太确定如何为树编写这个通用函数。

编辑：我尝试过这样的事情（甚至没有编译）：

treefoldr  _ g1 _ _    Void       = g1
treefoldr f1 g1 f2 g2 (Node a ts) = f1 a (foldr f2 g2 ts)

编辑2：再试一次......

treefoldr _ z1 _ _   Void      = z1
treefoldr f z1 g z2 (Node a ts) =
   f a (foldr g z2 (map (\x -> treefoldr f z1 g z2 x) ts))

treefoldl _ z1 _ _   Void      = z1
treefoldl f z1 g z2 (Node a ts) =
   f (foldl g z2 (map (\x -> treefoldl f z1 g z2 x) ts)) a

treefoldr正在工作，但treefoldl不是：

Couldn't match expected type `c' against inferred type `b'
      `c' is a rigid type variable bound by
          the type signature for `treefoldl' at trees.hs:47:42
      `b' is a rigid type variable bound by
          the type signature for `treefoldl' at trees.hs:47:32
    In the first argument of `foldl', namely `g'
    In the first argument of `f', namely
        `(foldl g z2 (map (\ x -> treefoldl f z1 g z2 x) ts))'
    In the expression:
        f (foldl g z2 (map (\ x -> treefoldl f z1 g z2 x) ts)) a
4

3 回答 3

2

完整的错误消息：

Couldn't match expected type `c' against inferred type `Tree a'
  `c' is a rigid type variable bound by
      the type signature for `treefoldr' at so.hs:5:14
  Expected type: [c]
  Inferred type: [Tree a]
In the third argument of `foldr', namely `ts'
In the second argument of `f1', namely `(foldr f2 g2 ts)'

这意味着

  • ts是类型[Tree a]
  • 你用它作为第三个参数foldr
  • foldr期望它的第三个参数是类型[c]
  • [c]并且[Tree a]是不同的类型，因此这是一个错误

所以你需要处理ts成某种类型的东西[c]并将结果传递给foldr而不是ts它本身。地图功能将是一个很好的起点。

于 2011-02-13T21:45:43.110 回答
0

我不知道你的作业是否允许这样的解决方案，但是当类型类的使用可以时，你可以写

import Data.Foldable
import Data.Monoid

data Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)


instance Foldable Tree where 
   foldMap f Void = mempty
   foldMap f (Node value []) = f value
   foldMap f (Node value (x:xs)) = foldMap f x `mappend` foldMap f (Node value xs)

使用这个定义，你的函数的实现应该是微不足道的，因为 Foldable 定义了 foldl、foldr 等。

于 2011-02-14T09:44:36.100 回答
0

我和你的教授谈过，最后我找到了正确的解决方案：

treefoldr :: (Eq a, Show a) => (a -> b -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c
treefoldr _ z1 _ _   Void      = z1
treefoldr f z1 g z2 (Node a ts) = f a $ foldr (aggr) z2 ts
    where
        aggr t z = g (treefoldr f z1 g z2 t) z

treefoldl :: (Eq a, Show a) => (b -> a -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c
treefoldl _ z1 _ _   Void      = z1
treefoldl f z1 g z2 (Node a ts) = f (foldl (aggr) z2 ts) a
    where
        aggr z t = g (treefoldl f z1 g z2 t) z

问候

于 2013-09-04T19:45:34.637 回答