Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-12T04:20:59.272Z Has data issue: false hasContentIssue false
  • English
  • Français

Countdown: A case study in origami programming

Published online by Cambridge University Press:  18 August 2005

RICHARD BIRD  and
SHIN-CHENG MU
RICHARD BIRD
Affiliation:
Programming Research Group, Oxford University, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
SHIN-CHENG MU
Affiliation:
Department of Information Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Countdown is the name of a game in which one is given a list of source numbers and a target number, with the aim of building an arithmetic expression out of the source numbers to get as close to the target as possible. Starting with a relational specification we derive a number of functional programs for solving Countdown. These programs are obtained by exploiting the properties of the folds and unfolds of various data types, a style of programming Gibbons has aptly called origami programming. Countdown is attractive as a case study in origami programming both as an illustration of how different algorithms can emerge from a single specification, as well as the space and time trade-offs that have to be taken into account in comparing functional programs.

Type
Article
Information
Journal of Functional Programming , Volume 15 , Issue 5 , September 2005 , pp. 679 - 702
Copyright
2005 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.