Open AccessOn Barron and Strachey's Cartesian Product Function
Author(s) -
Olivier Danvy,
Michael Z. Spivey
Publication year - 2007
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v14i14.21934
Subject(s) - cartesian product , function (biology) , representation (politics) , computer science , pearl , sequence (biology) , set (abstract data type) , programming language , scope (computer science) , power set , order (exchange) , product (mathematics) , cartesian coordinate system , power (physics) , mathematics , arithmetic , algebra over a field , pure mathematics , discrete mathematics , philosophy , quantum mechanics , physics , law , theology , genetics , biology , geometry , evolutionary biology , political science , finance , politics , economics
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.