Neil Sculthorpe
Jan Bracker
ABSTRACT
In Haskell, there are many data types that would form monads were it not for the presence of type-class constraints on the operations on that data type. This is a frustrating problem in practice, because there is a considerable amount of support and infrastructure for monads that these data types cannot use. Using several examples, we show that a monadic computation can be restructured into a normal form such that the standard monad class can be used. The technique is not specific to monads, and we show how it can also be applied to other structures, such as applicative functors. One significant use case for this technique is domain-specific languages, where it is often desirable to compile a deep embedding of a computation to some other language, which requires restricting the types that can appear in that computation.
- S. Adams. Efficient sets -- a balancing act. Journal of Functional Programming, 3 (4): 553--561, 1993.Google Scholar
Cross Ref
- H. Apfelmus. The Operational monad tutorial. The Monad.Reader, 15: 37--55, 2010.Google Scholar
- M. Bolingbroke. Constraint kinds for GHC, 2011. URL http://blog.omega-prime.co.uk/?p=127.Google Scholar
- M. M. T. Chakravarty, G. Keller, and S. Peyton Jones. Associated type synonyms. In International Conference on Functional Programming, pages 241--253. ACM, 2005. Google ScholarDigital Library
- C. Elliott, S. Finne, and O. de Moor. Compiling embedded languages. Journal of Functional Programming, 13 (3): 455--481, 2003. Google ScholarDigital Library
- A. Farmer and A. Gill. Haskell DSLs for interactive web services. In Cross-model Language Design and Implementation, 2012.Google Scholar
- J. Gibbons and B. C. dos Santos Oliveira. The essence of the iterator pattern. Journal of Functional Programming, 19 (3--4): 377--402, 2009. Google ScholarDigital Library
- A. Gill. Type-safe observable sharing in Haskell. In Haskell Symposium, pages 117--128. ACM, 2009. Google ScholarDigital Library
- G. Giorgidze, 2012. URL http://hackage.haskell.org/package/set-monad.Google Scholar
- P. Hudak. Modular domain specific languages and tools. In International Conference on Software Reuse, pages 134--142. IEEE Computer Society, 1998. Google ScholarDigital Library
- J. Hughes. A novel representation of lists and its application to the function 'reverse'. Information Processing Letters, 22 (3): 141--144, 1986. Google ScholarDigital Library
- J. Hughes. Restricted data types in Haskell. In Haskell Workshop, 1999.Google Scholar
- J. Hughes. Generalising monads to arrows. Science of Computer Programming, 37 (1--3): 67--111, 2000. Google ScholarDigital Library
- G. Hutton, M. Jaskelioff, and A. Gill. Factorising folds for faster functions. Journal of Functional Programming, 20 (3&4): 353--373, 2010. Google ScholarDigital Library
- R. Ingram and B. Felgenhauer, 2008. URL http://hackage.haskell.org/package/MonadPrompt.Google Scholar
- M. Jaskelioff. Monatron: An extensible monad transformer library. In Implementation and Application of Functional Languages 2008, volume 5836 of LNCS, pages 233--248. Springer, 2011. Google ScholarDigital Library
- W. Jones, T. Field, and T. Allwood. Deconstraining DSLs. In International Conference on Functional Programming, pages 299--310. ACM, 2012. Google ScholarDigital Library
- E. Kidd. How to make Data.Set a monad, 2007. URL http://www.randomhacks.net/articles/2007/03/15/data-set-monad-haskell-macros.Google Scholar
- O. Kiselyov. Restricted monads, 2006. URL http://okmij.org/ftp/Haskell/types.html#restricted-datatypes.Google Scholar
- O. Kiselyov, S. Peyton Jones, and C. Shan. Fun with type functions. In Reflections on the Work of C.A.R. Hoare, chapter 14, pages 301--331. Springer, 2010.Google ScholarCross Ref
- E. A. Kmett, 2013. URL http://hackage.haskell.org/package/kan-extensions.Google Scholar
- K. Laufer and M. Odersky. Polymorphic type inference and abstract data types. Transactions on Programming Languages and Systems, 16 (5): 1411--1430, 1994. Google ScholarDigital Library
- S. Liang, P. Hudak, and M. Jones. Monad transformers and modular interpreters. In Principles of Programming Languages, pages 333--343. ACM, 1995. Google ScholarDigital Library
- C. Lin. Programming monads operationally with Unimo. In International Conference on Functional Programming, pages 274--285. ACM, 2006. Google ScholarDigital Library
- C. McBride and R. Paterson. Applicative programming with effects. Journal of Functional Programming, 18 (1): 1--13, 2008. Google ScholarDigital Library
- M. Mitrofanov. A problem defining a monad instance, 2009. URL http://www.haskell.org/pipermail/haskell-cafe/2009-November/068761.html.Google Scholar
- E. Moggi. Computational lambda-calculus and monads. In Logic in Computer Science, pages 14--23. IEEE Press, 1989. Google ScholarDigital Library
- E. Moggi. Notions of computation and monads. Information and Computation, 93 (1): 55--92, 1991. Google ScholarDigital Library
- D. Orchard and T. Schrijvers. Haskell type constraints unleashed. In International Conference on Functional and Logic Programming, pages 56--71. Springer, 2010. Google ScholarDigital Library
- A. Persson, E. Axelsson, and J. Svenningsson. Generic monadic constructs for embedded languages. In Implementation and Application of Functional Languages 2011, volume 7257 of LNCS, pages 85--99. Springer, 2012. Google ScholarDigital Library
- S. Peyton Jones, D. Vytiniotis, S. Weirich, and G. Washburn. Simple unification-based type inference for GADTs. In International Conference on Functional Programming, pages 50--61. ACM, 2006. Google ScholarDigital Library
- S. Peyton Jones, D. Vytiniotis, S. Weirich, and M. Shields. Practical type inference for arbitrary-rank types. Journal of Functional Programming, 17 (1): 1--82, 2007. Google ScholarDigital Library
- F. Pfenning and C. Elliott. Higher-order abstract syntax. In Programming Language Design and Implementation, pages 199--208. ACM, 1988. Google ScholarDigital Library
- N. Sculthorpe, 2013. URL http://hackage.haskell.org/package/constrained-normal.Google Scholar
- G. Sittampalam and P. Gavin, 2008. URL http://hackage.haskell.org/package/rmonad.Google Scholar
- M. Spivey. A functional theory of exceptions. Science of Computer Programming, 14 (1): 25--42, 1990. Google ScholarDigital Library
- J. Svenningsson and E. Axelsson. Combining deep and shallow embedding for EDSL. In Trends in Functional Programming 2012, volume 7829 of LNCS. Springer.Google Scholar
- W. Swierstra. Data types à la carte. Journal of Functional Programming, 18 (4): 423--436, 2008. Google ScholarDigital Library
- J. Vizzotto, T. Altenkirch, and A. Sabry. Structuring quantum effects: Superoperators as arrows. Mathematical Structures in Computer Science, 16 (3): 453--468, 2006. Google ScholarDigital Library
- J. Voigtlander. Asymptotic improvement of computations over free monads. In Mathematics of Program Construction, pages 388--403. Springer, 2008. Google ScholarDigital Library
- P. Wadler. Comprehending monads. In LISP and Functional Programming, pages 61--78. ACM, 1990. Google ScholarDigital Library
- P. Wadler. The essence of functional programming. In Principles of Programming Languages, pages 1--14. ACM, 1992. Google ScholarDigital Library
- B. A. Yorgey, S. Weirich, J. Cretin, S. Peyton Jones, D. Vytiniotis, and J. P. Magalhaes. Giving Haskell a promotion. In Types in Language Design and Implementation, pages 53--66. ACM, 2012. Google ScholarDigital Library
Index Terms
- The constrained-monad problem
Recommendations
The constrained-monad problem
ICFP '13In Haskell, there are many data types that would form monads were it not for the presence of type-class constraints on the operations on that data type. This is a frustrating problem in practice, because there is a considerable amount of support and ...
Monad factory: type-indexed monads
TFP'10: Proceedings of the 11th international conference on Trends in functional programmingMonads provide a greatly useful capability to pure languages in simulating side-effects, but implementations such as the Monad Transformer Library [1] in Haskell prohibit reuse of those side-effects such as threading through two different states without ...
Algebras of the Extended Probabilistic Powerdomain Monad
AbstractWe investigate the Eilenberg-Moore algebras of the extended probabilistic powerdomain monad Vw over the category TOP0 of T0 topological spaces and continuous maps. We prove that every Vw-algebra in our setting is a weakly locally convex sober ...
Comments