Haskell 中的树的 zipWith

Question

我正在学习 Haskell 使用 Haskell 表达学派：通过多媒体学习函数式编程，我不确定如何着手解决这个练习。

Using the definition of trees given by
data Tree a = Node (Tree a) (Tree a) | Leaf a
Define tree versions of the list functions zip and zipWith. There will be cases at the leaves or where trees are of different shapes where you’ll have to make design decisions. Try to make your decisions as elegant as possible.

对于 zip 我有这个但我不确定它是否 "elegant"

zipTree :: Tree a -> Tree b -> Tree (a,b)
zipTree (Leaf a)     (Leaf b)     = Leaf (a,b)
zipTree (Node l1 r1) (Node l2 r2) = 
  let l = zipTree l1 l2
      r = zipTree r1 r2 
  in Node l r 

-- Problems...
zipTree (Node _ _)  (Leaf _)   = Node undefined undefined
zipTree (Leaf _)    (Node _ _) = Node undefined undefined

虽然我知道 zipWith 的优雅定义，但我不确定如何使其具有 zipWith 功能。

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []

Answer 1

首先，我认为您的解决方案并不优雅，因为您使用的是 undefined。您希望尽可能避免偏函数和结构，简单地在树结构中插入一些 Node undefined undefined 听起来不是个好主意。

想一想：一旦你有一个 Node undefined undefined 它将如何与树上的其他操作一起使用？您可能会遇到大量异常。

所以你必须找到替代方案。

zipTree (Node l r) (Leaf a) = Node x y
    where
        x = ... ? 
        y = ... ?

现在x和y应该怎么定义呢？ x 应该依赖于 l 和 Leaf a 而 y 应该依赖于 r 和 Leaf a。

定义这种情况的最简单方法是简单地执行递归调用：

zipTree (Node l r) a@(Leaf _) = Node (zipTree l a) (zipTree r a)

因此我们将 l 和 r 子树中的所有叶子与叶子 a.

压缩

至于zipWithTree：那很简单。您必须添加一个 f 参数并在执行压缩时使用 f x y 而不是 (x, y)，这仅在 Leaf v Leaf 情况下完成：

zipWithTree f (Leaf a) (Leaf b) = Leaf $ f a b

显然你必须将 f 参数添加到所有规则并将 f 传递给递归调用。

注意还有一种定义zipWith的方式，就是：

zipTree (Node _ _) (Leaf a) = Leaf (undefined, a)

这仍然不是一个好的解决方案，因为它引入了 undefined 但是它相对于 Node undefined undefined 解决方案有一些优势：

它的作用类似于列表中的 zip。 zip [1,2] [1,2,3,4] == [(1,1), (2,2)] 所以当较短的列表结束时你就停止了。
undefined是里面的值。这允许例如有：
```
mapTree snd (zipTree x y) == y
```
只要 x 有更长的分支。使用 Node undefined undefined 你有 mapTree f (zipTree x y) 是总是只要树不是同构的（因为 mapTree 将尝试评估 undefined ).

Haskell 中的树的 zipWith

zipWith for trees in Haskell

binary-tree

haskell