Tony Hoare famously observed in his Notes on Data Structuring in 1972 that “there are certain close analogies between the methods used for structuring data and the methods for structuring a program which processes that data”. A few years later in 1975, Fred Brooks wrote in The Mythical Man-Month: “Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.” In the same year, Michael Jackson wrote in Principles of Program Design that “data provides a model of the problem environment, and by basing our program structures on data structures we ensure that our programs will be intelligible and easy to maintain.”

This may be old news, but it is still good news. Today, we see it in higher-order functions that capture the structured program schemes associated with recursive datatypes - the maps, folds, unfolds, and traversals of modern functional programming. Hoare’s “close analogies” reveal themselves through beautiful programs, perfectly adapted to the data they consume and produce, functions following form. I will explain how this works, and show a bunch of pretty examples.

Jeremy Gibbons is Professor of Computing in the Department of Computer Science at the University of Oxford. He teaches on the Software Engineering Programme, which offers part-time professional Masters’ degrees in Software Engineering and in Software and Systems Security, and leads the Algebra of Programming research group. He is Editor-in-Chief of the Journal of Functional Programming, Past Vice Chair of ACM SIGPLAN, Past Chair of IFIP WG2.1, and Steering Committee Chair of the International Conference on Functional Programming.

I am Professor of Computing in the Department of Computer Science at the University of Oxford. I am currently Director of the Software Engineering Programme, which offers part-time professional Masters’ degrees in Software Engineering and in Software and Systems Security. I also lead the Algebra of Programming research group. I am Editor-in-Chief of the Journal of Functional Programming, Past Vice Chair of ACM SIGPLAN, Past Chair of IFIP WG2.1. Before taking up this post in 1999, I held lectureships at Oxford Brookes University and the University of Auckland, New Zealand.