Abstract
This paper explores a novel approach to selection functions through the introduction of a generalised selection monad. The foundation is laid with the conventional selection monad \(J\), defined as \((A \rightarrow R) \rightarrow A\), together with various combinators for computing new selection functions from old. However, inefficiencies in these combinators are identified. To address these issues, a specialised type \(K\) is introduced, and its isomorphism to \(J\) is demonstrated. The paper further generalises the \(K\) type to \(G\), where performance improvements and enhanced intuitive usability are observed. The embeddings between \(J\) and \(G\) are established, offering a more efficient and expressive alternative to the well established \(J\) type for selection functions. The findings emphasise the advantages of the generalised selection monad and its applicability in diverse scenarios, paving the way for further exploration and optimisation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Escardó, M., Oliva, P.: Selection functions, bar recursion and backward induction. Math. Struct. Comput. Sci. 20(2), 127–168 (2010)
Escardó, M., Oliva, P.: What sequential games, the Tychonoff Theorem and the double-negation shift have in common. In: Proceedings of the third ACM SIGPLAN workshop on Mathematically Structured Functional Programming, pp. 21–32 (2010)
Hartmann, J., Gibbons, J.: Algorithm design with the selection monad. In: Swierstra, W., Wu, N. (eds.) Trends in Functional Programming: 23rd International Symposium, TFP 2022, Virtual Event, March 17–18, 2022, Revised Selected Papers, pp. 126–143. Springer International Publishing, Cham (2022). https://doi.org/10.1007/978-3-031-21314-4_7
Hedges, J.: Monad transformers for backtracking search. In: Levy, P.B., Krishnaswami, N. (eds.) Mathematically Structured Functional Programming. EPTCS, vol. 153, pp. 31–50 (2014)
Wadler, P.: Theorems for free! In: Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, pp. 347–359 (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
1.1 Proof Monad Laws for G
Proof
(Left identity).
Proof
(Right identity).
Proof
(Associativity).
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Hartmann, J., Schrijvers, T., Gibbons, J. (2025). Towards a More Efficient Selection Monad. In: Hemann, J., Chang, S. (eds) Trends in Functional Programming. TFP 2024. Lecture Notes in Computer Science, vol 14843. Springer, Cham. https://doi.org/10.1007/978-3-031-74558-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-74558-4_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-74557-7
Online ISBN: 978-3-031-74558-4
eBook Packages: Computer ScienceComputer Science (R0)