There and back again

From There and Back Again by Danvy and Goldberg (via Lambda the Ultimate):

Computing a Symbolic Convolution

Given two lists [x₁,x₂,...,x_n-1,x_n] and [y₁,y₂,...,y_n-1,y_n], where n is not known in advance, write a function that constructs

[(x₁,y_n),(x₂,y_n-1),...,(x_n-1,y₂),(x_n,y₁)]

in n recursive calls and with no auxiliary list.

Their direct style solution uses a generalization convolve' that produces the convolution of two lists where the first list may be shorter than the second, as well as the extra prefix of the second list. I've written it here in pseudo-Haskell with dependent type annotations representing the lengths of the lists:

convolve' :: [a]m → [b]n → ([(a,b)]m, [b]n-m)   -- n ≥ m
convolve' [] ys = ([], ys)
convolve' (x:xs) ys =
   let (r, (y:ys')) = convolve' xs ys in
     ((x,y):r, ys')

convolve :: [a]n → [b]n → [(a,b)]n
convolve xs ys = r where (r, []) = convolve' xs ys

What it's doing is recurring down the first list until it hits the end and then pairing up the elements as it returns; whatever elements are leftover from the beginning of the second list get placed in the second "return register."

The other solution uses a similar generalization, but in CPS:

convolve' :: [a]m → [b]n → ([(a,b)]m → [b]n-m → c) → c   -- n ≥ m
convolve' [] ys k = k [] ys
convolve' (x:xs) ys k =
   convolve' xs ys (λr (y:ys') . k ((x,y):r) ys')

convolve :: [a]n → [b]n → [(a,b)]n
convolve xs ys = convolve' xs ys (λr [] . r)

Same thing, really. The interesting part isn't the direct style vs. CPS, but rather the discovery of the invariant, i.e., the generalization of the problem. Once we know to write a function that a) allows the first list to be shorter than the second, and b) produces both the partial solution and the remaining elements of the second list, the rest is actually not so challenging.

Update: No, no, no... I described the purpose of convolve' wrong. It produces a pair containing 1) the convolution of a given suffix of the original first list with the corresponding prefix of the second list, and 2) the remaining suffix of the second list.