|
We systematically develop a functional program that solves the countdown problem, a numbers game in which the aim is to construct arithmetic expressions satisfying certain constraints. Starting from a formal specification of the problem, we present a simple but inefficient program that solves the problem, and prove that this program is correct. We then use program fusion to calculate an equivalent but more efficient program, which is then further improved by exploiting arithmetic properties.
This is quite fun, since the original program is quite declerative, and the speed improvements are impressive (the program is more than 20 times faster after the first optimization, and more than 7 time faster than that after the second round of optimization).
Since the program solves a fun numbers game, this is quite motivating.
The Haskell source code is available.
Posted to functional by Ehud Lamm on 10/8/01; 4:31:21 AM
|
|
The countdown problem
