Book icon

Book

Origami Programming

Abstract:
One style of functional programming is based purely on recursive equations. Such equations are easy to explain, and adequate for any computational purpose, but hard to use well as programs get bigger and more complicated. In a sense, recursive equations are the `assembly language' of functional programming, and direct recursion the goto. As computer scientists discovered in the 1960s with structured programming, it is better to identify common patterns of use of such too-powerful tools, and capture these patterns as new constructions and abstractions. In functional programming, in contrast to imperative programming, we can often express the new constructions as higher-order operations within the language, whereas the move from unstructured to structured programming entailed the development of new languages.

In this chapter we will look at folds and unfolds as abstractions. In a precise technical sense, folds and unfolds are the natural patterns of computation over recursive datatypes; unfolds generate data structures and folds consume them. Functional programmers are very familiar with the foldr function on lists, and its directional dual foldl; they are gradually coming to terms with the generalisation to folds on other datatypes. The computational duals, unfolds, are still rather unfamiliar; we hope to show here that they are no more complicated than, and just as useful as, folds, and to promote a style of programming based on these and similar recursion patterns.

Actions

Access Document

Files:
Publisher copy:
10.1007/978-1-349-91518-7_3

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author

Contributors

Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Editor
Role:
Editor


Host title:
The Fun of Programming
Pages:
41-60
Publication date:
2003-01-01
DOI:
ISBN:
1403907722


UUID:
uuid:b86dbc7f-f5aa-4ffd-a711-bfc8f75aa4f2
Local pid:
cs:2335
Deposit date:
2015-03-12
ARK identifier:

Terms of use


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP