CODEWITHSUNDEEP
haskelltree
swaroop
swaroop

Reputation: 77

how to define zip function over trees in haskell

data Tree a = Leaf a | Node (Tree a ) (Tree a)

I can't figure out how to write a tree version of zip and zipWith functions in Haskell.

Upvotes: 4

Views: 2006

Answers (1)

stephen tetley
stephen tetley

Reputation: 4493

Your tree does not allow well formed empty trees - you can make a dodgy one Node undefined undefined but this is not very good. As others have commented a simpleminded treeZip will need both trees to have the same shape to get a "good" result. 

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

Note that simpleminded tree zipping truncates on shape not just "length" (if shapes don't match it will truncate) - this is more severe than lists which truncate "on length" (strictly speaking lists do truncate on "shape" but the "shape" must always be the same).

For this reason if I was writing a Tree library I wouldn't define zipTree.

Upvotes: 7

Related Questions