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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
