Maximum Segment Sum, Monadically (distilled tutorial)

Jeremy Gibbons
(University of Oxford)

The maximum segment sum problem is to compute, given a list of integers, the largest of the sums of the contiguous segments of that list. This problem specification maps directly onto a cubic-time algorithm; however, there is a very elegant linear-time solution too. The problem is a classic exercise in the mathematics of program construction, illustrating important principles such as calculational development, pointfree reasoning, algebraic structure, and datatype-genericity. Here, we take a sideways look at the datatype-generic version of the problem in terms of monadic functional programming, instead of the traditional relational approach; the presentation is tutorial in style, and leavened with exercises for the reader.

In Olivier Danvy and Chung-chieh Shan: Proceedings IFIP Working Conference on Domain-Specific Languages (DSL 2011), Bordeaux, France, 6-8th September 2011, Electronic Proceedings in Theoretical Computer Science 66, pp. 181–194.
Published: 1st September 2011.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: