[Haskell-cafe] Generalizing zip

Jason Dagit dagit at eecs.oregonstate.edu
Thu Nov 16 05:46:32 EST 2006


In #haskell on freenode we had a discussion about isPrefixOf, which is
probably implemented roughly as so:

isPrefixOf [] _ = True
isPrefixOf _ [] = False
isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys

Well, this is basically just a zip with a special base case.  But you
can't just write it with zipWith because zipWith stops when it exausts
either list.

How about we define zipWith'' like this:
zipWith'' _ []     _      l _ = [l]
zipWith'' _ _      []     _ r = [r]
zipWith'' f (x:xs) (y:ys) l r = f x y : zipWith'' f xs ys l r

Then we can write:
isPrefixOf xs ys = and (zipWith'' (==) xs ys True False)

A point free reduction might look like the following and probably
isn't worth it:
isPrefixOf = (and .) . flip flip False . flip flip True . zipWith'' (==)

Are there lots of other places where this zipWith'' would come in
handy?  It seems like I've found lots of times when I needed to
manually code the recursion because of the way zip behaves when it
exhausts one of its parameter lists.

Jason


More information about the Haskell-Cafe mailing list