Aug 05, 2020

Here's a clearer version of the paper[0].

This paper[1] is a good way for object-oriented programmers to understand why functional programmers care about these higher order abstractions. The goal is not so different from OOP, which is about structuring programs as reusable components (AKA design patterns). The difference of course is that one doesn't need to resort to diagrams and prose, instead they can be written directly in the programming language.

Relatedly, one of my favorite books in functional programming is Algebra of Programming[2], which is about treating programs as an algebra that can be manipulated as easy (with practice) as algebraic expressions in math. The book solves various problems through program derivation, for instance solving the maximum subsegment problem by refining a naïve spec, deriving sorting algorithms, greedy algorithms, dynamic programming and thinning algorithms.

This draft book[3] has similar content to the earlier chapters of AoP but is far more accessible. The downside of AoP is that I had to resort to reading it with a math professor to understand it.

[0] https://maartenfokkinga.github.io/utwente/mmf91m.pdf

[1] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/hodgp.pdf

[2] https://themattchan.com/docs/algprog.pdf

[3] http://www4.di.uminho.pt/~jno/ps/pdbc.pdf