https://wiki.haskell.org/api.php?action=feedcontributions&user=Piet+Delport&feedformat=atomHaskellWiki - User contributions [en]2020-04-03T20:53:38ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Applications_and_libraries/Mathematics&diff=58961Applications and libraries/Mathematics2014-10-06T14:28:32Z<p>Piet Delport: /* Computer Algebra */ update broken DoCon link with something working</p>
<hr />
<div>== Applications ==<br />
<br />
=== Physics ===<br />
<br />
;[http://ab-initio.mit.edu/meep/ Meep]<br />
:Meep (or MEEP) is a free finite-difference time-domain (FDTD) simulation software package developed at MIT to model electromagnetic systems. Meep used Haskell to generate C++ code, after Meep [http://ab-initio.mit.edu/wiki/index.php/Meep_release_notes 1.0] Haskell generation droped in favor of handwritten C++ code. <br />
<br />
;[[Numeric Quest]]<br />
:Jan Skibinski's [[Numeric Quest]] library provides modules that are useful for Quantum Mechanics, among other things.<br />
<br />
== Libraries ==<br />
<br />
=== Linear algebra ===<br />
<br />
;[http://hackage.haskell.org/package/bed-and-breakfast bed-and-breakfast]<br />
:A library that implements Matrix operations in pure Haskell using mutable arrays and the ST Monad. bed-and-breakfast does not need any additional software to be installed and can perform basic matrix operations like multiplication, finding the inverse, and calculating determinants efficiently.<br />
<br />
;[https://github.com/patperry/hs-linear-algebra hs-linear-algebra]<br />
:Patrick Perry's linear algebra library, built on BLAS. [https://github.com/cartazio/hs-cblas hs-cblas] seems to be a more up-to-date fork.<br />
<br />
;[http://www.cs.utah.edu/~hal/HBlas/index.html Wrapper to CLAPACK]<br />
<br />
;[http://haskelldsp.sourceforge.net/ Digital Signal Processing]<br />
:Modules for matrix manipulation, Fourier transform, interpolation, spectral estimation, and frequency estimation.<br />
<br />
;[http://article.gmane.org/gmane.comp.lang.haskell.general/13561 Index-aware linear algebra]<br />
:Frederik Eaton's library for statically checked matrix manipulation in Haskell<br />
<br />
;[[Numeric Quest]]<br />
:Jan Skibinski's [[Numeric Quest]] library provides several modules that are useful for linear algebra in general, among other things.<br />
<br />
;[[vector-space]]<br />
:The [[vector-space]] package defines classes and generic operations for vector spaces and affine spaces. It also defines a type of infinite towers of generalized derivatives (linear transformations).<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmatrix HMatrix]<br />
:By Alberto Ruiz. From the project [http://perception.inf.um.es/hmatrix/ website]:<br />
::''A purely functional interface to linear algebra and other numerical algorithms, internally implemented using LAPACK, BLAS, and GSL.<br />
<br />
::''This package includes standard matrix decompositions (eigensystems, singular values, Cholesky, QR, etc.), linear systems, numeric integration, root finding, etc.<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Vec Vec]<br />
:By Scott E. Dillard. Static dimension checking:<br />
::''Vectors are represented by lists with type-encoded lengths. The constructor is :., which acts like a cons both at the value and type levels, with () taking the place of nil. So x:.y:.z:.() is a 3d vector. The library provides a set of common list-like functions (map, fold, etc) for working with vectors. Built up from these functions are a small but useful set of linear algebra operations: matrix multiplication, determinants, solving linear systems, inverting matrices.''<br />
<br />
== See also ==<br />
<br />
* [[Linear algebra]]<br />
* [[Mathematical prelude discussion]]<br />
<br />
<br />
See also: [[Linear algebra|Design discussions]]<br />
<br />
=== [[Physical units]] ===<br />
<br />
;[[Dimensionalized numbers]]<br />
: Working with physical units like second, meter and so on in a type-safe manner.<br />
<br />
;[http://darcs.haskell.org/numericprelude/src/Number/SI.hs NumericPrelude: Physical units]<br />
: Numeric values with dynamically checked units.<br />
<br />
;[[CalDims]]<br />
:This is not simply a library providing a new type of <hask>Num</hask> class, but stand-alone calculation tool that supports user defined functions and units (basic and derived), so it can provide dimension-safe calculation (not embedded but via shell). Calculations can be modified/saved via shell. It uses rational numbers to avoid rounding errors where possible.<br />
<br />
;[http://code.google.com/p/dimensional/ Dimensional]<br />
: Library providing data types for performing arithmetic with physical quantities and units. Information about the physical dimensions of the quantities/units is embedded in their types and the validity of operations is verified by the type checker at compile time. The boxing and unboxing of numerical values as quantities is done by multiplication and division of units.<br />
<br />
=== Number representations ===<br />
<br />
==== Decimal numbers ====<br />
<br />
;[http://src.seereason.com/decimal/ Decimal arithmetic library]<br />
:An implementation of real decimal arithmetic, for cases where the binary floating point is not acceptable (for example, money).<br />
<br />
==== Real and rational numbers ====<br />
<br />
There are several levels of [[Exact real arithmetic|handling real numbers]] and according libraries.<br />
<br />
===== Arbitrary precision =====<br />
<br />
* Numbers have fixed precision<br />
* Rounding errors accumulate<br />
* Sharing is easy, i.e. in <hask>sqrt pi + sin pi</hask>, <hask>pi</hask> is computed only once<br />
* Fast, because the routines can make use of the fast implementation of <hask>Integer</hask> operations<br />
<br />
;[[Numeric Quest]]<br />
:Jan Skibinski's [[Numeric Quest]] library provides, among other things, a type for arbitrary precision rational numbers with transcendental functions.<br />
<br />
;[http://cvs.haskell.org/darcs/numericprelude/src/Number/FixedPoint.hs FixedPoint.hs]<br />
:part of NumericPrelude project<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-Basics AERN-Basics] [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-Real AERN-Real] [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-Real-Interval AERN-Real-Interval] [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-Real-Double AERN-Real-Double]<br />
:contains type classes that form a foundation for ''rounded arithmetic'' and ''interval arithmetic'' with explicit control of rounding and the possibility to increase the rounding precision arbitrarily for types that support it. At the moment there are instances for Double floating point numbers where one can control the direction of rounding but cannot increase the rounding precision. In the near future instances for MPFR arbitrary precision numbers will be provided. Intervals can use as endpoints any type that supports directed rounding in the numerical order (such as Double or MPFR) and operations on intervals are rounded either outwards or inwards. Outwards rounding allows to safely approximate exact real arithmetic while a combination of both outwards and inwards rounding allows one to safely approximate exact interval arithmetic. Inverted intervals with Kaucher arithmetic are also supported.<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-RnToRm AERN-RnToRm]<br />
:contains arithmetic of ''piecewise polynomial function intervals'' that approximate multi-dimensional (almost everywhere) continuous real functions to arbitrary precision<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmpfr hmpfr]<br />
:hmpfr is a purely functional haskell interface to the [http://www.mpfr.org/ MPFR] library<br />
<br />
;[http://hackage.haskell.org/package/numbers numbers]<br />
:provides an up-to-date, easy-to-use BigFloat implementation that builds with a modern GHC, among other things.<br />
<br />
===== Dynamic precision =====<br />
<br />
* You tell the precision and an expression shall be computed to, and the computer finds out, how precisely to compute the input values<br />
* Rounding errors do not accumulate<br />
* Sharing of temporary results is difficult, that is, in <hask>sqrt pi + sin pi</hask>, <hask>pi</hask> ''will'' be computed twice, each time with the required precision.<br />
* Almost as fast as arbitrary precision computation<br />
<br />
;[http://www.cs.man.ac.uk/arch/dlester/exact.html ERA] is an implementation (in Haskell 1.2) by David Lester.<br />
: It is quite fast, possibly the fastest Haskell implementation. At 220 lines it is also the shortest. Probably the shortest implementation of exact real arithmetic in any language.<br />
: The provided number type <hask>CReal</hask> is instance of the Haskell 98 numeric type classes and thus can be used whereever you used Float or Double before and encountered some numerical difficulties.<br />
:Here is a mirror: http://darcs.augustsson.net/Darcs/CReal/<br />
<br />
;[http://www.doc.ic.ac.uk/~ae/exact-computation/#bm:implementations IC-Reals] is an implementation by Abbas Edalat, Marko Krznar&#263; and Peter J. Potts.<br />
:This implementation uses linear fractional transformations.<br />
<br />
;[http://r6.ca/ Few Digits] by Russell O'Connor.<br />
:This is a prototype of the implementation he intendeds to write in [http://coq.inria.fr/ Coq]. Once the Coq implementation is complete, the Haskell code could be extracted producing an implementation that would be proved correct.<br />
<!--<br />
Example:<br />
*Data.Real.CReal> answer 1000 (exp 1 + sqrt 2)<br />
--><br />
<br />
;COMP is an implementation by Yann Kieffer.<br />
:The work is in beta and relies on new primitive operations on Integers which will be implemented in GHC. The library isn't available yet.<br />
<br />
;[http://www2.arnes.si/~abizja4/hera/ Hera] is an implementation by Aleš Bizjak.<br />
:It uses the [http://www.mpfr.org/ MPFR] library to implement dyadic rationals, on top of which are implemented intervals and real numbers. A real number is represented as a function <hask>Int -> Interval</hask> which represents a sequence of intervals converging to the real.<br />
<br />
===== Dynamic precision by lazy evaluation =====<br />
<br />
The real numbers are represented by an infinite datastructure, which allows you to increase precision successively by evaluating the data structure successively. All of the implementations below use some kind of digit stream as number representation.<br />
Sharing of results is simple.<br />
The implementations are either fast on simple expressions, because they use large blocks/bases, or they are fast on complex expressions, because they consume as little as possible input digits in order to emit the required output digits.<br />
<br />
;[http://medialab.freaknet.org/bignum/ BigFloat] is an implementation by Martin Guy.<br />
:It works with streams of decimal digits (strictly in the range from 0 to 9) and a separate sign. The produced digits are always correct. Output is postponed until the code is certain what the next digit is. This sometimes means that [http://medialab.freaknet.org/bignum/dudeney.html no more data is output].<br />
<br />
;In [http://users.info.unicaen.fr/~karczma/arpap/lazypi.ps.gz "The Most Unreliable Technique in the World to compute pi"] Jerzy Karczmarczuk develops some functions for computing pi lazily.<br />
<br />
;[http://darcs.haskell.org/numericprelude/src/Number/Positional.hs NumericPrelude: positional numbers]<br />
:Represents a real number as pair <hask>(exponent,[digit])</hask>, where the digits are <hask>Int</hask>s in the open range <hask>(-basis,basis)</hask>. There is no need for an extra sign item in the number data structure. The <hask>basis</hask> can range from <hask>10</hask> to <hask>1000</hask>. (Binary representations can be derived from the hexadecimal representation.) Showing the numbers in traditional format (non-negative digits) fails for fractions ending with a run of zeros. However the internal representation with negative digits can always be shown and is probably more useful for further processing. An interface for the numeric type hierarchy of the NumericPrelude project is provided.<br />
:It features<br />
:* basis conversion<br />
:* basic arithmetic: addition, subtraction, multiplication, division<br />
:* algebraic arithmetic: square root, other roots (no general polynomial roots)<br />
:* transcendental arithmetic: pi, exponential, logarithm, trigonometric and inverse trigonometric functions<br />
<br />
=== Type class hierarchies ===<br />
<br />
There are several approaches to improve the [[Mathematical prelude discussion|numeric type class hierarchy]].<br />
<br />
;Dylan Thurston and Henning Thielemann's [[Numeric Prelude]]<br />
:Experimental revised framework for numeric type classes. Needs hiding of Prelude, overriding hidden functions like fromInteger and multi-parameter type classes. Probably restricted to GHC.<br />
<br />
;Jerzy Karczmarczuk's [http://www.haskell.org/pipermail/haskell-cafe/2001-February/001510.html approach]<br />
<br />
;Serge D. Mechveliani's [ftp://ftp.botik.ru/pub/local/Mechveliani/basAlgPropos/ Basic Algebra proposal]<br />
<br />
;Andrew Frank's [http://www.haskell.org/pipermail/haskell-cafe/2006-April/015326.html approach]<br />
:The proposal: ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf<br />
<br />
;Haskell Prime: [http://hackage.haskell.org/trac/haskell-prime/ticket/112 Ongoing efforts for the language revision]<br />
<br />
=== Discrete mathematics ===<br />
<br />
;[http://andrew.bromage.org/darcs/numbertheory/ Number Theory Library]<br />
:Andrew Bromage's Haskell number theory library, providing operations on primes, fibonacci sequences and combinatorics.<br />
<br />
;[http://users.skynet.be/jyp/HGAL/ HGAL]<br />
:An haskell implementation of Brendan McKay's algorithm for graph canonic labeling and automorphism group. (aka Nauty)<br />
<br />
;[http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521849306 Computational Oriented Matroids]<br />
:is a book by [http://wwwopt.mathematik.tu-darmstadt.de/~bokowski/ Jürgen G. Bokowski], where he develops Haskell code for Matroid computations.<br />
<br />
See also [[Libraries and tools/Cryptography]]<br />
<br />
=== Computer Algebra ===<br />
<br />
<!-- Older link: http://haskell.org/docon/ --><br />
; [http://homepages.inf.ed.ac.uk/wadler/realworld/docon2.html DoCon], the Algebraic Domain Constructor<br />
: A library by Sergey D. Mechveliani for Algebra, turns GHCi into a kind of Computer Algebra System<br />
<br />
;[http://www.info.unicaen.fr/~karczma/arpap/ Papers by Jerzy Karczmarczuk]<br />
:Some interesting uses of Haskell in mathematics, including [[functional differentiation]], power series, continued fractions.<br />
<br />
;[http://www.robtougher.com/HCAS/ HCAS] by Rob Tougher.<br />
<br />
=== Statistics ===<br />
;[http://hackage.haskell.org/package/hstats hstats]<br />
: Statistical Computing with Haskell<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hmatrix-gsl-stats hmatrix-gsl-stats]<br />
: A binding to the statistics portion of GSL. Works with hmatrix<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hstatistics hstatistics]<br />
: A library for doing statistics. Works with hmatrix<br />
<br />
=== Plotting ===<br />
<br />
;[http://hackage.haskell.org/package/easyplot easyplot]<br />
: Simple and easy wrapper to gnuplot.<br />
<br />
;[[Gnuplot]]<br />
: Simple wrapper to gnuplot<br />
<br />
;[http://hackage.haskell.org/packages/archive/hmatrix/latest/doc/html/Graphics-Plot.html hmatrix]<br />
: contains a deprecated gnuplot wrapper<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Chart Chart]<br />
: A library for generating 2D Charts and Plots, based upon the cairo graphics library.<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/plot plot]<br />
: A library for generating figures, based upon the cairo graphics libary with<br />
a simple, monadic interface.<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/probability probability]<br />
: the module Numeric.Probability.Visualize contains a wrapper to [http://www.r-project.org/ R]<br />
<br />
=== Numerical optimization ===<br />
This classification is somewhat arbitrary. Something more systematic like GAMS might be helpful.<br />
<br />
==== bindings ====<br />
;[http://repetae.net/john/recent/out/HsASA.html Adaptive Simulated Annealing]<br />
:A Haskell interface to Lester Ingber's adaptive simulating annealing code.<br />
<br />
;[http://hackage.haskell.org/package/cmaes CMA-ES]<br />
:A wrapper for Covariance Matrix Adaptation Evolution Strategy<br />
<br />
;[https://github.com/ghorn/nlopt-haskell nlopt-haskell]<br />
:A low-level binding to the nlopt library<br />
<br />
;[http://hackage.haskell.org/package/ipopt-hs ipopt-hs]<br />
:A haskell binding to ipopt including automatic differentiation<br />
<br />
;[http://hackage.haskell.org/package/glpk-hs glpk-hs]<br />
:A high-level interface to GLPK's linear programming and mixed integer programming features.<br />
<br />
==== pure haskell ====<br />
;[http://hackage.haskell.org/package/nonlinear-optimization nonlinear-optimization]<br />
:A pure-haskell CG_DESCENT method is implemented<br />
<br />
=== Miscellaneous libraries ===<br />
<br />
;[http://www.robtougher.com/HaskellMath/ HaskellMath]<br />
:The HaskellMath library is a sandbox for experimenting with mathematics algorithms. So far I've implemented a few quantitative finance models (Black Scholes, Binomial Trees, etc) and basic linear algebra functions. Next I might work on either computer algebra or linear programming. All comments welcome!<br />
<br />
;[http://hackage.haskell.org/package/HaskellForMaths HaskellForMaths]<br />
:David Amos' library for combinatorics, group theory, commutative algebra and non-commutative algebra, which is described in an [http://haskellformaths.blogspot.com/ accompanying blog].<br />
<br />
;[http://darcs.haskell.org/htam/ Various math stuff by Henning Thielemann]<br />
:This is some unsorted mathematical stuff including: gnuplot wrapper (now maintained as separate package), portable grey map (PGM) image reader and writer, simplest numerical integration, differentiation, zero finding, interpolation, solution of differential equations, combinatorics, some solutions of math riddles, computation of fractal dimensions of iterated function systems (IFS)<br />
<br />
;[[Numeric Quest]]<br />
:Jan Skibinski wrote a collection of Haskell modules that are useful for Mathematics in general, and Quantum Mechanics in particular.<br />
<br />
:Some of the modules are hosted on [http://darcs.haskell.org/numeric-quest/ haskell.org]. They include modules for:<br />
:* Rational numbers with transcendental functions<br />
:* Roots of polynomials<br />
:* Eigensystems<br />
:* Tensors<br />
:* Dirac quantum mechanics<br />
<br />
:Other modules in Numeric Quest are currently only available via the [http://web.archive.org/web/20010605003250/http://www.numeric-quest.com/haskell/ Internet Archive]. They include, among many other things:<br />
:* [http://web.archive.org/web/*/http://www.numeric-quest.com/haskell/ State vector evolution]<br />
:* [http://web.archive.org/web/*/http://www.numeric-quest.com/haskell/ Short study of fuzzy oscillator]<br />
<br />
:See the [[Numeric Quest]] page for more information.<br />
<br />
;[http://www.dinkla.net/fp/cglib.html Geometric Algorithms]<br />
:A small Haskell library, containing algorithms for two-dimensional convex hulls, triangulations of polygons, Voronoi-diagrams and Delaunay-triangulations, the QEDS data structure, kd-trees and range-trees.<br />
<br />
;[http://home.solcon.nl/mklooster/repos/hmm/ Hmm: Haskell Metamath]<br />
:Hmm is a small Haskell library to parse and verify Metamath databases.<br />
<br />
;[[Probabilistic Functional Programming]]<br />
:The PFP library is a collection of modules for Haskell that facilitates probabilistic functional programming, that is, programming with stochastic values. The probabilistic functional programming approach is based on a data type for representing distributions. A distribution represent the outcome of a probabilistic event as a collection of all possible values, tagged with their likelihood. A nice aspect of this system is that simulations can be specified independently from their method of execution. That is, we can either fully simulate or randomize any simulation without altering the code which defines it.<br />
<br />
;[[Sinc function]]<br />
<br />
;[[Gamma and Beta function]]<br />
<br />
;[http://repetae.net/john/recent/out/Boolean.html Boolean]<br />
:A general boolean algebra class and some instances for Haskell.<br />
<br />
;[http://darcs.haskell.org/~lemmih/hode/ HODE]<br />
:HODE is a binding to the Open Dynamics Engine. ODE is an open source, high performance library for simulating rigid body dynamics.<br />
<br />
;[http://sourceforge.net/projects/ranged-sets Ranged Sets]<br />
:A ranged set is a list of non-overlapping ranges. The ranges have upper and lower boundaries, and a boundary divides the base type into values above and below. No value can ever sit on a boundary. So you can have the set <math>(2.0, 3.0] \cup (5.3, 6)</math>.<br />
<br />
;[http://code.google.com/p/hhydra/ hhydra]<br />
:Hhydra is a tool to compute Goodstein successions and hydra puzzles described by Bernard Hodgson in his article 'Herculean or Sisyphean tasks?' published in No 51 March 2004 of the Newsletter of the European Mathematical Society.<br />
<br />
[[Category:Mathematics|*]]<br />
{{LibrariesPage}}</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Template:Main/Headlines&diff=58640Template:Main/Headlines2014-08-09T23:49:15Z<p>Piet Delport: Haskell Platform 2014.2 has been released</p>
<hr />
<div><div class="subtitle">Headlines</div><br />
<br />
* ''2014:''<br />
** The '''[http://www.haskell.org/platform/ Haskell Platform 2014.2]''' has been [http://www.haskell.org/pipermail/haskell/2014-August/024284.html released]<br />
** [http://www.haskell.org/ghc/ GHC 7.8.2] is released<br />
<br />
* ''2013:''<br />
** '''[http://hackage.haskell.org/ Hackage 2]''' is now live, powered by Haskell.<br />
** '''[https://www.fpcomplete.com/business/haskell-center/overview/ FP Haskell Center]''', the commercial in-browser IDE by FP Complete '''[https://www.fpcomplete.com/business/blog/fp-complete-launches-fp-haskell-center-the-worlds-1st-haskell-ide-and-deployment-platform/ has been released]'''.<br />
** '''[http://www.haskell.org/pipermail/haskell/2013-September/039154.html Cabal 1.18]''' has been released.<br />
** The '''[http://haskell.org/platform?2013.2 Haskell Platform 2013.2]''' is now available<br />
** '''[http://www.fpcomplete.com FP Complete]''' has compiled a short '''[https://docs.google.com/forms/d/1dZVuT_2-x2C515YeXnAzXwddIvftALwgSoz2NYjS4aE/viewform survey]''' to help build the Haskell user community.<br />
<br />
* ''2012:''<br />
** The '''[http://haskell.org/platform Haskell Platform 2012.4]''' is now available<br />
** [http://www.haskell.org/ghc/ GHC 7.6] is released<br />
** The '''[http://haskell.org/platform Haskell Platform 2012.2]''' is now available<br />
** [http://www.yesodweb.com/blog/2012/04/announcing-yesod-1-0 Yesod 1.0] is now available<br />
** [http://www.haskell.org/ghc/ GHC 7.4] is released<br />
** O'Reilly have announced a forthcoming book on [http://www.haskell.org/pipermail/haskell/2012-May/023328.html Parallel and Concurrent Haskell]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Functional_dependencies&diff=58635Functional dependencies2014-08-06T12:56:13Z<p>Piet Delport: /* See also */ add Functional dependencies vs. type families</p>
<hr />
<div>[[Category:Glossary]]<br />
[[Category:Language extensions]]<br />
Functional dependencies are used to constrain the parameters of type classes. They let you state that in a [[multi-parameter type class]], one of the [[parameter]]s can be determined from the others, so that the [[parameter]] determined by the others can, for example, be the return type but none of the argument types of some of the methods.<br />
<br />
==Examples==<br />
Suppose you want to implement some code to perform simple [[linear algebra]]:<br />
<haskell><br />
data Vector = Vector Int Int deriving (Eq, Show)<br />
data Matrix = Matrix Vector Vector deriving (Eq, Show)<br />
</haskell><br />
You want these to behave as much like numbers as possible. So you might start by overloading Haskell's Num class:<br />
<haskell><br />
instance Num Vector where<br />
Vector a1 b1 + Vector a2 b2 = Vector (a1+a2) (b1+b2)<br />
Vector a1 b1 - Vector a2 b2 = Vector (a1-a2) (b1-b2)<br />
{- ... and so on ... -}<br />
<br />
instance Num Matrix where<br />
Matrix a1 b1 + Matrix a2 b2 = Matrix (a1+a2) (b1+b2)<br />
Matrix a1 b1 - Matrix a2 b2 = Matrix (a1-a2) (b1-b2)<br />
{- ... and so on ... -}<br />
</haskell><br />
The problem comes when you want to start multiplying quantities. You really need a multiplication function which overloads to different types:<br />
<haskell><br />
(*) :: Matrix -> Matrix -> Matrix<br />
(*) :: Matrix -> Vector -> Vector<br />
(*) :: Matrix -> Int -> Matrix<br />
(*) :: Int -> Matrix -> Matrix<br />
{- ... and so on ... -}<br />
</haskell><br />
How do we specify a type class which allows all these possibilities?<br />
<br />
We could try this:<br />
<haskell><br />
class Mult a b c where<br />
(*) :: a -> b -> c<br />
<br />
instance Mult Matrix Matrix Matrix where<br />
{- ... -}<br />
<br />
instance Mult Matrix Vector Vector where<br />
{- ... -}<br />
</haskell><br />
That, however, isn't really what we want. As it stands, even a simple expression like this has an ambiguous type unless you supply an additional type declaration on the intermediate expression:<br />
<haskell><br />
m1, m2, m3 :: Matrix<br />
(m1 * m2) * m3 -- type error; type of (m1*m2) is ambiguous<br />
(m1 * m2) :: Matrix * m3 -- this is ok<br />
</haskell><br />
After all, nothing is stopping someone from coming along later and adding another instance:<br />
<haskell><br />
instance Mult Matrix Matrix (Maybe Char) where<br />
{- whatever -}<br />
</haskell><br />
The problem is that <hask>c</hask> shouldn't really be a free type variable. When you know the types of the things that you're multiplying, the result type should be determined from that information alone.<br />
<br />
You can express this by specifying a functional dependency, or fundep for short:<br />
<haskell><br />
class Mult a b c | a b -> c where<br />
(*) :: a -> b -> c<br />
</haskell><br />
This tells Haskell that <hask>c</hask> is uniquely determined from <hask>a</hask> and <hask>b</hask>.<br />
<br />
Fundeps have lots more uses than just implementing C++-style function overloading, of course. See [http://web.cecs.pdx.edu/~mpj/pubs/fundeps.html the paper] by Mark P. Jones for further details.<br />
<br />
Fundeps are not standard Haskell 98. (Nor are [[multi-parameter type class]]es, for that matter.) They are, however, supported at least in [[GHC]] and [[Hugs]] and will almost certainly end up in Haskell'.<br />
<br />
[[User:AndrewBromage]]<br />
<br />
== Another example ==<br />
<br />
The following example makes use of the FlexibleInstances, MultiParamTypeClasses and FunctionalDependencies GHC extensions.<br />
<br />
<haskell><br />
-- Read as: "container" type determines "elem" type.<br />
class Extract container elem | container -> elem where<br />
extract :: container -> elem<br />
</haskell><br />
<br />
The functional dependency "container -> elem" promises that we won't declare multiple instances with the same "container" type.<br />
<br />
<haskell><br />
instance Extract (a,b) a where<br />
extract (x,_) = x<br />
</haskell><br />
<br />
Because of the functional dependency we can't have the previous instance *and* this one:<br />
<br />
<haskell>-- instance Extract (a,b) b where ...</haskell><br />
<br />
Because of the functional dependency we can say:<br />
<br />
<haskell>v = extract ('x', 3)</haskell><br />
<br />
and it will infer the type <haskell>v :: Char</haskell><br />
<br />
Without the functional dependency, both instances above would be allowed, and the type of v would be potentially ambiguous. Even if only one instance is defined, the type system will not figure it out without the functional dependency.<br />
<br />
== Tutorials ==<br />
<br />
* [http://www.cs.chalmers.se/~hallgren/Papers/wm01.html Fun with functional dependencies], Thomas Hallgren (2001)<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], Conrad Parker (2007)<br />
<br />
== See also ==<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#functional-dependencies GHC documentation]<br />
* [[Functional dependencies vs. type families]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Catamorphisms&diff=58631Catamorphisms2014-08-03T22:28:17Z<p>Piet Delport: /* References */ fix broken link to Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire</p>
<hr />
<div>== Folding data structures ==<br />
An overview and derivation of the category-theoretic notion of a catamorphism as a recursion scheme, and an exploration of common variations on the theme.<br />
<br />
<br />
== Description ==<br />
Catamorphisms are generalizations of the concept of a fold in functional programming. A catamorphism deconstructs a data structure with an F-algebra for its underlying functor.<br />
<br />
== History ==<br />
The name catamorphism appears to have been chosen by Lambert Meertens [1]. The category theoretic machinery behind these was resolved by Grant Malcolm [2][3], and they were popularized by Meijer, Fokkinga and Paterson[4][5]. The name comes from the Greek 'κατα-' meaning "downward or according to". A useful mnemonic is to think of a catastrophe destroying something.<br />
<br />
== Notation ==<br />
A catamorphism for some F-algebra (X,f) is denoted (| f |)F. When the functor F can be determined unambiguously, it is usually written (|φ|) or <b>cata φ</b>. Due to this choice of notation, a catamorphism is sometimes called a banana and the (|.|) notation is sometimes referred to as banana brackets.<br />
<br />
== Haskell Implementation ==<br />
<haskell><br />
type Algebra f a = f a -> a <br />
newtype Mu f = InF { outF :: f (Mu f) } <br />
cata :: Functor f => Algebra f a -> Mu f -> a <br />
cata f = f . fmap (cata f) . outF <br />
</haskell><br />
<br />
== Alternate Definitions ==<br />
<haskell><br />
cata f = hylo f outF <br />
cata f = para (f . fmap fst) <br />
</haskell><br />
<br />
== Duality ==<br />
A catamorphism is the categorical dual of an anamorphism.<br />
<br />
== Derivation ==<br />
If (μF,inF) is the initial F-algebra for some endofunctor F and (X,φ) is an F-algebra, then there is a unique F-algebra homomorphism from (μF,inF) to (X,φ), which we denote (| φ |)F. <br />
<br />
That is to say, the following diagram commutes:<br />
[[Image:cata-diagram.png|center]]<br />
<br />
== Laws == <br />
{| class="wikitable" style="text-align: center<br />
|- <br />
! Rule !! Haskell<br />
|-<br />
! cata-cancel <br />
| <hask>cata phi . InF = phi . fmap (cata phi)</hask><br />
|-<br />
! cata-refl <br />
| <hask>cata InF = id</hask><br />
|-<br />
! cata-fusion <br />
| <hask>f . phi = phi . fmap f => <br />
f . cata phi = cata phi</hask><br />
|-<br />
! cata-compose <br />
| <hask>eps :: f :~> g => <br />
cata phi . cata (In . eps) =<br />
cata (phi . eps)</hask><br />
|}<br />
<br />
== Examples ==<br />
<br />
The underlying functor for a string of Chars and its fixed point<br />
<haskell><br />
data StrF x = Cons Char x | Nil <br />
type Str = Mu StrF<br />
instance Functor StrF where <br />
fmap f (Cons a as) = Cons a (f as) <br />
fmap f Nil = Nil <br />
</haskell><br />
<br />
The length of a string as a catamorphism.<br />
<haskell><br />
length :: Str -> Int <br />
length = cata phi where <br />
phi (Cons a b) = 1 + b <br />
phi Nil = 0 <br />
</haskell><br />
<br />
The underlying functor for the natural numbers. <br />
<haskell><br />
data NatF a = S a | Z deriving (Eq,Show) <br />
type Nat = Mu NatF <br />
instance Functor NatF where <br />
fmap f Z = Z <br />
fmap f (S z) = S (f z) <br />
</haskell><br />
<br />
Addition as a catamorphism. <br />
<haskell><br />
plus :: Nat -> Nat -> Nat <br />
plus n = cata phi where <br />
phi Z = n <br />
phi (S m) = s m <br />
</haskell><br />
<br />
Multiplication as a catamorphism <br />
<haskell><br />
times :: Nat -> Nat -> Nat <br />
times n = cata phi where <br />
phi Z = z <br />
phi (S m) = plus n m <br />
z :: Nat <br />
z = InF Z <br />
s :: Nat -> Nat <br />
s = InF . S <br />
</haskell><br />
<br />
<br />
== Mendler Style ==<br />
A somewhat less common variation on the theme of a catamorphism is a catamorphism as a recursion scheme a la Mendler, which removes the dependency on the underlying type being an instance of Haskell's Functor typeclass [6].<br />
<br />
<haskell><br />
type MendlerAlgebra f c = forall a. (a -> c) -> f a -> c [8]<br />
mcata :: MendlerAlgebra f c -> Mu f -> c <br />
mcata phi = phi (mcata phi) . outF <br />
</haskell><br />
<br />
From which we can derive the original notion of a catamorphism:<br />
<br />
<haskell><br />
cata :: Functor f => Algebra f c -> Mu f -> c <br />
cata phi = mcata (\f -> phi . fmap f) <br />
</haskell><br />
This can be seen to be equivalent to the original definition of cata by expanding the definition of mcata.<br />
<br />
The principal advantage of using Mendler-style is it is independent of the definition of the Functor definition for f.<br />
<br />
== Mendler and the Contravariant Yoneda Lemma ==<br />
The definition of a Mendler-style algebra above can be seen as the application of the contravariant version of the Yoneda lemma to the functor in question. <br />
<br />
In type theoretic terms, the contravariant Yoneda lemma states that there is an isomorphism between (f a) and ∃b. (b -> a, f b), which can be witnessed by the following definitions.<br />
<br />
<haskell><br />
data CoYoneda f a = forall b. CoYoneda (b -> a) (f b) <br />
toCoYoneda :: f a -> CoYoneda f a <br />
toCoYoneda = CoYoneda id <br />
fromCoYoneda :: Functor f => CoYoneda f a -> f a <br />
fromCoYoneda (CoYoneda f v) = fmap f v <br />
</haskell><br />
Note that in Haskell using an existential requires the use of data, so there is an extra bottom that can inhabit this type that prevents this from being a true isomorphism.<br />
<br />
However, when used in the context of a (CoYoneda f)-Algebra, we can rewrite this to use universal quantification because the functor f only occurs in negative position, eliminating the spurious bottom.<br />
<haskell><br />
Algebra (CoYoneda f) a <br />
= (by definition) CoYoneda f a -> a <br />
~ (by definition) (exists b. (b -> a, f b)) -> a <br />
~ (lifting the existential) forall b. (b -> a, f b) -> a <br />
~ (by currying) forall b. (b -> a) -> f b -> a <br />
= (by definition) MendlerAlgebra f a<br />
</haskell><br />
<br />
== Generalized Catamorphisms ==<br />
Most more advanced recursion schemes for folding structures, such as paramorphisms and zygomorphisms can be seen in a common framework as "generalized" catamorphisms[7]. A generalized catamorphism is defined in terms of an F-W-algebra and a distributive law for the comonad W over the functor F which preserves the structure of the comonad W.<br />
<br />
<haskell><br />
type Dist f w = forall a. f (w a) -> w (f a) <br />
type FWAlgebra f w a = f (w a) -> a <br />
g_cata :: (Functor f, Comonad w) => <br />
Dist f w -> FWAlgebra f w a -> Mu f -> a <br />
g_cata k g = extract . c where <br />
c = liftW g . k . fmap (duplicate . c) . outF <br />
</haskell><br />
However, a generalized catamorphism can be shown to add no more expressive power to the concept of a catamorphism. That said the separation of a number of the "book keeping" concerns by isolating them in a reusable distributive law can ease the development of F-W-algebras.<br />
<br />
We can transform an F-W-algebra into an F-algebra by including the comonad in the carrier for the algebra and then extracting after we perform this somewhat more stylized catamorphism:<br />
<br />
<haskell><br />
lowerAlgebra :: (Functor f, Comonad w) => <br />
Dist f w -> FWAlgebra f w a -> Algebra f (w a) <br />
lowerAlgebra k phi = liftW phi . k . fmap duplicate <br />
g_cata :: (Functor f, Comonad w) => <br />
Dist f w -> FWAlgebra f w a -> Mu f -> a <br />
g_cata k phi = extract . cata (lowerGAlgebra k phi) <br />
</haskell><br />
<br />
and we can trivially transform an Algebra into an F-W-Algebra by mapping the counit of the comonad over F. Then using the trivial identity functor, we can represent every catamorphism as a generalized-catamorphism. <br />
<haskell><br />
liftAlgebra :: (Functor f, Comonad w) => <br />
Algebra f a -> FWAlgebra f w a<br />
<br />
liftAlgebra phi = phi . fmap extract<br />
<br />
<br />
cata :: Functor f => Algebra f a -> Mu f -> a<br />
cata f = g_cata (Identity . fmap runIdentity) (liftAlgebra f)<br />
</haskell><br />
Between these two definitions we can see that a generalized catamorphism does not increase the scope of a catamorphism to encompass any more operations, it simply further stylizes the pattern of recursion.<br />
<br />
== References ==<br />
# L. Meertens. First Steps towards the theory of Rose Trees. Draft Report, CWI, Amsterdam, 1987.<br />
# G. Malcolm. PhD. Thesis. University of Gronigen, 1990.<br />
# G. Malcolm. Data structures and program transformation. Science of Computer Programming, 14:255--279, 1990.<br />
# E. Meijer. [http://research.microsoft.com/~emeijer/Papers/Thesis.pdf Calculating Compilers], Ph.D Thesis, Utrecht State University, 1992.<br />
# E. Meijer, M. Fokkinga, R. Paterson, [http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire], 5th ACM Conference on Functional Programming Languages and Computer Architecture.<br />
# T. Uustalu, V. Vene. [http://citeseer.ist.psu.edu/314266.html Coding Recursion a la Mendler.] Proceedings 2nd Workshop on Generic Programming, WGP'2000, Ponte de Lima, Portugal, 6 July 2000<br />
# T. Uustalu, V. Vene, A. Pardo. [http://citeseer.ist.psu.edu/uustalu01recursion.html Recursion schemes from Comonads.] Nordic Journal of Computing. Volume 8 , Issue 3 (Fall 2001). 366--390, 2001 ISSN:1236-6064<br />
# E. Kmett. [http://comonad.com/reader/2008/catamorphism/ Catamorphism.] The Comonad.Reader, 2008.</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Template_Haskell&diff=58407Template Haskell2014-07-01T23:36:14Z<p>Piet Delport: /* Template Haskell tutorials and papers */ add Wayback Machine links for Bulat's tutorials</p>
<hr />
<div>'''[http://hackage.haskell.org/package/template-haskell Template Haskell]''' is a [[GHC]] extension to Haskell that adds compile-time metaprogramming facilities. The original design can be found here: http://research.microsoft.com/en-us/um/people/simonpj/papers/meta-haskell/. It is [http://www.haskell.org/ghc/docs/latest/html/users_guide/template-haskell.html included] in GHC since version 6. <br />
<br />
This page hopes to be a more central and organized repository of TH related things.<br />
<br />
<br />
=What is Template Haskell?=<br />
<br />
Template Haskell is an extension to Haskell 98 that allows you to do type-safe compile-time meta-programming, with Haskell both as the manipulating language and the language being manipulated. <br />
<br />
Intuitively Template Haskell provides new language features that allow us to convert back and forth between concrete syntax, i.e. what you would type when you write normal Haskell code, and abstract syntax trees. These abstract syntax trees are represented using Haskell datatypes and, at compile time, they can be manipulated by Haskell code. This allows you to reify (convert from concrete syntax to an abstract syntax tree) some code, transform it and splice it back in (convert back again), or even to produce completely new code and splice that in, while the compiler is compiling your module. <br />
<br />
For email about Template Haskell, use the [http://www.haskell.org/mailman/listinfo/glasgow-haskell-users GHC users mailing list]. It's worth joining if you start to use TH.<br />
<br />
<br />
= Template Haskell specification =<br />
<br />
Template Haskell is only documented rather informally at the moment. Here are the main resources:<br />
<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/template-haskell.html The user manual section on Template Haskell]<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/template-haskell.html#th-quasiquotation The user manual section on quasi-quotation], which is closely related to Template Haskell.<br />
* [http://research.microsoft.com/~simonpj/papers/meta-haskell/ The original Template Haskell paper]<br />
* [http://research.microsoft.com/en-us/um/people/simonpj/tmp/notes2.ps Notes on Template Haskell version 2], which describes changes since the original paper. Section 8 describes the difficulty with pattern splices, which are therefore not implemented.<br />
* [http://hackage.haskell.org/package/template-haskell The Template Haskell API]<br />
<br />
= Template Haskell tutorials and papers =<br />
<br />
* Bulat's tutorials:<br />
*# [http://web.archive.org/web/20100703060856/http://www.haskell.org/bz/thdoc.htm Wayback Machine], [http://docs.google.com/uc?id=0B4BgTwf_ng_TM2MxZjJjZjctMTQ0OS00YzcwLWE5N2QtMDI0YzE4NGUwZDM3 Google Docs]<br />
*# [http://web.archive.org/web/20100703060841/http://www.haskell.org/bz/th3.htm Wayback Machine], [http://docs.google.com/uc?id=0B4BgTwf_ng_TOGJkZjM4ZTUtNGY5My00ZThhLTllNDQtYzJjMWJiMzJhZjNj Google Docs]<br />
<br />
: One reader said "These docs are *brilliant* ! Exactly what I need to get an understanding of TH."<br />
<br />
<small>(Note: These documents are from [http://www.archive.org the Wayback machine] because the originals disappeared. They're public documents on Google docs, which shouldn't require logging in. However, if you're asked to sign in to view them, you're running into a known Google bug. You can fix it by browsing to [http://www.google.com Google], presumably gaining a cookie in the process.)</small><br />
<br />
<!--<br />
* Mark Snyder's Template Haskell chapter on the Software Generation and Configuration Report<br />
** http://nix.cs.uu.nl/dist/courses/sgc-report-unstable-latest/manual/chunk-chapter/templatehaskell.html<br />
--><br />
* A very short tutorial to understand the basics in 10 Minutes.<br />
** http://www.hyperedsoftware.com/blog/entries/first-stab-th.html<br />
<br />
* GHC Template Haskell documentation<br />
** http://www.haskell.org/ghc/docs/latest/html/users_guide/template-haskell.html<br />
<br />
* Papers about Template Haskell<br />
<br />
** Template metaprogramming for Haskell, by Tim Sheard and Simon Peyton Jones, Oct 2002. [[http://www.haskell.org/wikiupload/c/ca/Meta-haskell.ps ps]]<br />
** Template Haskell: A Report From The Field, by Ian Lynagh, May 2003. [[http://www.haskell.org/wikiupload/2/24/Template_Haskell-A_Report_From_The_Field.ps ps]]<br />
** Unrolling and Simplifying Expressions with Template Haskell, by Ian Lynagh, December 2002. [[http://www.haskell.org/wikiupload/e/ed/Template-Haskell-Utils.ps ps]]<br />
** Automatic skeletons in Template Haskell, by Kevin Hammond, Jost Berthold and Rita Loogen, June 2003. [[http://www.haskell.org/wikiupload/6/69/AutoSkelPPL03.pdf pdf]]<br />
** Optimising Embedded DSLs using Template Haskell, by Sean Seefried, Manuel Chakravarty, Gabriele Keller, March 2004. [[http://www.haskell.org/wikiupload/b/b5/Seefried04th-pan.pdf pdf]]<br />
** Typing Template Haskell: Soft Types, by Ian Lynagh, August 2004. [[http://www.haskell.org/wikiupload/7/72/Typing_Template_Haskell_Soft_Types.ps ps]]<br />
<br />
= Other useful resources =<br />
<br />
* (2011) [https://github.com/leonidas/codeblog/blob/master/2011/2011-12-27-template-haskell.md Basic Tutorial of Template Haskell] <br />
<br />
* (2011) Greg Weber's [http://www.yesodweb.com/blog/2011/10/code-generation-conversation blog post on Template Haskell and quasi-quoting] in the context of Yesod.<br />
<br />
* (2012) Mike Ledger's [http://quasimal.com/posts/2012-05-25-quasitext-and-quasiquoting.html tutorial on TemplateHaskell and QuasiQuotation] for making an interpolated text QuasiQuoter.<br />
<br />
<!-- * [http://www.haskell.org/th/ The old Template Haskell web page]. Would someone feel like moving this material into the HaskellWiki? <br />
--><br />
<!-- * Old and probably not too useful for most but maybe... http://www.cse.unsw.edu.au/~chak/haskell/ghc/comm/exts/th.html <br />
--><br />
* [http://www.cs.ox.ac.uk/people/ian.lynagh/Fraskell/ Fraskell documentation] & explanation of how Template Haskell is used to vastly speed it up.<br />
<br />
* [[Quasiquotation]]<br />
<br />
Feel free to update our Wikipedia entry http://en.wikipedia.org/wiki/Template_Haskell<br />
<br />
= Projects =<br />
<br />
What are you doing/planning to do/have done with Template Haskell?<br />
<br />
* The [http://www.ict.kth.se/org/ict/ecs/sam/projects/forsyde/www ForSyDe methodology] is currently implemented as a Haskell-based DSL which makes extensive use of Template Haskell.<br />
<br />
* I have written a primitive (untyped) binding to the Objective-C runtime system on Mac OS X. It needs just TH, no "stub files" are created, no separate utilities are required. Initial snapshot is at http://www.kfunigraz.ac.at/imawww/thaller/wolfgang/HOC020103.tar.bz2 -- WolfgangThaller<br />
<br />
* I am writing Template Greencard - a reimplementation of GreenCard using TH. Many bits work out really nicely. A few bits didn't work so nicely - once I get some time to think, I'll try to persuade the TH folk to make some changes to fix some of these. -- AlastairReid<br />
<br />
* I'm writing Hacanon - a framework for automatic generation of C++ bindings. Read "automated Template Greencard for C++" (-: Darcs repo: http://www.ScannedInAvian.org/repos/hacanon - You'll need gccxml (http://www.gccxml.org/) to compile the examples. - 27 Dec Lemmih.<br />
<br />
* Following other FFI tools developers, I see some future for Template HSFFIG, especially when it comes to autogenerate peek and poke methods for structures defined in C; may be useful for implementation of certain network protocols such as X11 where layout of messages is provided as C structure/union declaration. - 16 Dec 2005 DimitryGolubovsky<br />
<br />
* I am using Template Haskell as a mechanism to get parsed, typechecked code into an Ajax based Haskell Equational Reasoning tool [[Haskell Equational Reasoning Assistant]], as well as simplify the specification of equational relationships between pieces of code. There was a quicktime movie of the tool being used on http://www.gill-warbington.com/home/andy/share/hera1.html - AndyGill <br />
<br />
* I am working on functional metaprogramming techniques to enhance programming reliability and productivity, by reusing much of the existing compiler technology. Template Haskell is especially interesting for me because it permits to check size information of structures by the compiler, provided this information is available at compile time. This approach is especially appropriate for hardware designs, where the structures are fixed before the circuit starts operating. See our metaprogramming web page at http://www.infosun.fmi.uni-passau.de/cl/metaprog/ -- ChristophHerrmann(http://www.cs.st-and.ac.uk/~ch)<br />
<br />
* I am using Template Haskell to do type safe database access. I initially [http://www.nabble.com/Using-Template-Haskell-to-make-type-safe-database-access-td17027286.html proposed this on haskell-cafe]. I connect to the database at compile-time and let the database do SQL parsing and type inference. The result from parsing and type inference is used to build a type safe database query which can executed at run-time. [[MetaHDBC | You can find the project page here]] -- [mailto:mads_lindstroem@yahoo.dk Mads Lindstrøm]<br />
<br />
= Utilities =<br />
<br />
Helper functions, debugging functions, or more involved code e.g. a monadic fold algebra for TH.Syntax.<br />
<br />
* http://www.haskell.org/pipermail/template-haskell/2003-September/000176.html<br />
<br />
= Known Bugs =<br />
<br />
Take a look at the [http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status=reopened&component=Template+Haskell&order=priority open bugs against Template Haskell] on the GHC bug tracker.<br />
<br />
= Wish list =<br />
<br />
Things that Ian Lynagh (Igloo) mentioned in his paper ''Template Haskell: A Report From The Field'' in May 2003 (available [http://www.haskell.org/wikiupload/2/24/Template_Haskell-A_Report_From_The_Field.ps here]), by section:<br />
<br />
* Section 2 (curses)<br />
** The ability to splice names (into "foreign import" declarations, in particular)<br />
** The ability to add things to the export list from a splice(?)<br />
** The ability to use things defined at the toplevel of a module from splices in that same module (would require multi-stage compilation, as opposed to the current approach of expanding splices during typechecking)<br />
<br />
* Section 3 (deriving instances of classes)<br />
** <strike>First-class reification</strike> (the <hask>reify</hask> function)<br />
** A way to discover whether a data constructor was defined infix or prefix (which is necessary to derive instances for <hask>Read</hask> and <hask>Show</hask> as outlined in [http://www.haskell.org/onlinereport/derived.html The Haskell 98 Report: Specification of Derived Instances]) (if there is a way, [http://community.haskell.org/~ndm/derive/ Derive] seems ignorant of it)<br />
** Type/context splicing (in <hask>instance</hask> headers in particular)<br />
<br />
* Section 4 (printf)<br />
** He says something to the effect that a pattern-matching form of the quotation brackets would be cool if it was expressive enough to be useful, but that this would be hard. (Don't expect this anytime soon.)<br />
<br />
* Section 5 (fraskell)<br />
** Type information for quoted code (so that simplification can be done safely even with overloaded operations, like, oh, <hask>(+)</hask>)<br />
<br />
* Section 6 (pan)<br />
** Type info again, and strictness info too (this one seems a bit pie-in-the-sky...)<br />
<br />
(Please leave the implemented ones here, but crossed off.)<br />
<br />
Any other features that may be nice, and TH projects you'd want to see.<br />
<br />
* A TH tutorial (mainly a distillation and update of ''Template Meta-programming in Haskell'' at this point)<br />
* <strike>Write Haddock documentation for the Template Haskell library (http://hackage.haskell.org/trac/ghc/ticket/1576).</strike><br />
* Make `reify` on a class return a list of the instances of that class (http://www.haskell.org/pipermail/template-haskell/2005-December/000503.html). (See also [http://hackage.haskell.org/trac/ghc/ticket/1577 GHC ticket #1577].)<br />
* A set of simple examples on this wiki page<br />
* A TH T-shirt with new logo to wear at conferences<br />
* (Long-term) Unify Language.Haskell.Syntax with Language.Haskell.TH.Syntax so there's just one way to do things (http://hackage.haskell.org/package/haskell-src-meta does a one-way translation, for haskell-src-exts)<br />
<br />
---------------<br />
<br />
= Tips and Tricks =<br />
<br />
== What to do when you can't splice that there ==<br />
<br />
When you try to splice something into the middle of a template and find that you just can't, instead of getting frustrated about it, why not use the template to see what it would look like in longhand? <br />
<br />
First, an excerpt from a module of my own. I, by the way, am SamB.<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts -fth #-}<br />
<br />
module MMixMemory where<br />
<br />
import Data.Int<br />
import Data.Word<br />
<br />
class (Integral int, Integral word)<br />
=> SignConversion int word | int -> word, word -> int where<br />
<br />
toSigned :: word -> int<br />
toSigned = fromIntegral<br />
toUnsigned :: int -> word<br />
toUnsigned = fromIntegral<br />
<br />
</haskell><br />
<br />
Say I want to find out what I need to do to splice in the types for an instance declaration for the SignConversion class, so that I can declare instances for Int8 with Word8 through Int64 with Word64. So, I start up good-ol' GHCi and do the following:<br />
<br />
<haskell><br />
$ ghci -fth -fglasgow-exts<br />
Prelude> :l MMixMemory<br />
*MMixMemory> :m +Language.Haskell.TH.Syntax<br />
*MMixMemory Language.Haskell.TH.Syntax> runQ [d| instance SignConversion Int Word where |] >>= print<br />
[InstanceD [] (AppT (AppT (ConT MMixMemory.SignConversion) (ConT GHC.Base.Int)) (ConT GHC.Word.Word)) []]<br />
</haskell><br />
<br />
== What can <tt>reify</tt> see? ==<br />
<br />
When you use <tt>reify</tt> to give you information about a <tt>Name</tt>, GHC will tell you what it knows. But sometimes it doesn't know stuff. In particular<br />
<br />
* '''Imported things'''. When you reify an imported function, type constructor, class, etc, from (say) module M, GHC runs off to the interface file <tt>M.hi</tt> in which it deposited all the info it learned when compiling M. However, if you compiled M without optimisation (ie <tt>-O0</tt>, the default), and without <tt>-XTemplateHaskell</tt>, GHC tries to put as little info in the interface file as possible. (This is a possibly-misguided attempt to keep interface files small.) In particular, it may dump only the name and kind of a data type into <tt>M.hi</tt>, but not its constructors.<br />
: Under these circumstances you may reify a data type but get back no information about its data constructors or fields. Solution: compile M with <br />
:* <tt>-O</tt>, or<br />
:* <tt>-fno-omit-interface-pragmas</tt> (implied by -O), or<br />
:* <tt>-XTemplateHaskell</tt>.<br />
<br />
* '''Function definitions'''. The <tt>VarI</tt> constructor of the <tt>Info</tt> type advertises that you might get back the source code for a function definition. In fact, GHC currently (7.4) <em>always</em> returns <tt>Nothing</tt> in this field. It's a bit awkward and no one has really needed it.<br />
<br />
== Why does <tt>runQ</tt> crash if I try to reify something? ==<br />
<br />
This program will fail with an error message when you run it:<br />
<haskell><br />
main = do info <- runQ (reify (mkName "Bool")) -- more hygenic is: (reify ''Bool)<br />
putStrLn (pprint info)<br />
</haskell><br />
Reason: <tt>reify</tt> consults the type environment, and that is not available at run-time. The type of <tt>reify</tt> is <br />
<haskell><br />
reify :: Quasi m => Q a -> m a<br />
</haskell><br />
The IO monad is a poor-man's instance of <tt>Quasi</tt>; it can allocate unique names and gather error messages, but it can't do <tt>reify</tt>. This error should really be caught statically.<br />
<br />
Instead, you can run the splice directly (ex. in ghci -XTemplateHaskell), as the following shows:<br />
<br />
<haskell><br />
GHCi> let tup = $(tupE $ take 4 $ cycle [ [| "hi" |] , [| 5 |] ])<br />
GHCi> :type tup<br />
tup :: ([Char], Integer, [Char], Integer)<br />
<br />
GHCi> tup<br />
("hi",5,"hi",5)<br />
<br />
GHCi> $(stringE . show =<< reify ''Int)<br />
"TyConI (DataD [] GHC.Types.Int [] [NormalC GHC.Types.I# [(NotStrict,ConT GHC.Prim.Int#)]] [])"<br />
</haskell><br />
<br />
Here's an [http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010844.html email thread with more details].<br />
<br />
-----------------<br />
<br />
= Examples =<br />
== Tuples ==<br />
=== Select from a tuple ===<br />
<br />
An example to select an element from a tuple of arbitrary size. Taken from [http://research.microsoft.com/en-us/um/people/simonpj/papers/meta-haskell/meta-haskell.pdf this paper].<br />
<br />
Use like so:<br />
<br />
> $(sel 2 3) ('a','b','c')<br />
'b'<br />
> $(sel 3 4) ('a','b','c','d')<br />
'c'<br />
<br />
<br />
<haskell><br />
sel :: Int -> Int -> ExpQ<br />
sel i n = [| \x -> $(caseE [| x |] [alt]) |]<br />
where alt :: MatchQ<br />
alt = match pat (normalB rhs) []<br />
<br />
pat :: Pat<br />
pat = tupP (map varP as)<br />
<br />
rhs :: ExpQ<br />
rhs = varE(as !! (i -1)) -- !! is 0 based<br />
<br />
as :: [String]<br />
as = ["a" ++ show i | i <- [1..n] ]<br />
</haskell><br />
<br />
Alternately:<br />
<br />
<haskell><br />
sel' i n = lamE [pat] rhs<br />
where pat = tupP (map varP as)<br />
rhs = varE (as !! (i - 1))<br />
as = [ "a" ++ show j | j <- [1..n] ]<br />
</haskell><br />
<br />
=== Apply a function to the n'th element ===<br />
<br />
<haskell><br />
tmap i n = do<br />
f <- newName "f"<br />
as <- replicateM n (newName "a")<br />
lamE [varP f, tupP (map varP as)] $<br />
tupE [ if i == i'<br />
then [| $(varE f) $a |]<br />
else a<br />
| (a,i') <- map varE as `zip` [1..] ]<br />
</haskell><br />
<br />
Then tmap can be called as:<br />
<br />
> $(tmap 3 4) (+ 1) (1,2,3,4)<br />
(1,2,4,4)<br />
<br />
=== Convert the first n elements of a list to a tuple ===<br />
<br />
This example creates a tuple by extracting elements from a list. Taken from<br />
[http://www.xoltar.org/2003/aug/13/templateHaskellTupleSample.html www.xoltar.org]<br />
<br />
Use like so:<br />
<br />
> $(tuple 3) [1,2,3,4,5]<br />
(1,2,3)<br />
> $(tuple 2) [1,2]<br />
(1,2)<br />
<br />
<haskell><br />
tuple :: Int -> ExpQ<br />
tuple n = [|\list -> $(tupE (exprs [|list|])) |]<br />
where<br />
exprs list = [infixE (Just (list))<br />
(varE "!!")<br />
(Just (litE $ integerL (toInteger num)))<br />
| num <- [0..(n - 1)]]<br />
</haskell><br />
<br />
An alternative that has more informative errors (a failing pattern match failures give an exact location):<br />
<br />
<haskell><br />
tuple :: Int -> ExpQ<br />
tuple n = do<br />
ns <- replicateM n (newName "x")<br />
lamE [foldr (\x y -> conP '(:) [varP x,y]) wildP ns] (tupE $ map varE ns)<br />
</haskell><br />
<br />
=== Un-nest tuples ===<br />
Convert nested tuples like (a,(b,(c,()))) into (a,b,c) given the length to generate.<br />
<br />
<haskell><br />
unNest n = do<br />
vs <- replicateM n (newName "x")<br />
lamE [foldr (\a b -> tupP [varP a , b])<br />
(conP '() [])<br />
vs]<br />
(tupE (map varE vs))<br />
</haskell><br />
<br />
<br />
<br />
== [[Template Haskell/Marshall Data|Marshall a datatype to and from Dynamic]] ==<br />
This approach is an example of using template haskell to delay typechecking<br />
to be able to abstract out the repeated calls to fromDynamic:<br />
<br />
<haskell><br />
data T = T Int String Double<br />
<br />
toT :: [Dynamic] -> Maybe T<br />
toT [a,b,c] = do<br />
a' <- fromDynamic a<br />
b' <- fromDynamic b<br />
c' <- fromDynamic c<br />
return (T a' b' c')<br />
toT _ = Nothing<br />
</haskell><br />
<br />
== Printf ==<br />
Build it using a command similar to:<br />
<br />
ghc --make Main.hs -o main<br />
<br />
Main.hs:<br />
<br />
<haskell><br />
{-# LANGUAGE TemplateHaskell #-}<br />
<br />
-- Import our template "printf"<br />
import PrintF (printf)<br />
<br />
-- The splice operator $ takes the Haskell source code<br />
-- generated at compile time by "printf" and splices it into<br />
-- the argument of "putStrLn".<br />
main = do<br />
putStrLn $ $(printf "Hello %s %%x%% %d %%x%%") "World" 12<br />
</haskell><br />
<br />
PrintF.hs:<br />
<br />
<haskell><br />
{-# LANGUAGE TemplateHaskell #-}<br />
module PrintF where<br />
<br />
-- NB: printf needs to be in a separate module to the one where<br />
-- you intend to use it.<br />
<br />
-- Import some Template Haskell syntax<br />
import Language.Haskell.TH<br />
<br />
-- Possible string tokens: %d %s and literal strings<br />
data Format = D | S | L String<br />
deriving Show<br />
<br />
-- a poor man's tokenizer<br />
tokenize :: String -> [Format]<br />
tokenize [] = []<br />
tokenize ('%':c:rest) | c == 'd' = D : tokenize rest<br />
| c == 's' = S : tokenize rest<br />
tokenize (s:str) = L (s:p) : tokenize rest -- so we don't get stuck on weird '%'<br />
where (p,rest) = span (/= '%') str<br />
<br />
-- generate argument list for the function<br />
args :: [Format] -> [PatQ]<br />
args fmt = concatMap (\(f,n) -> case f of<br />
L _ -> []<br />
_ -> [varP n]) $ zip fmt names<br />
where names = [ mkName $ 'x' : show i | i <- [0..] ]<br />
<br />
-- generate body of the function<br />
body :: [Format] -> ExpQ<br />
body fmt = foldr (\ e e' -> infixApp e [| (++) |] e') (last exps) (init exps)<br />
where exps = [ case f of<br />
L s -> stringE s<br />
D -> appE [| show |] (varE n)<br />
S -> varE n<br />
| (f,n) <- zip fmt names ]<br />
names = [ mkName $ 'x' : show i | i <- [0..] ]<br />
<br />
-- glue the argument list and body together into a lambda<br />
-- this is what gets spliced into the haskell code at the call<br />
-- site of "printf"<br />
printf :: String -> Q Exp<br />
printf format = lamE (args fmt) (body fmt)<br />
where fmt = tokenize format<br />
</haskell><br />
<br />
== Handling Options with Templates ==<br />
A common idiom for treating a set of options, e.g. from GetOpt, is to define a datatype with all the flags and using a list over this datatype:<br />
<br />
<haskell><br />
data Options = B1 | B2 | V Integer<br />
<br />
options = [B1, V 3]<br />
</haskell><br />
<br />
While it's simple testing if a Boolean flag is set (simply use "elem"), it's harder to check if an option with an argument is set. It's even more tedious writing helper-functions to obtain the value from such an option since you have to explicitely "un-V" each. Here, Template Haskell can be (ab)used to reduce this a bit. The following example provides the module "OptionsTH" which can be reused regardless of the constructors in "Options". Let's start with showing how we'd like to be able to program. Notice that the resulting lists need some more treatment e.g. through "foldl".<br />
<br />
Options.hs:<br />
<br />
<haskell><br />
module Main where<br />
<br />
import OptionsTH<br />
import Language.Haskell.TH.Syntax<br />
<br />
data Options = B1 | B2 | V Int | S String deriving (Eq, Read, Show)<br />
<br />
options = [B1, V 3]<br />
<br />
main = do<br />
print foo -- test if B1 set: [True,False]<br />
print bar -- test if V present, w/o value: [False,True]<br />
print baz -- get value of V if available: [Nothing,Just 3]<br />
<br />
foo :: [Bool]<br />
-- Query constructor B1 which takes no arguments<br />
foo = map $(getopt (THNoArg (mkArg "B1" 0))) options<br />
<br />
bar :: [Bool]<br />
-- V is a unary constructor. Let mkArg generate the required<br />
-- wildcard-pattern "V _".<br />
bar = map $(getopt (THNoArg (mkArg "V" 1))) options<br />
<br />
-- Can't use a wildcard here!<br />
baz :: [(Maybe Int)]<br />
baz = map $(getopt (THArg (conP "V" [varP "x"]))) options<br />
</haskell><br />
<br />
OptionsTH.hs<br />
<br />
<haskell><br />
module OptionsTH where<br />
<br />
import Language.Haskell.TH.Syntax<br />
<br />
-- datatype for querying options:<br />
-- NoArg: Not interested in value (also applies to Boolean flags)<br />
-- Arg: Grep value of unary(!) constructor<br />
data Args = THNoArg Pat | THArg Pat<br />
<br />
getopt :: Args -> ExpQ<br />
getopt (THNoArg pat) = lamE [varP "y"] (caseE (varE "y") [cons0, cons1])<br />
where<br />
cons0 = match pat (normalB [| True |]) []<br />
cons1 = match wildP (normalB [| False |]) []<br />
<br />
-- bind "var" for later use!<br />
getopt (THArg pat@(ConP _ [VarP var])) = lamE [varP "y"] (caseE (varE "y") [cons0, cons1])<br />
where<br />
cons0 = match pat (normalB (appE [|Just|] (varE var))) []<br />
cons1 = match wildP (normalB [|Nothing|]) []<br />
<br />
mkArg :: String -> Int -> Pat<br />
mkArg k c = conP k (replicate c wildP)<br />
</haskell><br />
<br />
While the example might look contrived for the Boolean options which could have been tested much easier, it shows how both types of arguments can be treated in a similar way.<br />
<br />
=== Limitations ===<br />
<tt>getopt (THArg pat)</tt> is only able to treat unary constructors. See the pattern-binding: It matches exactly a single VarP.<br />
<br />
=== Improvements ===<br />
The following reduces things even a bit more, though I still don't know if I like it. It only works since <tt>c</tt> is either 0 or 1.<br />
<br />
<haskell><br />
mkArg k c = conP k (replicate c (varP "x"))<br />
<br />
baz = map $(getopt (THArg (mkArg "V" 1)))<br />
</haskell><br />
-- VolkerStolz<br />
<br />
== Generic constructor for records ==<br />
<br />
I have a large number of record types like this, of different length:<br />
<br />
<haskell><br />
data PGD = PGD {<br />
pgdXUnitBase :: !Word8,<br />
pgdYUnitBase :: !Word8,<br />
pgdXLUnitsperUnitBase :: !Word16<br />
}<br />
</haskell><br />
<br />
Currently I use GHC's Binary module to read them from files; it can handle<br />
types like <tt>(Word8, (Word8, Word16))</tt>, but there was no easy way to generate<br />
the correct amount of "uncurry" calls for automatically grabbing each element.<br />
<br />
With Template Haskell, the instance declarations are now written as such:<br />
<br />
<haskell><br />
instance Binary PGD where<br />
get bh = do a <- get bh ; return $ $(constrRecord PGD) a<br />
</haskell><br />
<br />
Here the trick lies in constrRecord, which is defined as:<br />
<br />
<haskell><br />
constrRecord x = reify exp where<br />
reify = \(Just r) -> appE r $ conE $ last args<br />
exp = foldl (dot) uncur $ replicate terms uncur<br />
terms = ((length args) `div` 2) - 2<br />
dot x y = (Just $ infixE x (varE ".") y)<br />
uncur = (Just [|uncurry|])<br />
args = words . show $ typeOf x<br />
</haskell><br />
<br />
-- AutrijusTang<br />
<br />
== zipWithN ==<br />
<br />
Here $(zipn 3) = zipWith3 etc.<br />
<br />
<haskell><br />
import Language.Haskell.TH; import Control.Applicative; import Control.Monad<br />
<br />
zipn n = do<br />
vs <- replicateM n (newName "vs")<br />
[| \f -><br />
$(lamE (map varP vs)<br />
[| getZipList $<br />
$(foldl<br />
(\a b -> [| $a <*> $b |])<br />
[| pure f |]<br />
(map (\v -> [| ZipList $(varE v) |]) vs))<br />
|])<br />
|]<br />
</haskell><br />
<br />
== 'generic' zipWith ==<br />
A generalization of zipWith to almost any data. Demonstrates the ability to do dynamic binding with TH splices (note 'dyn').<br />
<br />
<haskell><br />
zipCons :: Name -> Int -> [String] -> ExpQ<br />
zipCons tyName ways functions = do<br />
let countFields :: Con -> (Name,Int)<br />
countFields x = case x of<br />
NormalC n (length -> fields) -> (n, fields)<br />
RecC n (length -> fields) -> (n,fields)<br />
InfixC _ n _ -> (n,2)<br />
ForallC _ _ ct -> countFields ct<br />
<br />
TyConI (DataD _ _ _ [countFields -> (c,n)] _) <- reify tyName<br />
when (n /= length functions) $ fail "wrong number of functions named"<br />
vs <- replicateM ways $ replicateM n $ newName "x"<br />
lamE (map (conP c . map varP) vs) $<br />
foldl (\con (vs,f) -><br />
con `appE`<br />
foldl appE<br />
(dyn f)<br />
(map varE vs))<br />
(conE c)<br />
(transpose vs `zip` functions)<br />
</haskell><br />
<br />
This example uses whichever '+' is in scope when the expression is spliced:<br />
<br />
<haskell><br />
:type $(zipCons ''(,,,) 2 (replicate 4 "+"))<br />
<br />
$(zipCons ''(,,,) 2 (replicate 4 "+"))<br />
:: (Num t, Num t1, Num t2, Num t3) =><br />
(t, t1, t2, t3) -> (t, t1, t2, t3) -> (t, t1, t2, t3)<br />
</haskell><br />
<br />
==[[Template haskell/Instance deriving example|Instance deriving example]]==<br />
An example using a 'deriving function' to generate a method instance <br />
per constructor of a type. The deriving function provides the body of the<br />
method.<br />
<br />
Note that this example assumes that the functions of the class take a parameter that is the same type as instance is parameterized with. <br />
<br />
The message [http://www.haskell.org/pipermail/template-haskell/2006-August/000581.html email message] contains the full source ([http://www.iist.unu.edu/~vs/haskell/TH_render.hs extracted file]).<br />
<br />
== [[Quasiquotation|QuasiQuoters]] ==<br />
New in ghc-6.10 is -XQuasiQuotes, which allows one to extend GHC's syntax from library code. Quite a few examples are given in [http://hackage.haskell.org/package/haskell-src-meta haskell-src-meta].<br />
<br />
=== Similarity with splices ===<br />
<br />
Quasiquoters used in expression contexts (those using the ''quoteExp'') behave to a first approximation like regular TH splices:<br />
<br />
<haskell><br />
simpleQQ = QuasiQuoter { quoteExp = stringE } -- in another module<br />
<br />
[$simpleQQ| a b c d |] == $(quoteExp simpleQQ " a b c d ")<br />
</haskell><br />
<br />
== Generating records which are variations of existing records ==<br />
This example uses syb to address some of the pain of dealing with the rather large data types. <br />
<br />
<haskell><br />
{-# LANGUAGE ScopedTypeVariables, TemplateHaskell #-}<br />
module A where<br />
import Language.Haskell.TH<br />
import Data.Generics<br />
<br />
addMaybes modName input = let<br />
<br />
rename :: GenericT<br />
rename = mkT $ \n -> if nameModule n == modName<br />
then mkName $ nameBase n ++ "_opt"<br />
else n<br />
<br />
addMaybe :: GenericM Q<br />
addMaybe = mkM $ \(n :: Name, s :: Strict, ty :: Type) -> do<br />
ty' <- [t| Maybe $(return ty) |]<br />
return (n,s,ty')<br />
<br />
in everywhere rename `fmap` everywhereM addMaybe input<br />
<br />
mkOptional :: Name -> Q Dec<br />
mkOptional n = do<br />
TyConI d <- reify n<br />
addMaybes (nameModule n) d<br />
</haskell><br />
<br />
mkOptional then generates a new data type with all Names in that module with an added suffix _opt. Here is an example of its use:<br />
<haskell><br />
{-# LANGUAGE TemplateHaskell #-}<br />
import A<br />
data Foo = Foo { a,b,c,d,e :: Double, f :: Int }<br />
<br />
mapM mkOptional [''Foo]<br />
</haskell><br />
<br />
Generates something like<br />
<haskell><br />
data Foo_opt = Foo_opt {a_opt :: Maybe Double, ..... f_opt :: Maybe Int}<br />
</haskell><br />
<br />
<br />
<br />
[[Category:Language extensions]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Applications_and_libraries/Games&diff=58366Applications and libraries/Games2014-06-25T13:30:18Z<p>Piet Delport: /* Games */ fix broken link for "Defend The King from Forces of Different"</p>
<hr />
<div>{{LibrariesPage}}<br />
<br />
See also: [[Game Development]]<br />
<br />
<br />
== Games ==<br />
<br />
See also the [http://hackage.haskell.org/packages/archive/pkg-list.html#cat:game Game] category on Hackage.<br />
<br />
;[http://hackage.haskell.org/package/babylon babylon]<br />
: An implementation of a simple 2-player board game. Uses wxHaskell.<br />
<br />
;[http://hackage.haskell.org/package/boomslang boomslang]<br />
: A clone of the popular Flash game Boomshine.<br />
<br />
;[https://github.com/yairchu/defend Defend The King from Forces of Different]: A simple multiplayer real time strategy game.<br />
<br />
; [http://www.increpare.com/2008/11/endless-cavern/ Endless Cavern]: A 2D procedurally-generated cave exploration game.<br />
<br />
;[http://sourceforge.net/projects/fooengine/?abmode=1 Foo]<br />
:Foo (abbreviation from football) is a playing machine of [http://en.wikipedia.org/wiki/Paper_Soccer Paper Soccer], a pencil and paper game for two players. It contains a simple interface using HOpenGL library and provides many playing algorithms.<br />
<br />
;[[Frag]]<br />
:Frag is a 3D first person shooting game written in Haskell, by Mun Hon Cheong. It uses Yampa, Quake 3 BSP level format and OpenGL. It is licensed under the GPL.<br />
<br />
;[http://mfuglos.github.io/jeopardy Fuglos Jeopardy]<br />
:Fuglos Jeopardy is a free implementation of a game resembling the popular quiz show 'Jeopardy'. It is written using Gtk2Hs as GUI toolkit. It is quite feature complete and easy to use. It contains support for LaTeX, so you can for example use LaTeX math syntax in your data sheets and thus organize a math jeopoardy event. Licensed under GPL3.<br />
<br />
;[[GeBoP]]<br />
:The General Boardgames Player, offers a set of board games: Ataxx, Bamp, Halma, Hex, Kram, Nim, Reversi, TicTacToe, and Zenix. It uses wxHaskell.<br />
<br />
; [http://folk.uio.no/carljsv/gorillabas/GorillaBAS-0.1.tar.gz GorillaBAS]<br />
: A concrete game from an attempt on defining computer games.<br />
<br />
;[http://www.informatik.uni-bremen.de/~cxl/lehre/pi3.ws01/asteroids/ Haskell in Space]<br />
:An asteroid like game<br />
<br />
;[http://www.hedgewars.org/ Hedgewars]<br />
:A turn-based artillery game. The game server is written in Haskell.<br />
<br />
;[http://www.cs.ox.ac.uk/people/ian.lynagh/Hetris/ Hetris]<br />
:ASCII Tetris in Haskell<br />
<br />
;[http://hackage.haskell.org/package/hfiar hfiar]<br />
:Four in a Row in Haskell. Uses wxHaskell.<br />
<br />
;[http://hackage.haskell.org/package/hinvaders hinvaders]<br />
:A simple ANSI-graphics space invaders written entirely in Haskell 98.<br />
<br />
;[http://mu.org/~mux/LambdaChess/ LambdaChess]<br />
:GTK chess client<br />
<br />
;[http://quasimal.com/projects/level_0.html Level 0]<br />
:A fun and featureful Snake II clone using SDL.<br />
<br />
;[http://www.ncc.up.pt/~pbv/stuff/lostcities/ Lost Cities]<br />
:A two-player card game where each player tries to mount profitable expeditions. It uses wxHaskell.<br />
<br />
;[http://hackage.haskell.org/package/mage Mage]<br />
:Nethack clone written in Haskell (The web site have [http://www.scannedinavian.com/~shae/mage-1.0pre35.tar.gz this mage-1.0.pre35.tar.gz file] containing an older version that was using Data.FiniteMap.) There seems to be a problem with newer curses library even with the more recent 1.1.0 version.<br />
<br />
;[http://hackage.haskell.org/package/MazesOfMonad MazesOfMonad]<br />
:Role-Playing Game (influenced by Nethack), complete and fully playable. Console mode only.<br />
<br />
;[http://www.geocities.jp/takascience/haskell/monadius_en.html Monadius]<br />
:Monadius is a shoot 'em up with the selection bar power-up system for Windows, written in Haskell (now on [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Monadius Hackage]; see also the [http://www.youtube.com/watch?v=zqFgQiPKtOI video])<br />
<br />
;[http://mokehehe.blogspot.com/2009/04/super-nario-move-to-github.html Monao]<br />
:A Super Mario clone, using an SDL binding different from the one in Hackage: [https://github.com/mokehehe/monao Monao on github]<br />
<br />
;[http://joyridelabs.de/game/ Nikki and the Robots]<br />
:A puzzle, platformer game.<br />
<br />
;[http://berlinbrowndev.blogspot.com/2007/09/octane-mech-opengl-haskell-based-mech.html Octane Mech]<br />
:Octane Mech, OpenGL Haskell based mech game<br />
<br />
;[http://haskell-tetris.pbworks.com/w/page/16967421/Main OpenGL Tetris]<br />
:Tetris in Haskell with OpenGL<br />
<br />
;[http://www24.brinkster.com/srineet/para/para.html Paratrooper]<br />
:Paratrooper is a simple action game that runs on Windows and is written in literate Haskell.<br />
<br />
;[http://raincat.bysusanlin.com/ Raincat]<br />
:2D puzzle game featuring a fuzzy little cat (uses GLUT)<br />
<br />
;[http://roguestar.downstairspeople.org Roguestar]<br />
:Roguestar is a science fiction adventure role playing game using Haskell and OpenGL.<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Shu-thing Shu-thing]<br />
:A 2-D vector graphics upwards-scrolling keyboard-controlled shooter. You shoot the enemies while dodging their bullets until you reach and defeat the enemy.<br />
<br />
;[http://hackage.haskell.org/package/SpaceInvaders Space Invaders]<br />
:A video game, based on [[Yampa]]<br />
<br />
;[http://hackage.haskell.org/package/stunts stunts]<br />
:A revival of the classic racing game Stunts to serve as a non-toy-sized example for LambdaCube.<br />
<br />
;[https://github.com/nbartlomiej/tfoo Tfoo]<br />
:A simple Five in a Row game. Online, with server-sent events, deployed to [http://tfoo.herokuapp.com/ Heroku], open source.<br />
<br />
;[http://web.jfet.org/~kwantam/TriHs.tar.gz TriHs] (tar.gz)<br />
:A 1- or 2-player Tetris game using Gtk2Hs and Cairo.<br />
<br />
;[[wxAsteroids]]<br />
:Your space ship enters an asteroid belt, try to avoid collisions! wxAsteroids is based on wxHaskell.<br />
<br />
;[http://xiangqiboard.blogspot.com/2007/12/gnuxiangqi-angekndigt.html Xiangqiboard]<br />
:An implementation of xiangqi for Unix, using gtk2hs + cairo<br />
<br />
;{{HackagePackage | id =Yogurt}}<br />
:A functional MUD client featuring prioritized, regex-based hooks, variables, timers, logging, dynamic loading of Yogurt scripts and more. For example programs, please see [http://code.google.com/p/yogurt-mud/ Yogurt's home page]. <br />
<br />
=== Unfinished/in-progress games ===<br />
<br />
;[http://allureofthestars.com Allure of the Stars]<br />
:A near-future Sci-Fi roguelike and tactical squad game. Long-term goals are high replayability and auto-balancing through procedural content generation and persistent content modification based on player behaviour. The game is written using the [http://hackage.haskell.org/package/LambdaHack LambdaHack] roguelike game engine.<br />
<br />
;[http://ipwnstudios.com/node/4 Bloodknight]<br />
:An action RPG for mobile devices<br />
<br />
; [https://github.com/ghulette/haskell-game-of-life haskell-game-of-life]<br />
: Conway's Game of Life<br />
<br />
;[http://dotat.at/prog/life/hslife.hs HsLife]<br />
:A Haskell implementation of hashlife. It uses GLUT.<br />
<br />
== Game Engines and Libraries ==<br />
<br />
;[http://hackage.haskell.org/package/bullet Bullet]<br />
:A wrapper for the Bullet physics engine.<br />
<br />
;[http://hackage.haskell.org/package/free-game free-game]<br />
:A GUI/game library based on free monads.<br />
<br />
;[http://hackage.haskell.org/package/FunGEn FunGEn]<br />
:FunGEn (Functional Game Engine) is a platform-independent BSD-licensed 2D game engine based on OpenGL and GLUT. Its light dependencies make it easy to install, however GLUT is reputed to be unsuitable for simultaneous keypresses. As of 2011 it's the only general-purpose game engine, and the quickest way to throw together [http://darcsden.com/sordina/fungen/browse/examples/helloworld.hs simple] [http://darcsden.com/sordina/fungen/browse/examples/pong/pong.hs 2D] [http://darcsden.com/sordina/fungen/browse/examples/worms/worms.hs games], in Haskell. Example code: [http://joyful.com/fungen/old-site/example.html A Brief Example]. Forks and patches welcome!<br />
<br />
;[http://projects.haskell.org/game-tree/ game-tree]<br />
:game-tree is a purely functional library for searching game trees - useful for zero-sum two player games.<br />
<br />
;[http://hackage.haskell.org/package/GLFW-b GLFW-b]<br />
:Bindings to GLFW, a free, open source, multi-platform library for creating OpenGL contexts and managing input, including keyboard, mouse, joystick and time.<br />
<br />
;[http://gloss.ouroborus.net/ Gloss]<br />
:An OpenGL abstraction layer supporting game-style main loops.<br />
<br />
;[https://github.com/haskell-game haskell-game]<br />
:A project to make game development with Haskell easier to get started with by providing a suite of libraries for covering all sorts of aspects of game development.<br />
<br />
;[http://helm-engine.org/ Helm]<br />
:A functionally reactive game engine inspired by [http://elm-lang.org/ Elm].<br />
<br />
;[http://hackage.haskell.org/package/HGamer3D HGamer3D]<br />
:A game engine for Windows which includes Haskell bindings to a couple of C++ libraries and a Haskell API on top of that. Features include Audio, Joystick, Mouse and Keyboard handling, GUI, Network, Physics, 3D graphics. <br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Hipmunk Hipmunk]<br />
:Hipmunk: A Haskell binding for [http://chipmunk-physics.net/ Chipmunk]. Chipmunk is a fast, simple, portable, 2D physics engine. It is completely self-contained. See also [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HipmunkPlayground HipmunkPlayground]: a simple OpenGL program that allows you to see some of Hipmunk's functions in action.<br />
<br />
;[[Hpysics]]<br />
:Hpysics is a physics engine written using Data Parallel Haskell during Google Summer of Code 2008.<br />
<br />
;[http://hackage.haskell.org/package/hogre hogre]<br />
:Haskell bindings to the excellent OGRE 3D rendering engine. Ogre has been used in commercial games such as Torchlight and several books exist documenting the Ogre API. Ogre uses an MIT license making it compatible with many Haskell libraries.<br />
<br />
;[http://hackage.haskell.org/package/IrrHaskell IrrHaskell]<br />
:Haskell binding to the [http://irrlicht.sourceforge.net/ Irrlicht game engine]. The Irrlicht Engine is an open source high performance realtime 3D engine<br />
<br />
;[http://lambdacube3d.wordpress.com/ LambdaCube 3D]<br />
:LambdaCube 3D is a domain specific language and library that makes it possible to program GPUs in a purely functional style.<br />
<br />
<br />
=== Unfinished/in-progress game engines/libraries ===<br />
<br />
;[https://github.com/adorablepuppy/CurryDog CurryDog]<br />
:Aims to be a 2d and 3d modular game engine.<br />
<br />
;[https://github.com/keera-studios/gtk-helpers gtk-helpers]<br />
:A collection of auxiliary operations related to Gtk2hs. See also [http://keera.co.uk/blog/2013/03/19/creating-board-games-in-haskell/ Creating board games in Haskell in 100 lines of code]<br />
<br />
;[[HaskGame]]<br />
:An incomplete graphics system abstraction layer.<br />
<br />
; [https://github.com/shicks/hsgame hsgame]<br />
:A framework for network games<br />
<br />
;[https://github.com/LambdaHack/LambdaHack LambdaHack]<br />
:A game engine library for roguelike games of arbitrary theme, size and complexity, packaged together with a small example dungeon crawler. When completed, it will let you specify content to be procedurally generated, define the AI behaviour on top of the generic content-independent rules and compile a ready-to-play game binary, using either the supplied or a custom-made main loop. Several frontends are available (GTK is the default) and many other generic engine components are easily overridden, but the fundamental source of flexibility lies in the strict and type-safe separation of code and content.<br />
<br />
;[http://hackage.haskell.org/package/set-cover set-cover]<br />
:Solver for exact set cover problems. Included examples: Sudoku, 8 Queens, Soma Cube, Tetris Cube, Cube of L's, Logika's Baumeister puzzle. Generic algorithm allows to choose between slow but flexible Set from containers package and fast but cumbersome bitvectors.<br />
<br />
<br />
[[Category:Games|*]]<br />
[[Category:Applications]]<br />
[[Category:Libraries]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Non-empty_list&diff=58335Non-empty list2014-06-15T12:48:53Z<p>Piet Delport: avoid excess linebreak</p>
<hr />
<div>Errors such as taking <hask>head</hask> or <hask>tail</hask> of the empty list in Haskell are equivalent to the dereferencing of the zero pointer in C/C++ or <code>NullPointerException</code> in Java. These errors occur because the true domain of the function is smaller than the function's type suggests. For example, the type of <hask>head</hask> says that the function applies to any list. In reality, it can only be meaningfully applied to non-empty lists. One can eliminate such errors by giving functions <hask>head</hask> and <hask>tail</hask> more precise type, such as <hask>FullList a</hask>. Languages like [http://en.wikipedia.org/wiki/Cyclone_programming_language Cyclone] and [http://en.wikipedia.org/wiki/C%CF%89 Cw] do exactly that.<br />
<br />
It must be emphasized that we can eliminate head-of-empty-list errors<br />
'''now''', without any modification to the Haskell type system, without<br />
developing any new tool. In fact, it is possible in Haskell98! The<br />
same technique applies to OCaml and even Java and C++. The ''only''<br />
required advancement is in our thinking and programming style.<br />
<br />
Maybe, you are also interested in<br />
[http://www.haskell.org/pipermail/haskell-cafe/2006-November/019644.html advocacy] of this style.<br />
<br />
<br />
== Safe list functions ==<br />
<br />
Here's the 0th approximation of the advocated approach:<br />
<br />
<haskell><br />
{-# Haskell98! #-}<br />
-- Safe list functions<br />
<br />
module NList (FullList,<br />
fromFL,<br />
indeedFL,<br />
decon,<br />
head,<br />
tail,<br />
Listable (..)<br />
) where<br />
<br />
import Prelude hiding (head, tail)<br />
<br />
newtype FullList a = FullList [a] -- data constructor is not exported!<br />
<br />
fromFL (FullList x) = x -- Injection into general lists<br />
<br />
-- The following is an analogue of `maybe'<br />
indeedFL :: [a] -> w -> (FullList a -> w) -> w<br />
indeedFL x on_empty on_full <br />
| null x = on_empty<br />
| otherwise = on_full $ FullList x<br />
<br />
-- A possible alternative, with an extra Maybe tagging<br />
-- indeedFL :: [a] -> Maybe (FullList a)<br />
<br />
-- A more direct analogue of `maybe', for lists<br />
decon :: [a] -> w -> (a -> [a] -> w) -> w<br />
decon [] on_empty on_full = on_empty<br />
decon (h:t) on_empty on_full = on_full h t<br />
<br />
<br />
-- The following are _total_ functions<br />
-- They are guaranteed to be safe, and so we could have used<br />
-- unsafeHead# and unsafeTail# if GHC provides though...<br />
<br />
head :: FullList a -> a<br />
head (FullList (x:_)) = x<br />
<br />
tail :: FullList a -> [a]<br />
tail (FullList (_:x)) = x<br />
<br />
-- Mapping over a non-empty list gives a non-empty list<br />
instance Functor FullList where<br />
fmap f (FullList x) = FullList $ map f x<br />
<br />
<br />
-- Adding something to a general list surely gives a non-empty list<br />
infixr 5 !:<br />
<br />
class Listable l where<br />
(!:) :: a -> l a -> FullList a<br />
<br />
instance Listable [] where<br />
(!:) h t = FullList (h:t)<br />
<br />
instance Listable FullList where<br />
(!:) h (FullList t) = FullList (h:t)<br />
</haskell><br />
<br />
<br />
Now we can write<br />
<haskell><br />
import NList<br />
import Prelude hiding (head, tail)<br />
safe_reverse l = loop l [] <br />
where<br />
loop l accum = indeedFL l accum $<br />
(\l -> loop (tail l) (head l : accum))<br />
<br />
test1 = safe_reverse [1,2,3]<br />
</haskell><br />
<br />
As we can see, the null test is algorithmic. After we've done it, head<br />
and tail no longer need to check for null list. Those head and tail<br />
functions are total. Thus we achieve both safety and performance.<br />
<br />
We can also write<br />
<haskell><br />
-- Again, we are statically assured of no head [] error!<br />
test2 = head $ 1 !: 2 !: 3 !: []<br />
</haskell><br />
<br />
I should point to<br />
[http://pobox.com/~oleg/ftp/Computation/lightweight-dependent-typing.html Lightweight dependent typing] for justification and formalization, as<br />
well as for for further, more complex examples. <br />
We can also use the approach to<br />
ensure various control properties, e.g., the yield property: a thread may<br />
not invoke `yield' while holding a lock. We can assure this property<br />
both for recursive and non-recursive locks.<br />
<br />
If there is a surprise in this, it is in the triviality of<br />
approach. One can't help but wonder why don't we program in this<br />
style.<br />
<br />
== Integrating with the existing list-processing functions ==<br />
<br />
Jan-Willem Maessen wrote:<br />
<blockquote><br />
In addition, we have this rather nice assembly of functions which <br />
work on ordinary lists. Sadly, rewriting them all to also work on <br />
NonEmptyList or MySpecialInvariantList is a nontrivial task.<br />
</blockquote><br />
<br />
That's an excellent question. Indeed, let us assume we have a function<br />
<haskell><br />
foo:: [a] -> [a]<br />
</haskell><br />
(whose code, if available, we'd rather not change) and we want to<br />
write something like<br />
<haskell><br />
\l -> [head l, head (foo l)]<br />
</haskell><br />
To use the safe <hask>head</hask> from NList.hs , we should write<br />
<haskell><br />
\l -> indeedFL l onempty (\l -> [head l, head (foo l)])<br />
</haskell><br />
But that doesn't type: first of all, <hask>foo</hask> applies to <br />
<hask>[a]</hask> rather than<br />
<hask>FullList a</hask>, and second, the result of <br />
<hask>foo</hask> is not <hask>FullList a</hask>, required<br />
by our <hask>head</hask>. The first problem is easy to solve: we can always<br />
inject <hask>FullList a</hask> into the general list: <br />
<hask>fromFL</hask>. We insist on writing<br />
the latter function explicitly, which keeps the typesystem simple,<br />
free of subtyping and implicit coercions. One may regard<br />
<hask>fromFL</hask> as an<br />
analogue of <hask>fromIntegral</hask> -- which, too, we have to <br />
write explicitly, in any code with more than one sort of integral <br />
numbers (e.g., Int and Integer, or Int and CInt).<br />
<br />
If we are not sure if our function foo maps non-empty lists<br />
to non-empty lists, we really should handle the empty list case:<br />
<haskell><br />
\l -> indeedFL l onempty $<br />
\l -> [head l, indeedFL (foo $ fromFL l) onempty' head]<br />
</haskell><br />
If we have a hunch that foo maps non-empty lists to non-empty lists,<br />
but we are too busy to verify it, we can write<br />
<haskell><br />
\l -> indeedFL l onempty $<br />
\l -> [head l, indeedFL (foo $ fromFL l) <br />
(error msg)<br />
head]<br />
where msg = "I'm quite sure foo maps non-empty lists to " ++<br />
"non-empty lists. I'll be darned if it doesn't."<br />
</haskell><br />
That would get the code running. Possibly at some future date (during<br />
the code review?) I'll be called to justify my hunch, to whatever<br />
degree of formality (informal argument, formal proof) required by the<br />
policies in effect. If I fail at this justification, I'd better think<br />
what to do if the result of foo is really the empty list. If I<br />
succeed, I'd be given permission to update the module NList with the<br />
following definition<br />
<haskell><br />
nfoo (FullList x) = FullList $ foo x<br />
</haskell><br />
after which I could write<br />
<haskell><br />
\l -> indeedFL l onempty (\l -> [head l, head (nfoo l)])<br />
</haskell><br />
with no extra empty list checks.<br />
<br />
Excerpted from the discussion on Haskell-Cafe, November 2006.<br />
<br />
<br />
== Reliable and simple approach ==<br />
<br />
The above approach requires a trusted kernel of functions<br />
that assert the non-emptiness of lists.<br />
However, when implementing the kernel, and even more when you extend or alter it,<br />
you may make mistakes.<br />
The best approach to avoid even this,<br />
is to make the non-emptiness explicit in the type from the beginning:<br />
<haskell><br />
type NonEmptyList a = (a, [a])<br />
</haskell><br />
The first member of the pair represents the first element in the non-empty list.<br />
Now the compiler can test non-emptiness for you and you cannot cheat anymore.<br />
<br />
This approach is extended in the {{HackagePackage|id=non-empty}} package<br />
such that you can add more leading elements.<br />
That is, you can define lists with at least two or three or more elements.<br />
You can even define lists that allow for a given set of admissible list lengths.<br />
A unified interface to all these variants is provided by standard type classes<br />
like Functor, Foldable, Traversable and some custom classes.<br />
All that is achieved with Haskell 98!<br />
<br />
<br />
== Packages ==<br />
<br />
These packages implement non-empty lists:<br />
* {{HackagePackage|id=NonEmpty}}<br />
* {{HackagePackage|id=NonEmptyList}}<br />
* {{HackagePackage|id=Cardinality}}<br />
* {{HackagePackage|id=non-empty}}<br />
* {{HackagePackage|id=semigroups}}<br />
<br />
[[Category:Idioms]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Jobs&diff=57540Jobs2014-02-05T23:03:14Z<p>Piet Delport: /* Industry positions */ fix Bluespec link</p>
<hr />
<div>This page collects advertisements for commercial and academic positions involving Haskell or related technologies. <br />
<br />
If you are seeking Haskell jobs, or wish to recruit, good places to follow are the Haskell and Haskell-cafe mailing lists, the [http://cufp.org/jobs CUFP Job Opportunities list] and the Types mailing list (particularly for research jobs). Contacting those organisations listed on the [[Haskell in industry]] is a good idea. Joining the nascent networking site [http://www.haskellers.com Haskellers] may also prove beneficial.<br />
<br />
Please also supply the date when you add a new job opening to the list below.<br />
<br />
<br />
==Industry positions==<br />
<br />
*[http://www.bluespec.com/careers.html Bluespec, Inc.]<br />
*[http://www.functor.se/careers/openings/ Functor AB]<br />
*[http://corp.galois.com/careers/ Galois, Inc]<br />
*[http://www.starling-software.com/en/employment/ Starling Software K.K.]<br />
*[http://www.tsurucapital.com/en/ Tsuru Capital LLC] <br />
<br />
===Related positions===<br />
<br />
* [https://www.erlang-solutions.com/about/careers Erlang Solutions]<br />
<br />
==Academic positions==<br />
<br />
* [http://cufp.org/jobs/programming-languages-researcher-haskell-expertise Programming Languages Researcher with Haskell Expertise] (added Sep 2010)<br />
<br />
<br />
==PhD/MSc Studentships==<br />
<br />
* [http://users.ugent.be/~tschrijv/phdposition3.html PhD studentship at Ghent University (posted on November 22, 2013)]<br />
* [http://www.functor.se Industrial PhDs and MSc projects at Functor AB]<br />
<br />
==Internships==<br />
<br />
* [http://hackage.haskell.org/trac/ghc/wiki/Internships Internships on Haskell and GHC, at Microsoft Research, Cambridge]<br />
* [http://www.haskellers.com/jobs/5 Spring Internship at Intel to develop EDSL for parallel vector computation] (added Nov 2010)<br />
<br />
<br />
==Job sites==<br />
<br />
* [http://www.haskellers.com/jobs Haskellers]<br />
* [http://cufp.org/jobs/language/31 Commercial Users of Functional Programming]<br />
* [http://functionaljobs.com/ Functional Jobs]<br />
<br />
[[Category:Community]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Quotes&diff=22250Quotes2008-08-06T02:15:11Z<p>Piet Delport: Id monad</p>
<hr />
<div><pre><br />
<Philippa> do we have a case of haskell faster than C on a platform where GHC<br />
compiles via C and doesn't screw with the output yet?<br />
<jethr0> wouldn't that just be a blatant case of slow c benchmarking code? :)<br />
<dons> the concurrency or binary tree benchmarks?<br />
<jethr0> someone could put the haskell intermediate c code up as the c benchmark *g*<br />
<musasabi> yes, 30000 lines of C? ;)<br />
%<br />
seen on comp.lang.functional:<br />
<br />
From: Ashley Yakeley <ashley@semantic.org><br />
Subject: Re: Type advocacy<br />
Newsgroups: comp.lang.functional<br />
Date: Thu, 11 Oct 2001 21:16:20 -0700<br />
Organization: Myself<br />
<br />
In article <9pdvgc$u3d$1@news.fas.harvard.edu>, Ken Shan<br />
<ken@digitas.harvard.edu> wrote:<br />
<br />
> I am preparing a three-minute talk to tell incoming graduate students<br />
> at my school about types.<br />
<br />
Oh like that's going to work. You'd be better off selling T-shirts that<br />
say "WHAT PART OF" (and then the Hindley-Milner prinicipal-type<br />
algorithm) "DON'T YOU UNDERSTAND?".<br />
<br />
If anyone gives you any lip, ask them how to find the square-root of a<br />
string. Everything else follows on from that.<br />
<br />
> What pointers should I give?<br />
<br />
Safe ones.<br />
<br />
--<br />
Ashley Yakeley, Seattle WA<br />
%<br />
<kaol> @src liftM<br />
<lambdabot> liftM f m1 = do { x1 <- m1; return (f x1) }<br />
<kaol> @src liftM2<br />
<lambdabot> liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }<br />
<osfameron> does that lift monads which are twice as heavy?<br />
<LoganCapaldo> No, it just lifts a monad in each hand<br />
<osfameron> harr!<br />
<byorgey> you know what they say, a monad in each hand is better than two in<br />
the bush... no wait...<br />
<jfredett> if this were not a family chat channel, I might say something about that...<br />
<DRMacIver> Hand me a long enough monad and I will move the world?<br />
<cjeris> jfredett: yeah, well, the first time I tried to explain what was<br />
different about Haskell to my wife, her response was "Monad? Is that<br />
when you only have one ball?"<br />
%<br />
* EvilTerran . o O ( is a comathematician a device for turning theorems into coffee? )<br />
<oerjan> EvilTerran: no, it's for turning cotheorems into ffee.<br />
<slava> oerjan: it's not clear that the category of cocoffee is isomorphic to ffee<br />
<oerjan> slava: bah, it's mpletely coclear.<br />
%<br />
<roconnor> comonads are just as hard to understand as monads.<br />
<Toxaris> you have to co-understand them?<br />
<quicksilver> Toxaris: I believe you actually have to over-costand them<br />
%<br />
<wli> Modius: nub<br />
<Modius> Thanks<br />
<evir> If this was a gaming channel, one could take that as an insult.<br />
<idnar> evir: wtf stfu<br />
<olsner> how? it's a haskell function - gamers don't know haskell!<br />
<evir> idnar: dieplzkthx<br />
<idnar> evir: lol no u<br />
<EvilTerran> zomglolwut<br />
<idnar> this is vaguely disturbing<br />
<Modius> If I'd have asked for the search clause they would have called you a nubBy<br />
%<br />
<ehird> <interactive>:1:4:<br />
<ehird> My brain just exploded.<br />
<ehird> I can't handle pattern bindings for existentially-quantified constructors.<br />
<ehird> ^_____^<br />
<ehird> I DID IT<br />
<ehird> I DID IT I DID IT I DID IT<br />
<ehird> rite of passage #2: COMPLETE<br />
%<br />
<Twey> What's the use of the Id monad?<br />
<BMeph> Twey: The Id monad is used to express subliminal desires to make Monad Transformers act like Monads... ;p<br />
<edwardk> Its a little harder to reason with than the Ego monad however<br />
<Dzlk> However, you can make the Id monad somewhat better behaved by wrapping it in SuperegoT.<br />
</pre><br />
<br />
[[Category:Community]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Blow_your_mind&diff=16339Blow your mind2007-10-25T15:49:35Z<p>Piet Delport: section instead of flip</p>
<hr />
<div>Useful Idioms that will blow your mind (unless you already know them :)<br />
<br />
This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead him to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions.<br />
<br />
More examples are always welcome, especially "obscure" monadic ones.<br />
<br />
<br />
== List/String operations ==<br />
<br />
<br />
<haskell><br />
-- split at whitespace<br />
-- "hello world" -> ["hello","world"]<br />
words<br />
<br />
unfoldr (\b -> fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)<br />
<br />
takeWhile (not . null) . evalState (repeatM $ modify (drop 1) >> State (break (== ' '))) . (' ' :)<br />
where repeatM = sequence . repeat<br />
<br />
fix (\f l -> if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e))<br />
<br />
<br />
-- splitting in two (alternating)<br />
-- "1234567" -> ("1357", "246")<br />
-- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists<br />
foldr (\a ~(x,y) -> (a:y,x)) ([],[])<br />
<br />
(map snd *** map snd) . partition (even . fst) . zip [0..]<br />
<br />
transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
-- this one uses the solution to the next problem in a nice way :)<br />
<br />
toMaybe b x = if b then Just x else Nothing<br />
-- or generalize it:<br />
-- toMaybe = (toMonadPlus :: Bool -> a -> Maybe a)<br />
toMonadPlus b x = guard b >> return x<br />
<br />
-- splitting into lists of length N<br />
-- "1234567" -> ["12", "34", "56", "7"]<br />
unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
<br />
takeWhile (not . null) . unfoldr (Just . splitAt 2)<br />
<br />
<br />
-- sorting by a custom function<br />
-- length -> ["abc", "ab", "a"] -> ["a", "ab", "abc"]<br />
comparing f x y = compare (f x) (f y)<br />
sortBy (comparing length)<br />
<br />
map snd . sortBy (comparing fst) . map (length &&& id) <br />
-- the so called "Schwartzian Transform" for computationally more expensive <br />
-- functions.<br />
<br />
-- comparing adjacent elements<br />
rises xs = zipWith (<) xs (tail xs)<br />
<br />
-- lazy substring search<br />
-- "ell" -> "hello" -> True<br />
substr a b = any (a `isPrefixOf`) $ tails b<br />
<br />
-- multiple splitAt's:<br />
-- splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]<br />
splitAts = foldr (\n r -> splitAt n >>> second r >>> uncurry (:)) return<br />
<br />
-- frequency distribution<br />
-- "abracadabra" -> fromList [('a',5),('b',2),('c',1),('d',1),('r',2)]<br />
import Data.Map<br />
histogram = fromListWith (+) . (`zip` repeat 1)<br />
<br />
-- using arrows and sort<br />
histogramArr = map (head&&&length) . group . sort<br />
</haskell><br />
<br />
== Mathematical sequences, etc ==<br />
<br />
<br />
<haskell><br />
-- factorial<br />
-- 6 -> 720<br />
product [1..6]<br />
<br />
foldl1 (*) [1..6]<br />
<br />
(!!6) $ scanl (*) 1 [1..]<br />
<br />
fix (\f n -> if n <= 0 then 1 else n * f (n-1))<br />
<br />
<br />
-- powers of two sequence<br />
iterate (*2) 1<br />
<br />
unfoldr (\z -> Just (z,2*z)) 1<br />
<br />
<br />
-- fibonacci sequence<br />
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)<br />
<br />
fibs = 0:1:zipWith (+) fibs (tail fibs)<br />
<br />
fib = 0:scanl (+) 1 fib<br />
<br />
<br />
-- pascal triangle<br />
pascal = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]<br />
<br />
<br />
-- prime numbers<br />
-- example of a memoising caf (??)<br />
primes = sieve [2..] where<br />
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]<br />
<br />
unfoldr sieve [2..] where <br />
sieve (p:x) = Just(p, [ n | n <- x, n `mod` p > 0 ])<br />
<br />
-- or if you want to use the Sieve of Eratosthenes..<br />
diff [] l = l<br />
diff l [] = l<br />
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl<br />
| x > y = diff xl ys<br />
| otherwise = diff xs ys <br />
esieve [] = []<br />
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))<br />
eprimes = esieve [2..]<br />
<br />
-- enumerating the rationals (see [1])<br />
rats :: [Rational]<br />
rats = iterate next 1 where<br />
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x<br />
<br />
-- another way<br />
rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]<br />
</haskell><br />
<br />
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]<br />
<br />
== Monad magic ==<br />
<br />
The list monad can be used for some amazing Prolog-ish search problems.<br />
<br />
<haskell><br />
-- all combinations of a list of lists.<br />
-- these solutions are all pretty much equivalent in that they run<br />
-- in the List Monad. the "sequence" solution has the advantage of<br />
-- scaling to N sublists.<br />
-- "12" -> "45" -> ["14", "15", "24", "25"]<br />
sequence ["12", "45"]<br />
<br />
[[x,y] | x <- "12", y <- "45"]<br />
<br />
do { x <- "12"; y <- "45"; return [x,y] }<br />
<br />
"12" >>= \a -> "45" >>= \b -> return [a,b]<br />
<br />
-- all combinations of letters<br />
(inits . repeat) ['a'..'z'] >>= sequence<br />
<br />
-- apply a list of functions to an argument<br />
-- even -> odd -> 4 -> [True,False]<br />
map ($4) [even,odd]<br />
<br />
sequence [even,odd] 4<br />
<br />
-- all subsequences of a sequence/ aka powerset.<br />
filterM (const [True, False])<br />
<br />
-- apply a function to two other function the same argument<br />
-- (lifting to the Function Monad (->))<br />
-- even 4 && odd 4 -> False<br />
liftM2 (&&) even odd 4<br />
<br />
liftM2 (>>) putStrLn return "hello"<br />
<br />
fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]<br />
[1%1,2%1,1%2,3%1,1%3,3%2,2%3,4%1,1%4,4%3,3%4,5%2,2%5,5%3,3%5,5%1,1%5,5%4,4%5...<br />
<br />
-- forward function concatenation<br />
(*3) >>> (+1) $ 2<br />
<br />
foldl1 (flip (.)) [(+1),(*2)] 500<br />
<br />
<br />
-- perform functions in/on a monad, lifting<br />
fmap (+2) (Just 2)<br />
<br />
liftM2 (+) (Just 4) (Just 2)<br />
<br />
<br />
-- [still to categorize]<br />
(id >>= (+) >>= (+) >>= (+)) 3 -- (3+3)+(3+3) = 12<br />
<br />
double = join (+)<br />
<br />
(join . liftM2) (*) (+3) 5 -- 64<br />
<br />
mapAccumL (\acc n -> (acc+n,acc+n)) 0 [1..10] -- interesting for fac, fib, ...<br />
<br />
do f <- [not, not]; d <- [True, False]; return (f d) -- [False,True,False,True]<br />
<br />
do { Just x <- [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x }<br />
</haskell><br />
<br />
== Other ==<br />
<br />
<br />
<haskell><br />
-- simulating lisp's cond<br />
case () of () | 1 > 2 -> True<br />
| 3 < 4 -> False<br />
| otherwise -> True<br />
<br />
<br />
-- match a constructor<br />
-- this is better than applying all the arguments, because this way the<br />
-- data type can be changed without touching the code (ideally).<br />
case a of Just{} -> True<br />
_ -> False<br />
<br />
<br />
{- <br />
TODO, IDEAS:<br />
more fun with monad, monadPlus (liftM, ap, guard, when)<br />
fun with arrows (second, first, &&&, ***)<br />
liftM, ap<br />
lazy search (searching as traversal of lazy structures)<br />
innovative data types (i.e. having fun with Maybe sequencing)<br />
<br />
LINKS:<br />
bananas, envelopes, ... (generic traversal)<br />
why functional fp matters (lazy search, ...)<br />
-}<br />
</haskell><br />
<br />
=== Polynomials ===<br />
In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients). <br />
<br />
instance Num a => Num [a] where -- (1)<br />
<br />
(f:fs) + (g:gs) = f+g : fs+gs -- (2)<br />
fs + [] = fs -- (3a)<br />
[] + gs = gs -- (3b)<br />
<br />
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) -- (4)<br />
_ * _ = [] -- (5)<br />
<br />
====Explanation====<br />
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.<br />
<br />
Lists are ordered by increasing powers. Thus <tt>f:fs</tt> means <tt>f+x*fs</tt> in algebraic notation. (2) and (4) follow from these algebraic identities:<br />
<br />
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs)<br />
(f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))<br />
<br />
(3) and (5) handle list ends.<br />
<br />
The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support.<br />
<br />
====Comments====<br />
<br />
The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.<br />
<br />
The methods are suitable for on-line computation. Only<br />
<i>n</i> terms of each input must be seen before the <i>n</i>-th term<br />
of output is produced.<br />
<br />
Thus the methods work on infinite series as well as polynomials.<br />
<br />
Integer power comes for free. This example tests the cubing of (1+x):<br />
<br />
[1, 1]^3 == [1, 3, 3, 1]<br />
<br />
See also<br />
* [[Pointfree]]<br />
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.hs NumericPrelude: Polynomials]<br />
* [[Add polynomials]]<br />
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].<br />
<br />
[[Category:Idioms]]<br />
[[Category:Mathematics]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Quotes&diff=15357Quotes2007-08-30T15:53:55Z<p>Piet Delport: nub</p>
<hr />
<div><pre><br />
<Philippa> do we have a case of haskell faster than C on a platform where GHC<br />
compiles via C and doesn't screw with the output yet?<br />
<jethr0> wouldn't that just be a blatant case of slow c benchmarking code? :)<br />
<dons> the concurrency or binary tree benchmarks?<br />
<jethr0> someone could put the haskell intermediate c code up as the c benchmark *g*<br />
<musasabi> yes, 30000 lines of C? ;)<br />
%<br />
seen on comp.lang.functional:<br />
<br />
From: Ashley Yakeley <ashley@semantic.org><br />
Subject: Re: Type advocacy<br />
Newsgroups: comp.lang.functional<br />
Date: Thu, 11 Oct 2001 21:16:20 -0700<br />
Organization: Myself<br />
<br />
In article <9pdvgc$u3d$1@news.fas.harvard.edu>, Ken Shan<br />
<ken@digitas.harvard.edu> wrote:<br />
<br />
> I am preparing a three-minute talk to tell incoming graduate students<br />
> at my school about types.<br />
<br />
Oh like that's going to work. You'd be better off selling T-shirts that<br />
say "WHAT PART OF" (and then the Hindley-Milner prinicipal-type<br />
algorithm) "DON'T YOU UNDERSTAND?".<br />
<br />
If anyone gives you any lip, ask them how to find the square-root of a<br />
string. Everything else follows on from that.<br />
<br />
> What pointers should I give?<br />
<br />
Safe ones.<br />
<br />
--<br />
Ashley Yakeley, Seattle WA<br />
%<br />
<kaol> @src liftM<br />
<lambdabot> liftM f m1 = do { x1 <- m1; return (f x1) }<br />
<kaol> @src liftM2<br />
<lambdabot> liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }<br />
<osfameron> does that lift monads which are twice as heavy?<br />
<LoganCapaldo> No, it just lifts a monad in each hand<br />
<osfameron> harr!<br />
<byorgey> you know what they say, a monad in each hand is better than two in<br />
the bush... no wait...<br />
<jfredett> if this were not a family chat channel, I might say something about that...<br />
<DRMacIver> Hand me a long enough monad and I will move the world?<br />
<cjeris> jfredett: yeah, well, the first time I tried to explain what was<br />
different about Haskell to my wife, her response was "Monad? Is that<br />
when you only have one ball?"<br />
%<br />
* EvilTerran . o O ( is a comathematician a device for turning theorems into coffee? )<br />
<oerjan> EvilTerran: no, it's for turning cotheorems into ffee.<br />
<slava> oerjan: it's not clear that the category of cocoffee is isomorphic to ffee<br />
<oerjan> slava: bah, it's mpletely coclear.<br />
%<br />
<roconnor> comonads are just as hard to understand as monads.<br />
<Toxaris> you have to co-understand them?<br />
<quicksilver> Toxaris: I believe you actually have to over-costand them<br />
%<br />
<wli> Modius: nub<br />
<Modius> Thanks<br />
<evir> If this was a gaming channel, one could take that as an insult.<br />
<idnar> evir: wtf stfu<br />
<olsner> how? it's a haskell function - gamers don't know haskell!<br />
<evir> idnar: dieplzkthx<br />
<idnar> evir: lol no u<br />
<EvilTerran> zomglolwut<br />
<idnar> this is vaguely disturbing<br />
<Modius> If I'd have asked for the search clause they would have called you a nubBy<br />
</pre><br />
<br />
[[Category:Community]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Blow_your_mind&diff=15216Blow your mind2007-08-22T01:13:02Z<p>Piet Delport: /* List/String operations */ Data.Map histogram</p>
<hr />
<div>Useful Idioms that will blow your mind (unless you already know them :)<br />
<br />
This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead him to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions.<br />
<br />
More examples are always welcome, especially "obscure" monadic ones.<br />
<br />
<br />
== List/String operations ==<br />
<br />
<br />
<haskell><br />
-- split at whitespace<br />
-- "hello world" -> ["hello","world"]<br />
words<br />
<br />
unfoldr (\b -> fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)<br />
<br />
takeWhile (not . null) . evalState (repeatM $ modify (drop 1) >> State (break (== ' '))) . (' ' :)<br />
where repeatM = sequence . repeat<br />
<br />
fix (\f l -> if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e))<br />
<br />
<br />
-- splitting in two (alternating)<br />
-- "1234567" -> ("1357", "246")<br />
-- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists<br />
foldr (\a ~(x,y) -> (a:y,x)) ([],[])<br />
<br />
(map snd *** map snd) . partition (even . fst) . zip [0..]<br />
<br />
transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
-- this one uses the solution to the next problem in a nice way :)<br />
<br />
toMaybe b x = if b then Just x else Nothing<br />
-- or generalize it:<br />
-- toMaybe = (toMonadPlus :: Bool -> a -> Maybe a)<br />
toMonadPlus b x = guard b >> return x<br />
<br />
-- splitting into lists of length N<br />
-- "1234567" -> ["12", "34", "56", "7"]<br />
unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
<br />
takeWhile (not . null) . unfoldr (Just . splitAt 2)<br />
<br />
<br />
-- sorting by a custom function<br />
-- length -> ["abc", "ab", "a"] -> ["a", "ab", "abc"]<br />
comparing f x y = compare (f x) (f y)<br />
sortBy (comparing length)<br />
<br />
map snd . sortBy (comparing fst) . map (length &&& id) <br />
-- the so called "Schwartzian Transform" for computationally more expensive <br />
-- functions.<br />
<br />
-- comparing adjacent elements<br />
rises xs = zipWith (<) xs (tail xs)<br />
<br />
-- lazy substring search<br />
-- "ell" -> "hello" -> True<br />
substr a b = any (a `isPrefixOf`) $ tails b<br />
<br />
-- multiple splitAt's:<br />
-- splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]<br />
splitAts = foldr (\n r -> splitAt n >>> second r >>> uncurry (:)) return<br />
<br />
-- frequency distribution<br />
-- "abracadabra" -> fromList [('a',5),('b',2),('c',1),('d',1),('r',2)]<br />
import Data.Map<br />
histogram = fromListWith (+) . flip zip (repeat 1)<br />
</haskell><br />
<br />
== Mathematical sequences, etc ==<br />
<br />
<br />
<haskell><br />
-- factorial<br />
-- 6 -> 720<br />
product [1..6]<br />
<br />
foldl1 (*) [1..6]<br />
<br />
(!!6) $ scanl (*) 1 [1..]<br />
<br />
fix (\f n -> if n <= 0 then 1 else n * f (n-1))<br />
<br />
<br />
-- powers of two sequence<br />
iterate (*2) 1<br />
<br />
unfoldr (\z -> Just (z,2*z)) 1<br />
<br />
<br />
-- fibonacci sequence<br />
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)<br />
<br />
fibs = 0:1:zipWith (+) fibs (tail fibs)<br />
<br />
fib = 0:scanl (+) 1 fib<br />
<br />
<br />
-- pascal triangle<br />
pascal = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]<br />
<br />
<br />
-- prime numbers<br />
-- example of a memoising caf (??)<br />
primes = sieve [2..] where<br />
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]<br />
<br />
unfoldr sieve [2..] where <br />
sieve (p:x) = Just(p, [ n | n <- x, n `mod` p > 0 ])<br />
<br />
-- or if you want to use the Sieve of Eratosthenes..<br />
diff [] l = l<br />
diff l [] = l<br />
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl<br />
| x > y = diff xl ys<br />
| otherwise = diff xs ys <br />
esieve [] = []<br />
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))<br />
eprimes = esieve [2..]<br />
<br />
-- enumerating the rationals (see [1])<br />
rats :: [Rational]<br />
rats = iterate next 1 where<br />
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x<br />
<br />
-- another way<br />
rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]<br />
</haskell><br />
<br />
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]<br />
<br />
== Monad magic ==<br />
<br />
The list monad can be used for some amazing Prolog-ish search problems.<br />
<br />
<haskell><br />
-- all combinations of a list of lists.<br />
-- these solutions are all pretty much equivalent in that they run<br />
-- in the List Monad. the "sequence" solution has the advantage of<br />
-- scaling to N sublists.<br />
-- "12" -> "45" -> ["14", "15", "24", "25"]<br />
sequence ["12", "45"]<br />
<br />
[[x,y] | x <- "12", y <- "45"]<br />
<br />
do { x <- "12"; y <- "45"; return [x,y] }<br />
<br />
"12" >>= \a -> "45" >>= \b -> return [a,b]<br />
<br />
-- all combinations of letters<br />
(inits . repeat) ['a'..'z'] >>= sequence<br />
<br />
-- apply a list of functions to an argument<br />
-- even -> odd -> 4 -> [True,False]<br />
map ($4) [even,odd]<br />
<br />
sequence [even,odd] 4<br />
<br />
-- all subsequences of a sequence/ aka powerset.<br />
filterM (const [True, False])<br />
<br />
-- apply a function to two other function the same argument<br />
-- (lifting to the Function Monad (->))<br />
-- even 4 && odd 4 -> False<br />
liftM2 (&&) even odd 4<br />
<br />
liftM2 (>>) putStrLn return "hello"<br />
<br />
fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]<br />
[1%1,2%1,1%2,3%1,1%3,3%2,2%3,4%1,1%4,4%3,3%4,5%2,2%5,5%3,3%5,5%1,1%5,5%4,4%5...<br />
<br />
-- forward function concatenation<br />
(*3) >>> (+1) $ 2<br />
<br />
foldl1 (flip (.)) [(+1),(*2)] 500<br />
<br />
<br />
-- perform functions in/on a monad, lifting<br />
fmap (+2) (Just 2)<br />
<br />
liftM2 (+) (Just 4) (Just 2)<br />
<br />
<br />
-- [still to categorize]<br />
(id >>= (+) >>= (+) >>= (+)) 3 -- (3+3)+(3+3) = 12<br />
<br />
double = join (+)<br />
<br />
(join . liftM2) (*) (+3) 5 -- 64<br />
<br />
mapAccumL (\acc n -> (acc+n,acc+n)) 0 [1..10] -- interesting for fac, fib, ...<br />
<br />
do f <- [not, not]; d <- [True, False]; return (f d) -- [False,True,False,True]<br />
<br />
do { Just x <- [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x }<br />
</haskell><br />
<br />
== Other ==<br />
<br />
<br />
<haskell><br />
-- simulating lisp's cond<br />
case () of () | 1 > 2 -> True<br />
| 3 < 4 -> False<br />
| otherwise -> True<br />
<br />
<br />
-- match a constructor<br />
-- this is better than applying all the arguments, because this way the<br />
-- data type can be changed without touching the code (ideally).<br />
case a of Just{} -> True<br />
_ -> False<br />
<br />
<br />
{- <br />
TODO, IDEAS:<br />
more fun with monad, monadPlus (liftM, ap, guard, when)<br />
fun with arrows (second, first, &&&, ***)<br />
liftM, ap<br />
lazy search (searching as traversal of lazy structures)<br />
innovative data types (i.e. having fun with Maybe sequencing)<br />
<br />
LINKS:<br />
bananas, envelopes, ... (generic traversal)<br />
why functional fp matters (lazy search, ...)<br />
-}<br />
</haskell><br />
<br />
=== Polynomials ===<br />
In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients). <br />
<br />
instance Num a => Num [a] where -- (1)<br />
<br />
(f:fs) + (g:gs) = f+g : fs+gs -- (2)<br />
fs + [] = fs -- (3a)<br />
[] + gs = gs -- (3b)<br />
<br />
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) -- (4)<br />
_ * _ = [] -- (5)<br />
<br />
====Explanation====<br />
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.<br />
<br />
Lists are ordered by increasing powers. Thus <tt>f:fs</tt> means <tt>f+x*fs</tt> in algebraic notation. (2) and (4) follow from these algebraic identities:<br />
<br />
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs)<br />
(f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))<br />
<br />
(3) and (5) handle list ends.<br />
<br />
The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support.<br />
<br />
====Comments====<br />
<br />
The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.<br />
<br />
The methods are suitable for on-line computation. Only<br />
<i>n</i> terms of each input must be seen before the <i>n</i>-th term<br />
of output is produced.<br />
<br />
Thus the methods work on infinite series as well as polynomials.<br />
<br />
Integer power comes for free. This example tests the cubing of (1+x):<br />
<br />
[1, 1]^3 == [1, 3, 3, 1]<br />
<br />
See also<br />
* [[Pointfree]]<br />
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.hs NumericPrelude: Polynomials]<br />
* [[Add polynomials]]<br />
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].<br />
<br />
[[Category:Idioms]]<br />
[[Category:Mathematics]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Pointfree&diff=14888Pointfree2007-08-05T08:31:16Z<p>Piet Delport: /* Dot */ (=<<) == join `dot` fmap</p>
<hr />
<div>__TOC__<br />
<br />
'''Pointfree Style'''<br />
<br />
It is very common for functional programmers to write functions as a<br />
composition of other functions, never mentioning the actual arguments<br />
they will be applied to. For example, compare:<br />
<br />
<haskell><br />
sum = foldr (+) 0<br />
</haskell><br />
<br />
with:<br />
<br />
<haskell><br />
sum' xs = foldr (+) 0 xs<br />
</haskell><br />
<br />
These functions perform the same operation, however, the former is more<br />
compact, and is considered cleaner. This is closely related to function<br />
pipelines (and to [http://www.vex.net/~trebla/weblog/pointfree.html unix shell scripting]<br />
): it is clearer to write <hask>let fn = f . g . h</hask> than to<br />
write <hask>let fn x = f (g (h x))</hask>.<br />
<br />
This style is particularly useful when deriving efficient programs by<br />
calculation, but it is good discipline in general. It helps the writer<br />
(and reader) think about composing functions (high level), rather than<br />
shuffling data (low level).<br />
<br />
It is a common experience when rewriting expressions in pointfree style<br />
to derive more compact, clearer versions of the code -- explicit points<br />
often obscure the underlying algorithm.<br />
<br />
Point-free map fusion:<br />
<br />
<haskell><br />
foldr f e . map g == foldr (f . g) e<br />
</haskell><br />
<br />
versus pointful map fusion:<br />
<br />
<haskell><br />
foldr f e . map g == foldr f' e<br />
where f' a b = f (g a) b<br />
</haskell><br />
<br />
Some more examples:<br />
<br />
<haskell><br />
-- point-wise, and point-free member<br />
mem, mem' :: Eq a => a -> [a] -> Bool<br />
<br />
mem x lst = any (== x) lst<br />
mem' = any . (==)<br />
</haskell><br />
<br />
== But pointfree has more points! ==<br />
<br />
A common misconception is that the 'points' of pointfree style are the<br />
<hask>(.)</hask> operator (function composition, as an ASCII symbol),<br />
which uses the same identifier as the decimal point. This is wrong. The<br />
term originated in topology, a branch of mathematics which works with<br />
spaces composed of points, and functions between those spaces. So a<br />
'points-free' definition of a function is one which does not explicitly<br />
mention the points (values) of the space on which the function acts. In<br />
Haskell, our 'space' is some type, and 'points' are values. In the<br />
declaration:<br />
<haskell><br />
f x = x + 1<br />
</haskell><br />
we define the function <hask>f</hask> in terms of its action on an<br />
arbitrary point <hask>x</hask>. Contrast this with the points-free<br />
version:<br />
<haskell><br />
f = (+ 1)<br />
</haskell><br />
where there is no mention of the value on which the function is acting.<br />
<br />
== Background ==<br />
<br />
To find out more about this style, search for Squiggol and the<br />
Bird-Meertens Formalism, a style of functional programming by<br />
calculation that was developed by [http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications.html Richard Bird], [http://www.kestrel.edu/home/people/meertens/ Lambert Meertens], and<br />
others at Oxford University. [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/ Jeremy Gibbons] has also written a number of<br />
papers about the topic, which are cited below.<br />
<br />
== Tool support ==<br />
<br />
Thomas Yaeger has<br />
[http://www.cse.unsw.edu.au/~dons/code/lambdabot/Plugins/Pl/ written] a <br />
[http://www.cse.unsw.edu.au/~dons/lambdabot.html Lambdabot] <br />
plugin to automatically convert a large subset of Haskell expressions to<br />
pointfree form. This tool has made it easier to use the more abstract<br />
pointfree encodings (as it saves some mental gymnastics on the part of<br />
the programmer). You can experiment with this in the [[IRC channel|Haskell IRC channel]]. A stand-alone command-line version is available at [http://hackage.haskell.org/packages/archive/pkg-list.html HackageDB] (package pointfree).<br />
<br />
The @pl (point-less) plugin is rather infamous for using the <hask>(-> a)</hask> <br />
[[Monad|monad]] to obtain concise code. It also makes use of [[Arrow|Arrows]]. <br />
It also sometimes produces (amusing) code blow ups with the<br />
<hask>(.)</hask> operator. Recently, @unpl has been written, which<br />
(attempts) to unscramble @pl-ified code.<br />
<br />
A transcript:<br />
<br />
<haskell><br />
> pl \x y -> x y<br />
id<br />
<br />
> unpl id<br />
(\ a -> a)<br />
<br />
> pl \x y -> x + 1<br />
const . (1 +)<br />
<br />
> unpl const . (1 +)<br />
(\ e _ -> 1 + e)<br />
<br />
> pl \v1 v2 -> sum (zipWith (*) v1 v2)<br />
(sum .) . zipWith (*)<br />
<br />
> unpl (sum .) . zipWith (*)<br />
(\ d g -> sum (zipWith (*) d g))<br />
<br />
> pl \x y z -> f (g x y z)<br />
((f .) .) . g<br />
<br />
> unpl ((f .) .) . g<br />
(\ e j m -> f (g e j m))<br />
<br />
> pl \x y z -> f (g x y) z<br />
(f .) . g<br />
<br />
> unpl (f .) . g<br />
(\ d i -> f (g d i))<br />
<br />
> pl \x y z -> f z (g x y)<br />
(flip f .) . g<br />
<br />
> unpl (flip f .) . g<br />
(\ i l c -> f c (g i l))<br />
<br />
> pl \(a,b) -> (b,a)<br />
uncurry (flip (,))<br />
<br />
> pl f a b = b a<br />
f = flip id<br />
<br />
> pl \ x -> x * x<br />
join (*)<br />
<br />
> pl \a b -> a:b:[]<br />
(. return) . (:)<br />
<br />
> pl \x -> x+x+x<br />
(+) =<< join (+)<br />
<br />
> pl \a b -> Nothing<br />
const (const Nothing)<br />
<br />
> pl \(a,b) -> (f a, g b)<br />
f *** g<br />
<br />
> pl \f g h x -> f x `h` g x<br />
flip . (ap .) . flip (.)<br />
<br />
> pl \x y -> x . f . y<br />
(. (f .)) . (.)<br />
<br />
> pl \f xs -> xs >>= return . f<br />
fmap<br />
<br />
> pl \h f g x -> f x `h` g x<br />
liftM2<br />
<br />
> pl \f a b c d -> f b c d a<br />
flip . ((flip . (flip .)) .)<br />
<br />
> pl \a (b,c) -> a c b<br />
(`ap` snd) . (. fst) . flip<br />
<br />
> pl \x y -> compare (f x) (f y)<br />
((. f) . compare .)<br />
</haskell><br />
<br />
For many many more examples, google for the results of '@pl' in the<br />
[[IRC_channel|#haskell]] logs. (Or join #haskell on FreeNode and try it<br />
yourself!) It can, of course, get out of hand:<br />
<br />
<haskell><br />
> pl \(a,b) -> a:b:[]<br />
uncurry ((. return) . (:))<br />
<br />
> pl \a b c -> a*b+2+c<br />
((+) .) . flip flip 2 . ((+) .) . (*)<br />
<br />
> pl \f (a,b) -> (f a, f b)<br />
(`ap` snd) . (. fst) . (flip =<< (((.) . (,)) .))<br />
<br />
> pl \f g (a,b) -> (f a, g b)<br />
flip flip snd . (ap .) . flip flip fst . ((.) .) . flip . (((.) . (,)) .)<br />
<br />
> unpl flip flip snd . (ap .) . flip flip fst . ((.) .) . flip . (((.) . (,)) .)<br />
(\ aa f -><br />
(\ p w -> ((,)) (aa (fst p)) (f w)) >>=<br />
\ ao -> snd >>= \ an -> return (ao an))<br />
</haskell><br />
<br />
== Combinator discoveries ==<br />
<br />
Some fun combinators have been found via @pl. Here we list some of the<br />
best:<br />
<br />
=== The owl ===<br />
<br />
<haskell><br />
((.)$(.))<br />
</haskell><br />
<br />
The owl has type <hask>(a -> b -> c) -> a -> (a1 -> b) -> a1 -><br />
c</hask>, and in pointful style can be written as <hask> f a b c d = a b<br />
(c d)</hask>.<br />
<br />
Example <br />
<haskell><br />
> ((.)$(.)) (==) 1 (1+) 0<br />
True<br />
</haskell><br />
<br />
=== Dot ===<br />
<br />
<haskell><br />
dot = ((.).(.))<br />
<br />
dot :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c<br />
</haskell><br />
<br />
Example:<br />
<br />
<haskell><br />
sequence `dot` replicate == <br />
(sequence .) . replicate ==<br />
replicateM<br />
<br />
(=<<) == join `dot` fmap<br />
</haskell><br />
<br />
=== Swing ===<br />
<br />
<haskell><br />
swing :: (((a -> b) -> b) -> c -> d) -> c -> a -> d<br />
swing = flip . (. flip id)<br />
swing f c a = f ($ c) a<br />
</haskell><br />
<br />
=== Squish ===<br />
<br />
<haskell><br />
f >>= a . b . c =<< g<br />
</haskell><br />
<br />
Example:<br />
<br />
<haskell><br />
(readFile y >>=) . ((a . b) .) . c =<< readFile x<br />
</haskell><br />
<br />
[[/Combine|An actually useful example]], numbering lines of a file.<br />
<br />
== Problems with pointfree ==<br />
<br />
Point-free style can (clearly) lead to [[Obfuscation]] when used unwisely.<br />
As higher-order functions are chained together, it can become harder to<br />
mentally infer the types of expressions. The mental cues to an<br />
expression's type (explicit function arguments, and the number of<br />
arguments) go missing.<br />
<br />
Point-free style often times leads to code which is difficult to modify. A function written in a pointfree style may have to be radically changed to make minor changes in functionality. This is because the function becomes more complicated than a composition of lambdas and other functions, and compositions must be changed to application for a pointful function.<br />
<br />
Perhaps these are why pointfree style is sometimes (often?) referred to as<br />
''pointless style''.<br />
<br />
== References ==<br />
<br />
One early reference is<br />
<br />
* Backus, J. 1978. "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs," Communications of the Association for Computing Machinery 21:613-641.<br />
<br />
which appears to be available (as a scan) at http://www.stanford.edu/class/cs242/readings/backus.pdf<br />
<br />
A paper specifically about point-free style: <br />
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#radix<br />
<br />
This style underlies a lot of expert Haskeller's intuitions. <br />
A rather infamous paper (for all the cute symbols) is Erik Meijer et. al's:<br />
<br />
* Functional Programming with Bananas, Lenses, and Barbed Wire, http://wwwhome.cs.utwente.nl/~fokkinga/mmf91m.ps.<br />
<br />
[http://en.wikipedia.org/wiki/Squiggol Squiggol], and the Bird-Meertens Formalism:<br />
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#squiggolintro.<br />
* A Calculus of Functions for Program Derivation, R.S. Bird, in Res Topics in Fnl Prog, D. Turner ed, A-W 1990.<br />
* The Squiggolist, ed Johan Jeuring, published irregularly by CWI Amsterdam.<br />
<br />
[http://wiki.di.uminho.pt/wiki/bin/view/Alcino/PointlessHaskell Pointless Haskell] is a library for point-free programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions. [http://wiki.di.uminho.pt/wiki/pub/Ze/Bic/report.pdf Haskell Manipulation] by Jose Miguel Paiva Proenca discusses this tool based approach to re-factoring.<br />
<br />
This project is written by [http://www.di.uminho.pt/~mac/ Manuel Alcino Cunha], see his homepage for more related materials on the topic.<br />
An extended verson of his paper ''Point-free Programming with Hylomorphisms'' can be found [http://web.comlab.ox.ac.uk/oucl/research/pdt/ap/dgp/workshop2004/cunha.pdf here].<br />
<br />
== Other areas ==<br />
<br />
[[Combinatory logic]] and also [[Recursive function theory]] can be said in some sense pointfree.<br />
<br />
Are there pointfree approaches to [[relational algebra]]?<br />
See [http://www.di.uminho.pt/~jno/ps/_.pdf First Steps in Pointfree Functional Dependency Theory] written by Jos Nuno Oliveira. A concise and deep approach. See also [http://www.di.uminho.pt/~jno/html/ the author's homepage] and also [http://www.di.uminho.pt/~jno/html/jnopub.html his many other papers] -- many materials related to this topic can be found there.<br />
<br />
[[Category:Idioms]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Blow_your_mind&diff=14771Blow your mind2007-08-01T06:30:13Z<p>Piet Delport: /* Monad magic */ double = join (+)</p>
<hr />
<div>Useful Idioms that will blow your mind (unless you already know them :)<br />
<br />
This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead him to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions.<br />
<br />
More examples are always welcome, especially "obscure" monadic ones.<br />
<br />
<br />
== List/String operations ==<br />
<br />
<br />
<haskell><br />
-- split at whitespace<br />
-- "hello world" -> ["hello","world"]<br />
words<br />
<br />
unfoldr (\b -> fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)<br />
<br />
fix (\f l -> if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e))<br />
<br />
<br />
-- splitting in two (alternating)<br />
-- "1234567" -> ("1357", "246")<br />
-- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists<br />
foldr (\a ~(x,y) -> (a:y,x)) ([],[])<br />
<br />
(map snd *** map snd) . partition (even . fst) . zip [0..]<br />
<br />
transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
-- this one uses the solution to the next problem in a nice way :)<br />
<br />
toMaybe b x = if b then Just x else Nothing<br />
<br />
-- splitting into lists of length N<br />
-- "1234567" -> ["12", "34", "56", "7"]<br />
unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
<br />
takeWhile (not . null) . unfoldr (Just . splitAt 2)<br />
<br />
<br />
-- sorting by a custom function<br />
-- length -> ["abc", "ab", "a"] -> ["a", "ab", "abc"]<br />
comparing f x y = compare (f x) (f y)<br />
sortBy (comparing length)<br />
<br />
map snd . sortBy (comparing fst) . map (length &&& id) <br />
-- the so called "Schwartzian Transform" for computationally more expensive <br />
-- functions.<br />
<br />
-- comparing adjacent elements<br />
rises xs = zipWith (<) xs (tail xs)<br />
<br />
-- lazy substring search<br />
-- "ell" -> "hello" -> True<br />
substr a b = any (a `isPrefixOf`) $ tails b<br />
<br />
-- multiple splitAt's:<br />
-- splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]<br />
splitAts = foldr (\n r -> splitAt n >>> second r >>> uncurry (:)) return<br />
</haskell><br />
<br />
== Mathematical sequences, etc ==<br />
<br />
<br />
<haskell><br />
-- factorial<br />
-- 6 -> 720<br />
product [1..6]<br />
<br />
foldl1 (*) [1..6]<br />
<br />
(!!6) $ scanl (*) 1 [1..]<br />
<br />
fix (\f n -> if n <= 0 then 1 else n * f (n-1))<br />
<br />
<br />
-- powers of two sequence<br />
iterate (*2) 1<br />
<br />
unfoldr (\z -> Just (z,2*z)) 1<br />
<br />
<br />
-- fibonacci sequence<br />
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)<br />
<br />
fibs = 0:1:zipWith (+) fibs (tail fibs)<br />
<br />
fib = 0:scanl (+) 1 fib<br />
<br />
<br />
-- pascal triangle<br />
pascal = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]<br />
<br />
<br />
-- prime numbers<br />
-- example of a memoising caf (??)<br />
primes = sieve [2..] where<br />
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]<br />
<br />
unfoldr sieve [2..] where <br />
sieve (p:x) = Just(p, [ n | n <- x, n `mod` p > 0 ])<br />
<br />
-- or if you want to use the Sieve of Eratosthenes..<br />
diff [] l = l<br />
diff l [] = l<br />
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl<br />
| x > y = diff xl ys<br />
| otherwise = diff xs ys <br />
esieve [] = []<br />
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))<br />
eprimes = esieve [2..]<br />
<br />
-- enumerating the rationals (see [1])<br />
rats :: [Rational]<br />
rats = iterate next 1 where<br />
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x<br />
<br />
-- another way<br />
rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]<br />
</haskell><br />
<br />
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]<br />
<br />
== Monad magic ==<br />
<br />
The list monad can be used from some amazing Prolog-ish search problems.<br />
<br />
<haskell><br />
-- all combinations of a list of lists.<br />
-- these solutions are all pretty much equivalent in that they run<br />
-- in the List Monad. the "sequence" solution has the advantage of<br />
-- scaling to N sublists.<br />
-- "12" -> "45" -> ["14", "15", "24", "25"]<br />
sequence ["12", "45"]<br />
<br />
[[x,y] | x <- "12", y <- "45"]<br />
<br />
do { x <- "12"; y <- "45"; return [x,y] }<br />
<br />
"12" >>= \a -> "45" >>= \b -> return [a,b]<br />
<br />
-- all combinations of letters<br />
(inits . repeat) ['a'..'z'] >>= sequence<br />
<br />
-- apply a list of functions to an argument<br />
-- even -> odd -> 4 -> [True,False]<br />
map ($4) [even,odd]<br />
<br />
sequence [even,odd] 4<br />
<br />
-- all subsequences of a sequence/ aka powerset.<br />
filterM (const [True, False])<br />
<br />
-- apply a function to two other function the same argument<br />
-- (lifting to the Function Monad (->))<br />
-- even 4 && odd 4 -> False<br />
liftM2 (&&) even odd 4<br />
<br />
liftM2 (>>) putStrLn return "hello"<br />
<br />
fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]<br />
[1%1,2%1,1%2,3%1,1%3,3%2,2%3,4%1,1%4,4%3,3%4,5%2,2%5,5%3,3%5,5%1,1%5,5%4,4%5...<br />
<br />
-- forward function concatenation<br />
(*3) >>> (+1) $ 2<br />
<br />
foldl1 (flip (.)) [(+1),(*2)] 500<br />
<br />
<br />
-- perform functions in/on a monad, lifting<br />
fmap (+2) (Just 2)<br />
<br />
liftM2 (+) (Just 4) (Just 2)<br />
<br />
<br />
-- [still to categorize]<br />
(id >>= (+) >>= (+) >>= (+)) 3 -- (3+3)+(3+3) = 12<br />
<br />
double = join (+)<br />
<br />
(join . liftM2) (*) (+3) 5 -- 64<br />
<br />
mapAccumL (\acc n -> (acc+n,acc+n)) 0 [1..10] -- interesting for fac, fib, ...<br />
<br />
do f <- [not, not]; d <- [True, False]; return (f d) -- [False,True,False,True]<br />
<br />
do { Just x <- [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x }<br />
</haskell><br />
<br />
== Other ==<br />
<br />
<br />
<haskell><br />
-- simulating lisp's cond<br />
case () of () | 1 > 2 -> True<br />
| 3 < 4 -> False<br />
| otherwise -> True<br />
<br />
<br />
-- match a constructor<br />
-- this is better than applying all the arguments, because this way the<br />
-- data type can be changed without touching the code (ideally).<br />
case a of Just{} -> True<br />
_ -> False<br />
<br />
<br />
{- <br />
TODO, IDEAS:<br />
more fun with monad, monadPlus (liftM, ap, guard, when)<br />
fun with arrows (second, first, &&&, ***)<br />
liftM, ap<br />
lazy search (searching as traversal of lazy structures)<br />
innovative data types (i.e. having fun with Maybe sequencing)<br />
<br />
LINKS:<br />
bananas, envelopes, ... (generic traversal)<br />
why functional fp matters (lazy search, ...)<br />
-}<br />
</haskell><br />
<br />
=== Polynomials ===<br />
In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients). <br />
<br />
instance Num a => Num [a] where -- (1)<br />
<br />
(f:fs) + (g:gs) = f+g : fs+gs -- (2)<br />
fs + [] = fs -- (3a)<br />
[] + gs = gs -- (3b)<br />
<br />
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) -- (4)<br />
_ * _ = [] -- (5)<br />
<br />
====Explanation====<br />
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.<br />
<br />
Lists are ordered by increasing powers. Thus <tt>f:fs</tt> means <tt>f+x*fs</tt> in algebraic notation. (2) and (4) follow from these algebraic identities:<br />
<br />
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs)<br />
(f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))<br />
<br />
(3) and (5) handle list ends.<br />
<br />
The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support.<br />
<br />
====Comments====<br />
<br />
The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.<br />
<br />
The methods are suitable for on-line computation. Only<br />
<i>n</i> terms of each input must be seen before the <i>n</i>-th term<br />
of output is produced.<br />
<br />
Thus the methods work on infinite series as well as polynomials.<br />
<br />
Integer power comes for free. This example tests the cubing of (1+x):<br />
<br />
[1, 1]^3 == [1, 3, 3, 1]<br />
<br />
See also<br />
* [[Pointfree]]<br />
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.hs NumericPrelude: Polynomials]<br />
* [[Add polynomials]]<br />
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].<br />
<br />
[[Category:Idioms]]<br />
[[Category:Mathematics]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=IRC_channel&diff=14730IRC channel2007-07-29T22:44:53Z<p>Piet Delport: /* Logs */ update meme.b9.com link to ircbrowse.com</p>
<hr />
<div>== Overview ==<br />
<br />
Internet Relay Chat is a worldwide text chat service with many thousands<br />
of users among various irc networks.<br />
<br />
The Freenode IRC network hosts the large #haskell channel, and we've had up to<br />
367 concurrent users (average is 319). One famous resident is<br />
[[Lambdabot]], another is [http://hpaste.org hpaste] (see the [[#Bots|Bots]] section below).<br />
<br />
The IRC channel can be an excellent place to learn more about Haskell,<br />
and to just keep in the loop on new things in the Haskell world. Many<br />
new developments in the Haskell world first appear on the irc channel.<br />
<br />
== Getting there ==<br />
<br />
If you point your irc client to [irc://chat.freenode.net/haskell chat.freenode.net] and then join the #haskell channel, you'll be there. Alternately, you can try [http://ircatwork.com/ ircatwork.com] which connects inside the browser.<br />
<br />
Example, using [http://www.irssi.org/ irssi]:<br />
<br />
$ irssi -c chat.freenode.org -n myname -w mypassword<br />
/join #haskell<br />
<br />
Tip, if you're using Emacs to edit your Haskell sources then why not use it to chat about Haskell? Check out [http://www.emacswiki.org/cgi-bin/wiki/EmacsIRCClient ERC], The Emacs IRC client. Invoke it like this and follow the commands:<br />
<br />
M-x erc-select<br />
...<br />
/join #haskell<br />
<br />
[[Image:Irc--haskell-screenshot.png|frame|A screenshot of an irssi session in #haskell]]<br />
<br />
== Principles ==<br />
<br />
The #haskell channel is a very friendly, welcoming place to hang out,<br />
teach and learn. The goal of #haskell is to encourage learning and<br />
discussion of Haskell, functional programming, and programming in<br />
general. As part of this we welcome newbies, and encourage teaching of<br />
the language.<br />
<br />
Part of the #haskell success comes from the approach that the community<br />
is quite tight knit -- we know each other -- it's not just a homework<br />
channel. As a result, many collaborative projects have arisen between<br />
Haskell irc channel citizens.<br />
<br />
To maintain the friendly, open culture, the following is required:<br />
<br />
* Low to zero tolerance for ridiculing questions. Insulting new users is unacceptable<br />
<br />
New Haskell users should feel entirely comfortable asking new questions.<br />
Helpful answers should be encouraged with <hask>name++</hask> karma<br />
points, in public, as a reward for providing a good answer.<br />
<br />
== History ==<br />
<br />
The #haskell channel appeared in the late 90s, and really got going<br />
in early 2001, with the help of Shae Erisson (aka shapr).<br />
<br />
A fairly extensive analysis of the traffic on #haskell over the years is<br />
[http://www.cse.unsw.edu.au/~dons/irc/ kept here]<br />
<br />
<br />
== Related channels ==<br />
<br />
In addition to the main Haskell channel there are also:<br />
<br />
{| border="1" cellspacing="0" cellpadding="5" align="center"<br />
! Channel<br />
! Purpose<br />
|- <br />
| #haskell.de<br />
| German speakers<br />
|-<br />
| #haskell.dut<br />
| Dutch speakers<br />
|-<br />
| #haskell.es<br />
| Spanish speakers<br />
|-<br />
| #haskell.fi<br />
| Finnish speakers<br />
|-<br />
| #haskell.fr <br />
| French speakers <br />
|-<br />
| #haskell.hr<br />
| Croatian speakers<br />
|-<br />
| #haskell.it <br />
| Italian speakers<br />
|-<br />
| #haskell.jp <br />
| Japanese speakers<br />
|-<br />
| #haskell.no <br />
| Norwegian speakers<br />
|-<br />
| #haskell.ru <br />
| Russian speakers. Seems that most of them migrated to Jabber conference (haskell@conference.jabber.ru)<br />
|-<br />
| #haskell.se <br />
| Swedish speakers<br />
|-<br />
| #haskell-overflow<br />
| Overflow conversations<br />
|-<br />
| #haskell-blah <br />
| Haskell people talking about anything except Haskell itself<br />
|-<br />
| #haskell-books <br />
| Authors organizing the collaborative writing of the [http://en.wikibooks.org/wiki/Haskell Haskell wikibook] and other books or tutorials.<br />
|-<br />
| #gentoo-haskell <br />
| [[Gentoo]]/Linux specific Haskell conversations<br />
|-<br />
| #darcs <br />
| [[Darcs]] revision control channel (written in Haskell)<br />
|-<br />
| #perl6 <br />
| [http://www.pugscode.org Perl 6] development (plenty of Haskell chat there too)<br />
|-<br />
| #happs<br />
| [http://happs.org HAppS] Haskell Application Server channel<br />
|-<br />
| #xmonad<br />
| [http://xmonad.org Xmonad] a tiling window manager written in Haskell<br />
|}<br />
<br />
[[Image:Nick-activity.png|frame|Growth of #haskell]]<br />
<br />
== Logs ==<br />
<br />
'''Logs''' are kept at a few places, including<br />
<br />
* [http://tunes.org/~nef/logs/haskell/ tunes.org]<br />
* [http://ircbrowse.com/cdates.html?channel=haskell IRCBrowse]<br />
<br />
== Bots ==<br />
<br />
=== Lambdabot ===<br />
<br />
[[Lambdabot]] provides many useful services for visitors to the IRC channel. Check out its wiki page for information on its commands.<br />
<br />
=== Hpaste ===<br />
The hpaste bot provides a notification interface to the [http://hpaste.org hpaste pastebin]. [[Hpaste.el|Emacs integration]] is available.<br />
<br />
== Locations ==<br />
<br />
To get an overview of where everybody on the channel might<br />
be, physically, please visit [[Haskell user locations]].<br />
<br />
[[Category:Community]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Quotes&diff=14553Quotes2007-07-20T10:36:13Z<p>Piet Delport: over-costanding comonads</p>
<hr />
<div><pre><br />
<Philippa> do we have a case of haskell faster than C on a platform where GHC<br />
compiles via C and doesn't screw with the output yet?<br />
<jethr0> wouldn't that just be a blatant case of slow c benchmarking code? :)<br />
<dons> the concurrency or binary tree benchmarks?<br />
<jethr0> someone could put the haskell intermediate c code up as the c benchmark *g*<br />
<musasabi> yes, 30000 lines of C? ;)<br />
%<br />
seen on comp.lang.functional:<br />
<br />
From: Ashley Yakeley <ashley@semantic.org><br />
Subject: Re: Type advocacy<br />
Newsgroups: comp.lang.functional<br />
Date: Thu, 11 Oct 2001 21:16:20 -0700<br />
Organization: Myself<br />
<br />
In article <9pdvgc$u3d$1@news.fas.harvard.edu>, Ken Shan<br />
<ken@digitas.harvard.edu> wrote:<br />
<br />
> I am preparing a three-minute talk to tell incoming graduate students<br />
> at my school about types.<br />
<br />
Oh like that's going to work. You'd be better off selling T-shirts that<br />
say "WHAT PART OF" (and then the Hindley-Milner prinicipal-type<br />
algorithm) "DON'T YOU UNDERSTAND?".<br />
<br />
If anyone gives you any lip, ask them how to find the square-root of a<br />
string. Everything else follows on from that.<br />
<br />
> What pointers should I give?<br />
<br />
Safe ones.<br />
<br />
--<br />
Ashley Yakeley, Seattle WA<br />
%<br />
<kaol> @src liftM<br />
<lambdabot> liftM f m1 = do { x1 <- m1; return (f x1) }<br />
<kaol> @src liftM2<br />
<lambdabot> liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }<br />
<osfameron> does that lift monads which are twice as heavy?<br />
<LoganCapaldo> No, it just lifts a monad in each hand<br />
<osfameron> harr!<br />
<byorgey> you know what they say, a monad in each hand is better than two in<br />
the bush... no wait...<br />
<jfredett> if this were not a family chat channel, I might say something about that...<br />
<DRMacIver> Hand me a long enough monad and I will move the world?<br />
<cjeris> jfredett: yeah, well, the first time I tried to explain what was<br />
different about Haskell to my wife, her response was "Monad? Is that<br />
when you only have one ball?"<br />
%<br />
* EvilTerran . o O ( is a comathematician a device for turning theorems into coffee? )<br />
<oerjan> EvilTerran: no, it's for turning cotheorems into ffee.<br />
<slava> oerjan: it's not clear that the category of cocoffee is isomorphic to ffee<br />
<oerjan> slava: bah, it's mpletely coclear.<br />
%<br />
<roconnor> comonads are just as hard to understand as monads.<br />
<Toxaris> you have to co-understand them?<br />
<quicksilver> Toxaris: I believe you actually have to over-costand them<br />
</pre><br />
<br />
[[Category:Community]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Learn_Haskell_in_10_minutes&diff=14492Learn Haskell in 10 minutes2007-07-18T12:54:10Z<p>Piet Delport: last two → last three are Fractional</p>
<hr />
<div>== Overview ==<br />
<br />
Haskell is a functional (that is, everything is done with function calls), statically, implicitly typed ([[type]]s are checked by the compiler, but you don't have to declare them), lazy (nothing is done until it needs to be) language. Its closest popular relative is probably the ML family of languages.<br />
<br />
The most common Haskell compiler is [[GHC]]. You can download GHC from http://www.haskell.org/ghc/download_ghc_661.html . GHC binaries are available for [[GNU/Linux]], [[BSD | FreeBSD]], [[Mac OS X |MacOS]], [[Windows]], and [[Solaris]]. Once you've installed [[GHC]], you get two programs you're interested in right now: <tt>ghc</tt>, and <tt>[[GHC/GHCi | ghci]]</tt>. The first compiles Haskell libraries or applications to binary code. The second is an interpreter that lets you write Haskell code and get feedback right away.<br />
<br />
== Simple expressions ==<br />
<br />
You can type most math expressions directly into <tt>ghci</tt> and get an answer. <tt>Prelude></tt> is the default GHCi prompt.<br />
<br />
Prelude> <hask>3 * 5</hask><br />
15<br />
Prelude> <hask>4 ^ 2 - 1</hask><br />
15<br />
Prelude> <hask>(1 - 5)^(3 * 2 - 4)</hask><br />
16<br />
<br />
Strings are in "double quotes." You can concatenate them with <hask>++</hask>.<br />
<br />
Prelude> <hask>"Hello"</hask><br />
"Hello"<br />
Prelude> <hask>"Hello" ++ ", Haskell"</hask><br />
"Hello, Haskell"<br />
<br />
Calling [[function]]s is done by putting the arguments directly after the function. There are no parentheses as part of the function call:<br />
<br />
Prelude> <hask>succ 5</hask><br />
6<br />
Prelude> <hask>truncate 6.59</hask><br />
6<br />
Prelude> <hask>round 6.59</hask><br />
7<br />
Prelude> <hask>sqrt 2</hask><br />
1.4142135623730951<br />
Prelude> <hask>not (5 < 3)</hask><br />
True<br />
Prelude> <hask>gcd 21 14</hask><br />
7<br />
<br />
== The console ==<br />
<br />
[[Introduction to IO |I/O actions]] can be used to read from and write to the console. Some common ones include:<br />
<br />
Prelude> <hask>putStrLn "Hello, Haskell"</hask><br />
Hello, Haskell<br />
Prelude> <hask>putStr "No newline"</hask><br />
No newlinePrelude> <hask>print (5 + 4)</hask><br />
9<br />
Prelude> <hask>print (1 < 2)</hask><br />
True<br />
<br />
The <hask>putStr</hask> and <hask>putStrLn</hask> functions output strings to the terminal. The <hask>print</hask> function outputs any type of value. (If you <hask>print</hask> a string, it will have quotes around it.)<br />
<br />
If you need multiple I/O actions in one expression, you can use a <hask>do</hask> block. Actions are separated by semicolons.<br />
<br />
Prelude> <hask>do { putStr "2 + 2 = " ; print (2 + 2) }</hask><br />
2 + 2 = 4<br />
Prelude> <hask>do { putStrLn "ABCDE" ; putStrLn "12345" }</hask><br />
ABCDE<br />
12345<br />
<br />
Reading can be done with <hask>getLine</hask> (which gives back a <hask>String</hask>) or <hask>readLn</hask> (which gives back whatever type of value you want). The <hask> <- </hask> symbol is used to assign a name to the result of an I/O action.<br />
<br />
Prelude> <hask>do { n <- readLn ; print (n^2) }</hask><br />
4<br />
16<br />
<br />
(The 4 was input. The 16 was a result.)<br />
<br />
There is actually another way to write <hask>do</hask> blocks. If you leave off the braces and semicolons, then indentation becomes significant. This doesn't work so well in <tt>ghci</tt>, but try putting the file in a source file (say, <tt>Test.hs</tt>) and build it.<br />
<br />
<haskell><br />
main = do putStrLn "What is 2 + 2?"<br />
x <- readLn<br />
if x == 4<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
You can build with <tt>ghc --make Test.hs</tt>, and the result will be called <tt>Test</tt>. (On [[Windows]], <tt>Test.exe</tt>) You get an <hask>if</hask> expression as a bonus.<br />
<br />
Every line that starts in the same column as the first <hask>putStrLn</hask> is part of the <hask>do</hask> block. This is called "layout", and Haskell uses it to avoid making you put in statement terminators and braces all the time. (The <hask>then</hask> and <hask>else</hask> phrases have to be indented for this reason: if they started in the same column, they'd be separate statements, which is wrong.)<br />
<br />
(Note: Do '''not''' indent with tabs if you're using layout. It technically still works if your tabs are 8 spaces, but it's a bad idea.)<br />
<br />
== Simple types ==<br />
<br />
So far, not a single [[type]] declaration has been mentioned. That's because Haskell does type inference. You generally don't have to declare types unless you want to. If you do want to declare types, you use <hask>::</hask> to do it.<br />
<br />
Prelude> <hask>5 :: Int</hask><br />
5<br />
Prelude> <hask>5 :: Double</hask><br />
5.0<br />
<br />
[[Type]]s (and type [[class]]es, discussed later) always start with upper-case letters in Haskell. Variables always start with lower-case letters. This is a rule of the language, not a [[Studly capitals|naming convention]].<br />
<br />
You can also ask <tt>ghci</tt> what type it has chosen for something. This is useful because you don't generally have to declare your types.<br />
<br />
Prelude> :t <hask>True</hask><br />
<hask>True :: Bool</hask><br />
Prelude> :t <hask>'X'</hask><br />
<hask>'X' :: Char</hask><br />
Prelude> :t <hask>"Hello, Haskell"</hask><br />
<hask>"Hello, Haskell" :: [Char]</hask><br />
<br />
(In case you noticed, <hask>[Char]</hask> is another way of saying <hask>String</hask>. See the [[#Structured data|section on lists]] later.)<br />
<br />
Things get more interesting for numbers.<br />
<br />
Prelude> :t <hask>42</hask><br />
<hask>42 :: (Num t) => t</hask><br />
Prelude> :t <hask>42.0</hask><br />
<hask>42.0 :: (Fractional t) => t</hask><br />
Prelude> :t <hask>gcd 15 20</hask><br />
<hask>gcd 15 20 :: (Integral t) => t</hask><br />
<br />
These types use "type classes." They mean:<br />
<br />
* <hask>42</hask> can be used as any numeric type. (This is why I was able to declare <hask>5</hask> as either an <hask>Int</hask> or a <hask>Double</hask> earlier.)<br />
* <hask>42.0</hask> can be any fractional type, but not an integral type.<br />
* <hask>gcd 15 20</hask> (which is a function call, incidentally) can be any integral type, but not a fractional type.<br />
<br />
There are five numeric types in the Haskell "prelude" (the part of the library you get without having to import anything):<br />
<br />
* <hask>Int</hask> is an integer with at least 30 bits of precision.<br />
* <hask>Integer</hask> is an integer with unlimited precision.<br />
* <hask>Float</hask> is a single precision floating point number.<br />
* <hask>Double</hask> is a double precision floating point number.<br />
* <hask>Rational</hask> is a fraction type, with no rounding error.<br />
<br />
All five are '''instances''' of the <hask>Num</hask> type class. The first two are '''instances''' of <hask>Integral</hask>, and the last three are '''instances''' of <hask>Fractional</hask>.<br />
<br />
Putting it all together,<br />
<br />
Prelude> <hask>gcd 42 35 :: Int</hask><br />
7<br />
Prelude> <hask>gcd 42 35 :: Double</hask><br />
<br />
<interactive>:1:0:<br />
No instance for (Integral Double)<br />
<br />
The final type worth mentioning here is <hask>()</hask>, pronounced "unit." It only has one value, also written as <hask>()</hask> and pronounced "unit."<br />
<br />
Prelude> <hask>()</hask><br />
<hask>()</hask><br />
Prelude> :t <hask>()</hask><br />
<hask>() :: ()</hask><br />
<br />
You can think of this as similar to the <tt>void</tt> keyword in C family languages. You can return <hask>()</hask> from an I/O action if you don't want to return anything.<br />
<br />
== Structured data ==<br />
<br />
Basic data types can be easily combined in two ways: lists, which go in [square brackets], and tuples, which go in (parentheses).<br />
<br />
Lists are used to hold multiple values of the same type.<br />
<br />
Prelude> <hask>[1, 2, 3]</hask><br />
[1,2,3]<br />
Prelude> <hask>[1 .. 5]</hask><br />
[1,2,3,4,5]<br />
Prelude> <hask>[1, 3 .. 10]</hask><br />
[1,3,5,7,9]<br />
Prelude> <hask>[True, False, True]</hask><br />
[True,False,True]<br />
<br />
Strings are just lists of characters.<br />
<br />
Prelude> <hask>['H', 'e', 'l', 'l', 'o']</hask><br />
"Hello"<br />
<br />
The <hask>:</hask> operator appends an item to the beginning of a list. (It is Haskell's version of the <tt>cons</tt> function in the Lisp family of languages.)<br />
<br />
Prelude> <hask>'C' : ['H', 'e', 'l', 'l', 'o']</hask><br />
"CHello"<br />
<br />
Tuples hold a fixed number of values, which can have different types.<br />
<br />
Prelude> <hask>(1, True)</hask><br />
(1,True)<br />
Prelude> <hask>zip [1 .. 5] ['a' .. 'e']</hask><br />
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]<br />
<br />
The last example used <hask>zip</hask>, a library function that turns two lists into a list of tuples.<br />
<br />
The types are probably what you'd expect.<br />
<br />
Prelude> :t <hask>['a' .. 'c']</hask><br />
<hask>['a' .. 'c'] :: [Char]</hask><br />
Prelude> :t <hask>[('x', True), ('y', False)]</hask><br />
<hask>[('x', True), ('y', False)] :: [(Char, Bool)]</hask><br />
<br />
Lists are used a lot in Haskell. There are several functions that do nice things with them.<br />
<br />
Prelude> <hask>[1 .. 5]</hask><br />
<hask>[1,2,3,4,5]</hask><br />
Prelude> <hask>map (+ 2) [1 .. 5]</hask><br />
<hask>[3,4,5,6,7]</hask><br />
Prelude> <hask>filter (> 2) [1 .. 5]</hask><br />
<hask>[3,4,5]</hask><br />
<br />
There are two nice functions on ordered pairs (tuples of two elements):<br />
<br />
Prelude> <hask>fst (1, 2)</hask><br />
<hask>1</hask><br />
Prelude> <hask>snd (1, 2)</hask><br />
<hask>2</hask><br />
Prelude> <hask>map fst [(1, 2), (3, 4), (5, 6)]</hask><br />
<hask>[1,3,5]</hask><br />
<br />
Also see [[how to work on lists]]<br />
<br />
== [[Function]] definitions ==<br />
<br />
We wrote a [[function]] earlier, called <hask>main</hask>:<br />
<br />
<haskell><br />
main = do putStrLn "What is 2 + 2?"<br />
x <- readLn<br />
if x == 4<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
Let's write another, and call it <hask>factorial</hask>. I'm also adding a module header, which is good form.<br />
<br />
<haskell><br />
module Main where<br />
<br />
factorial n = if n == 0 then 1 else n * factorial (n - 1)<br />
<br />
main = do putStrLn "What is 5! ?"<br />
x <- readLn<br />
if x == factorial 5<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
Build again with <tt>ghc --make Test.hs</tt>. And,<br />
<br />
$ ./Test<br />
What is 5! ?<br />
120<br />
You're right!<br />
<br />
There's a function. Just like the built-in functions, it can be called as <hask>factorial 5</hask> without needing parentheses.<br />
<br />
Now ask <tt>ghci</tt> for the [[type]].<br />
<br />
$ ghci Test.hs<br />
<< GHCi banner >><br />
Ok, modules loaded: Main.<br />
Prelude Main> :t <hask>factorial</hask><br />
<hask>factorial :: (Num a) => a -> a</hask><br />
<br />
Function types are written with the argument type, then <hask> -> </hask>, then the result type. (This also has the type class <hask>Num</hask>.)<br />
<br />
Factorial can be simplified by writing it with case analysis.<br />
<br />
<haskell><br />
factorial 0 = 1<br />
factorial n = n * factorial (n - 1)<br />
</haskell><br />
<br />
== Convenient syntax ==<br />
<br />
A couple extra pieces of [[:Category:Syntax |syntax]] are helpful.<br />
<br />
<haskell><br />
secsToWeeks secs = let perMinute = 60<br />
perHour = 60 * perMinute<br />
perDay = 24 * perHour<br />
perWeek = 7 * perday<br />
in secs * perWeek<br />
</haskell><br />
<br />
The <hask>let</hask> expression defines temporary names. (This is using layout again. You could use {braces}, and separate the names with parentheses, if you prefer.)<br />
<br />
<haskell><br />
classify age = case age of 0 -> "newborn"<br />
1 -> "infant"<br />
2 -> "toddler"<br />
_ -> "senior citizen"<br />
</haskell><br />
<br />
The <hask>case</hask> expression does a multi-way branch. The special label <hask>_</hask> means "anything else".<br />
<br />
== Using libraries ==<br />
<br />
Everything used so far in this tutorial is part of the [[Prelude]], which is the set of Haskell functions that are always there in any program.<br />
<br />
The best road from here to becoming a very productive Haskell programmer (aside from practice!) is becoming familiar with other [[Applications and libraries | libraries]] that do the things you need. Documentation on the standard libraries is at [http://haskell.org/ghc/docs/latest/html/libraries/ http://haskell.org/ghc/docs/latest/html/libraries/]. There are modules there with:<br />
<br />
* [[Applications and libraries/Data structures |Useful data structures]]<br />
* [[Applications and libraries/Concurrency and parallelism |Concurrent and parallel programming]]<br />
* [[Applications and libraries/GUI libraries | Graphics and GUI libraries]]<br />
* [[Applications and libraries/Network | Networking, POSIX, and other system-level stuff]]<br />
* Two test frameworks, QuickCheck and HUnit<br />
* Regular expressions and predictive parsers<br />
* More...<br />
<br />
<haskell><br />
module Main where<br />
<br />
import Data.Map as M<br />
<br />
errorsPerLine = M.fromList<br />
[ ("Chris", 472), ("Don", 100), ("Simon", -5) ]<br />
<br />
main = do putStrLn "Who are you?"<br />
name <- getLine<br />
case M.lookup name errorsPerLine of<br />
Nothing -> putStrLn "I don't know you"<br />
Just n -> do putStr "Errors per line: "<br />
print n<br />
</haskell><br />
<br />
The <hask>import</hask> says to use code from <hask>Data.Map</hask> and that it will be prefixed by <hask>M</hask>. (That's necessary because some of the functions have the same names as functions from the prelude. Most libraries don't need the <hask>as</hask> part.)<br />
<br />
If you want something that's not in the standard library, try looking at http://hackage.haskell.org/packages/hackage.html or this wiki's [[applications and libraries]] page. This is a collection of many different libraries written by a lot of people for Haskell. Once you've got a library, extract it and switch into that directory and do this:<br />
<br />
runhaskell Setup configure<br />
runhaskell Setup build<br />
runhaskell Setup install<br />
<br />
On a UNIX system, you may need to be root for that last part.<br />
<br />
== Topics that don't fit in 10 minute limit ==<br />
<br />
* [[:Category:Language | Advanced data types]]<br />
** Arithmetic lists<br />
** [[List comprehension]]s<br />
** [[Type#Type and newtype | Type synonyms]]<br />
** [[Type|data vs newtype]] (and [[Newtype|here]])<br />
** [[Class |Type classes and instances]]<br />
* [[:Category:Syntax |Advanced syntax]]<br />
** [[Operator]]s<br />
** [[Infix operators |(+) and `foo`]]<br />
** [[Fixity declaration]]s<br />
* Advanced functions<br />
** [[Currying]]<br />
** [[Lambda abstraction]]s<br />
** [[Section of an infix operator |Sections]]<br />
* [[:Category:Monad |Monads]]<br />
* [[Tutorials/Programming Haskell/String IO |File I/O]]<br />
** Reading files<br />
** Writing Files<br />
<br />
[[Category:Tutorials]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Quotes&diff=14463Quotes2007-07-17T23:22:52Z<p>Piet Delport: rococo</p>
<hr />
<div><pre><br />
<Philippa> do we have a case of haskell faster than C on a platform where GHC<br />
compiles via C and doesn't screw with the output yet?<br />
<jethr0> wouldn't that just be a blatant case of slow c benchmarking code? :)<br />
<dons> the concurrency or binary tree benchmarks?<br />
<jethr0> someone could put the haskell intermediate c code up as the c benchmark *g*<br />
<musasabi> yes, 30000 lines of C? ;)<br />
%<br />
seen on comp.lang.functional:<br />
<br />
From: Ashley Yakeley <ashley@semantic.org><br />
Subject: Re: Type advocacy<br />
Newsgroups: comp.lang.functional<br />
Date: Thu, 11 Oct 2001 21:16:20 -0700<br />
Organization: Myself<br />
<br />
In article <9pdvgc$u3d$1@news.fas.harvard.edu>, Ken Shan<br />
<ken@digitas.harvard.edu> wrote:<br />
<br />
> I am preparing a three-minute talk to tell incoming graduate students<br />
> at my school about types.<br />
<br />
Oh like that's going to work. You'd be better off selling T-shirts that<br />
say "WHAT PART OF" (and then the Hindley-Milner prinicipal-type<br />
algorithm) "DON'T YOU UNDERSTAND?".<br />
<br />
If anyone gives you any lip, ask them how to find the square-root of a<br />
string. Everything else follows on from that.<br />
<br />
> What pointers should I give?<br />
<br />
Safe ones.<br />
<br />
--<br />
Ashley Yakeley, Seattle WA<br />
%<br />
<kaol> @src liftM<br />
<lambdabot> liftM f m1 = do { x1 <- m1; return (f x1) }<br />
<kaol> @src liftM2<br />
<lambdabot> liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }<br />
<osfameron> does that lift monads which are twice as heavy?<br />
<LoganCapaldo> No, it just lifts a monad in each hand<br />
<osfameron> harr!<br />
<byorgey> you know what they say, a monad in each hand is better than two in<br />
the bush... no wait...<br />
<jfredett> if this were not a family chat channel, I might say something about that...<br />
<DRMacIver> Hand me a long enough monad and I will move the world?<br />
<cjeris> jfredett: yeah, well, the first time I tried to explain what was<br />
different about Haskell to my wife, her response was "Monad? Is that<br />
when you only have one ball?"<br />
%<br />
* EvilTerran . o O ( is a comathematician a device for turning theorems into coffee? )<br />
<oerjan> EvilTerran: no, it's for turning cotheorems into ffee.<br />
<slava> oerjan: it's not clear that the category of cocoffee is isomorphic to ffee<br />
<oerjan> slava: bah, it's mpletely coclear.<br />
</pre><br />
<br />
[[Category:Community]]</div>Piet Delporthttps://wiki.haskell.org/index.php?title=User:Piet_Delport&diff=13485User:Piet Delport2007-06-15T15:19:07Z<p>Piet Delport: stub</p>
<hr />
<div>See Wikipedia: [http://en.wikipedia.org/wiki/User:Piet_Delport User:Piet Delport].</div>Piet Delporthttps://wiki.haskell.org/index.php?title=Quotes&diff=13484Quotes2007-06-15T15:10:55Z<p>Piet Delport: monadic mirth</p>
<hr />
<div><pre><br />
<Philippa> do we have a case of haskell faster than C on a platform where GHC<br />
compiles via C and doesn't screw with the output yet?<br />
<jethr0> wouldn't that just be a blatant case of slow c benchmarking code? :)<br />
<dons> the concurrency or binary tree benchmarks?<br />
<jethr0> someone could put the haskell intermediate c code up as the c benchmark *g*<br />
<musasabi> yes, 30000 lines of C? ;)<br />
%<br />
seen on comp.lang.functional:<br />
<br />
From: Ashley Yakeley <ashley@semantic.org><br />
Subject: Re: Type advocacy<br />
Newsgroups: comp.lang.functional<br />
Date: Thu, 11 Oct 2001 21:16:20 -0700<br />
Organization: Myself<br />
<br />
In article <9pdvgc$u3d$1@news.fas.harvard.edu>, Ken Shan<br />
<ken@digitas.harvard.edu> wrote:<br />
<br />
> I am preparing a three-minute talk to tell incoming graduate students<br />
> at my school about types.<br />
<br />
Oh like that's going to work. You'd be better off selling T-shirts that<br />
say "WHAT PART OF" (and then the Hindley-Milner prinicipal-type<br />
algorithm) "DON'T YOU UNDERSTAND?".<br />
<br />
If anyone gives you any lip, ask them how to find the square-root of a<br />
string. Everything else follows on from that.<br />
<br />
> What pointers should I give?<br />
<br />
Safe ones.<br />
<br />
--<br />
Ashley Yakeley, Seattle WA<br />
%<br />
<kaol> @src liftM<br />
<lambdabot> liftM f m1 = do { x1 <- m1; return (f x1) }<br />
<kaol> @src liftM2<br />
<lambdabot> liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }<br />
<osfameron> does that lift monads which are twice as heavy?<br />
<LoganCapaldo> No, it just lifts a monad in each hand<br />
<osfameron> harr!<br />
<byorgey> you know what they say, a monad in each hand is better than two in<br />
the bush... no wait...<br />
<jfredett> if this were not a family chat channel, I might say something about that...<br />
<DRMacIver> Hand me a long enough monad and I will move the world?<br />
<cjeris> jfredett: yeah, well, the first time I tried to explain what was<br />
different about Haskell to my wife, her response was "Monad? Is that<br />
when you only have one ball?"<br />
</pre><br />
<br />
[[Category:Community]]</div>Piet Delport