haskell - 如何折叠一棵树而不使其成为 Foldable 的实例？

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

我试过这样的方法，但我认为它行不通，因为 Tree 不是幺半群:

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

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

现在你的尝试

foldTree f Tip = Tip

缺少参数，结果类型也没有意义:Tip 是一棵树(-叶)，但您希望结果只是 b.

在您难以看到应该发生的情况下编写函数的一个好方法是让编译器帮助您。同样，foldTree 有三个 个参数，所以通常它的定义应该有以下形式

foldTree q r t = _

t 是树，所以第一个子句是

foldTree q r Tip = _

嗯，you can actually present GHC (>= 7.8) with this “definition” .这是它的回复:

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，但这需要一个一个要评估的值，你没有。

那么，让我们继续:

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 为您提供的正确类型来填补空白即可。