[Haskell-cafe] Generalizing zip

[Bjorn Bringert]

On 16 nov 2006, at 11.46, Jason Dagit wrote:

> 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.

I needed something like this just the other day. I think that it  
could be made more general:

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

Now zipWith is a special case of zipWith'':

 > zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
 > zipWith f xs ys = zipWith'' f xs ys (const []) (const [])

Though isPrefixOf becomes a bit more complex:

 > isPrefixOf :: Eq a => [a] -> [a] -> Bool
 > isPrefixOf xs ys = and (zipWith'' (==) xs ys (const [True]) (const  
[False]))

/Björn