How to implement zip with foldl (in an eager language)

Question

A Clojure programmer I know recently remarked that it's possible to implement lots of sequence functions in terms of Clojure's reduce (which is Haskell's foldl'), but that regrettably there's no way to implement (map list xs ys) (which is Haskell's zip) with just reduce.

Now, I've read about the universality of folds, so I'm pretty sure this isn't true: certainly zip is possible with foldr, and I'd be surprised if it weren't possible with foldl. For purposes of this discussion we're ignoring the problems of the eagerness of foldl compared to foldr: imagine we have unlimited memory and only work with finite sequences.

So, I took the Haskell code to implement zip with foldr, and translated it to Clojure, doing my best to adjust for the difference between foldr and foldl:

(defn zip [xs ys]
  (letfn [(done [_] [])
          (step [z x]
            (fn [ys]
              (if (empty? ys)
                []
                (conj (z (rest ys)) [x (first ys)]))))]
    ((reduce step done xs) ys)))
user> (zip [1 2] '[a b c]) ;=> [[1 b] [2 a]]

And indeed we do get pairs of elements from xs and ys tupled together, but out of order: the first element of xs is paired with the last element of ys, and so on down the line. I can kinda see the cause of the problem: the function we produce consumes ys starting from the left, but the outermost closure (which is called first) has closed over the last element of xs, so it can't pair them in the right order.

I think the fix is to somehow build the closures inside-out, but I can't really see how to do it. I would happily accept a solution in either Haskell or Clojure.

I'm hoping for a solution of the form zip = foldl f x, so that I can say it's "just" a reduce. Of course I can reverse one of the lists, but then it ends up looking like zip xs ys = foldl f x xs $ reverse ys which doesn't seem very satisfying or clean.

Answer 1

In Haskell:

-- foldr f z xs == foldl (\r x a-> r (f x a)) id xs z

zip1 xs ys = -- foldr f (const []) xs ys
            foldl (\r x a-> r (f x a)) id xs (const []) ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

Prelude> zip1 [1..9] [100..120]
[(1,100),(2,101),(3,102),(4,103),(5,104),(6,105),(7,106),(8,107),(9,108)]

Since Clojure likes appending at the end of list, another variant is

zip2 xs ys = foldl f (const []) xs ys
  where
    f r x [] = []
    f r x ys = let (ys0,y) = (init ys, last ys) -- use some efficient Clojure here
               in r ys0 ++ [(x,y)]

Prelude> zip2 [1..9] [100..120]
[(1,112),(2,113),(3,114),(4,115),(5,116),(6,117),(7,118),(8,119),(9,120)]

As you can see the end of lists lines up here, instead of the front.