I had a chance to show the students, in 25 minutes, what functional program calculation is about. The student have just been exposed to functional programming a week ago in a three-hour course, and I have talked to them about maximum segment sum way too many times.
Given an array of integers having at least two elements, compute the sum of squares of the difference between all pairs of elements. It is not hard to quickly write up a
O(N²) program using nested loops, which, I have to confess, is what I would do before reading Kaldewaij’s book and realised that it is possible to do the task in linear time using one loop.
In the recent work of Sharon and me on maximally dense segments we needed quite a number of functions to be monotonic, idempotent, etc. It only occurred to me after submitting the paper: could they be defined as Galois connections?
Sharon and I have finally concluded, for now, our work on the maximally dense segment problem (download the draft here), on which we have been working on and off for the past two years. Considering the algorithm itself and its derivation/proofs, I am quite happy with what we have achieved. The algorithm is rather complex, however, and it is a challenge presenting it in an accessible way. Sharon has done a great job polishing the paper, and I do hope more people would be interested in reading it and it would, eventually, inspire more work on interesting program derivations.
In a previous paper of mine, regrettably, I wrongly attributed the origin of the maximum segment sum problem to Dijkstra and Feijen’s Een methode van programmeren. In fact, the story behind the problem was told very well in Jon Bentley’s Programming Pearls.
I learned the function derivation of the maximum segment sum problem from one of Jeremy’s papers and was very amazed. It was perhaps one of the early incident that inspired my interest in program calculation.
Code and proof accompanying our forthcoming paper Functional Pearl: Maximally Dense Segments.