CODEWITHSUNDEEP
haskellbinary-tree
user6137776
user6137776

Reputation:

zipWith for trees in Haskell

I am learning Haskell using The Haskell School of Expression: Learning Functional Programming through Multimedia and I am unsure how to go about solving this exercise.

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.

For zip I have this but I am unsure if it is "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

And I am unsure how to adapt it to have zipWith functionality although I do know a elegant definition of zipWith.

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

Upvotes: 2

Views: 1245

Answers (1)

Bakuriu
Bakuriu

Reputation: 101909

First of all I believe your solution is not elegant because you are using undefined. You want to avoid partial functions, and structures, as much as possible and simply inserting some Node undefined undefined in a tree structure doesn't sound like a good idea.

Think about this: once you have a Node undefined undefined how would it act with the other operations on the tree? You'd probably get tons of exceptions.

So you have to find an alternative. 

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

Now how should x and y be defined? x should depend on l and Leaf a while y should depend on r and Leaf a.

The easiest way to define this case is to simply perform the recursive calls:

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

So we are zipping all leafs in the l and r subtrees with the leaf a.

As for the zipWithTree: that's easy. You have to add an f parameter and use f x y instead of (x, y) when you perform the zipping, which is done only in the Leaf v Leaf case:

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

Obviously you have to add the f parameter to all the rules and pass f to recursive calls.

Note that there is also an other way to define zipWith, which is:

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

This still isn't a good solution because it introduces an undefined however it has some advantages against the Node undefined undefined solution:

  1. It acts for similarly to zip from lists. zip [1,2] [1,2,3,4] == [(1,1), (2,2)] so you stop when the shorter list ends.

  2. The undefined is inside the value. This allows for example to have:

    mapTree snd (zipTree x y) == y

    whenever x has longer branches. Using Node undefined undefined you have mapTree f (zipTree x y) is always an exception whenever the trees aren't isomorphic (because mapTree will try to evaluate undefined).

Upvotes: 5

Related Questions