haskell - 如何在haskell中定义树上的zip函数

Question

数据树 a = 叶 a |节点(树a)(树a)

我不知道如何在 Haskell 中编写 zip 和 zipWith 函数的树版本。

Answer 1

你的树不允许结构良好的空树 - 你可以制作一个狡猾的Node undefined undefined但这不是很好。正如其他人评论的那样，头脑简单的 treeZip 需要两棵树具有相同的形状才能获得“良好”的结果。

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

请注意，头脑简单的树压缩不仅仅在“长度”上截断(如果形状不匹配，它将截断) - 这比“在长度”上截断的列表更严重(严格来说，列表会在“形状”上截断)但“形状”必须始终相同)。

因此，如果我正在编写一个 Tree 库，我不会定义 zipTree。