implement zip using foldr

Question

I'm currently on chapter 4 of Real World Haskell, and I'm trying to wrap my head around implementing foldl in terms of foldr.

(Here's their code:)

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

I thought I'd try to implement zip using the same technique, but I don't seem to be making any progress. Is it even possible?

Answer 1

zip using foldr?

You might be able to work something out. But you need to consume two lists with zip, right? So, it would be difficult with using nth and a value for the current location.

You traditionally write zip with map2.

Answer 2

I found a way using quite similar method to yours:

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Answer 3

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

How this works: (foldr step done xs) returns a function that consumes ys; so we go down the xs list building up a nested composition of functions that will each be applied to the corresponding part of ys.

How to come up with it: I started with the general idea (from similar examples seen before), wrote

zip2 xs ys = foldr step done xs ys

then filled in each of the following lines in turn with what it had to be to make the types and values come out right. It was easiest to consider the simplest cases first before the harder ones.

The first line could be written more simply as

zip2 = foldr step done

as mattiast showed.

Answer 4

For the non-native Haskellers here, I've written a Scheme version of this algorithm to make it clearer what's actually happening:

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

The foldr results in a function which, when applied to a list, will return the zip of the list folded over with the list given to the function. The Haskell hides the inner lambda because of lazy evaluation.

---

To break it down further:

Take zip on input: '(1 2 3) The foldr func gets called with

el->3, func->(lambda (a) empty)

This expands to:

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

If we were to return this now, we'd have a function which takes a list of one element and returns the pair (3 element):

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

Continuing, foldr now calls func with

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

This is a func which takes a list with two elements, now, and zips them with (list 2 3):

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

What's happening?

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

a, in this case, is (list 9 1)

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

And, as you recall, f zips its argument with 3.

And this continues etc...