Exercise 7.4

It’s not clear what the action of zip should be on trees with data only at the leaves: if the two trees are mismatched, what should the zipped tree look like? So it is easier to define zipWith on an InternalTree, and of course to define zip in terms of zipWith.

zipWithInternalTree :: (a -> b -> c) -> InternalTree a
                    -> InternalTree b -> InternalTree c
zipWithInternalTree f ILeaf _ = ILeaf
zipWithInternalTree f _ ILeaf = ILeaf
zipWithInternalTree f (IBranch a x y) (IBranch b i j)
    = IBranch (f a b) x' y'
      where x' = (zipWithInternalTree f x i)
            y' = (zipWithInternalTree f y j)
 
zipInternalTree :: InternalTree a -> InternalTree b -> InternalTree (a,b)
zipInternalTree x y = zipWithInternalTree (,) x y

One Response to “Exercise 7.4”

  1. Internal and othe trees:
    >zipWithIT f (IBranch x l1 r1) (IBranch y l2 r2) =
    > IBranch (f x y) (zipWithIT f l1 l2) (zipWithIT f r1 r2)
    >zipWithIT _ _ _ = ILeaf
    >
    >zipWithT f (Leaf a) (Leaf b) = Leaf (f a b)
    >zipWithT _ (Branch _ _) (Leaf _) = error “unzipable trees”
    >zipWithT _ (Leaf _) (Branch _ _) = error “unzipable trees”
    >zipWithT f (Branch l1 r1) (Branch l2 r2) =
    > Branch (zipWithT f l1 l2) (zipWithT f r1 r2)
    >
    >
    >zipWithFT f (FBranch x l1 r1) (FBranch y l2 r2) =
    > FBranch (f x y) (zipWithFT f l1 l2) (zipWithFT f r1 r2)
    >zipWithFT f (FLeaf x ) (FBranch y l r) = FLeaf (f x y)
    >zipWithFT f (FBranch y l r) (FLeaf x ) = FLeaf (f x y)
    >zipWithFT f (FLeaf y) (FLeaf x ) = FLeaf (f x y)
    >
    >zipT = zipWithT (,)
    >zipIT = zipWithIT (,)
    >zipFT = zipWithFT (,)

Leave a Reply