https://wiki.haskell.org/api.php?action=feedcontributions&user=Steshaw&feedformat=atom
HaskellWiki - User contributions [en]
2016-07-27T17:16:03Z
User contributions
MediaWiki 1.19.14+dfsg-1
https://wiki.haskell.org/The_JavaScript_Problem
The JavaScript Problem
2014-04-21T04:36:42Z
<p>Steshaw: /* GorrilaScript */ correct spelling</p>
<hr />
<div>== The problem ==<br />
<br />
The JavaScript problem is two-fold and can be described thus:<br />
<br />
# '''JavaScript sucks.''' The depths to which JavaScript sucks is well-documented and well-understood. Its main faults are: its lack of module system, weak-typing, verbose function syntax¹, late binding², which has led to the creation of various static analysis tools to alleviate this language flaw³, but with limited success⁴ (there is even a static type checker⁵), finicky equality/automatic conversion, <code>this</code> behaviour, and lack of static types.<br />
<br />
# '''We need JavaScript.''' Using it for what it is good for, i.e. providing a platform for browser development, but not using the language ''per se'', is therefore desirable, and many are working to achieve this, in varying forms. There are various ways to do it, but we ought to opt for compiling an existing language, Haskell, to JavaScript, because we do not have time to learn or teach other people a new language, garner a new library set and a new type checker and all that Haskell implementations provide.<br />
<br />
== Mainstream alternatives ==<br />
<br />
=== Coffeescript ===<br />
It makes many aspects of Javascript sane and convenient, and you get a compilation check that verifies syntax, however it still suffers greatly from weak-typing.<br />
<br />
=== TypeScript ===<br />
<br />
Structural typing with traditional generics on top of Javascript.<br />
Of all the alternatvies, TypeScript's advantage is that it makes no changes to Javascript. Existing javascript code that passes jshint is valid Typescript code. TypeScript also adds features from the latest javascript standards that it can compile down to older versions of javascript. TypeScript is by far the easiest javascript variant to learn. The downside is that one might desire a better language then just javascript + types.<br />
<br />
TypeScript defaults to dynamic typing when it can't figure the type out. However, it now has a noImplicitAny setting that will give a compilation error if it can't figure out the type.<br />
<br />
Structural sub-typing seems a good fit for JavaScript. <br />
Perhaps Typescript's biggest problem is that null is a valid value for any type.<br />
<br />
== Haskell -> JS ==<br />
<br />
=== UHC ===<br />
<br />
Original blog post [https://github.com/atzedijkstra/javascript-runtime-for-UHC here.] Quickstart guide [http://chrisdone.com/posts/2012-01-06-uhc-javascript.html here.] A more in-depth discussion about the current capabilities of the backend [http://www.norm2782.com/improving-uhc-js-report.pdf here.] For an example of using the JavaScript compilation for a real app see this [http://alessandrovermeulen.me/2012/01/26/getting-rid-of-javascript-with-haskell/ blog post], there is also a port of wxAsteroids to the browser (see [http://uu-computerscience.github.io/js-asteroids/ github] or a [http://www.rubendegooijer.nl/posts/2013-04-06-haskell-oop.html blog post]). <br />
<br />
* Beta.<br />
* Only works for UHC, but promising. <br />
* UHC compiles enough of Hackage to be very useful.<br />
* Doesn't produce an explosion of code, seemingly.<br />
* Fairly substantial JS/DOM/W3C/HTML5 API.<br />
* Currently works.<br />
<br />
=== Fay ===<br />
<br />
Website: http://fay-lang.org/ Discussion on Reddit: [http://www.reddit.com/r/haskell/comments/11yrpi/fay_slides/ Fay slides]. The package is on [http://hackage.haskell.org/package/fay Hackage]. Fetch with Git: <br />
git clone git://github.com/faylang/fay.git<br />
<br />
* Compiles a subset of Haskell, needs more<br />
* Currently works.<br />
<br />
=== GHCJS ===<br />
<br />
The Github page is [https://github.com/ghcjs/ghcjs here.]<br />
<br />
* Alpha.<br />
* Works.<br />
* Incomplete.<br />
* Nicely designed.<br />
* Compiles most pure Haskell libraries no problem.<br />
* FFI to JS works, and the author, sviperll is a helpful guy.<br />
<br />
=== Haste ===<br />
<br />
[http://haste-lang.org Website], [http://hackage.haskell.org/package/haste-compiler Hackage]<br />
<br />
* Seamless, type-safe single program framework for client-server communication<br />
* Easy Javascript interoperability<br />
* Generates small, fast, minifiable code.<br />
* Lightweight concurrency, Cabal integration, FFI and GHC extensions supported.<br />
* Cross platform.<br />
* Works.<br />
<br />
=== [[JMacro]] ===<br />
<br />
On the Haskell wiki (see above) and on [http://hackage.haskell.org/package/jmacro hackage]<br />
<br />
* Mature, Maintained<br />
* Not Haskell but an EDSL _in_ Haskell nonetheless.<br />
* JMacro Panels provides a purely haskell combinator library that generates dynamically updating html and js with asynchronous client-server communication.<br />
* Syntax is a fusion of Haskell and JavaScript<br />
* Untyped, but with syntactic correctness (at least) enforced at compile-time.<br />
* Embeddable through quasi-quoting<br />
* Support for various forms of code-generation<br />
<br />
=== Others ===<br />
<br />
* [https://github.com/johang88/haskellinjavascript Haskell interpreter in JS] — An interpreter. Haven't tried but is apparently dead.<br />
* YHC JS backend — Beta-ish. Apparently works, but I was unable to compile YHC, so haven't tried yet. I would be interested in anyone's experience using it. There's [http://www.haskell.org/haskellwiki/Yhc/Javascript an old wiki page] about Yhc's JavaScript support, but Yhc itself is a dead project.<br />
* Emscripten — not Haskell→JS, but compiles LLVM/Clang output to JavaScript. Could possibly be used for GHC→LLVM→JS compiling, which I tried, and works, but would have to also compile the GHC runtime which is not straight-forward (to me) for it to actually run. <br />
* hjscript — Beta. EDSL, not Haskell→JS. Works. Not ''very'' annoying to program in, but is JS semantics, not Haskell. Hackage package [http://hackage.haskell.org/package/HJScript here.]<br />
* Some have also tried writing a Haskell→JS compiler to make a more direct JS-aware translation of code (to not have huge code output a la GHCJS, YHC, Emscripten).<br />
<br />
<br />
== FP -> JS ==<br />
<br />
=== Ur/Web ===<br />
<br />
http://www.impredicative.com/ur/<br />
<br />
Perhaps the problem with Ur is that they are selling both a backend and a frontend together. Being a new language, the backend is lacking in libraries to be practical for many tasks. However, there is an RSS reader that is using Ur for the front-end and Haskell for the backend: https://bazqux.com/<br />
<br />
<br />
=== OCaml ===<br />
<br />
The OCaml -> JS compiler is supposed to be good, it is now used at facebook for an internal in-browser code editor.<br />
http://ocsigen.org/js_of_ocaml/<br />
<br />
=== GorillaScript ===<br />
<br />
http://ckknight.github.io/gorillascript/<br />
<br />
immutable by default, global type inference, macros, what coffeescript should have been. The syntax is similar to coffeescript<br />
<br />
=== Roy, PureScript ===<br />
<br />
[http://roy.brianmckenna.org/ Roy]: meld JavaScript semantics with functional languages. Experimental, but has many bread-and-butter Haskell features.<br />
Roy is written in JS. PureScript is written in Haskell.<br />
<br />
=== Idris ===<br />
<br />
Idris is a compiled language with dependent types, implemented in Haskell, with backends for both LLVM and JavaScript. Experimental.<br />
<br />
* Full dependent types with dependent pattern matching where clauses, with rule, simple case expressions, pattern matching let and lambda bindings<br />
* Dependent records with projection and update<br />
* Type classes<br />
* Monad comprehensions<br />
* Syntactic conveniences for lists, tuples, dependent pairs do notation and idiom brackets<br />
* Indentation significant syntax<br />
* Extensible syntax<br />
* Tactic based theorem proving (influenced by Coq)<br />
* Cumulative universes<br />
* Totality checking<br />
* Simple foreign function interface (to C)<br />
* Hugs style interactive environment<br />
<br />
Links:<br />
* [http://idris-lang.org/ Website idris-lang.org] <br />
* [[Dependent_type|Dependent Type in haskell wiki]]<br />
* [http://en.wikipedia.org/wiki/Dependent_type WP (en) Dependent type] (with Idris listed under language comparison)<br />
<br />
<br />
== Links ==<br />
<br />
* [https://github.com/yesodweb/yesod/wiki/Javascript-Options Yesod - Javascript Options]<br />
* [http://chrisdone.com/tags/javascript Chris Done Blog] - Tag: Javascript<br />
<br />
== Footnotes ==<br />
<br />
# Its support for closures is commonly noted as being one of JavaScript’s redeeming features.<br />
# Early binding allows for static verification of the existence of method-signature pairs (e.g. v-tables). Late binding does not give the compiler (or an IDE) enough information for existence verification, it has to be looked up at run-time.<br />
# There are several hinting libraries, which developers insist are indispensable tools when developing JavaScript seriously, such as JavaScript lint, JSLint, and JSure.<br />
# “Any non-trivial analysis is very difficult due to Javascript’s dynamic nature.” — Berke Durak, Ph.D., author of jsure.<br />
# Google Inc. thought it necessary to develop a compiler, Google Closure, which does type-checking and limited inference.<br />
<br />
<br />
[[Category:Web|*]]</div>
Steshaw
https://wiki.haskell.org/Research_papers/Generics
Research papers/Generics
2012-06-21T02:56:07Z
<p>Steshaw: /* Overview */ Update url for Comparing Approaches to Generic Programming in Haskell</p>
<hr />
<div>__TOC__<br />
<br />
== Overview ==<br />
<br />
;[http://www.staff.science.uu.nl/~jeuri101/homepage/Publications/ComparingGpFinal.pdf Comparing Approaches to Generic Programming in Haskell]<br />
:Ralf Hinze, Johan Jeuring, and Andres Löh. To appear in Roland Backhouse, Jeremy Gibbons, Ralf Hinze, and Johan Jeuring, editors, Lecture notes of the Spring School on Datatype-Generic Programming 2006, © Springer-Verlag.<br />
<br />
;[http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-010.pdf Comparing Libraries for Generic Programming in Haskell]<br />
:Alexey Rodriguez Yakushev, Johan Jeuring, Patrik Jansson, Alex Gerdes, Oleg Kiselyov, Bruno C. d. S. Oliviera. In Andy Gill, editor, Proceedings of the ACM SIGPLAN Haskell Symposium 2008, pages 111-122, and available as an extended version: Technical report Utrecht University UU-CS-2008-010, 2008.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/papers/Concepts/ConceptsJFP_Bernardy_et_al_20100831.pdf Generic programming with C++ concepts and Haskell type classes - a comparison]<br />
:Jean-Philippe Bernardy, Patrik Jansson, Marcin Zalewski, and Sibylle Schupp. JFP, 2010. In press. An earlier and shorter version was published in Proc. ACM SIGPLAN Workshop on Generic Programming (WGP), pages 37-48. ACM, 2008 as [A comparison of C++ concepts and Haskell type classes -> http://doi.acm.org/10.1145/1411318.1411324]<br />
<br />
;[ftp://ftp.kestrel.edu/pub/papers/meertens/AFP-Portugal.ps.gz Generic Programming -- An Introduction]<br />
:Roland Backhouse, Patrik Jansson, Johan Jeuring and Lambert Meertens. Advanced Functional Programming (S. Doaitse Swierstra, editor), LNCS 1608, pp. 28-115, 1999.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/poly/polyp/polylib/ PolyLib - a polytypic function library]<br />
:Patrik Jansson and Johan Jeuring. Workshop on Generic Programming, Marstrand, June 1998.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/papers/Polytypic_Programming_AFP_1996_Jeuring_Jansson.pdf Polytypic programming]<br />
:J. Jeuring and P. Jansson. In J. Launchbury et al., editors, Advanced Functional Programming '96, volume 1129 of LNCS, pages 68-114. Springer-Verlag, 1996.<br />
<br />
==Scrap your boilerplate!==<br />
<br />
;[http://research.microsoft.com/~simonpj/Papers/hmap/index.htm Scrap your boilerplate: a practical approach to generic programming]<br />
:Ralf Laemmel and Simon Peyton Jones, Proc ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI 2003), New Orleans, pp26-37, Jan 2003.<br />
<br />
;[http://www.cwi.nl/~ralf/syb2/ Scrap more boilerplate: reflection, zips, and generalised casts]<br />
:Ralf Laemmel and Simon Peyton Jones. appeared in Proceedings of ICFP 2004, ACM Press<br />
<br />
;[http://www.cwi.nl/~ralf/syb3/ Scrap your boilerplate with class: extensible generic functions]<br />
:Ralf Laemmel and Simon Peyton Jones. appeared in Proceedings of ICFP 2005, ACM Press<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/SYB0.pdf "Scrap Your Boilerplate" Reloaded]<br />
:Ralf Hinze, Andres Löh and Bruno C. d. S. Oliveira. In Philip Wadler and Masimi Hagiya, editors, Proceedings of the Eighth International Symposium on Functional and Logic Programming (FLOPS 2006), 24-26 April 2006, Fuji Susono, Japan.<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/reclib/ RecLib - A Recursion and Traversal Library for Haskell (Or: Scrap Your Boilerplate Systematically)]<br />
:Deling Ren and Martin Erwig, Haskell Workshop 2006<br />
<br />
;[http://www-users.cs.york.ac.uk/~ndm/uniplate/ Uniplate - Uniform Boilerplate and List Processing]<br />
:Neil Mitchell and Colin Runciman, Haskell Workshop 2007<br />
<br />
==Generic Haskell==<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications.html Generic Haskell: Applications] <br />
:Ralf Hinze and Johan Jeuring. Technical Report UU-CS-2003-16, Department of Computer Science, Utrecht University, 2003.<br />
<br />
;[http://www.cs.uu.nl/research/projects/generic-haskell/ Generic Haskell: a language for generic programming] <br />
:Johan Jeuring et al<br />
<br />
;[http://www.springerlink.com/index/F1WPGU2J9V59G4GR.pdf Generic Haskell: Practice and theory]<br />
:R Hinze, J Jeuring - lecture notes of the Summer School on Generic Programming, 2002 - Springer<br />
<br />
;[http://www.cs.uu.nl/people/stefan/pubs/holdermans06generic.html Generic views on data types]<br />
:Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriquez. In Tarmo Uustalu, editor, Mathemetics of Program Construction, 8th International Conference, MPC 2006, Kuressaare, Estonia, July 3&mdash;5, 2006, Proceedings, volume 4014 of Lecture Notes in Computer Science, pages 209&mdash;234. Springer-Verlag, 2006.<br />
<br />
;[http://homepages.cwi.nl/~atanasso/papers/atanassow04inferring.pdf Inferring type isomorphisms generically]<br />
:Frank Atanassow and Johan Jeuring. In Proc. Mathematics of Program Construction (MPC) 2004.<br />
<br />
===Applications of Generic Haskell===<br />
<br />
;[http://homepages.cwi.nl/~atanasso/papers/atanassow03scripting.pdf Scripting XML with Generic Haskell]<br />
:Frank Atanassow, Dave Clarke and Johan Jeuring. In Proc. 7th Brazilian Symposium on Programming Languages (SBLP) 2003.<br />
<br />
;[http://homepages.cwi.nl/~atanasso/papers/atanassow04uuxml.pdf UUXML: A Type-Preserving XML SchemaHaskell Data Binding]<br />
:Frank Atanassow, Dave Clarke and Johan Jeuring. In Proc. Practical Aspects of Declarative Languages (PADL) 2004.<br />
<br />
==Testing==<br />
<br />
;[http://www.springerlink.com/content/d721893h62144724/ Testing properties of generic functions]<br />
:Patrik Jansson, Johan Jeuring, and students of the Utrecht University Generic Programming class. In Zoltan Horvath, editor, Proceedings of IFL 2006, volume 4449 of LNCS, pages 217-234. Springer-Verlag, 2007.<br />
<br />
;[http://www.cse.chalmers.se/~bernardy/PolyTest.pdf Testing polymorphic properties]<br />
:Jean-Philippe Bernardy, Patrik Jansson, and Koen Claessen. In Proceedings of ESOP 2010, volume 6012 of LNCS. Springer, 2010.<br />
<br />
==DSL / applications / C++==<br />
<br />
;[http://www.springerlink.com/index/v10642g0j71m345p.pdf Generic libraries in C++ with concepts from high-level domain descriptions in Haskell: A DSL for computational vulnerability assessment.]<br />
:Daniel Lincke, Patrik Jansson, Marcin Zalewski, and Cezar Ionescu. In IFIP Working Conf. on Domain Specific Languages, volume 5658/2009 of LNCS, pages 236{261, 2009.<br />
<br />
;[http://dx.doi.org/10.1016/S0167-6423(01)00020-X Polytypic data conversion programs]<br />
:Patrik Jansson and Johan Jeuring. Science of Computer Programming, 43(1):35-75, 2002. An earlier version was published as "Polytypic compact printing and parsing" in Doaitse Swierstra, editor, ESOP'99: European Symposium on Programming, volume 1576 of LNCS, pages 273-287. Springer-Verlag, 1999.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/poly/terms/polytermsandrewriting.ps.gz A framework for polytypic programming on terms, with an application to rewriting]<br />
:Patrik Jansson and Johan Jeuring. In Workshop on Generic Programming. Utrecht University, 2000. UU-CS-2000-19.<br />
<br />
;[http://portal.acm.org/citation.cfm?id=969590 Functional pearl: Polytypic unification]<br />
:Patrik Jansson and Johan Jeuring. J. Funct. Program., 8(5):527-536, 1998.<br />
<br />
==Theory, cata, etc.==<br />
<br />
;[http://www.cse.chalmers.se/%7Ebernardy/ParDep/pardep.pdf Parametricity and dependent types]<br />
:Jean-Philippe Bernardy, Patrik Jansson, and Ross Paterson. In Proceedings of ICFP 2010, pages 345-356, Baltimore, Maryland, 2010. ACM.<br />
<br />
;[http://www.iis.sinica.edu.tw/~scm/pub/aopa.pdf Algebra of programming in Agda: dependent types for relational program derivation]<br />
:Shin-Cheng Mu, Hsiang-Shang Ko, and Patrik Jansson. J. Funct. Program., 19:545-579, 2009. Earlier version published as "Algebra of programming using dependent types" in Mathematics of Program Construction, volume 5133/2008 of LNCS, pages 268-283. Springer-Verlag, 2008.<br />
<br />
:[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.2150&rep=rep1&type=pdf Universes for generic programs and proofs in dependent type theory]<br />
;Marcin Benke, Peter Dybjer, and Patrik Jansson. Nordic Journal of Computing, 10(4):265{289, 2003.<br />
<br />
;[http://www.cse.chalmers.se/~patrikj/papers/polypPOPL97.pdf PolyP - a polytypic programming language extension]<br />
:P. Jansson and J. Jeuring. In Proc. POPL'97: Principles of Programming Languages, pages 470-482. ACM Press, 1997.<br />
<br />
==Other==<br />
<br />
;[http://www.cse.chalmers.se/~ulfn/papers/genericth.pdf Prototyping generic programming in Template Haskell]<br />
:Ulf Norell and Patrik Jansson. In Dexter Kozen, editor, Mathematics of Program Construction, volume 3125 of LNCS, pages 314-333. Springer-Verlag, 2004.<br />
<br />
;[http://www.cse.chalmers.se/~ulfn/papers/polyhaskell.pdf Polytypic programming in Haskell]<br />
:Ulf Norell and Patrik Jansson. In Phil Trinder, Greg Michaelson, and Ricardo Peña, editors, Implementation of Functional Languages 2003, 15th International Workshop, volume 3145 of LNCS, pages 168-184. Springer-Verlag, 2004.<br />
<br />
;[http://publications.lib.chalmers.se/records/fulltext/804.pdf Functional Polytypic Programming]<br />
:Patrik Jansson. PhD thesis, Computing Science, Chalmers University of Technology and Göteborg University, Sweden, May 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP04.pdf Generics for the masses]<br />
:Ralf Hinze. In Kathleen Fisher, editor, Proceedings of the 2004 International Conference on Functional Programming, Snowbird, Utah, September 19-22, 2004.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2002.ps.gz A Lightweight Implementation of Generics and Dynamics]<br />
:James Cheney and Ralf Hinze. In Manuel Chakravarty, editor, Proceedings of the ACM SIGPLAN 2002 Haskell Workshop, Pittsburgh, PA, USA, October 3, 2002, pp 90-104.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Tidata.ps.gz Type-indexed data types]<br />
:Ralf Hinze, Johan Jeuring, Andres Löh. In Eerke Boiten, Bernhard Möller, editors, Proceedings of the Sixth International Conference on Mathematics of Program Construction (MPC 2002), Dagstuhl, Germany, July 8-10, 2002. Lecture Notes in Computer Science 2386, pp. 148-174.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/WGP00b.ps.gz Memo functions, polytypically!]<br />
:Ralf Hinze. In Johan Jeuring, editor, Proceedings of the Second Workshop on Generic Programming, WGP 2000, Ponte de Lima, Portugal, 6th July 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/WGP00a.ps.gz Efficient Generalized Folds]<br />
:Ralf Hinze. In Johan Jeuring, editor, Proceedings of the Second Workshop on Generic Programming, WGP 2000, Ponte de Lima, Portugal, 6th July 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/MPC00.ps.gz Polytypic values possess polykinded types]<br />
:Ralf Hinze. In Roland Backhouse, J.N. Oliveira, editors, Proceedings of the Fifth International Conference on Mathematics of Program Construction (MPC 2000), Ponte de Lima, Portugal, July 3-5, 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/POPL00.ps.gz A New Approach to Generic Functional Programming] <br />
:Ralf Hinze. In Proceedings of the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Boston, Massachusetts, January 19-21, 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/FLOPS99.ps.gz Polytypic Programming with Ease]<br />
:Ralf Hinze. In 4th Fuji International Symposium on Functional and Logic Programming (FLOPS'99), Tsukuba, Japan, November 1999, pp. 21-36. Lecture Notes in Computer Science 1722.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW99.ps.gz A Generic Programming Extension for Haskell]<br />
:Ralf Hinze. In Erik Meijer, editor, Proceedings of the Third Haskell Workshop, Paris, France, September 1999. The proceedings appear as a technical report of Universiteit Utrecht, UU-CS-1999-28.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/CLAPF99.ps.gz Polytypic Functions Over Nested Datatypes]<br />
:Ralf Hinze. In Rafael Dueire Lins, editor, 3rd Latin-American Conference on Functional Programming (CLaPF'99), March 1999.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/habilitation.pdf Generic Programs and Proofs]<br />
:Ralf Hinze. Habilitationsschrift, Universitt Bonn, October 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications.html Type-indexed data types]<br />
:Ralf Hinze, Johan Jeuring, and Andres Löh. Technical Report UU-CS-2002-11, Department of Computer Science, Utrecht University, 2002.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications.html Combining generics and dynamics] <br />
:Peter Achten and Ralf Hinze. Technical Report NIII-R0206, Nijmegen Institute for Computing and Information Sciences, University of Nijmegen, July 2002.<br />
<br />
;[http://homepages.cwi.nl/~ralf/wrs04/ Programmable rewriting strategies in Haskell]<br />
:Ralf Lämmel, Invited paper, Proceedings of WRS 2004 13 pages To appear in ENTCS, 2004<br />
<br />
;[http://homepages.cwi.nl/~ralf/padl03/ A Strafunski Application Letter]<br />
:Ralf Lämmel and Joost Visser, Proc. of Practical Aspects of Declarative Programming (PADL'03), LNCS 2562, 2003, 357--375.<br />
<br />
;[http://homepages.cwi.nl/~ralf/wgp00/ Dealing with Large Bananas]<br />
:Ralf Lämmel and Joost Visser and Jan Kort, 46--59, WGP00 Proceedings of WGP'2000, Technical Report, Universiteit Utrecht<br />
<br />
;[http://www.cwi.nl/~ralf/just-two/ Strategic polymorphism requires just two combinators!]<br />
:Ralf Lämmel and Joost Visser, arXiv, cs.PL/0212048, 2002<br />
<br />
;[http://homepages.cwi.nl/~ralf/sfp00/ Type-safe Functional Strategies]<br />
:Ralf Lämmel and Joost Visser, draft proceedings of SFP'00, St Andrews, 2000.<br />
<br />
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/typecase.pdf TypeCase: A Design Pattern for Type-Indexed Functions] <br />
:Bruno C. d. S. Oliveira and Jeremy Gibbons (2005). Haskell Workshop, September 2005.<br />
<br />
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/hodgp.pdf Design Patterns as Higher-Order Datatype-Generic Programs]<br />
:Jeremy Gibbons (2006). Submitted for publication.<br />
<br />
;[ftp://ftp.kestrel.edu/pub/papers/meertens/Fpull.ps Functor Pulling]<br />
:Lambert Meertens. Proceedings of the International Workshop on Generic Programming (WGP'98), Marstrand, Sweden, June 1998.<br />
<br />
;[http://www.kestrel.edu/home/people/meertens/diverse/calc.pdf Calculemus Igitur!]<br />
:Lambert Meertens, Presented at The Fun of Programming, a Symposium in honour of Richard Bird's 60th birthday<br />
<br />
;[ftp://ftp.kestrel.edu/pub/papers/meertens/pp.ps Calculate Polytypically!]<br />
:Lambert Meertens, Programming Languages: Implementations Logics, and Programs, Proceedings PLILP '96 (Herbert Kuchen and S. Doaitse Swierstra, editors), LNCS 1140, pp. 1--16, 1996.<br />
<br />
;[http://www.kestrel.edu/home/people/meertens/diverse/ct4pc.pdf Category Theory for Program Construction] <br />
:Lambert Meertens, Lecture Notes for ESSLLI '95, Barcelona, Catalunya.<br />
<br />
;[http://www.seas.upenn.edu/~sweirich/RepLib/haskell08-weirich.pdf RepLib: A Library for Derivable Type Classes] <br />
:Stephanie Weirich. Haskell Workshop, Portland, OR, USA, September 2006.<br />
<br />
;[http://journals.cambridge.org/action/displayFulltext?type=1&fid=409644&jid=JFP&volumeId=-1&issueId=-1&aid=409643 Type-safe Runtime Polytypic Programming] <br />
:Stephanie Weirich. To appear in Journal of Functional Programming, 2006.<br />
<br />
;[http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/parametric.pdf Parametric datatype-genericity]<br />
:Jeremy Gibbons and Ross Paterson. Submitted for publication.<br />
<br />
<br />
[[Category:Research]]</div>
Steshaw
https://wiki.haskell.org/Orphan_instance
Orphan instance
2012-05-11T03:08:54Z
<p>Steshaw: </p>
<hr />
<div>An orphan instance is a type class instance for class C and type T which is neither defined in the module where C is defined nor in the module where T is defined.<br />
<br />
Type class instances are special in that they don't have a name and cannot be imported explicitly. This also means that they cannot be ''excluded'' explicitly. All instances defined in a module A are imported automatically when importing A, or importing any module that imports A, directly or indirectly.<br />
<br />
Say you want to define an alternative instance to an existing instance. This is a bad thing, since if two instances for the same class/type pair are in scope, then you cannot describe in Haskell 98 which instance to use. If you want to use multiple instances for the same class/type, you have to ensure that they are never imported together in a module somewhen. It is almost impossible to assert that, or put differently, it would reduce the composability of libraries considerably.<br />
<br />
The <hask>Monad</hask> instance of <hask>Either</hask> is a good example.<br />
It is not defined where <hask>Either</hask> is defined, thus all of its <hask>Monad</hask> instances must be orphan.<br />
Instead it is defined both in <hask>Control.Monad.Error</hask> of the [[Monad Transformer Library]]<br />
and in <hask>Control.Monad.Trans.Error</hask> of its lightweight cousin the 'transformers' package.<br />
Since some packages use MTL and others 'transformers' it becomes difficult to use that instance at all,<br />
although both instances are equivalent!<br />
Practical advice:<br />
The [[Exception|explicit-exception]] package with its <hask>Exceptional</hask> might be a better choice to use since it avoids the current problem with orphan Monad instances of <hask>Either</hask>.<br />
<br />
Actually, non-orphan instances can avoid definition of [[multiple instances]]. For defining an instance you have to import the class and the type and then you will automatically have the according non-orphan instances imported, too. If you want to define a new instance then the compiler will reject it immediately.<br />
<br />
<br />
A last advice:<br />
If you encounter a missing instance for a class or a type of a package,<br />
resist to define your own orphan instance, because it will likely collide with such instances of other packages,<br />
or it will collide with new instances added in later versions of that package.<br />
Instead ask the package author to add your instance.<br />
Sometimes it turns out that the instance was not included for the good reason<br />
that there is more than one reasonable instance definition.<br />
If your instance cannot be included, follow the advices in the article about [[multiple instances]].<br />
<br />
<br />
== See also ==<br />
<br />
* [[Multiple instances]]<br />
* Libraries mailing list on [http://www.haskell.org/pipermail/libraries/2008-August/010399.html Orphan instances can be good]<br />
* [http://modula3.elegosoft.com/pm3/pkg/modula3/src/discussion/partialRev.html Partial Revelation feature] of Modula-3 which causes similar problems like Haskell's type class instances<br />
<br />
[[Category:FAQ]]<br />
[[Category:Style]]</div>
Steshaw
https://wiki.haskell.org/Orphan_instance
Orphan instance
2012-05-11T03:07:44Z
<p>Steshaw: </p>
<hr />
<div>An orphan instance is a type class instance for class C and type T which is neither defined in the module where C is defined nor in the module where T is defined.<br />
<br />
Type class instances are special in that they don't have a name and cannot be imported explicitly. This also means that they cannot be ''excluded'' explicitly. All instances defined in a module A are imported automatically when importing A, or importing any module that imports A, directly or indirectly.<br />
<br />
Say you want to define an alternative instance to an existing instance. This is a bad thing, since if two instances for the same class/type pair are in scope, then you cannot describe in Haskell 98 which instance to use. If you want to use multiple instances for the same class/type, you have to ensure that they are never imported together in a module somewhen. It is almost impossible to assert that, or put differently, it would reduce the composability of libraries considerably.<br />
<br />
The <hask>Monad</hask> instance of <hask>Either</hask> is a good example.<br />
It is not defined where <hask>Either</hask> is defined, thus all of its <hask>Monad</hask> instances must be orphan.<br />
Instead it is defined both in <hask>Control.Monad.Error</hask> of the [[Monad Transformer Library]]<br />
and in <hask>Control.Monad.Trans.Error</hask> of its lightweight cousin the 'transformers' package.<br />
Since some packages use MTL and others 'transformers' it becomes difficult to use that instance at all,<br />
although both instances are equivalent!<br />
Practical advice:<br />
The [[Exception|explicit-exception]] package with its <hask>Exceptional</hask> might be a better choice to use since it avoids the current problem with orphan Monad instances of <hask>Either</hask>.<br />
<br />
Actually, non-orphan instances can avoid definition of [[multiple instances]]. For defining an instance you have to import the class and the type and then you will automatically have the according non-orphan instances imported, too. If you want to define a new instance then the compiler will reject it immediately.<br />
<br />
<br />
A last advice:<br />
If you encounter a missing instance for a class or a type of a package,<br />
resist to define your own orphan instance, because it will likely collide with such instances of other packages,<br />
or it will collide with new instances added in later versions of that package.<br />
Instead ask the package author to add your instance.<br />
Sometimes it turns out that the instance was not included for a good reason,<br />
that there is more than one reasonable instance definition.<br />
If your instance cannot be included, follow the advices in the article about [[multiple instances]].<br />
<br />
<br />
== See also ==<br />
<br />
* [[Multiple instances]]<br />
* Libraries mailing list on [http://www.haskell.org/pipermail/libraries/2008-August/010399.html Orphan instances can be good]<br />
* [http://modula3.elegosoft.com/pm3/pkg/modula3/src/discussion/partialRev.html Partial Revelation feature] of Modula-3 which causes similar problems like Haskell's type class instances<br />
<br />
[[Category:FAQ]]<br />
[[Category:Style]]</div>
Steshaw
https://wiki.haskell.org/List_function_suggestions
List function suggestions
2012-01-30T14:16:01Z
<p>Steshaw: /* groupOn and sortOn */ fix type signatures for groupOn + groupOn'</p>
<hr />
<div>This page lists proposed extensions to the Haskell list functions, whether in the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html Prelude] or [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html Data.List].<br />
Please discuss the proposals on the Talk Page or the libraries list, and use this page to record the results of discussions.<br />
However, since the advent of [[Hackage]]DB and [[Cabal-Install]] it is preferred to provide such functionality in specialised packages, rather than extending the already large base library.<br />
<br />
== Splitting on a separator, etc ==<br />
<br />
We need these useful functions in Data.List; I'll call them 'split' (and variants) and 'replace'. These are easily implemented but everyone always reinvents them. Various versions have been proposed, but there was no consensus on which was best, e.g.<br />
<br />
* [http://www.haskell.org/pipermail/haskell-cafe/2006-July/thread.html#16559 haskell-cafe thread July 2006]<br />
* [http://www.haskell.org/pipermail/libraries/2004-July/thread.html#2342 libraries thread July 2004]<br />
<br />
Note: a lot of good points (diverging opinions!) are covered in the mailing lists, but if we include all these various cases, split* will have 9 variants! The goal is to reach some kind of reasonable consensus, specifically on naming and semantics. Even if we need pairs of functions to satisfy various usage and algebraic needs. Failing to accommodate every possible use of these functions should not be a sufficient reason to abandon the whole project.<br />
<br />
The goal is clarity/uniformity (everyone uses them widely and recognizes them) and portability (I don't have to keep reimplementing these or copying that one file UsefulMissingFunctions.hs).<br />
<br />
Note: I (Jared Updike) am working with the belief that efficiency should not be a valid argument to bar these otherwise universally useful functions from the libraries; regexes are overkill for 'split' and 'replace' for common simple situations. Let's assume people will know (or learn) when they need heavier machinery (regexes, ByteString) and will use it when efficiency is important. We can try to facilitate this by reusing any names from ByteString, etc.<br />
<br />
=== split (working name) ===<br />
<br />
First of all: Check out whether the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/split split] package provides, what you need.<br />
<br />
We need a few of these:<br />
<br />
<haskell><br />
split :: Eq a => a -> [a] -> [[a]]<br />
splitWith :: (a -> Bool) -> [a] -> [[a]]<br />
tokens :: (a -> Bool) -> [a] -> [[a]]<br />
</haskell><br />
<br />
That preserve:<br />
<br />
<haskell><br />
join sep . split sep = id<br />
</haskell><br />
<br />
See below for 'join'<br />
<br />
And some that use above split but filter to remove empty elements (but do not preserve above property). Easy enough:<br />
<br />
<haskell><br />
split' :: Eq a => a -> [a] -> [[a]]<br />
splitWith' :: (a -> Bool) -> [a] -> [[a]]<br />
tokens' :: (a -> Bool) -> [a] -> [[a]]<br />
</haskell><br />
<br />
i.e.<br />
<br />
<haskell><br />
split' sep = filter (not . null) . split sep<br />
</haskell><br />
<br />
Usage would be:<br />
<br />
<haskell><br />
tokensws = tokens' (`elem` " \f\v\t\n\r\b")<br />
<br />
tokensws "Hello there\n \n Haskellers! " ==<br />
["Hello", "there", "Haskellers!"]<br />
</haskell><br />
<br />
'''TODO: add version like python with multi-element separator'''<br />
<br />
'''TODO: give code, copy-paste from threads mentioned above'''<br />
<br />
'''TODO: list names and reasons for/against'''<br />
<br />
=== replace (working name) ===<br />
<br />
<haskell><br />
replace :: [a] -> [a] -> [a] -> [a]<br />
</haskell><br />
<br />
like Python replace:<br />
<br />
<haskell><br />
replace "the" "a" "the quick brown fox jumped over the lazy black dog"<br />
===><br />
"a quick brown fox jumped over a lazy black dog"<br />
</haskell><br />
<br />
'''TODO: give code, copy-paste from threads mentioned above'''<br />
<br />
'''TODO: list names and reasons for/against'''<br />
<br />
Implemented for instance in [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-HT.html#v%3Areplace utility-ht].<br />
<br />
=== join (working name) ===<br />
<br />
<haskell><br />
join :: [a] -> [[a]] -> [a]<br />
</haskell><br />
<br />
<haskell><br />
join sep = concat . intersperse sep<br />
</haskell><br />
<br />
Note: this function has been implemented as 'intercalate' in Data.List.<br />
<br />
'''TODO: copy-paste things from threads mentioned above'''<br />
<br />
'''TODO: list names and reasons for/against'''<br />
<br />
== Sorted lists ==<br />
<br />
The following are versions of standard prelude functions, but intended for sorted lists. The advantage is that they frequently reduce execution time by an O(n). The disadvantage is that the elements have to be members of Ord, and the lists have to be already sorted.<br />
<br />
<haskell><br />
-- Eliminates duplicate entries from the list, where duplication is defined<br />
-- by the 'eq' function. The last value is kept.<br />
sortedNubBy :: (a -> a -> Bool) -> [a] -> [a]<br />
sortedNubBy eq (x1 : xs@(x2 : _)) =<br />
if eq x1 x2 then sortedNubBy eq xs else x1 : sortedNubBy eq xs<br />
sortedNubBy _ xs = xs<br />
<br />
sortedNub :: (Eq a) => [a] -> [a]<br />
sortedNub = sortedNubBy (==)<br />
<br />
-- Merge two sorted lists into a new sorted list. Where elements are equal<br />
-- the element from the first list is taken first.<br />
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]<br />
mergeBy cmp xs@(x1:xs1) ys@(y1:ys1) =<br />
if cmp x1 y1 == GT<br />
then y1 : mergeBy cmp xs ys1<br />
else x1 : mergeBy cmp xs1 ys<br />
mergeBy _ [] ys = ys<br />
mergeBy _ xs [] = xs<br />
<br />
merge :: (Ord a) => [a] -> [a] -> [a]<br />
merge = mergeBy compare<br />
</haskell><br />
<br />
<hask>mergeBy</hask> is implemented in [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-HT.html#v%3AmergeBy utility-ht].<br />
<br />
== Generalize groupBy and friends ==<br />
<br />
In the Haskell 98 List library, <hask>groupBy</hask> assumes that its argument function defines an equivalence, and the reference definition returns sublists where each element is equivalent to the first. The following definition, comparing adjacent elements, does the same thing on equivalence relations:<br />
<haskell><br />
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]<br />
groupBy rel [] = []<br />
groupBy rel (x:xs) = (x:ys) : groupBy rel zs<br />
where (ys,zs) = groupByAux x xs<br />
groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs)<br />
where (ys,zs) = groupByAux x xs<br />
groupByAux y xs = ([], xs)<br />
</haskell><br />
However it is also useful on other relations, e.g.<br />
* Picking out maximal ascending sublists (runs):<br />
<haskell><br />
> groupBy (<=) [7,3,5,9,6,8,3,5,4]<br />
[[7],[3,5,9],[6,8],[3,5],[4]]<br />
</haskell><br />
* Picking out contiguous sublists from an ascending sequence:<br />
<haskell><br />
> groupBy (\a b -> a+1 == b) [1,2,3,4,6]<br />
[[1,2,3,4],[6]]<br />
</haskell><br />
* Splitting a line at the start of each word:<br />
<haskell><br />
> groupBy (\ c1 c2 -> isLetter c1 || not (isLetter c2)) "This is a line"<br />
["This ","is ","a ","line"]<br />
</haskell><br />
Since this more useful definition agrees with the Haskell 98 one on its specified domain, it should be a backwards-compatible replacement.<br />
<br />
The same applies to <hask>nubBy</hask>, and possibly <hask>deleteBy</hask>, <hask>deleteFirstsBy</hask> and <hask>intersectBy</hask> (which could have more general types to make this clear).<br />
<br />
See:<br />
* Libraries list on [http://www.haskell.org/pipermail/libraries/2007-August/008028.html Data.List.groupBy with non-transitive equality predicate]<br />
* Implementation in [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-HT.html#v%3AgroupBy utility-ht]<br />
<br />
== groupOn and sortOn ==<br />
<br />
Almost all uses of <hask>groupBy</hask> and <hask>sortBy</hask> actually use a specific compare function. This can (using a recent version of base) as<br />
<hask>sortBy (comparing fst)</hask><br />
or<br />
<hask>sortBy (compare `on` fst)</hask>.<br />
Since this use is so common, it might be worthwhile to add separate functions for this:<br />
<haskell><br />
sortOn :: Ord b => (a -> b) -> [a] -> [a]<br />
sortOn = sortBy . comparing<br />
</haskell><br />
The same goes for <hask>groupBy</hask><br />
<haskell><br />
groupOn :: Eq b => (a -> b) -> [a] -> [[a]]<br />
groupOn f = groupBy ((==) `on` f)<br />
</haskell><br />
That is,<br />
<haskell><br />
groupOn' :: Eq b => (a -> b) -> [a] -> [[a]]<br />
groupOn' f = groupBy (\x y -> f x == f y)<br />
</haskell><br />
The names could be better, the idea behind 'on' comes from the 'on' function.<br />
<br />
See [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-Key.html utility-ht] package.<br />
<br />
== See also ==<br />
* [[Prelude extensions]]<br />
* [[Hackage]]<br />
<br />
[[Category:Proposals]]<br />
[[Category:Standard libraries]]<br />
[[Category:Idioms]]</div>
Steshaw
https://wiki.haskell.org/Category_theory
Category theory
2011-11-05T03:41:23Z
<p>Steshaw: Fix link to paper</p>
<hr />
<div>{{Foundations infobox}}<br />
'''Category theory''' can be helpful in understanding Haskell's type system. There exists a "Haskell category", of which the objects are Haskell types, and the morphisms from types <hask>a</hask> to <hask>b</hask> are Haskell functions of type <hask>a -> b</hask>. Various other Haskell structures can be used to make it a Cartesian closed category.<br />
<br />
__TOC__<br />
<br />
The Haskell wikibooks has [http://en.wikibooks.org/wiki/Haskell/Category_theory an introduction to Category theory], written specifically with Haskell programmers in mind.<br />
<br />
==Definition of a category==<br />
<br />
<br />
A category <math>\mathcal{C}</math>consists of two collections:<br />
<br />
Ob<math>(\mathcal{C})</math>, the objects of <math>\mathcal{C}</math><br />
<br />
Ar<math>(\mathcal{C})</math>, the arrows of <math>\mathcal{C}</math><br />
(which are not the same as [[Arrow]]s defined in [[GHC]])<br />
<br />
Each arrow <math>f</math> in Ar<math>(\mathcal{C})</math> has a<br />
domain, dom <math>f</math>, and a codomain, cod <math>f</math>, each<br />
chosen from Ob<math>(\mathcal{C})</math>. The notation <math>f\colon<br />
A \to B</math> means <math>f</math> is an arrow with domain<br />
<math>A</math> and codomain <math>B</math>. Further, there is a<br />
function <math>\circ</math> called composition, such that <math>g<br />
\circ f</math> is defined only when the codomain of <math>f</math> is<br />
the domain of <math>g</math>, and in this case, <math>g \circ f</math><br />
has the domain of <math>f</math> and the codomain of <math>g</math>. <br />
<br />
In symbols, if <math>f\colon A \to B</math> and <math>g\colon B \to<br />
C</math>, then <math>g \circ f \colon A \to C</math>. <br />
<br />
Also, for each object <math>A</math>, there is an arrow<br />
<math>\mathrm{id}_A\colon A \to A</math>, (often simply denoted as<br />
<math>1</math> or <math>\mathrm{id}</math>, when there is no chance of<br />
confusion). <br />
<br />
===Axioms===<br />
The following axioms must hold for <math>\mathcal{C}</math> to be a category:<br />
<br />
#If <math>f\colon A \to B</math> then <math>f \circ \mathrm{id}_A = \mathrm{id}_B\circ f = f</math> (left and right identity) <br />
#If <math>f\colon A \to B</math> and <math>g \colon B \to C</math> and <math>h \colon C \to D</math>, then <math>h \circ (g \circ f) = (h<br />
\circ g) \circ f</math> (associativity) <br />
<br />
===Examples of categories===<br />
* Set, the category of sets and set functions.<br />
* Mon, the category of monoids and monoid morphisms.<br />
* Monoids are themselves one-object categories.<br />
* Grp, the category of groups and group morphisms.<br />
* Rng, the category of rings and ring morphisms.<br />
* Grph, the category of graphs and graph morphisms.<br />
* Top, the category of topological spaces and continuous maps.<br />
* Preord, the category of preorders and order preserving maps.<br />
* CPO, the category of complete partial orders and continuous functions.<br />
* Cat, the category of categories and functors.<br />
<br />
* [[Hask]]<br />
* the category of data types and functions on data structures <br />
* the category of functions and data flows (~ data flow diagram)<br />
* the category of stateful objects and dependencies (~ object diagram)<br />
* the category of values and value constructors<br />
* the category of states and messages (~ state diagram)<br />
<br />
===Further definitions===<br />
With examples in Haskell at:<br />
* [[Category theory/Functor]]<br />
* [[Category theory/Natural transformation]]<br />
* [[Category theory/Monads]]<br />
<br />
== Categorical programming ==<br />
<br />
Catamorphisms and related concepts, categorical approach to functional programming, categorical programming. Many materials cited here refer to category theory, so as an introduction to this discipline see the [[#See also]] section.<br />
* Erik Meijer, Maarten Fokkinga, Ross Paterson: [http://research.microsoft.com/en-us/um/people/emeijer/Papers/fpca91.pdf Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire]. See also related documents (in the CiteSeer page). Understanding the article does not require knowledge of category theory—the paper is self-contained with regard to understanding catamorphisms, anamorphisms and other related concepts.<br />
* Roland Backhouse, Patrik Jansson, Johan Jeuring and Lambert Mertens. [http://www.cse.chalmers.se/~patrikj/poly/afp98/ Generic Programming - an Introduction]: Detailed introduction to categorial sums, product, polynomial functors and folds for the purpose of generic programming. Supplements the bananas paper.<br />
* Varmo Vene and Tarmo Uustalu: [http://citeseer.ist.psu.edu/vene98functional.html Functional Programming with Apomorphisms / Corecursion]<br />
* Varmo Vene: [http://www.cs.ut.ee/~varmo/papers/thesis.pdf Categorical Programming with Inductive and Coinductive Types]. The book gives Haskell examples to illustrate the deep categorical theory topic.<br />
* Tatsuya Hagino: [http://www.tom.sfc.keio.ac.jp/~hagino/thesis.pdf A Categorical Programming Language]<br />
* [http://pll.cpsc.ucalgary.ca/charity1/www/home.html Charity], a categorical programming language implementation.<br />
* [http://okmij.org/ftp/Haskell/categorical-maxn.lhs Deeply uncurried products, as categorists might like them] article mentions a conjecture: relatedness to [[Combinatory logic]]<br />
<br />
==Haskell libraries and tools==<br />
<br />
* [http://www.eyrie.org/~zednenem/2004/hsce/ Category extras] by [http://www.eyrie.org/~zednenem/about/dave.html David Menendez]: libraries for e.g. comonads, infinite data types.<br />
<br />
==Books==<br />
<br />
*Michael Barr and Charles Wells: [http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]. The online, freely available book is both an introductory and a detailed description of category theory. It also contains a category-theoretical description of the concept of ''monad'' (but calling it a ''triple'' instead of ''monad'').<br />
<br />
*R. F. C. Walters: [http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521419972 Categories and Computer Science]. Category Theory has, in recent years, become increasingly important and popular in computer science, and many universities now introduce Category Theory as part of the curriculum for undergraduate computer science students. Here, the theory is developed in a straightforward way, and is enriched with many examples from computer science.<br />
<br />
* Arbib&Manes: Arrow, Structures and Functors - The Categorical Imperative. (c)1975 Academic Press, ISBN 0-12-059060-3. Sadly now out of print but very little prerequisite knowledge is needed. It covers monads and the Yoneda lemma.<br />
<br />
==See also==<br />
<br />
* Michael Barr and Charles Wells have a [http://www.math.upatras.gr/~cdrossos/Docs/B-W-LectureNotes.pdf paper] that presents category theory from a computer-science perspective, assuming no prior knowledge of categories.<br />
*[http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.html A Gentle Introduction to Category Theory - the calculational approach] written by [http://wwwhome.cs.utwente.nl/~fokkinga/index.html Maarten M Fokkinga].<br />
* Wikipedia has a good [http://en.wikipedia.org/wiki/List_of_category_theory_topics collection of category-theory articles], although, as is typical of Wikipedia articles, they are rather dense.<br />
<br />
[[Category:Theoretical foundations]]<br />
[[Category:Mathematics]]</div>
Steshaw
https://wiki.haskell.org/User:Steshaw
User:Steshaw
2011-11-05T03:33:44Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw is dedicated to mastering the art of Haskell programming :)<br />
<br />
More at [http://steshaw.org/ steshaw.org].</div>
Steshaw
https://wiki.haskell.org/User:Steshaw
User:Steshaw
2010-12-22T10:52:08Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw is dedicated to mastering the art of Haskell programming :)<br />
<br />
More at [http://steshaw.org/ steshaw.org]. Works for [http://codefu.com.au Code Fu].</div>
Steshaw
https://wiki.haskell.org/OzHaskell
OzHaskell
2010-10-30T02:18:49Z
<p>Steshaw: </p>
<hr />
<div>'''There is AngloHaskell and now AmeroHaskell. Doesn't that call for OzHaskell?'''<br />
<br />
Who would be interested to have a Haskell event in Australia, possibly in Sydney? This is just a wild idea without any concrete date or format yet. Jot down any suggestions on this page.<br />
<br />
Interested Haskellers:<br />
<br />
* [[:User:Chak|Manuel Chakravarty]] (Sydney)<br />
* [[:User:TonyMorris|Tony Morris]] (Brisbane)<br />
* [[:User:Brecknell|Matthew Brecknell]] (Brisbane, will travel, prefer late Jan)<br />
* [[:User:Mark_Wassell|Mark Wassell]] - Prefer Jan/Feb option.<br />
* [[:User:Rl|Roman Leshchinskiy]]<br />
* [[:User:cbrad|Brad Clow]] (Brisbane)<br />
* [[:User:nornagon|Jeremy Apthorp]]<br />
* [[:User:AndrewA|Andrew Appleyard]] (Sydney)<br />
* [[:User:bjpop|Bernie Pope]] (Melbourne)<br />
* [[:User:benl23|Ben Lippmeier]]<br />
* [[:User:RohanDrape|Rohan Drape]] (Melbourne)<br />
* [[:User:ivanm|Ivan Miljenovic]] (Canberra)<br />
* [[:User:EricWilligers|Eric Willigers]]<br />
* [[:User:TonySloane|Tony Sloane]] (Sydney)<br />
* [[:User:Bens|Ben Sinclair]] (Sydney)<br />
* [[:User:andrep|Andre Pang]]<br />
* [[:User:AndrewBromage|Andrew Bromage]] (Melbourne)<br />
* [[:User:Droberts|Dale Roberts]] (Sydney)<br />
* [[:User:GeoffWilson|Geoff Wilson]] (Melbourne)<br />
* [[:User:Saulzar|Oliver Batchelor]] (Brisbane)<br />
* [[:User:Nick|Nick Seow]] (Sydney)<br />
* [[:User:sseefried|Sean Seefried]] (Sydney)<br />
* [[:User:green_tea|Alexis Hazell]] (Melbourne)<br />
* [[:User:PhilipDerrin|Philip Derrin]] (Sydney)<br />
* [[:User:Jeeva|Jeeva]] (Sydney)<br />
* [[:User:michaelneale|Michael Neale]] (Brisbane)<br />
* [[:User:rus|Ruslan Abdulkhalikov]] (Sydney)<br />
* [[:User:doverton|David Overton]] (London, soon to be Melbourne)<br />
* [[:User:mleeming|Michael Leeming]] (Sydney)<br />
* [[:User:horsfall|Ben Horsfall]] (Melbourne)<br />
* [[:User:trh|Toby Hutton]] (Melbourne)<br />
* [[:User:OJ|OJ Reeves]] (Brisbane)<br />
* [[:User:mwotton|Mark Wotton]] (Sydney)<br />
* [[:User:isaacsu | Isaac Su]] (Melbourne)<br />
* [[:User:steshaw|Steven Shaw]] (Brisbane)<br />
<br />
(Add your name!)<br />
<br />
== Possible dates ==<br />
<br />
== Format ==<br />
<br />
How about the following?<br />
<br />
* One day meeting with informal talks and demos (preferably on a Friday)<br />
* There could be a second, even less formal day, for those who want to hang out some more and maybe some hacking<br />
* Run it at the University of New South Wales, Sydney<br />
<br />
(Add your thoughts to the above.)<br />
<br />
== Talks and demos ==<br />
<br />
Do you have anything you'd like to talk about or a system you'd like to demo? '''This is just a tentative list - you commit to nothing.'''<br />
<br />
=== Talk proposals ===<br />
<br />
=== Demo proposals ===<br />
<br />
[[Category:Events]]</div>
Steshaw
https://wiki.haskell.org/User:Steshaw
User:Steshaw
2010-10-30T02:16:30Z
<p>Steshaw: </p>
<hr />
<div>Steven Shaw is dedicated to mastering the art of Haskell programming :)<br />
<br />
More at [http://steshaw.org/ steshaw.org]. Works for [http://codefu.com.au CodeFu].</div>
Steshaw
https://wiki.haskell.org/User:Steshaw
User:Steshaw
2010-10-30T01:56:02Z
<p>Steshaw: </p>
<hr />
<div>More at [http://steshaw.org/ steshaw.org].<br />
<br />
Steven Shaw</div>
Steshaw
https://wiki.haskell.org/User:Steshaw
User:Steshaw
2010-10-30T01:55:39Z
<p>Steshaw: </p>
<hr />
<div>More at [http://steshaw.org/].<br />
<br />
Steven Shaw</div>
Steshaw
https://wiki.haskell.org/New_monads
New monads
2010-09-07T23:10:30Z
<p>Steshaw: Link to wiki page on monadLib instead of old galios.com pages</p>
<hr />
<div>__TOC__<br />
<br />
Remember to add a [ [ Category:Code ] ] tag to any new sub-pages.<br />
<br />
== MonadBase ==<br />
<br />
It seems that the liftIO function from MonadIO can be generalized to access whatever the base of a transformer stack happens to be. So there is no need for a liftSTM, liftST, etc.<br />
<br />
View [[New monads/MonadBase]].<br />
<br />
== MonadLib ==<br />
<br />
[[MonadLib]] is written by Iavor S. Diatchki.<br />
<br />
It is a new version of the mtl package with base monads: Id, and Lift, and transformers ReaderT, WriterT, StateT, ExceptionT, ChoiceT, and ContT.<br />
<br />
It also defines BaseM which is like MonadBase above.<br />
<br />
== MonadRandom ==<br />
<br />
A simple monad transformer to allow computations in the transformed monad to generate random values.<br />
<br />
View [[New monads/MonadRandom]].<br />
<br />
===MonadRandomSplittable===<br />
A refinement of MonadRandom to integrate RandomGen's split function.<br />
<br />
View at [[New monads/MonadRandomSplittable]]<br />
<br />
== MaybeT ==<br />
<br />
The Maybe monad deserves a transformer, just like the other classic monads.<br />
<br />
View [[New monads/MaybeT]].<br />
<br />
== MonadSupply ==<br />
<br />
Here is a simple monad/monad transformer for computations which consume values from a (finite or infinite) supply. Note that due to pattern matching, running out of supply in a non-MonadZero monad will cause an error.<br />
<br />
View [[New monads/MonadSupply]].<br />
<br />
== MonadUndo ==<br />
<br />
Here is a modified state monad transformer for keeping track of undo/redo states automatically.<br />
<br />
View [[New monads/MonadUndo]].<br />
<br />
== MonadUnique ==<br />
<br />
This is a simple (trivial) monad transformer for supplying unique integer values to an algorithm.<br />
<br />
View [[New monads/MonadUnique]].<br />
<br />
== MonadSTO ==<br />
<br />
Here's an extension of the ST monad in which the references are ordered and showable (they list their creation index).<br />
<br />
View [[New monads/MonadSTO]].<br />
<br />
== MonadNondet ==<br />
<br />
There is a [[Sudoku#Monadic_Non-Deterministic_Solver | MonadNondet]] that when compiled with optimizations outperforms List.<br />
<br />
== Stateful nondeterminism ==<br />
<br />
There is a [[Stateful nondeterminism]] monad for if you want to do nondeterministic computation with local states for each of your threads and a global state shared by all your threads.<br />
<br />
== MonadAdvSTM ==<br />
<br />
Here is an extension of STM to easy interaction with IO after committing or retrying. Inspired by Simon P-J.<br />
<br />
View [[New monads/MonadAdvSTM]].<br />
<br />
== TimedStateT ==<br />
<br />
A monad transformer which combines State, Reader, and Error functionality to give the effect of a StateT monad which checks clock-time and stops the current computation if a period is exceeded.<br />
<br />
darcs get http://www.mapcar.org/haskell/TimedStateT/<br />
<br />
Haddocks: http://www.mapcar.org/haskell/TimedStateT/dist/doc/html/<br />
<br />
== MonadExit ==<br />
<br />
The Exit monad provides [[short-circuiting]] for complex program flow logic.<br />
<br />
If you are using CPS or MonadCont only for this purpose, the Exit monad will likely simplify your program considerably.<br />
<br />
View [[New monads/MonadExit|MonadExit]].<br />
<br />
== MonadSplit ==<br />
<br />
Represents the class of monads such that <br />
<br />
<haskell>l == (msplit l >>= \(x,xs) -> return x `mplus` xs)</haskell><br />
<br />
In English, msplit is a counterpart to "mplus".<br />
<br />
Using this, you can redefine many of the functions which previously depended on lists: foldM, scanM, inits, tails, and some derived functions.<br />
<br />
Note: A more general form of this monad,<br />
[http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html Data.Foldable], is now part of the<br />
[http://haskell.org/ghc/docs/latest/html/libraries/ standard libraries].<br />
<br />
View [[New monads/MonadSplit]].<br />
<br />
== Lazy and Strict variants ==<br />
<br />
This section contains monads that have interesting Strict or Lazy properties.<br />
<br />
=== LazyWriterT ===<br />
<br />
This came up on the mailing list: Why is WriterT never lazy? The answer is it does not use lazy patterns with "~". So here is a more useful [[New monads/LazyWriterT]] that add two "~" to the definition of (>>=) and renames WriterT to LazyWriterT.<br />
<br />
=== Strict RWS ===<br />
<br />
This was contribute by John Meacham on on the haskell-cafe mailing list. [[New monads/UnboxedRWS]] is an strict variant of RWS.<br />
<br />
[[Category:Idioms]]<br />
[[Category:Monad]]<br />
[[Category:Proposals]]</div>
Steshaw