CODEWITHSUNDEEP
haskell
Charly Ríos
Charly Ríos

Reputation: 3

How can zipWith be implemented with foldr?

I am learning haskell and I need to define zipWith function using foldr.

I can do it using pattern matching and recursion, but that doesn't work for me at the moment. For example:

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

I also understand how folds work, but I can't really think of how I can use them to define zipWith.

From already thank you very much.

Upvotes: 0

Views: 646

Answers (3)

oisdk
oisdk

Reputation: 10091

If you only want to do a foldr on one of the lists, then this isn't too difficult and one of the other answers will help you.

However, if you want to use foldr on both, this is actually quite a difficult question, and one that was thought to not be possible for quite a while!

We can do it with the following bizarre type:

data Hyp a b = Hyp { invoke :: Hyp b a -> b }

This is the type of hyperfunctions from a to b. Here's how it can be used to zip:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith c xs ys = invoke (foldr xf xb xs) (foldr yf yb ys)
  where
    xf x xk = Hyp (\yk -> invoke yk xk x)
    xb = Hyp (\_ -> [])

    yf y yk = Hyp (\xk x -> c x y : invoke xk yk)
    yb = Hyp (\_ _ -> [])

If you want to read more about the problem look here.

Upvotes: 1

SergeyKuz1001
SergeyKuz1001

Reputation: 875

You can define zipWith' using foldr like so:

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = fst $ foldr go ([], reverse xs) ys where
    go _ (res, []) = (res, [])
    go y (res, z:zs) = (f z y : res, zs)

Upvotes: 0

chi
chi

Reputation: 116139

To use foldr, you need to rewrite your definition in an equivalent way so that it has this form:

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f = go
    where
    go []     = someConstant
    go (x:xs) = someFunction x (go xs)

Indeed, that is equivalent to zipWith' f = foldr someFunction someConstant.

We need the second list argument, so let's add it as a lambda. The "constant" we met above is actually a function of the second list, since that's the only way to obtain the wanted type:

    go []     = \ _list -> []   -- first case complete
    go (x:xs) = \ list  ->
        somehowUse x (go xs) list

Now we can pattern match on list

    go []     = \ _list -> []   -- first case complete
    go (x:xs) = \ list  -> case list of
        []     -> ...
        (y:ys) -> ...

and now we can follow the original code.

Can you see how to proceed now?

Upvotes: 2

Related Questions