Monday, June 06, 2005

There and back again

From There and Back Again by Danvy and Goldberg (via Lambda the Ultimate):
Computing a Symbolic Convolution

Given two lists [x1,x2,...,xn-1,xn] and [y1,y2,...,yn-1,yn], where n is not known in advance, write a function that constructs


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.


Billy Mark said...

Positive web page source, where did u come up with the information on this posting? I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work.

Unknown said...

Our Company is a leading tech support brand which renders non-stop support to its consumers and businesses across the globe. Since our humble beginning, we have primarily focused on making technology simpler for the world by delivering turnkey technical support solutions for computers and peripherals.

Online Technichal Support...
TomTom Update

Activate AVG Antivirus said...

Activate avg on your mac and pc.
When you activate avg antivirus, it protects your device from unwanted threats and spywares.

Below mentioned are the services provided by avg activation

avg activation code

avg activation page

avg retail activation

avg ultimate activation

Install Kaspersky with activation code said...

install kaspersky with activation code | How to install and activate kaspersky on multiple computers

• Each copy of a multiple-device license for Kaspersky Anti-Virus 2019 (for example, a 3 PCs license) is installed and activated in the same way on all computers you want to protect.
• In conclusion to activate Kaspersky Internet Security 2016 on all computers, use one and the same activation code you purchased.

Install Kaspersky with activation code

activate kaspersky internet security

kaspersky geek squad download install

Activate Kaspersky Internet Security for Mac

reinstall kaspersky total security

kaspersky without cd

ginareeese49 said...

TomTom is a location technology specialist who uses unique technologies to navigate people to their destination with the help of GPS MAP. The continuous TomTom update is available for latest advancement so that user can get safer driver over any of place. |
tomtom get started | |

Stone Supplier Edmonton said...

We understand the demands of the industry. That’s why we work tirelessly to ensure you have an efficient and smooth Stone Supplier Edmonton
Stone Supplier Edmonton

Eva Wilson said...

We pioneer in providing research and analytical tutorial assistance to all doctoral candidates. Our highly qualified research team will assist you all throughout your thesis.

Online Thesis Help

jackpeterson said...

Hi! this is nice article you shared with great information. Thanks for giving such a wonderful informative information. Do check
Telstra email login