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.

Answer 2

Another Clojure expert pointed out that it's easier to do this in Clojure without trying to use the same structure as Haskell's foldr solution:

(defn zip [xs ys]
  (first (reduce
          (fn [[acc rest :as state] itm]
            (if rest
              [(conj acc [itm (first rest)])
               (next rest)]
              state))
          [[] (seq ys)]
          xs)))

This just folds over a pair, the first of which is a result sequence being built up, and the second is what remains of ys; xs are being fed in one item at a time via the reduce. In Haskell this would look like:

zip' :: [a] -> [b] -> [(a,b)]
zip' xs ys = fst $ foldl f ([], ys) xs
  where f state@(_, []) _x = state
        f (acc, (y:ys)) x = ((acc ++ [(x, y)]), ys)

except that of course the acc ++ [(x, y)] is much more reasonable in Clojure than in Haskell, since it's efficient.

Answer 3

Simply implement

reverse = foldl (flip (:)) []

and apply it to the second list.

Answer 4

These two solutions are both of the form (-> (reduce f init x) something) rather than just (reduce f init x). Both carry along a container with the accumulated sequence and a some extra state, then extract the sequence from the container. In one case the container is a closure, in the other a vector.

If you want "just" (reduce f init x) then recognize that you already have all the state you need in the accumulated sequence itself -- its length.

(defn zip* [xs ys] 
  (let [xs (vec xs)
        f (fn [a y]
            (if (contains? xs (count a))
              (conj a [(xs (count a)) y])
              a))]
    (reduce f [] ys)))