Haskell; functional programming (9.25.24)
A question- is it possible to reverse a functional list, then zip it with another list, in one pass? In Haskell, a solution to this problem looks something like this:
zipRev = foldl f b
where b = const []
f z x = \case
[] -> []
(y:ys) -> (x,y) : z ys
Note that this requires the LambdaCase extension.
The function is a pretty elegant application of foldl, but I don't think its implementation is intuitively obvious - which begs the question of how one might come up with it from scratch.
Defining zip in terms of foldr and some folding function g is a potentially fruitful start,
since foldl (flip g) can be loosely thought of as folding the first input list in "reverse".
zip = foldr g b implies that zip xs = foldr g b xs.
Thus, zip [] = b by the definition of foldr, meaning that b = \ys -> [] or const [] based on the semantics of zip.
At the same time, zip (x:xs) = g x (foldr g b xs), meaning that zip (x:xs) ys = g x (foldr g b xs) ys.
This tells us that our folding function g takes the head of xs, the result of folding its tail, and ys as arguments and returns a zipped list. Remembering that
folding its tail yields a function that zips its tail with whatever list you apply it to, we can straightforwardly define g as:
g x z = \case
[] -> []
(y:ys) -> (x,y) : z ys
Now, foldl (flip g) b builds up a thunk such that the outermost application of flip g is partially applied to the last element of xs,
before being applied to ys. This is the behavior we want - the elements of xs are being paired up with the elements of ys in reverse order!
With this in mind, we can define f = flip g and zipRev = foldl f b.