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

Question

data Tree a = Leaf a | Node (Tree a ) (Tree 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。