On Barron and Strachey's cartesian product function

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.

• Publication year

  2007

• Venue

  ACM SIGPLAN International Conference on Functional Programming

• Publication date

  2007-07-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1291151.1291161
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A complete, co-inductive syntactic theory of sequential control and state

  2007cited by this paper
• A Simple Application of Lightweight Fusion to Proving the Equivalence of Abstract Machines

  2007cited by this paper
• Analyzing Ambiguity of Context-Free Grammars

  2007cited by this paper
• On the Existence of a Finite Base for Complete Trace Equivalence over BPA with Interrupt

  2007cited by this paper
• On one-pass CPS transformations

  2007cited by this paper
• Optimal Resilient Dynamic Dictionaries

  2007cited by this paper
• The Saga of the Axiomatization of Parallel Composition

  2007cited by this paper
• On Barron and Strachey's cartesian product function

  2007cited by this paper
• Refunctionalization at work

  2006cited by this paper
• Defunctionalization at work

  2001cited by this paper
• Cambridge and CPL in the 1960s

  2000cited by this paper
• Christopher Strachey and the Cambridge CPL Compiler

  2000cited by this paper
• Christopher Strachey: Recollections of His Influence

  2000cited by this paper
• Lambda-dropping: transforming recursive equations into programs with block structure

  1997cited by this paper
• Attribute grammars as a functional programming paradigm

  1987cited by this paper
• A Novel Representation of Lists and its Application to the Function "reverse"

  1986cited by this paper
• On the Power of List Iteration

  1979cited by this paper
• Christopher Strachey: a personal reminiscence

  1975cited by this paper

• On the Correctness of Barron and Strachey's Cartesian Product Function

  2025cites this paper
• Program Synthesis Using Example Propagation

  2022cites this paper
• From Curry to Haskell

  2020influential citation
• Folding left and right over Peano numbers

  2019cites this paper
• Automated synthesis of data extraction and transformation programs

  2017cites this paper
• Deriving Pure , Naturally-Recursive Operations for Processing Tail-Aligned Lists

  2016cites this paper
• Synthesizing data structure transformations from input-output examples

  2015influential citation
• A Study of Syntactic and Semantic Artifacts and its Application to Lambda Definability, Strong Normalization, and Weak Normalization in the Presence of...

  2008cites this paper
• Dynamic normal forms and dynamic characteristic polynomial

  2008cites this paper
• Inter-deriving semantic artifacts for object-oriented programming

  2008cites this paper
• An Investigation of Abadi and Cardelli's Untyped Calculus of Objects

  2008cites this paper
• Control-flow analysis of functional programs

  2007cites this paper
• On the equivalence between small-step and big-step abstract machines: a simple application of lightweight fusion

  2007cites this paper
• Refunctionalization at work

  2006cites this paper
• From Curry to Haskell (cid:63) Paths to abstraction in programming languages

  year unknowncites this paper