<p>The problem with all these solutions for <code>zip</code> is that they only fold over one list or the other, which can be a problem if both of them are "good producers", in the parlance of list fusion. What you actually need is a solution that folds over both lists. Fortunately, there is a paper about exactly that, called <a href="https://arxiv.org/pdf/1309.5135.pdf" rel="noreferrer">"Coroutining Folds with Hyperfunctions"</a>.</p>

<p>You need an auxiliary type, a hyperfunction, which is basically a function that takes another hyperfunction as its argument.</p>

<pre><code>newtype H a b = H { invoke :: H b a -&gt; b }
</code></pre>

<p>The hyperfunctions used here basically act like a "stack" of ordinary functions.</p>

<pre><code>push :: (a -&gt; b) -&gt; H a b -&gt; H a b
push f q = H $ \k -&gt; f $ invoke k q
</code></pre>

<p>You also need a way to put two hyperfunctions together, end to end.</p>

<pre><code>(.#.) :: H b c -&gt; H a b -&gt; H a c
f .#. g = H $ \k -&gt; invoke f $ g .#. k
</code></pre>

<p>This is related to <code>push</code> by the law:</p>

<pre><code>(push f x) .#. (push g y) = push (f . g) (x .#. y)
</code></pre>

<p>This turns out to be an associative operator, and this is the identity:</p>

<pre><code>self :: H a a
self = H $ \k -&gt; invoke k self
</code></pre>

<p>You also need something that disregards everything else on the "stack" and returns a specific value:</p>

<pre><code>base :: b -&gt; H a b
base b = H $ const b
</code></pre>

<p>And finally, you need a way to get a value out of a hyperfunction:</p>

<pre><code>run :: H a a -&gt; a
run q = invoke q self
</code></pre>

<p><code>run</code> strings all of the <code>push</code>ed functions together, end to end, until it hits a <code>base</code> or loops infinitely.</p>

<p>So now you can fold both lists into hyperfunctions, using functions that pass information from one to the other, and assemble the final value.</p>

<pre><code>zip xs ys = run $ foldr (\x h -&gt; push (first x) h) (base []) xs .#. foldr (\y h -&gt; push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)
</code></pre>

<p>The reason why folding over both lists matters is because of something GHC does called <em>list fusion</em>, which is talked about in <a href="http://hackage.haskell.org/package/base-4.9.0.0/docs/src/GHC.Base.html#build" rel="noreferrer">the GHC.Base module</a>, but probably should be much more well-known. Being a good list producer and using <code>build</code> with <code>foldr</code> can prevent lots of useless production and immediate consumption of list elements, and can expose further optimizations.</p>
Implement zip using foldr
<p>I'm currently on chapter 4 of Real World Haskell, and I'm trying to wrap my head around <a href="http://book.realworldhaskell.org/read/functional-programming.html#x_E9" rel="noreferrer">implementing foldl in terms of foldr</a>.</p>

<p>(Here's their code:)</p>

<pre><code>myFoldl :: (a -&gt; b -&gt; a) -&gt; a -&gt; [b] -&gt; a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)
</code></pre>

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