haskell - 如何使用 `zipTree` 实现 `foldTree` ？

Question

你如何实现 zipTree，它的行为是这样的

1. 进行合并，tree1，tree2
2. 对于每对节点
   • 如果两者都有值(value)，则合并merger
   • 否则变成叶子

>>> :t zipTree
zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
>>> zipTree (+) (Branch 1 Leaf (Branch 2 Leaf Leaf)) (Branch 3 Leaf Leaf)
(Branch 4 Leaf Leaf)

使用下面定义的foldTree

data Tree a = Leaf | Branch a (Tree a) (Tree a) deriving (Show, Eq)

foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b
foldTree e _ Leaf     = e
foldTree e n (Branch a n1 n2) = n a (foldTree e n n1) (foldTree e n n2)

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f = foldTree Leaf (\x t1 t2 -> Branch (f x) t1 t2)

我只设法实现了不使用 foldTree 的自回溯版本

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree f Leaf _ = Leaf
zipTree f _ Leaf = Leaf
zipTree f (Branch aroot a1 a2) (Branch broot b1 b2) = Branch (f aroot broot) (zipTree f a1 b1) (zipTree f a2 b2)

我一直致力于在 tree1 上使用 foldTree 返回回调以对 tree2 进行操作，但无济于事

有人知道如何使用foldTree 来实现zipTree 吗？提前致谢!

Answer 1

从您的定义开始:

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree f Leaf _ = Leaf
zipTree f _ Leaf = Leaf
zipTree f (Branch aroot a1 a2) (Branch broot b1 b2) = Branch (f aroot broot) (zipTree f a1 b1) (zipTree f a2 b2)

让我们把大小写匹配分开:

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree f Leaf _ = Leaf
zipTree f (Branch aroot a1 a2) t2 =
  case t2 of
    Leaf -> Leaf
    Branch broot b1 b2 -> Branch (f aroot broot) (zipTree f a1 b1) (zipTree f a2 b2)

为清楚起见，让我们使用 lambda 将 zipTree 表示为两个参数的函数:

zipTree :: (a -> a -> b) -> Tree a -> (Tree a -> Tree b)
zipTree f Leaf = \ _ -> Leaf
zipTree f (Branch aroot a1 a2) = \ t2 ->
  case t2 of
    Leaf -> Leaf
    Branch broot b1 b2 -> Branch (f aroot broot) ((zipTree f a1) b1) ((zipTree f a2) b2)

这是否有助于指出使用 foldTree 实现它的方法？我已经暗示性地用括号括起来了。

---

在评论中，你写道

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree f atree btree = g btree
 where
   g = foldTree (const Leaf) callback atree
   callback aroot fWithA1 fWithA2 b =
     case b of
       Leaf -> Leaf
       (Branch broot b1 b2) -> Branch (f aroot broot) (fWithA1 b1) (fWithA2 b2)

让我们看看是否可以使它更具可读性。

首先，我们可以在其调用位置内联 g:

zipTree f atree btree = foldTree (const Leaf) callback atree btree

接下来，我们可以抛开atree和btree的显式抽象和应用:

zipTree f = foldTree (const Leaf) callback

下一步纯粹是一个约定问题:在 Haskell 代码中，像 callback 这样的主要工作函数往往被命名为 go。在折叠的上下文中，我有时会调用“we're done”函数(这里是const Leaf)作为对比，stop。让我们停下来把这些都放在适当的位置:

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree f = foldTree (const Leaf) go
  where
    go aroot fWithA1 fWithA2 b =
      case b of
        Leaf -> Leaf
        (Branch broot b1 b2) -> Branch (f aroot broot) (fWithA1 b1) (fWithA2 b2)

这里的最后一点也是一个品味问题。当 b 是叶子时，您不会使用 go 的任何其他参数，所以我认为如果您在多行中定义函数(无论你怎么调用它们)而不是使用 case 表达式。

zipTree :: (a -> a -> b) -> Tree a -> Tree a -> Tree b
zipTree f = foldTree (const Leaf) go
  where
    go _ _ _ Leaf = Leaf
    go aroot fWithA1 fWithA2 (Branch broot b1 b2) =
      Branch (f aroot broot) (fWithA1 b1) (fWithA2 b2)

这并不比您的版本更正确、更有效。我认为它看起来更容易一些，但您应该使用您认为最容易理解的任何一个。

---

我刚刚注意到您的定义具有比它需要的更具体的类型。这降低了它的用处，也降低了编译器在其实现中检测错误的能力。具体来说，您需要两个参数树具有相同类型的元素。让我们概括一下:

zipTree :: (a -> b -> c) -> Tree a -> Tree b -> Tree c
zipTree f = foldTree (const Leaf) go
  where
    go _ _ _ Leaf = Leaf
    go aroot fWithA1 fWithA2 (Branch broot b1 b2) =
      Branch (f aroot broot) (fWithA1 b1) (fWithA2 b2)

我个人会在可读性方面更进一步，使用作用域类型变量为 go 提供类型签名。

-- This line goes at the very top of the file.
{-# language ScopedTypeVariables #-}

zipTree :: forall a b c. (a -> b -> c) -> Tree a -> Tree b -> Tree c
zipTree f = foldTree (const Leaf) go
  where
    go :: a -> (Tree b -> Tree c) -> (Tree b -> Tree c) -> Tree b -> Tree c
    go _ _ _ Leaf = Leaf
    go aroot fWithA1 fWithA2 (Branch broot b1 b2) =
      Branch (f aroot broot) (fWithA1 b1) (fWithA2 b2)