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