Maximum Segment Sum, Monadically (distilled tutorial, with solutions)

Autor:	Gibbons, Jeremy
Rok vydání:	2011
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics Computer Science - Programming Languages
Zdroj:	EPTCS 66, 2011, pp. 181-194
Druh dokumentu:	Working Paper
DOI:	10.4204/EPTCS.66.9
Popis:	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. Comment: Revision of the article in Proceedings DSL 2011, EPTCS 66, arXiv:1109.0323, to provide solutions to the exercises
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1109.0782 Zobrazit plný text záznamu View this record from Arxiv