Developing Behavioral Concepts of Higher-Order Functions

Posted on 31 July 2021.

Higher-Order Functions (HOFs) are an integral part of the programming process. They are so ubiquitous, even Java had to bow and accept them. They’re especially central to cleanly expressing the stages of processing data, as the R community and others have discovered.

How do we teach higher-order functions? In some places, like How to Design Programs, HOFs are presented as abstractions over common patterns. That is, you see a certain pattern of program behavior over and over, and eventually learn to parameterize it and call it map, filter, and so on. That is a powerful method.

In this work, we take a different perspective. Our students often write examples first, so they can think in terms of the behavior they want to achieve. Thus, they need to develop an understanding of HOFs as abstractions over common behaviors: “mapping”, “filtering”, etc.

Our goal in this work is to study how well students form behavioral abstractions having been taught code pattern abstractions. Our main instrument is sets of input-output behavior, such as

(list "red" "green" "blue")
-->
(list 3 5 4)

(Hopefully that calls to mind “mapping”.) We very carefully designed a set of these to capture various specific similarities, overlaps, and impossibilities.

We then evaluated students using two main devices, inspired by activities in machine learning:

  • Clustering: Group behaviors into clusters of similar ones.

  • Classification: For each behavior, assign a label.

We also tried labeling over visual presentations.

Our paper describes these instruments in detail, and our outcomes. What is most interesting, perhaps, is not our specific outcomes, but this style of thinking about teaching HOFs. We think the materials—especially the input-output pairs, and a table of properties—will be useful to educators who are tackling this topic. More broadly, we think there’s a huge unexplored space of HOF pedagogy combined with meaningful evaluation. We hope this work inspires more work along these lines.