Andrey Mokhov
Georgy Lukyanov
Skip Abstract Section
Skip Supplemental Material SectionAbstract
Applicative functors and monads have conquered the world of functional programming by providing general and powerful ways of describing effectful computations using pure functions. Applicative functors provide a way to compose independent effects that cannot depend on values produced by earlier computations, and all of which are declared statically. Monads extend the applicative interface by making it possible to compose dependent effects, where the value computed by one effect determines all subsequent effects, dynamically.
This paper introduces an intermediate abstraction called selective applicative functors that requires all effects to be declared statically, but provides a way to select which of the effects to execute dynamically. We demonstrate applications of the new abstraction on several examples, including two industrial case studies.
Supplemental Material
- Nick Benton and Andrew Kennedy. 2001. Exceptional syntax. Journal of Functional Programming 11, 4 (2001), 395–410. Google Scholar
Digital Library
- Yves Bertot and Pierre Castéran. 2013. Interactive theorem proving and program development: Coq’Art: the calculus of inductive constructions. Springer Science & Business Media.Google Scholar
- Chris Birchall and Hamish Dickson. 2019. Implementation of selective applicative functors in Scala. (2019). https://web.archive.org/web/20190623214126/https://github.com/cb372/cats- selective/blob/master/core/src/main/ scala/cats/Selective.scala .Google Scholar
- Baldur Blöndal, Andres Löh, and Ryan Scott. 2018. Deriving Via. In Proceedings of the 11th ACM Haskell Symposium (Haskell’18).Google Scholar
- Paolo Capriotti and Ambrus Kaposi. 2014. Free applicative functors. Proceedings 5th Workshop on Mathematically Structured Functional Programming 153, 2–30.Google ScholarCross Ref
- Jack B Dennis and David P Misunas. 1975. A preliminary architecture for a basic data-flow processor. In ACM SIGARCH Computer Architecture News, Vol. 3. ACM, 126–132. Google ScholarDigital Library
- Dominique Devriese, Ilya Sergey, Dave Clarke, and Frank Piessens. 2013. Fixing idioms: a recursion primitive for applicative DSLs. In Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation. ACM, 97–106. Google ScholarDigital Library
- Will Fancher. 2016. More on Applicative Effects in Free Monads. (2016). https://web.archive.org/web/20190307232337/https: //elvishjerricco.github.io/2016/04/13/more- on- applicative- effects- in- free- monads.html .Google Scholar
- Will Fancher. 2017. Profunctors, Arrows, & Static Analysis. (2017). https://web.archive.org/web/20190307232429/https: //elvishjerricco.github.io/2017/03/10/profunctors- arrows- and- static- analysis.html .Google Scholar
- Jeremy Gibbons. 2016. Free delivery (functional pearl). In ACM SIGPLAN Notices, Vol. 51. ACM, 45–50. Google ScholarDigital Library
- Richard Gibson. 2019. Implementation of selective applicative functors in Kotlin. (2019). https://web. archive.org/web/20190623213927/https://github.com/arrow- kt/arrow/blob/master/modules/core/arrow- coredata/src/main/kotlin/arrow/typeclasses/Selective.kt .Google Scholar
- Andy Gill, Neil Sculthorpe, Justin Dawson, Aleksander Eskilson, Andrew Farmer, Mark Grebe, Jeffrey Rosenbluth, Ryan Scott, and James Stanton. 2015. The remote monad design pattern. In ACM SIGPLAN Notices, Vol. 50. ACM, 59–70. Google ScholarDigital Library
- Robert Harper. 2011. Boolean Blindness. (2011). https://web.archive.org/web/20110321191234/http://existentialtype. wordpress.com/2011/03/15/boolean- blindness/ .Google Scholar
- Antti Holvikari. 2018. Implementation of selective applicative functors in PureScript. (2018). https://web.archive.org/web/ 20190623214040/https://github.com/anttih/purescript- selective/blob/master/src/Control/Selective.purs .Google Scholar
- John Hughes. 2000. Generalising monads to arrows. Science of computer programming 37, 1-3 (2000), 67–111. Google ScholarDigital Library
- Graham Hutton and Erik Meijer. 1998. Monadic parsing in Haskell. Journal of functional programming 8, 4 (1998), 437–444. Google ScholarDigital Library
- Jane Street. 2015. Incremental: A library for incremental computations. Bind, scopes, and invalidation. (2015). https://web.archive.org/web/20190709231158/https://ocaml.janestreet.com/ocaml- core/latest/doc/incremental/ Incremental__/Incremental_intf/#bind, - scopes, - and- invalidation .Google Scholar
- Jane Street. 2018. Dune: A composable build system. (2018). https://dune.build/ .Google Scholar
- Oleg Kiselyov and Hiromi Ishii. 2015. Freer Monads, More Extensible Effects. SIGPLAN Not. 50, 12 (Aug. 2015), 94–105. Google ScholarDigital Library
- Daan Leijen and Erik Meijer. 2000. Domain specific embedded compilers. ACM Sigplan Notices 35, 1 (2000), 109–122. Google ScholarDigital Library
- Sam Lindley, Philip Wadler, and Jeremy Yallop. 2011. Idioms are oblivious, arrows are meticulous, monads are promiscuous. Electronic notes in theoretical computer science 229, 5 (2011), 97–117. Google ScholarDigital Library
- Georgy Lukyanov. 2019. Implementation of selective applicative functors in Coq. (2019). https://web.archive.org/web/ 20190623213821/https://github.com/tuura/selective- theory- coq/blob/master/src/Control/Selective.v .Google Scholar
- Simon Marlow, Louis Brandy, Jonathan Coens, and Jon Purdy. 2014. There is no fork: An abstraction for efficient, concurrent, and concise data access. In ACM SIGPLAN Notices, Vol. 49. ACM, 325–337. Google ScholarDigital Library
- Simon Marlow, Simon Peyton Jones, Edward Kmett, and Andrey Mokhov. 2016. Desugaring Haskell’s do-notation into applicative operations. In ACM SIGPLAN Notices, Vol. 51. ACM, 92–104. Google ScholarDigital Library
- Conor McBride and Ross Paterson. 2008. Applicative programming with effects. Journal of Functional Programming 18, 1 (2008), 1–13. Google ScholarDigital Library
- Adam Megacz. 2011. Hardware design with generalized arrows. In International Symposium on Implementation and Application of Functional Languages. Springer, 164–180. Google ScholarDigital Library
- Dave Menendez. 2013. Free Applicative Functors in Haskell. (2013). https://web.archive.org/web/20190625202450/https: //www.eyrie.org/~zednenem/2013/05/27/freeapp .Google Scholar
- Eugenio Moggi. 1991. Notions of computation and monads. Information and computation 93, 1 (1991), 55–92. Google ScholarDigital Library
- Andrey Mokhov. 2009. Conditional partial order graphs. Ph.D. Dissertation. Newcastle University.Google Scholar
- Andrey Mokhov. 2018. Selective applicative functors (blog post). (2018). https://web.archive.org/web/20190501160729/https: //blogs.ncl.ac.uk/andreymokhov/selective/ . Google ScholarDigital Library
- Andrey Mokhov. 2019. Implementation of selective applicative functors in Haskell. (2019). https://hackage.haskell.org/ package/selective . Google ScholarDigital Library
- Andrey Mokhov, Neil Mitchell, and Simon Peyton Jones. 2018. Build Systems à la Carte. Proceedings of the ACM on Programming Languages 2, ICFP (2018), 79. Google ScholarDigital Library
- Ross Paterson. 2001. A new notation for arrows. In ACM SIGPLAN Notices, Vol. 36. ACM, 229–240. Google ScholarDigital Library
- Daniel Peebles. 2019. Sigma Selective. (2019). http://web.archive.org/web/20190625225137/https://gist.github.com/ copumpkin/d5bdbc7afda54ff04049b6bdbcffb67e .Google Scholar
- Evgeny Permyakov et al. 2012. Applicative functors with branch/choice. (2012). https://web.archive.org/web/20190626004303/ https://mail.haskell.org/pipermail/haskell- cafe/2012- July/102518.html .Google Scholar
- Matthew Pickering, Jeremy Gibbons, and Nicolas Wu. 2017. Profunctor optics: Modular data accessors. Art, Science, and Engineering of Programming 1, 2 (2017).Google Scholar
- Exequiel Rivas and Mauro Jaskelioff. 2017. Notions of computation as monoids. Journal of functional programming 27 (2017).Google Scholar
- Tomás Ruiz-López. 2019. Implementation of selective applicative functors in Swift. (2019). https://web.archive.org/save/https: //github.com/bow- swift/bow/blob/master/Sources/Bow/Typeclasses/Selective.swift .Google Scholar
- Colin Runciman, Matthew Naylor, and Fredrik Lindblad. 2008. SmallCheck and Lazy SmallCheck: automatic exhaustive testing for small values. In Acm sigplan notices, Vol. 44. ACM, 37–48. Google ScholarDigital Library
- Danil Sokolov, Alessandro de Gennaro, and Andrey Mokhov. 2018. Reconfigurable asynchronous pipelines: From formal models to silicon. In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 1562–1567.Google Scholar
- S Doaitse Swierstra and Luc Duponcheel. 1996. Deterministic, error-correcting combinator parsers. In International School on Advanced Functional Programming. Springer, 184–207. Google ScholarDigital Library
- Wouter Swierstra. 2008. Data types à la carte. Journal of functional programming 18, 4 (2008), 423–436. Google ScholarDigital Library
- The OPAM team. 2018. OCaml Package Manager. (2018). https://opam.ocaml.org/ .Google Scholar
- Philip Wadler. 1989. Theorems for free!. In FPCA, Vol. 89. 347–359. Google ScholarDigital Library
- P. Wadler. 1995. Monads for functional programming. In Int’l School on Advanced Functional Programming. Springer, 24–52. Google ScholarDigital Library
- Jeremy Yallop. 2010. Abstraction for web programming. Ph.D. Dissertation. The University of Edinburgh.Google Scholar
- Brent Yorgey et al. 2009. An IRC conversation about Branchy type class. (2009). https://web.archive.org/web/20190626003950/ https://github.com/snowleopard/selective/blob/master/paper/irc- log- branchy.md .Google Scholar
Index Terms
- Selective applicative functors
Recommendations
Idioms are Oblivious, Arrows are Meticulous, Monads are Promiscuous
We revisit the connection between three notions of computation: Moggi s monads, Hughes s arrows and McBride and Paterson s idioms (also called applicative functors). We show that idioms are equivalent to arrows that satisfy the type isomorphism A B 1 (A ...
Algebraic effects and effect handlers for idioms and arrows
WGP '14: Proceedings of the 10th ACM SIGPLAN workshop on Generic programmingPlotkin and Power's algebraic effects combined with Plotkin and Pretnar's effect handlers provide a foundation for modular programming with effects. We present a generalisation of algebraic effects and effect handlers to support other kinds of effectful ...
Handlers for Non-Monadic Computations
IFL '17: Proceedings of the 29th Symposium on the Implementation and Application of Functional Programming LanguagesAlgebraic effects and handlers are a convenient method for structuring monadic effects with primitive effectful operations and separating the syntax from the interpretation of these operations. However, the scope of conventional handlers are somewhat ...
Comments