On Barron and Strachey's Cartesian Product Function

Authors

  • Olivier Danvy
  • Michael Spivey

DOI:

https://doi.org/10.7146/brics.v14i14.21934

Abstract

Over forty years ago, David Barron and Christopher Strachey published a startlingly elegant program for the Cartesian product of a list of lists, expressing it with a three nested occurrences of the function we now call foldr. This program is remarkable for its time because of its masterful display of higher-order functions and lexical scope, and we put it forward as possibly the first ever functional pearl. We first characterize it as the result of a sequence of program transformations, and then apply similar transformations to a program for the classical power set example. We also show that using a higher-order representation of lists allows a definition of the Cartesian product function where foldr is nested only twice.

Downloads

Published

2007-07-12

How to Cite

Danvy, O., & Spivey, M. (2007). On Barron and Strachey’s Cartesian Product Function. BRICS Report Series, 14(14). https://doi.org/10.7146/brics.v14i14.21934