Algorithm design with the selection monad

Conference item

The selection monad has proven useful for modelling exhaustive search algorithms. It is well studied in the area of game theory as an elegant way of expressing algorithms that calculate optimal plays for sequential games with perfect information; composition of moves is modeled as a ‘product’ of selection functions. This paper aims to expand the application of the selection monad to other classes of algorithms. The structure used to describe exhaustive search problems can easily be applied to greedy algorithms; with some changes to the product function, the behaviour of the selection monad can be changed from an exhaustive search behaviour to a greedy one. This enables an algorithm design framework in which the behaviour of the algorithm can be exchanged modularly by using different product functions.

Authors: Hartmann, J; Gibbons, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Host title: Trends in Functional Programming, TFP 2022
• Volume: 13401
• Pages: 126-143
• Series: Lecture Notes in Computer Science
• Series number: 13401
• Publication date: 2023-01-01
• Acceptance date: 2022-05-30
• Event title: 23rd International Symposium on Trends in Functional Programming
• Event location: Virtual Event
• Event start date: 2022-03-17
• Event end date: 2022-03-18
• DOI: 10.1007/978-3-031-21314-4_7
• EISSN: 1611-3349
• ISSN: 0302-9743
• EISBN: 978-3-031-21314-4
• ISBN: 978-3-031-21313-7
• Language: English
• Keywords: monads; selection monad; functional programming; algorithm design; greedy algorithms