Computing a Symbolic ConvolutionTheir 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:

Given two lists [x_{1},x_{2},...,x_{n-1},x_{n}] and [y_{1},y_{2},...,y_{n-1},y_{n}], where n is not known in advance, write a function that constructs

[(x_{1},y_{n}),(x_{2},y_{n-1}),...,(x_{n-1},y_{2}),(x_{n},y_{1})]

in n recursive calls and with no auxiliary list.

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."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

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

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.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)

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.

## No comments:

Post a Comment