如何折叠树而不使其成为可折叠的实例？

Question

我已经将我的树定义如下:

data Tree a
  = Tip
  | Node (Tree a) a (Tree a)
  deriving Show

并使其成为Functor的一个实例:

instance Functor Tree where
  fmap f Tip                       = Tip
  fmap f (Node leftsub x rightsub) = Node (fmap f leftsub) (f x) (fmap f rightsub)

现在我想定义以下函数来折叠树:

foldTree :: b -> (b -> a -> b -> b) -> Tree a -> b

我尝试过类似的东西,但我认为它不起作用,因为树不是幺半群:

foldTree f z Tip = Tip
foldTree f z (Node leftsub x rightsub) = foldr f leftsub ++ f x ++ foldr f rightsub

我在思考如何做到这一点时遇到了一些麻烦.任何帮助,将不胜感激.

Answer 1

首先要注意的是foldTree有三个参数:

foldTree :: b                   -- ^ Starting value
         -> (b -> a -> b -> b)  -- ^ Folding function
         -> Tree a              -- ^ Tree to fold over
         -> b

实际上,使用folds的约定是将函数参数放在第一位,所以我将在下面讨论foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b.

现在你的尝试

foldTree f Tip = Tip

缺少一个参数,结果类型也没有意义:Tip是一个树(-leaf),但你希望结果是简单的b.

在难以看清应该发生什么的情况下编写函数的好方法是让编译器帮助你.同样,foldTree有三个参数,所以一般来说它的定义应该有形式

foldTree q r t = _

t树在哪里,所以第一个子句就是

foldTree q r Tip = _

那么,你可以用这个"定义"实际呈现GHC(> = 7.8).这是它回复的内容:

Found hole ‘_’ with type: b
Where: ‘b’ is a rigid type variable bound by
           the type signature for
             foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
           at /tmp/wtmpf-file26763.hs:6:13
Relevant bindings include
  r :: b (bound at /tmp/wtmpf-file26763.hs:8:12)
  q :: b -> a -> b -> b (bound at /tmp/wtmpf-file26763.hs:8:10)
  foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
    (bound at /tmp/wtmpf-file26763.hs:8:1)
In the expression: _
In an equation for ‘foldTree’: foldTree q r Tip = _

所以,它想要一个类型的结果b.碰巧你有一个类型的值b,即r.所以这个条款的一个定义是

foldTree q r Tip = r

事实上,这是正确的定义,也是唯一可能的定义,因为此时你唯一的另一件事是函数q,但这需要一个a值来评估,你没有.

那么,让我们继续:

foldTree _ r Tip = r
foldTree q r (Node lsub x rsub) = _

给

Found hole ‘_’ with type: b
Where: ‘b’ is a rigid type variable bound by
           the type signature for
             foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
           at /tmp/wtmpf-file26763.hs:6:13
Relevant bindings include
  rsub :: Tree a (bound at /tmp/wtmpf-file26763.hs:9:27)
  x :: a (bound at /tmp/wtmpf-file26763.hs:9:25)
  lsub :: Tree a (bound at /tmp/wtmpf-file26763.hs:9:20)
  r :: b (bound at /tmp/wtmpf-file26763.hs:9:12)
  q :: b -> a -> b -> b (bound at /tmp/wtmpf-file26763.hs:9:10)
  foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
    (bound at /tmp/wtmpf-file26763.hs:8:1)
In the expression: _
In an equation for ‘foldTree’: foldTree q r (Node lsub x rsub) = _

好的,所以你需要一个b.你当然可以再次简单地返回r,但这意味着该功能只是忽略整个树.特别是,现在你有一个值x :: a可以传递给你q- 听起来像个好主意.q实际上有类型的结果b,所以让我们尝试使用它作为整个子句的结果.

q 有三个论点,我很懒,所以我会再次先打出打孔...

foldTree q r (Node lsub x rsub) = q _q? _q? _q?

给

Found hole ‘_q?’ with type: b
...
Found hole ‘_q?’ with type: a
...
Found hole ‘_q?’ with type: b
...
Relevant bindings include
  rsub :: Tree a (bound at /tmp/wtmpf-file26763.hs:9:27)
  x :: a (bound at /tmp/wtmpf-file26763.hs:9:25)
  lsub :: Tree a (bound at /tmp/wtmpf-file26763.hs:9:20)
  r :: b (bound at /tmp/wtmpf-file26763.hs:9:12)
  q :: b -> a -> b -> b (bound at /tmp/wtmpf-file26763.hs:9:10)
  foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
    (bound at /tmp/wtmpf-file26763.hs:8:1)

好吧,其中一个是明确的:我们有一个值x :: a,所以这是自然适合_q?.

foldTree q r (Node lsub x rsub) = q _q? x _q?

对于_q?,_q?我们需要再次输入类型的值b.我们原则上可以传递r给这两个,但这意味着我们仍然不使用子树lsub和rsub.我们怎么能用那些？嗯,提示中有一个功能就是吃树:foldTree.实际上它也会产生b结果.所以看起来我们需要递归调用.再次为缺少的参数使用漏洞:

foldTree q r (Node lsub x rsub)
        = q (foldTree _? _? lsub) x (foldTree _? _? rsub)

...

Found hole ‘_?’ with type: b -> a -> b -> b
...
Relevant bindings include
      q :: b -> a -> b -> b (bound at /tmp/wtmpf-file26763.hs:9:10)

啊哈,这导致我们

foldTree q r (Node lsub x rsub)
        = q (foldTree q _? lsub) x (foldTree _? _? rsub)

...

Found hole ‘_?’ with type: b

好的,现在我们已经使用了其他所有内容,所以我们不妨插入初始值.

foldTree q r (Node lsub x rsub)
        = q (foldTree q r lsub) x (foldTree _? _? rsub)

等等,只需填补GHC为您提供的正确类型的空白.