如何折叠一棵树而不使其成为 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

其实folds的约定是把函数参数放在第一位，所以我会在下面讨论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，但这需要一个a 要评估的值，其中您有 none.

所以，让我们继续：

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。您当然可以再次简单地 return 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 为您提供的正确类型来填补空白即可。

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

How to fold a tree without making it an instance of Foldable?

haskell

tree

functional-programming

fold