haskell - zipWith 用于 Haskell 中的树

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 我有这个，但我不确定它是否“优雅”

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 ，它会如何与树上的其他操作一起操作？您可能会遇到大量异常(exception)情况。

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

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

现在应该如何定义x和y？ x 应该依赖于 l 和 Leaf a 而 y 应该依赖于 r 和留下一个。

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

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 解决方案有一些优势:

1. 它的作用类似于列表中的zip。 zip [1,2] [1,2,3,4] == [(1,1), (2,2)] 这样你就可以在较短的列表结束时停止。

2. 未定义位于该值的内部。例如，这允许:

   mapTree snd (zipTree x y) == y
   

   每当x有更长的分支时。使用 Node undefined undefined 你有 mapTree f (zipTree x y) 每当树不是同构时总是一个异常(因为 mapTree 将尝试评估undefined)。