Tomas Petricek
Alan Mycroft
Abstract
Sequencing of effectful computations can be neatly captured using monads and elegantly written using do notation. In practice such monads often allow additional ways of composing computations, which have to be written explicitly using combinators.
We identify joinads, an abstract notion of computation that is stronger than monads and captures many such ad-hoc extensions. In particular, joinads are monads with three additional operations: one of type m a -> m b -> m (a, b) captures various forms of parallel composition, one of type m a -> m a -> m a that is inspired by choice and one of type m a -> m (m a) that captures aliasing of computations. Algebraically, the first two operations form a near-semiring with commutative multiplication.
We introduce docase notation that can be viewed as a monadic version of case. Joinad laws imply various syntactic equivalences of programs written using docase that are analogous to equivalences about case. Examples of joinads that benefit from the notation include speculative parallelism, waiting for a combination of user interface events, but also encoding of validation rules using the intersection of parsers.
Supplemental Material
- Haskell Trac. Bring back monad comprehensions, retrieved 2011. http://hackage.haskell.org/trac/ghc/ticket/4370.Google Scholar
- Haskell Documentation. Control.Monad, retrieved 201.Google Scholar
- S. Brookes, S. Geva. Computational comonads and intensional semantics. Technical Report Carnegie Mellon University-CS-91-190, Carnegie Mellon University, 1991.Google Scholar
- N. C. C. Brown. Communicating Haskell Processes: Composable Explicit Concurrency using Monads. In Communicating Process Architectures 2008, pages 67--83, 2008.Google Scholar
- K. Claessen. A Poor Man's Concurrency Monad. Journal of Functional Programming, 9:313--323, May 1999. ISSN 0956-7968. Google ScholarDigital Library
- C. Elliott. Push-Pull Functional Reactive Programming. In Haskell Symposium, 2009. Google ScholarDigital Library
- B. Emir, M. Odersky, and J. Williams. Matching Objects with Patterns. In ECOOP 2007, 2007. Google ScholarDigital Library
- M. Fluet, M. Rainey, J. Reppy, and A. Shaw. Implicitly threaded parallelism in Manticore. Journal of Functional Programming, 20 (Special Issue 5-6):537--576, 2010. Google ScholarDigital Library
- G. Giorgidze, T. Grust, N. Schweinsberg, and J. Weijers Bringing Back Monad Comprehensions. To appear in Haskell'11, 2011. Google ScholarDigital Library
- P. Haller and T. Van Cutsem. Implementing Joins using Extensible Pattern Matching. In Proceedings of the 10th International Conference on Coordination Models and Languages, 2008. Google ScholarDigital Library
- HaskellWiki. MonadPlus reform proposal, retrieved 2011. http://tinyurl.com/monadplus-reform-proposal.Google Scholar
- P. Hudak, A. Courtney, H. Nilsson, and J. Peterson. Arrows, Robots, and Functional Reactive Programming. In Advanced Functional Programming, volume 2638 of LNCS, pages 1949--1949. 2003.Google Scholar
- J. Hughes. Generalising Monads to Arrows. Science of Computer Programming, 37:67--111, 1998. Google ScholarDigital Library
- G. Hutton and E. Meijer. Monadic Parsing in Haskell. Journal of Functional Programming, 8(4):437--444, July 1998. Google ScholarDigital Library
- S. P. Jones, S. Marlow, and R. Newton. A Monad for Deterministic Parallelism, 2011. http://tinyurl.com/monad-par. Google ScholarDigital Library
- S. P. Jones and P. Wadler. Comprehensive Comprehensions. In Haskell'07, pages 61--72, 2007. Google ScholarDigital Library
- R. B. Kieburtz. Codata and Comonads in Haskell. Unpublished manuscript, 1999.Google Scholar
- E. A. Kmett. The comonad package, retrieved 2011. http://hackage.haskell.org/package/comonad.Google Scholar
- D. Leijen and E. Meijer. Parsec: Direct Style Monadic Parser Combinators for the Real World. Technical Report UU-CS-2001-27, Department of Computer Science, Universiteit Utrecht, 2001.Google Scholar
- H. Liu, E. Cheng, and P. Hudak. Causal Commutative Arrows and Their Optimization. In ICFP'09, pages 35--46, 2009. Google ScholarDigital Library
- S. Marlow, P. Maier, H.-W. Loidl, M. K. Aswad, and P. Trinder. Seq no more: Better Strategies for Parallel Haskell. In Haskell'10. Google ScholarDigital Library
- C. McBride and R. Paterson. Applicative Programming with Effects. Journal of Functional Programming, 18:1--13, 2007. Google ScholarDigital Library
- D. A. Orchard, M. Bolingbroke, and A. Mycroft. Ypnos: Declarative, Parallel Structured Grid Programming. DAMP '10, 2010. Google ScholarDigital Library
- R. Paterson. A New Notation for Arrows. In Proceedings of ICFP'01, pages 229--240. ACM Press, Sept. 2001. Google ScholarDigital Library
- T. Petricek. Fun with parallel monad comprehensions, 2011. The Monad.Reader, Issue 18.Google Scholar
- T. Petricek. Explicit speculative parallelism for Haskell's Par monad, http://tomasp.net/blog/speculative-par-monad.aspx, retrieved 2011.Google Scholar
- T. Petricek and D. Syme. Joinads: A retargetable control-flow construct for reactive, parallel and concurrent programming. In PADL'11, pages 205--219, 2011. Google ScholarDigital Library
- J. H. Reppy. Concurrent Programming in ML. Cambridge University Press, 2007. ISBN 978-0-521-71472-3. Google ScholarDigital Library
- E. Scholz. Imperative Streams--A Monadic Combinator Library for Synchronous Programming. In ICFP'98, 1998. Google ScholarDigital Library
- S. D. Swierstra. Combinator Parsing: A Short Tutorial. Technical report, Utrecht University, 2008.Google Scholar
- D. Syme, G. Neverov, and J. Margetson. Extensible Pattern Matching via a Lightweight Language Extension. ICFP, 2007. Google ScholarDigital Library
- P. W. Trinder, K. Hammond, H.-W. Loidl, and S. L. Peyton Jones. Algorithm + Strategy = Parallelism. Journal of Functional Programming, 8(1):23--60, Jan. 1998. Google ScholarDigital Library
- M. Tullsen. First-Class Patterns. In PADL 2000, 2000. Google ScholarDigital Library
- T. Uustalu and V. Vene. The essence of dataflow programming. In APLAS, pages 2--18, 2005. Google ScholarDigital Library
- P. Wadler. Views: a way for pattern matching to cohabit with data abstraction. POPL, 1987. Google ScholarDigital Library
- P. Wadler. Comprehending Monads. In Proceedings of the 1990 ACM conference on LISP and functional programming, pages 61--78, 1990. Google ScholarDigital Library
Index Terms
- Extending monads with pattern matching
Recommendations
Extending monads with pattern matching
Haskell '11: Proceedings of the 4th ACM symposium on HaskellSequencing of effectful computations can be neatly captured using monads and elegantly written using do notation. In practice such monads often allow additional ways of composing computations, which have to be written explicitly using combinators.
We ...
Coproducts of Monads on Set
LICS '12: Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer ScienceCoproducts of monads on $\Set$ have arisen in both the study of computational effects and universal algebra. We describe coproducts of consistent monads on $\Set$ by an initial algebra formula, and prove also the converse: if the coproduct exists, so do ...
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 ...
Comments