https://wiki.haskell.org/api.php?action=feedcontributions&user=ConradParker&feedformat=atomHaskellWiki - User contributions [en]2015-07-02T04:07:02ZUser contributionsMediaWiki 1.19.14+dfsg-1https://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-03-31T06:44:32Z<p>ConradParker: add zoom-cache and scope links</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [https://github.com/kfish/raft raft], an implementation of the Raft consensus protocol<br />
* zoom-cache and scope<br />
** [https://plus.google.com/+ConradParker/posts/CJxACUYTLuM Multichannel support in zoom-cache and scope]<br />
** [https://plus.google.com/+ConradParker/posts/M2678hYANYy New scope-cairo package, and scope-0.8.0.0]<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
** [http://blog.kfish.org/2008/12/release-hogg-041.html Release: HOgg 0.4.1]<br />
** [http://blog.kfish.org/2008/03/release-hogg-040.html Release: HOgg 0.4.0]<br />
** [http://blog.kfish.org/2007/12/release-hogg-030.html Release: HOgg 0.3.0]<br />
* Conference talks:<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
** [http://blog.kfish.org/2011/09/iteratees-at-tsuru.html Iteratees at Tsuru Capital]<br />
<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2009/03/random-code-pretty-printing-durations.html Random code: Pretty printing durations in Haskell]<br />
** [http://blog.kfish.org/2010/07/haskell-template-for-gtk-glade-cairo.html A Haskell template for GTK, Glade and Cairo apps]<br />
** [http://blog.kfish.org/2010/04/trivial-git-routines-in-haskell-ght-020.html Trivial git routines in Haskell]<br />
** [http://blog.kfish.org/2010/04/uicommand.html UI.Command]<br />
<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-03-31T06:32:43Z<p>ConradParker: split out conference talk links</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [https://github.com/kfish/raft raft], an implementation of the Raft consensus protocol<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
** [http://blog.kfish.org/2008/12/release-hogg-041.html Release: HOgg 0.4.1]<br />
** [http://blog.kfish.org/2008/03/release-hogg-040.html Release: HOgg 0.4.0]<br />
** [http://blog.kfish.org/2007/12/release-hogg-030.html Release: HOgg 0.3.0]<br />
* Conference talks:<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
** [http://blog.kfish.org/2011/09/iteratees-at-tsuru.html Iteratees at Tsuru Capital]<br />
<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2009/03/random-code-pretty-printing-durations.html Random code: Pretty printing durations in Haskell]<br />
** [http://blog.kfish.org/2010/07/haskell-template-for-gtk-glade-cairo.html A Haskell template for GTK, Glade and Cairo apps]<br />
** [http://blog.kfish.org/2010/04/trivial-git-routines-in-haskell-ght-020.html Trivial git routines in Haskell]<br />
** [http://blog.kfish.org/2010/04/uicommand.html UI.Command]<br />
<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-03-31T06:31:01Z<p>ConradParker: Add HOgg release note links</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [https://github.com/kfish/raft raft], an implementation of the Raft consensus protocol<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
** [http://blog.kfish.org/2008/12/release-hogg-041.html Release: HOgg 0.4.1]<br />
** [http://blog.kfish.org/2008/03/release-hogg-040.html Release: HOgg 0.4.0]<br />
** [http://blog.kfish.org/2007/12/release-hogg-030.html Release: HOgg 0.3.0]<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
** [http://blog.kfish.org/2009/03/random-code-pretty-printing-durations.html Random code: Pretty printing durations in Haskell]<br />
** [http://blog.kfish.org/2010/07/haskell-template-for-gtk-glade-cairo.html A Haskell template for GTK, Glade and Cairo apps]<br />
** [http://blog.kfish.org/2010/04/trivial-git-routines-in-haskell-ght-020.html Trivial git routines in Haskell]<br />
** [http://blog.kfish.org/2010/04/uicommand.html UI.Command]<br />
** [http://blog.kfish.org/2011/09/iteratees-at-tsuru.html Iteratees at Tsuru Capital]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-03-31T06:29:38Z<p>ConradParker: Add more kfish blog links</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [https://github.com/kfish/raft raft], an implementation of the Raft consensus protocol<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
** [http://blog.kfish.org/2009/03/random-code-pretty-printing-durations.html Random code: Pretty printing durations in Haskell]<br />
** [http://blog.kfish.org/2010/07/haskell-template-for-gtk-glade-cairo.html A Haskell template for GTK, Glade and Cairo apps]<br />
** [http://blog.kfish.org/2010/04/trivial-git-routines-in-haskell-ght-020.html Trivial git routines in Haskell]<br />
** [http://blog.kfish.org/2010/04/uicommand.html UI.Command]<br />
** [http://blog.kfish.org/2011/09/iteratees-at-tsuru.html Iteratees at Tsuru Capital]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-03-31T06:19:15Z<p>ConradParker: add gtk, iteratees blog links</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [https://github.com/kfish/raft raft], an implementation of the Raft consensus protocol<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
** [http://blog.kfish.org/2010/07/haskell-template-for-gtk-glade-cairo.html A Haskell template for GTK, Glade and Cairo apps]<br />
** [http://blog.kfish.org/2011/09/iteratees-at-tsuru.html Iteratees at Tsuru Capital]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-03-31T06:14:56Z<p>ConradParker: add Raft link</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [https://github.com/kfish/raft raft], an implementation of the Raft consensus protocol<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2015-02-11T08:53:54Z<p>ConradParker: Update my user info</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on machine learning systems at Commonwealth Bank, and before that on trading strategies in Haskell at Tsuru Capital in Singapore and Tokyo.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/HoogleHoogle2012-08-06T02:40:32Z<p>ConradParker: /* GHCi Integration */ add Simon Hengel's :doc suggestion from haskell-cafe</p>
<hr />
<div>Hoogle is a Haskell API search engine, which allows you to search many standard Haskell libraries by either function name, or by approximate [[type signature]].<br />
<br />
* '''Online version:''' http://haskell.org/hoogle<br />
* '''Hackage page:''' http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hoogle<br />
* '''Darcs repository:''' http://code.haskell.org/hoogle<br />
* '''Bug tracker:''' http://code.google.com/p/ndmitchell/issues/list<br />
* '''Manual:''' https://github.com/ndmitchell/hoogle/blob/master/README.md<br />
<br />
Below is the old manual, which is gradually being phased out.<br />
<br />
<br />
== Hoogle Use ==<br />
<br />
Hoogle can be used in several ways:<br />
<br />
* Online, with the web interface: http://haskell.org/hoogle<br />
* In the [[IRC channel|Haskell IRC channel]], using the [[Lambdabot]] plugin, <tt>@hoogle</tt> and <tt>@hoogle+</tt><br />
* With the command line version [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hoogle available on Hackage].<br />
<br />
This section describes Hoogle searches, and the flags available from the Hoogle command line tool. The information applies only to Hoogle 4, the next version of Hoogle, and is still being fleshed out.<br />
<br />
=== Searches ===<br />
<br />
Before explaining the syntax of searches, we first give a list of example searches with their meaning:<br />
<br />
* "map" Search for the text "map"<br />
* "con map" Search for the text "map" and the text "con"<br />
* "a -> a" Search for the type "a -> a"<br />
* ":: a -> a" Search for the type "a -> a"<br />
* "a" Search for the text "a"<br />
* ":: a" Search for the type "a"<br />
* "id :: a -> a" Search for the text "id" and the type "a -> a"<br />
<br />
Searches can be either textual (a list of words), or by type (a type signature) or both. A type search may optionally start with a "::" symbol. A search is considered a text search unless it contains a combination of text and symbols, or if it starts with (::). To search for both a type and a name, place a :: between them, for example "undefined :: a"<br />
<br />
Searches can be restricted to a particular module with +Module.Name, or to avoid a module with -Module.Name. The command Module.Name.Foo is treated as +Module.Name Foo.<br />
<br />
Searches can be restricted to a particular package with +packagename, or to avoid a package with -package. By default Hoogle will search a standard set of packages.<br />
<br />
==== Command Line Search Flags ====<br />
<br />
Flags can be specified as <tt>--flag</tt> or <tt>/flag</tt>. Flags requiring arguments are specified as <tt>--flag=arg</tt> or <tt>/flag=arg</tt>. Anything which is not a flag is counted as a search query. Because a console will treat <tt>-></tt> as a redirection, you can do <tt>-#</tt> to get the right character.<br />
<br />
* <tt>--version</tt> Print out version information<br />
* <tt>--help</tt> Show help on the command line flags<br />
* <tt>--include=dir</tt> Specify which directories are searched for necessary files, defaults to "." and the data directory configured with Cabal.<br />
* <tt>--color</tt> Show color output, requires an ANSI compliant terminal, defaults to false<br />
* <tt>--count=int</tt> Maximum number of results to print, defaults to showing all results<br />
* <tt>--start=int</tt> 1-based index of first result to print, defaults to 1<br />
* <tt>--info</tt> Show extended information for the first results<br />
<br />
=== Database Creation ===<br />
<br />
Hoogle has both binary databases (extension .hoo) and textual databases (extension .txt). Textual database files are a list of functions and their types, along with information about type synonyms, instances etc. The textual database files can be generated by [http://haskell.org/haddock/ Haddock] with the <tt>--hoogle</tt> flag. Support for this is now in [http://haskell.org/cabal/ Cabal] with <tt>runhaskell Setup haddock --hoogle</tt>.<br />
<br />
A more detailed tutorial style style post on database creation is available [http://neilmitchell.blogspot.com/2008/08/hoogle-database-generation.html on the author's blog].<br />
<br />
You can create some default databases with (Windows users, please read [http://stackoverflow.com/questions/7523151/hoogle-data-on-windows Hoogle data on Windows] first):<br />
<br />
$ hoogle data<br />
<br />
==== Converting text databases to binary databases ====<br />
<br />
A text database can be converted to a binary database with the command <tt>hoogle --convert=file.txt</tt>. Any package dependencies should be specified with <tt>+package</tt> or <tt>--data=package.hoo</tt>, and will require the binary databases for those packages. The output file can be controlled with <tt>--output=file.hoo</tt>.<br />
<br />
==== Merging binary databases ====<br />
<br />
Multiple binary databases can be merged with <tt>hoogle --combine=file1.hoo --combine=file2.hoo</tt>. As before, <tt>--output=default.hoo</tt> can be specified.<br />
<br />
The following script (from Matt Brown) may be helpful:<br />
<br />
$cat hoogleCombiner.sh <br />
#!/bin/bash<br />
<br />
function combines {<br />
for f in ~/.hoogle/*.hoo<br />
do<br />
echo -n " --combine=$(readlink -f $f)"<br />
done<br />
}<br />
<br />
hoogle --output=$(readlink -f ~/.hoogle.hoo) $(combines)<br />
<br />
Simon Michaels suggests: <br />
<br />
#!/bin/bash<br />
#<br />
# Search for hoogle databases in or under the directories/files specified<br />
# as arguments or hard-coded below (see allHoogleDbs), and combine them as<br />
# ~/.hoogle/default.hoo. Lets you search all your code (and installed<br />
# haskell libs) at once.<br />
#<br />
# Usage:<br />
# $ hoogle-update-db<br />
# $ alias hoogle="hoogle --i=$HOME/.hoogle"<br />
# $ hoogle something<br />
<br />
# nb current hoogle cli quirks: path options should have two hyphens, one<br />
# equals, and no tildes, eg: --d=NOTILDEFILEPATH<br />
<br />
#set -x<br />
<br />
ARGS=$*<br />
<br />
function allHoogleDbs {<br />
for p in $ARGS ~/src/ ~/.cabal/share/ # add paths here<br />
do<br />
echo -n " $(findHoogleDbs $p)"<br />
done<br />
}<br />
<br />
function findHoogleDbs {<br />
find $1 -name '*.hoo'<br />
}<br />
<br />
function combineOpts {<br />
for f in $*<br />
do<br />
echo -n " --combine=$(readlink -f $f)"<br />
done<br />
}<br />
<br />
dbs=$(allHoogleDbs)<br />
echo Found $dbs<br />
mkdir -p ~/.hoogle<br />
hoogle --output=$(readlink -f ~/.hoogle/default.hoo) $(combineOpts $dbs)<br />
echo Created ~/.hoogle/default.hoo<br />
<br />
==== Scope of Web Searches ====<br />
<br />
Using the standard web interface, Hoogle searches: array, arrows, base, bytestring, Cabal, cgi, containers, directory, filepath, haskell-src, HUnit, mtl, old-locale, old-time, packedstring, parallel, parsec, pretty, process, QuickCheck, random, stm, template-haskell, time, xhtml.<br />
<br />
Using the [http://haskell.org/hoogle/?hoogle=gtk+%2bpackage Gtk2hs Hoogle], Hoogle searches only in the Gtk2hs package.<br />
<br />
=== Developer Flags ===<br />
<br />
,f (ArgNone Web) ["w","web"] [PCmdLine] "Run as though it was a CGI script"<br />
,f (ArgNone Test) ["test"] [PCmdLine] "Run the regression tests"<br />
,f (ArgStr Dump) ["dump"] [PCmdLine] "Dump a database for debugging"<br />
,f (ArgFileIn DataFile ["hoo"]) ["d","data"] [PCmdLine,PMultiple] "Database file"<br />
,f (ArgNone Verbose) ["v","verbose"] [PCmdLine] "Display verbose information"<br />
,f (ArgNone Debug) ["debug"] [PCmdLine] "Debugging only"<br />
,f (ArgFileIn TestFile ["txt"]) ["testfile"] [PCmdLine,PMultiple] "Run tests from a file"<br />
,f (ArgFileIn Rank ["txt"]) ["rank"] [PCmdLine,PMultiple] "Generate ranking scores"<br />
<br />
== Hoogle Integration Modes ==<br />
<br />
Hoogle can be integrated with various programs, listed below. Most of these integration modes were contributed by users, and users are encouraged to add more programs to this list.<br />
<br />
=== Firefox Integration ===<br />
<br />
'''From the search bar:''' Go to the [http://haskell.org/hoogle/ Hoogle website] in Firefox and click on "Search plugin", top right hand corner (some versions of firefox instead will have an "add Hoogle" option in the list of search engines when you are viewing the Hoogle page). This will add a Hoogle entry to the search box in Firefox.<br />
<br />
'''As a keyword search:''' You can set up Hoogle as a keyword search in Firefox. This means that you can type <tt>h map</tt> directly into the location bar and you'll jump directly to the Hoogle search results page.<br />
<br />
# Visit Hoogle's web interface: http://haskell.org/hoogle<br />
# Right-click on the text input box and click "Add a Keyword for this Search..."<br />
# Give it a nice short keyword like "h".<br />
<br />
If you want to also search for special symbols in Firefox keyword search, modify the keyword search URL to be: <tt>javascript:window.location.href="http://haskell.org/hoogle?q=" + encodeURIComponent("%s")</tt><br />
<br />
=== Chrome Integration ===<br />
<br />
'''Add to list of available search engines:''' Exactly as for the search bar in Firefox above.<br />
<br />
'''As a keyword search:''' Under Chrome Preferences (Basic),<br />
select Manage Search Engines. You can then edit the keyword box appropriately.<br />
<br />
To get the new Hoogle engine into the "default" section from the "other" section, make it default, and then re-select what was the original default.<br />
<br />
(Works with Chrome on Mac OS X, at least).<br />
<br />
=== GHCi Integration ===<br />
<br />
Ever feel like having access to hoogle whilst messing around in GHCi? It's relatively easy to integrate the two. <br />
<br />
The following will install hoogle as a shell command, and configure GHCi to have commands ":hoogle" showing all matches, and ":doc" showing haddock documentation for the first match:<br />
<br />
# <tt>cabal install hoogle</tt><br />
# <tt>echo >> ~/.ghci ':def hoogle \x -> return $ ":!hoogle \"" ++ x ++ "\""'</tt><br />
# <tt>echo >> ~/.ghci ':def doc \x -> return $ ":!hoogle --info \"" ++ x ++ "\""'</tt><br />
<br />
NB. the above wraps the argument in quotes before passing to the shell command, so there is no need to supply quotes; eg.<br />
<br />
:hoogle map<br />
:hoogle (a -> b) -> [a] -> [b]<br />
<br />
Done!<br />
<br />
On Windows you should add the same lines<br />
:def hoogle \x -> return $ ":!hoogle \"" ++ x ++ "\""<br />
:def doc \x -> return $ ":!hoogle --info \"" ++ x ++ "\""<br />
to file (XP/2003):<br />
C:\Documents and Settings\[your windows account]\Application Data\ghc\ghci.conf <br />
or(Windows Vista/7):<br />
C:\users\[your windows account]\Application Data\ghc\ghci.conf <br />
<br />
<br />
==== Installation from source (without cabal) ====<br />
<br />
First, you need to download and compile Hoogle. Then, we want to move hoogle to somewhere in your system's <code>$PATH</code> (open a terminal and type <code>echo $PATH</code> to see where this is). I suggest ~/bin, although you might want to go for /usr/bin or /usr/local/bin, etc.<br />
<br />
Copy the Hoogle binary and hoogle.txt to the directory you chose. If you're using a version of hoogle pulled straight from darcs, you can ignore everything up until the 'Next, we need to integrate it into GHCi' bit. Otherwise:<br />
<br />
There's a problem in that hoogle doesn't look for hoogle.txt in the system <code>$PATH</code>, it only looks in the current directory. This is a slight pain but is easily worked around: rename the hoogle binary to hoogle-bin, then create a new text file called 'hoogle' with the following contents:<br />
<br />
#! /bin/bash<br />
hoogle-bin -l /path/to/your/chosen/directory/hoogle.txt "$@"<br />
<br />
chmod hoogle to make it executable (try <code>chmod +x hoogle</code>). Now you should be able to run hoogle requests from the shell. Try a few of the examples above.<br />
<br />
==== How it works ====<br />
<br />
Next, we need to integrate it into GHCi. We can execute shell commands with GHCi via <code>:def</code>. Load up GHCi, and type the following:<br />
<br />
:def hoogle \x -> return $ ":!hoogle " ++ x<br />
<br />
If this executes cleanly, you should be able to run hoogle commands from GHCi via <code>:hoogle</code>, i.e. <code>:hoogle map</code> or <code>:hoogle "(a -> b) -> [a] -> [b]"</code>. Be careful: you need the extra quotes when hoogling types, at least on my system. <code>:ho</code> works as an abbreviation of <code>:hoogle</code> (just <code>:h</code> clashes with <code>:help</code>).<br />
<br />
Finally, we want to make this persist across GHCi sessions. GHCi loads a file called ~/.ghci before running, so simply stick the above <code>:def</code> in that file and all should work.<br />
<br />
Contributed by [[User:DavidHouse|DavidHouse]]<br />
<br />
=== Emacs Integration ===<br />
[[Haskell_mode_for_Emacs|haskell-mode]] from versions 2.4 onwards have the function haskell-hoogle, which will hoogle the identifier at point. Setup:<br />
<br />
(require 'haskell-mode)<br />
(define-key haskell-mode-map "\C-ch" 'haskell-hoogle)<br />
;(setq haskell-hoogle-command "hoogle")<br />
<br />
You will need a web browser configured for best results. Here's an example setup for Safari:<br />
<br />
(setq browse-url-browser-function 'browse-url-safari)<br />
(defun browse-url-safari (url &optional new-window)<br />
"Open URL in a new Safari window."<br />
(interactive (browse-url-interactive-arg "URL: "))<br />
(unless<br />
(string= ""<br />
(shell-command-to-string<br />
(concat "open -a Safari " url)))<br />
(message "Starting Safari...")<br />
(start-process (concat "open -a Safari " url) nil "open -a Safari " url)<br />
(message "Starting Safari... done")))<br />
<br />
Alternately, you can build the command-line hoogle (darcs repo below) and uncomment the third line above, then results will appear in a buffer.<br />
<br />
=== Firefox Ubiquity Integration ===<br />
<br />
[https://wiki.mozilla.org/Labs/Ubiquity Ubiquity] provides a graphical command-line for Firefox. To install Ubiquity, see the [https://wiki.mozilla.org/Labs/Ubiquity/Ubiquity_0.1_User_Tutorial tutorial].<br />
<br />
To install the Ubiquity Hoogle command, visit the [http://www.randomhacks.net/git/ubiquity/hoogle/ command's home page] and click <b>Subscribe...</b> when asked whether you want to install it. You may also want to look at the [http://www.randomhacks.net/articles/2008/09/01/ubiquitous-hoogle introductory article].<br />
<br />
== Developers ==<br />
<br />
This work is licensed under the [http://www.gnu.org/copyleft/gpl.html GPL version 2.0]. By submitting any patches to Hoogle you agree to license them under the BSD license, or to assign copyright to Neil Mitchell who will include them under the GPL (either one, your choice). This is so I can relicense Hoogle under the BSD at a later date if that proves beneficial to the Haskell community.<br />
<br />
The work is intended to be helpful, open and free. If the license doesn't meet your needs then talk to me.<br />
<br />
=== The Source Code ===<br />
<br />
<tt>$ darcs get http://code.haskell.org/hoogle/</tt><br />
<br />
Contributions are most welcome. Hoogle is written in Haskell 98 + Heirarchical Modules, I do not wish to change this. Other than that, I'm pretty flexible about most aspects of Hoogle. The [http://code.google.com/p/ndmitchell/issues/list bug tracker] has many outstanding tasks, but please contact me if you have thoughts on doing something major to Hoogle, so I can give some advice.<br />
<br />
== Theoretical Foundations ==<br />
<br />
A lot of related work was done by Rittri [1] and Runciman [2] in the late 80's. Since then Di Cosmo [3] has produced a book on type isomorphisms, which is also related. Unfortunately the implementations that accompanied the earlier works were for functional languages that have since become less popular, and to my knowledge no existing functional programming language has a tool such as Hoogle.<br />
<br />
# Mikael Rittri, Using Types as Search Keys in Function Libraries. Proceedings of the fourth international conference on Functional programming languages and computer architecture: 174-183, June 1989. (http://portal.acm.org/citation.cfm?id=99384)<br />
# Colin Runciman and Ian Toyn, Retrieving reusable software components by polymorphic type. Journal of Functional Programming 1 (2): 191-211, April 1991. (http://portal.acm.org/citation.cfm?id=99383)<br />
# Roberto Di Cosmo. Isomorphisms of types: from lambda-calculus to information retrieval and language design. Birkhauser, 1995. ISBN-0-8176-3763-X (http://www.pps.jussieu.fr/~dicosmo/Publications/ISObook.html)<br />
<br />
I have given two presentations on type searching in Hoogle:<br />
<br />
* [http://www-users.cs.york.ac.uk/~ndm/downloads/slides-hoogle-08_dec_2005.pdf December 2005, York University] - information on Hoogle type searching in versions 1 to 3.<br />
* [http://www.wellquite.org/anglohaskell2008/ August 2008, AngloHaskell] - information on type searching in versions 1 to 4. Audio is also available from that link.<br />
<br />
=== Similar Tools ===<br />
<br />
I didn't know of any similar tools before starting development, and no other tool has really influenced this tool (except the first on this list). The follow are provided for comparison.<br />
<br />
* [http://www.google.com/ Google] - Google rock!<br />
* [http://holumbus.fh-wedel.de/hayoo/hayoo.html Hayoo] - Similar to Hoogle, but with less focus on type search<br />
* [http://www.krugle.com/ Krugle] - Search code, no Haskell :(<br />
<br />
== Acknowledgements ==<br />
<br />
The code is all &copy; [http://community.haskell.org/~ndm/ Neil Mitchell] 2004-2010. The initial version was done in my own time, and further refinement and reimplementation was done as part of my PhD. During Summer 2008 I was funded to full-time on Hoogle by [http://code.google.com/soc/ Google Summer of Code] with the [http://haskell.org/ haskell.org] mentoring organisation. Since then I have been working on Hoogle in my spare time. Various people have given lots of useful ideas, including my supervisor [http://www.cs.york.ac.uk/~colin/ Colin Runciman], and various members of the [http://www.cs.york.ac.uk/plasma/ Plasma group]. In addition the following people have also contributed some code or significant debugging work:<br />
<br />
* [http://www.cs.kent.ac.uk/people/rpg/tatd2/ Thomas "Bob" Davie]<br />
* [http://www.cse.unsw.edu.au/~dons/ Don Stewart]<br />
* Thomas Jäger<br />
* [http://gaal.livejournal.com/ Gaal Yahas]<br />
* [http://www-users.cs.york.ac.uk/~miked/ Mike Dodds]<br />
* [http://www.cs.chalmers.se/~d00nibro/ Niklas Broberg]<br />
* Esa Ilari Vuokko<br />
* Udo Stenzel<br />
* [http://members.chello.nl/hjgtuyl/ Henk-Jan van Tuyl]<br />
* Gwern Branwen<br />
* Tillmann Rendel<br />
* David Waern<br />
* Ganesh Sittampalam<br />
* Duncan Coutts<br />
* Peter Collingbourne<br />
* Andrea Vezzosi<br />
* Ian Lynagh<br />
<br />
In previous versions, all the data was taken from [http://www.zvon.org/other/haskell/Outputglobal/ Zvon's Haskell Guide]. Thanks to their open and friendly policy of allowing the data to be reused, this project became possible. More recent versions use the Hierarchical Libraries as distributed with GHC, and databases generated by Haddock.<br />
<br />
[[Category:Tools]]</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2011-11-18T00:58:51Z<p>ConradParker: Update type family link to web archive version (hpaste copy is gone)</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.<br />
<br />
----<br />
<br />
Patryk Zadarnowski offered the following during an email discussion:<br />
<br />
''> Are overlapping and undecidable instances different things?''<br />
<br />
Yep, quite different. Both try to add general programming to the type<br />
level.<br />
Overlapping instances do that by allowing things like:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (a, b) where ...<br />
</haskell><br />
and devising rules fo choosing (1) over (2) whenever possible. Right<br />
now,<br />
this is very, very clunky, under-specified and likely to go away once<br />
Manuel<br />
finishes his [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] implementation. :) For example,<br />
what is<br />
GHC supposed to do with:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (Int, b) where ...<br />
</haskell><br />
Undecidable instances basically means that general recursion is allowed<br />
at the type level. So the above will be accepted (I think) and, more<br />
likely<br />
than not, result in GHC's typechecker spinning into an infinite loop<br />
when<br />
it tries to resolve all these instance declarations. Hence the name; if<br />
the instance declarations are allowed to express any patterns, they<br />
provide<br />
a Turing complete language, and if they provide a Turing complete<br />
language,<br />
than it's impossible to decide whether any given type-level program will<br />
terminate (i.e. is OK) or not. If you're using<br />
<tt>-fallow-undecidable-instances</tt><br />
than yes, your haskell type system is Turing-complete :)<br />
<br />
BTW, the way GHC solves this is by declaring a fixed-depth stack for<br />
"evaluation" of instance declarations. It's something small like 5-deep<br />
by default. If it gets exceeded, GHC will bail out with an error<br />
message.<br />
You can increase the stack depth using some other <tt>-f</tt> on the command<br />
line :)<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 10 September 2007 (UTC)<br />
<br />
On that note, [[User:Mnislaih | Pepe Iborra]] pasted a version of [http://web.archive.org/web/20081022030352/http://hpaste.org/2689 Instant Insanity with type families].<br />
<br />
[[User:ConradParker|ConradParker]] 06:53, 12 September 2007 (UTC)<br />
<br />
There was a further discussion about termination of type-checking, and about associated types in the thread<br />
[http://www.haskell.org/pipermail/haskell-cafe/2007-September/thread.html#31757 Monad.Reader 8: Haskell, the new C++] on the haskell-cafe mailing list.<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 25 September 2007 (UTC)<br />
<br />
Alex Rubinsteyn posted [http://www.rubinsteyn.com/template_insanity.html Almost Solving Instant Insanity with C++ templates].<br />
This was followed up (in the [http://programming.reddit.com/info/609y7/comments/ proggit discussion]) by a<br />
[http://paste.dprogramming.com/dps43zro D version].<br />
<br />
[[User:ConradParker|ConradParker]] 08:21, 12 November 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/AndroidAndroid2011-11-04T04:10:30Z<p>ConradParker: /* Related */ add link to GHC on ARM</p>
<hr />
<div>= Discussions =<br />
<br />
* StackOverflow: [http://stackoverflow.com/questions/5151858/running-a-haskell-program-on-the-android-os Running a Haskell program on the Android OS]<br />
* Reddit: [http://www.reddit.com/r/haskell/comments/ful84/haskell_on_android/ Haskell on Android]<br />
* Google+ [https://plus.google.com/101555949501667191720/posts/JaFk1HS5oR7 So who else is interested in getting Haskell running on Android?]<br />
<br />
= Related =<br />
<br />
* [https://ghcarm.wordpress.com/ GHC on ARM]<br />
<br />
[[Category:OS]]</div>ConradParkerhttps://wiki.haskell.org/AndroidAndroid2011-09-26T00:31:05Z<p>ConradParker: initial version: add links to existing discussions</p>
<hr />
<div>= Discussions =<br />
<br />
* StackOverflow: [http://stackoverflow.com/questions/5151858/running-a-haskell-program-on-the-android-os Running a Haskell program on the Android OS]<br />
* Reddit: [http://www.reddit.com/r/haskell/comments/ful84/haskell_on_android/ Haskell on Android]<br />
* Google+ [https://plus.google.com/101555949501667191720/posts/JaFk1HS5oR7 So who else is interested in getting Haskell running on Android?]<br />
<br />
[[Category:OS]]</div>ConradParkerhttps://wiki.haskell.org/LinuxLinux2011-09-25T03:13:58Z<p>ConradParker: Add redirect from Linux to GNU/Linux</p>
<hr />
<div>#REDIRECT [[GNU/Linux]]</div>ConradParkerhttps://wiki.haskell.org/Mailing_listsMailing lists2011-09-16T04:56:16Z<p>ConradParker: add a link to lists hosted at projects.haskell.org</p>
<hr />
<div>There are three mailing lists to discuss issues related to Haskell in<br />
general, and several additional mailing lists for more detailed<br />
discussion topics, including one for each particular implementation of<br />
Haskell.<br />
<br />
* [http://haskell.org/mailman/listinfo/haskell Subscribe to haskell@haskell.org] (announces only, low traffic)<br />
* [http://haskell.org/mailman/listinfo/haskell-cafe Subscribe to haskell-cafe@haskell.org] (very busy, daily community discussion)<br />
* [http://haskell.org/mailman/listinfo/beginners Subscribe to beginners@haskell.org] (busy, daily community discussion)<br />
* [http://haskell.org/mailman/listinfo A comprehensive list of all mailing lists hosted at haskell.org]<br />
* [http://projects.haskell.org/cgi-bin/mailman/listinfo/ Lists hosted at projects.haskell.org]<br />
<br />
==Mailing lists in detail==<br />
<br />
;[mailto:haskell@haskell.org haskell@haskell.org] ([[#Archives|archives]])<br />
:Announcements only. <br> [mailto:haskell@haskell.org haskell@haskell.org] is intended to be a low-bandwidth list, to which it is safe to subscribe without risking being buried in email. If a thread becomes longer than a handful of messages, please transfer to [mailto:haskell-cafe@haskell.org haskell-cafe@haskell.org].<br />
;[mailto:haskell-cafe@haskell.org haskell-cafe@haskell.org] ([[#Archives|archives]])<br />
:General Haskell questions; extended discussions.<br> In Simon Peyton Jones' words: "forum in which it's acceptable to ask anything, no matter how naive, and get polite replies."<br />
;[mailto:beginners@haskell.org beginners@haskell.org] ([[#Archives|archives]])<br />
:Beginner-level, i.e., elementary, Haskell questions and discussions.<br> In the words of Benjamin L. Russell (the one who first suggested creating the mailing list and the current administrator): "Here, there is no such thing as a 'stupid question.'"<br />
<br />
===Mailing list tone===<br />
<br />
In practice, 'haskell' tends to be devoted mainly to announcements, 'haskell-cafe' tends to be devoted mainly to freeform discussion, and 'haskell-beginners' tends to be devoted mainly to beginner-level Haskell language discussions.<br />
<br />
The division of the general list into announcements and the cafe was introduced for people who want to stay in touch with what's happening in the Haskell world, but who don't want to be swamped with mail. '''If you are new to Haskell, then you have a choice: either haskell-cafe, or haskell-beginners.'''<br />
<br />
The readership of the three mailing lists also varies. Whereas both 'haskell' and 'haskell-cafe' tend to be frequented by either language designers or researchers, 'haskell-beginners' tends to be frequented by beginner-level students and educators. 'Haskell-beginners' was created to address the needs of readers of 'haskell-cafe' who felt that the discussion there was either too academic, or too mathematical.<br />
<br />
When posting on 'haskell-cafe', remember:<br />
<br />
* Respect others. This is a civil discussion forum. Remember, the person on the other side of the keyboard is a person too, and is probably well-intentioned.<br />
<br />
* Try to keep discussions on-topic. Threads that have lost any relevance to the Haskell language should be moved elsewhere, including tangential or joking posts (though humor in the context of on-topic discussion is welcome.)<br />
<br />
* Think before sending. Avoid content-free posts, such as a message consisting merely of the phrase "+1." The etiquette for academic mailing list discussions is different from the etiquette for other Internet fora or for ordinary conversation. Remember that your posting will be sent to thousands of people, some of whom are very busy. Ask yourself whether your contribution adds anything of value to any of them.<br />
<br />
* Bottom post and trim irrelevant parts of earlier replies. It's more natural to read the context of the original message and then a response instead of backwards. But if you quote too much of the original message, people will likely give up before getting to the new comment you added several pages down.<br />
<br />
In the case of 'haskell-beginners', please keep in mind the following pointers when posting:<br />
<br />
* Since many readers of this mailing list are beginner-level students of Haskell, try to keep the discussion at a level that allows students of all backgrounds to participate in the discussion. I.e., when explaining difficult concepts, be careful not to assume an advanced background of the reader. For example, don't start a discussion on monads by saying: "A monad is a category theory-based data structure used to supplement pure computations with features like state, common environment or I/O." Instead, say: "A monad is a tool used in Haskell when we want to allow a program to do anything other than just return a value."<br />
<br />
* Again, since many readers of this mailing list are beginner-level students of Haskell, do not assume that readers have an advanced mathematics background, or that they know everything that may seem elementary to a computer science student. For example, if a student here asks whether the screen resolution is important in determining the precision of an algorithm to compute prime numbers by picking points randomly from a square, do not accuse the student of "polluting" the newsgroup by asking a question that "has nothing to do with Haskell." Understand that the student may not have enough mathematical or programming background to realize that screen resolution may be independent of the precision of the actual algorithm used to compute the prime numbers, which may then be represented on the screen independently of the precision of the algorithm itself. If beginner-level students are required to worry about offending somebody with a question that is too elementary every time they need an answer, they will stay beginners.<br />
<br />
===Subscription information===<br />
<br />
Haskell mailing lists are managed by [http://www.gnu.org/software/mailman/mailman.html mailman] -<br />
each list has a web interface. To subscribe, unsubscribe, or view the<br />
archives of a list visit the home page of the list, such as the [http://haskell.org/mailman/listinfo/haskell Haskell mailing list home page], the [http://haskell.org/mailman/listinfo/haskell-cafe Haskell Cafe mailing list home page], or the [http://haskell.org/mailman/listinfo/beginners Haskell-Beginners mailing list home page]. <br />
<br />
===Archiving===<br />
<br />
mail-archive.com provides an archive of all messages sent to the haskell list since March 1997. This includes messages from before the list was converted to mailman. You may search these archives: [http://www.mail-archive.com/haskell@haskell.org/ haskell archive], [http://www.mail-archive.com/haskell-cafe@haskell.org/ haskell-cafe archive], and [http://www.mail-archive.com/beginners@haskell.org/ haskell-beginners archive].<br />
<br />
MarkMail has a [http://haskell.markmail.org/ searchable archive] of all Haskell lists going back to around 2000.<br />
<br />
Also, the archives of the Haskell mailing list from September 1990 until 2006, before and after the list was converted to mailman, are [http://www.cse.unsw.edu.au/~dons/haskell-1990-2006/threads.html hosted here] (and as a [http://www.cse.unsw.edu.au/~dons/haskell-1990-2006.tar.bz2 tar file]).<br />
Related to this is the archives of [http://groups.google.com/group/comp.lang.functional/about?hl=en comp.lang.functional] going back to 1990.<br />
<br />
You may also [http://www.google.com/coop/cse?cx=015832023690232952875%3Acunmubfghzq search the mailing list] using the Google Coop Haskell Search Engine.<br />
<br />
====Archives====<br />
<br />
The following archives exist:<br />
<br />
haskell<br />
<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.general gmane] ([http://dir.gmane.org/gmane.comp.lang.haskell.general info]) 2006/12-present<br />
* [http://www.haskell.org/pipermail/haskell/ mailman] 2000/10-present<br />
* [http://www.mail-archive.com/haskell@haskell.org/ mail-archive] 1997/03-present<br />
* [http://www.cse.unsw.edu.au/~dons/haskell-1990-2006/threads.html dons archive] ([http://www.cse.unsw.edu.au/~dons/haskell-1990-2006.tar.bz2 tar]) 1990/09-2006/08<br />
<br />
haskell-cafe<br />
<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.cafe gmane] ([http://dir.gmane.org/gmane.comp.lang.haskell.cafe info]) 2002/04-present<br />
* [http://www.haskell.org/pipermail/haskell-cafe/ mailman] 2000/10-present<br />
* [http://www.mail-archive.com/haskell-cafe@haskell.org/ mail-archive] 1997/03-present<br />
<br />
haskell-beginners<br />
<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.beginners gmane] ([http://dir.gmane.org/gmane.comp.lang.haskell.beginners info]) 2008/07-present<br />
* [http://www.haskell.org/pipermail/beginners/ mailman] 2008/07-present<br />
* [http://www.mail-archive.com/beginners@haskell.org/ mail-archive] 2008/07-present<br />
<br />
Any problems with haskell or haskell-cafe should be reported to [mailto:haskell-admin@haskell.org haskell-admin@haskell.org], and any problems with haskell-beginners should be reported to [mailto:DekuDekuplex@Yahoo.com DekuDekuplex@Yahoo.com].<br />
<br />
==More specific lists==<br />
<br />
* [http://haskell.org/mailman/listinfo A comprehensive list of all Mailing lists hosted at haskell.org]<br />
* [http://gmane.org/find.php?list=haskell Haskell lists at gmane]<br />
<br />
There are mailing lists for each implementation of Haskell,<br />
and for more detailed discussion topics. Questions, comments, and bug<br />
reports regarding a specific implementation should be sent directly<br />
to the appropriate list instead of the entire Haskell community.<br />
Separate topics such as documentation tools, the common FFI, and<br />
libraries, also have lists of their own.<br />
<br />
==Outside haskell.org==<br />
<br />
There are also Haskell related mailing lists that are not hosted at haskell.org.<br />
<br />
* [[Haskell art]]<br />
* [https://lists.sourceforge.net/lists/listinfo/gtk2hs-users Gtk2hs users mailing list]<br />
<br />
[[Category:Community]]</div>ConradParkerhttps://wiki.haskell.org/HakkuTaikaiHakkuTaikai2011-08-25T23:44:47Z<p>ConradParker: /* Registration */ add note about security</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
'''Venue security requires a list of attendees' names.'''<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>ConradParkerhttps://wiki.haskell.org/HakkuTaikai/ProjectsHakkuTaikai/Projects2011-08-25T23:41:45Z<p>ConradParker: /* Sharing your code */ switch git and darcs (we all use git anyway...)</p>
<hr />
<div>== Sharing your code ==<br />
<br />
If you need a place to host a project so that others can help with it, we suggest<br />
[http://github.com github], which offers free hosting for public git repositories. If you're using darcs, [http://patch-tag.com/ patch-tag] is just dandy as well. You can also apply for an account on [http://community.haskell.org/admin/ the community server].<br />
<br />
== Projects ==<br />
<br />
If you have a project that you want to work on at the Hackathon, please describe it here.<br />
<br />
Since Hackathons are great for teamwork, consider joining one of the projects mentioned below. If you're interested in one of these projects, add your name to the list of hackers under that project.<br />
<br />
=== containers ===<br />
<br />
Johan Tibell has [http://blog.johantibell.com/2011/05/new-release-of-unordered-containers.html recently been doing some work] on [http://hackage.haskell.org/package/unordered-containers unordered-containers], with an eventual goal of unifying the current {Int,Hash,}Map interfaces. Would be nice to have some form of unboxed containers in there too.<br />
<br />
* Liyang<br />
<br />
=== time ===<br />
<br />
The current implementation of time uses lots of Integers internally which makes it much slower than necessary. Thinking about moving to an Int64-based representation while still being able to represent any conceivable dates & times.<br />
<br />
* Liyang<br />
<br />
=== unordered-containers ===<br />
<br />
I anticipate to make a new release of the package just before ICFP, with a completely rewritten implementation. I'd like to spend some time after the release to flesh out the API a bit more.<br />
<br />
* Johan Tibell<br />
<br />
<!-- Copy this template<br />
=== Project name ===<br />
<br />
I am a project. Love me.<br />
<br />
* Hacker 1<br />
* Hacker 2<br />
--></div>ConradParkerhttps://wiki.haskell.org/HakkuTaikai/AttendeesHakkuTaikai/Attendees2011-08-25T23:38:39Z<p>ConradParker: /* HakkuTaikai Attendees */ add note about security</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
The venue is not open to the public on the day of the Hackathon, so we must submit a list of names to security. If you're name is not on the list, you may not be admitted.<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
|-<br />
| kfish<br />
| [[User:ConradParker|Conrad Parker]]<br />
| Tsuru Capital SG Pte Ltd<br />
| +81 80 4162 1307<br />
|-<br />
| erikde/m3ga<br />
| [[User:Erik de Castro Lopo|Erik de Castro Lopo]]<br />
| bCODE Pty Ltd<br />
| +61 400 912 480<br />
|-<br />
| kazu<br />
| Kazu Yamamoto<br />
| IIJ<br />
| not public<br />
|-<br />
| tibbe<br />
| Johan Tibell<br />
| Google<br />
| not public<br />
|}</div>ConradParkerhttps://wiki.haskell.org/HakkuTaikaiHakkuTaikai2011-08-19T02:50:39Z<p>ConradParker: /* What to bring */ add japan plug info</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please help improve this page or direct queries to liyang on FreeNode IRC in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2011-08-17T04:16:33Z<p>ConradParker: s/Kyoto Uni/Tsuru Capital</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I work on trading strategies in Haskell at Tsuru Capital in Singapore.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* <strike>[[User:ConradParker/SoC2008 | Summer of Code 2008]]</strike><br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/HakkuTaikai/AttendeesHakkuTaikai/Attendees2011-08-17T04:15:16Z<p>ConradParker: /* HakkuTaikai Attendees */ add link to my user page, keitai</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
(The information we need hasn't been finalised yet, but please fill in your details for now anyway, to give us an indication of numbers.)<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
!Accommodation?<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
| lives in Tokyo<br />
|-<br />
| kfish<br />
| [[User:ConradParker|Conrad Parker]]<br />
| Tsuru Capital SG Pte Ltd<br />
| +81 80 4162 1307<br />
| no<br />
|}</div>ConradParkerhttps://wiki.haskell.org/Haskell_programming_tipsHaskell programming tips2011-05-16T02:44:01Z<p>ConradParker: /* Forget about quot and rem */ Formatting</p>
<hr />
<div>==Preface==<br />
<br />
This page shows several examples of how code can be improved. We try to derive general rules from them, though they cannot be applied deterministically and are a matter of taste. We all know this, please don't add "this is disputable" to each item!<br />
<br />
Instead, you can now add "this is disputable" on [[/Discussion]] and change this page only when some sort of consensus is reached.<br />
<br />
==Be concise==<br />
<br />
===Don't reinvent the wheel===<br />
<br />
The standard libraries are full of useful, well-tuned functions. If you rewrite an existing library function, the reader of your code might spend a minute trying to figure out why you've done that. But if you use a standard function, the reader is likely to either immediately understand what you've done, or can learn something new.<br />
<br />
===Avoid explicit recursion===<br />
<br />
Explicit recursion is not generally bad, but you should spend some time trying to find a more declarative implementation using higher order functions.<br />
<br />
Don't define<br />
<haskell><br />
raise :: Num a => a -> [a] -> [a]<br />
raise _ [] = []<br />
raise x (y:ys) = x+y : raise x ys<br />
</haskell><br />
because it is hard for the reader to find out<br />
how much of the list is processed and<br />
on which values the elements of the output list depend.<br />
Just write<br />
<haskell><br />
raise x ys = map (x+) ys<br />
</haskell><br />
or even<br />
<haskell><br />
raise x = map (x+)<br />
</haskell><br />
and the reader knows that the complete list is processed and that each output element depends only on the corresponding input element.<br />
<br />
If you don't find appropriate functions in the standard library, extract a general function.<br />
This helps you and others understand the program.<br />
Thanks to [[higher order function]]s Haskell gives you '''very''' much opportunities to factor out parts of the code.<br />
If you find the function very general, put it in a separate module and re-use it. It may appear in the standard libraries later, or you may later find that it is already there in an even more general way.<br />
<br />
Decomposing a problem this way also has the advantage that you can debug more easily. If the last implementation of <hask>raise</hask> does not show the expected behaviour, you can inspect <hask>map</hask> (I hope it is correct :-) ) and the invoked instance of <hask>(+)</hask> separately.<br />
<br />
<br />
''This is a special case of the general principle of [[separation of concerns|separating concerns]]. If you can write the loop over a data structure once and debug it, then there's no need to duplicate that code.''<br />
<br />
<br />
Another example:<br />
The function <hask>count</hask> counts the number of elements<br />
which fulfill a certain property,<br />
i.e. the elements for which the predicate <hask>p</hask> is <hask>True</hask>.<br />
<br />
I found the following code (but convoluted in a more specific function) in a Haskell program<br />
<haskell><br />
count :: (a -> Bool) -> [a] -> Int<br />
count _ [] = 0<br />
count p (x:xs)<br />
| p x = 1 + count p xs<br />
| otherwise = count p xs<br />
</haskell><br />
which you won't like after you become aware of<br />
<haskell><br />
count p = length . filter p<br />
</haskell><br />
.<br />
<br />
===Only introduce identifiers you need===<br />
<br />
Here is some advice that is useful for every language, including scientific prose<br />
(http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD993.html):<br />
Introduce only identifiers you use.<br />
The compiler will check this for you if you pass an option like <code>-Wall</code> to GHC.<br />
<br />
In an expression like<br />
<haskell><br />
[a | i <- [1..m]]<br />
</haskell><br />
where <hask>a</hask> might be a horrible complex expression it is not easy to see,<br />
that <hask>a</hask> really does not depend on <hask>i</hask>.<br />
<haskell><br />
replicate m a<br />
</haskell><br />
is certainly better here.<br />
<br />
<br />
===Remember the zero===<br />
<br />
Don't forget that zero is a natural number. Recursive definitions become more complicated if the recursion anchor is not chosen properly. For example the function <hask>tupel</hask> presented in ''DMV-Mitteilungen 2004/12-3, Jürgen Bokowski: Haskell, ein gutes Werkzeug der Diskreten Mathematik'' (Haskell, a good tool for discrete mathematics). This is also a good example of how to avoid guards.<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples r l<br />
| r == 1 = [[el] | el <- l]<br />
| length l == r = [l]<br />
| otherwise = (map ([head l] ++) (tuples (r-1) (tail l)))<br />
++ tuples r (tail l)<br />
</haskell><br />
Do you have an idea what it does?<br />
<br />
Let's strip the guards and forget about list comprehension.<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples 1 l = map (:[]) l<br />
tuples r l =<br />
if r == length l<br />
then [l]<br />
else<br />
let t = tail l<br />
in map (head l :) (tuples (r-1) t)<br />
++ tuples r t<br />
</haskell><br />
<br />
What about tuples with zero elements? We can add the pattern<br />
<haskell><br />
tuples 0 _ = [[]]<br />
</haskell><br />
but then we can also omit the pattern for 1-tuples.<br />
<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples 0 _ = [[]]<br />
tuples r l =<br />
if r == length l<br />
then [l]<br />
else<br />
let t = tail l<br />
in map (head l :) (tuples (r-1) t)<br />
++ tuples r t<br />
</haskell><br />
What about the case <hask>r > length l</hask>? Sure, no reason to let <hask>head</hask> fail - in that case there is no tuple, thus we return an empty list. Again, this saves us one special case.<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples 0 _ = [[]]<br />
tuples r l =<br />
if r > length l<br />
then []<br />
else<br />
let t = tail l<br />
in map (head l :) (tuples (r-1) t)<br />
++ tuples r t<br />
</haskell><br />
<br />
We have learnt above that <hask>length</hask> is evil! What about<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples 0 _ = [[]]<br />
tuples _ [] = []<br />
tuples r (x:xs) =<br />
map (x :) (tuples (r-1) xs)<br />
++ tuples r xs<br />
</haskell><br />
? It is no longer necessary to compute the length of <hask>l</hask> again and again. The code is easier to read and it covers all special cases, including <hask>tuples (-1) [1,2,3]</hask>!<br />
<br />
''Eliminating the <hask>length</hask> test can worsen performance dramatically in some cases, like <hask>tuples 24 [1..25]</hask>. We could also use <hask>null (drop (r-1) l)</hask> instead of <hask>length l < r</hask>, which works for infinite lists. See also [[#Don't ask for the length of a list, if you don't need it|below]].''<br />
<br />
You can even save one direction of recursion<br />
by explicit computation of the list of all suffixes provided by <hask>tails</hask>.<br />
You can do this with do notation<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples 0 _ = [[]]<br />
tuples r xs = do<br />
y:ys <- tails xs<br />
map (y:) (tuples (r-1) ys)<br />
</haskell><br />
<br />
Since <hask>(=<<)</hask> in the list monad is <hask>concatMap</hask>, we can also write this as follows.<br />
Where in the previous version the pattern <hask>y:ys</hask> filtered out the last empty suffix<br />
we have to do this manually now with <hask>init</hask>.<br />
<haskell><br />
tuples :: Int -> [a] -> [[a]]<br />
tuples 0 _ = [[]]<br />
tuples r xs =<br />
concatMap (\(y:ys) -> map (y:) (tuples (r-1) ys))<br />
(init (tails xs))<br />
</haskell><br />
The list of all suffixes could be generated with <hask>iterate tail</hask><br />
but this ends with a "Prelude.tail: empty list".<br />
<hask>tails</hask> generates the suffixes in the same order but aborts properly.<br />
<br />
<br />
''More generally, [[Base cases and identities]]''<br />
<br />
===Don't overuse lambdas===<br />
<br />
Like explicit recursion, using explicit lambdas isn't a universally bad idea, but a better solution often exists.<br />
For example, Haskell is quite good at currying. Don't write<br />
<haskell><br />
zipWith (\x y -> f x y)<br />
<br />
map (\x -> x + 42)<br />
</haskell><br />
<br />
instead, write<br />
<haskell><br />
zipWith f<br />
<br />
map (+42)<br />
</haskell><br />
<br />
also, instead of writing<br />
<haskell><br />
-- sort a list of strings case insensitively<br />
sortBy (\x y -> compare (map toLower x) (map toLower y))<br />
</haskell><br />
<br />
write<br />
<haskell><br />
comparing p x y = compare (p x) (p y)<br />
<br />
sortBy (comparing (map toLower))<br />
</haskell><br />
which is both clearer and re-usable.<br />
Actually, starting with GHC-6.6 you do not need to define <hask>comparing</hask>, since it is already in module <hask>Data.Ord</hask>.<br />
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Ord.html<br />
<br />
(Just a remark for this special example:<br />
We can avoid multiple evaluations of the conversions<br />
with a function that is present in GHC.Exts of GHC 6.10:<br />
<haskell><br />
sortWith :: (Ord b) => (a -> b) -> [a] -> [a]<br />
sortWith f x = map snd (sortBy (comparing fst) (zip (map f x) x))<br />
</haskell><br />
)<br />
<br />
As a rule of thumb, once your expression becomes too long to easily be point-freed, it probably deserves a name anyway.<br />
Lambdas are occasionally appropriate however, e.g. for control structures in monadic code (in this example, a control-structure "foreach2" which most languages don't even support.):<br />
<haskell><br />
foreach2 xs ys f = zipWithM_ f xs ys<br />
<br />
linify :: [String] -> IO ()<br />
linify lines<br />
= foreach2 [1..] lines $ \lineNr line -> do<br />
unless (null line) $<br />
putStrLn $ shows lineNr $ showString ": " $ show line<br />
</haskell><br />
<br />
<br />
===<hask>Bool</hask> is a regular type===<br />
<br />
Logic expressions are not restricted to guards and <hask>if</hask> statements.<br />
Avoid verbosity like in<br />
<haskell><br />
isEven n<br />
| mod n 2 == 0 = True<br />
| otherwise = False<br />
</haskell><br />
since it is the same as<br />
<haskell><br />
isEven n = mod n 2 == 0<br />
</haskell><br />
.<br />
<br />
The definitions<br />
<haskell><br />
hasSpace (a:as)<br />
| isSpace a = True<br />
| otherwise = hasSpace as<br />
</haskell><br />
and<br />
<haskell><br />
hasSpace (a:as) = if isSpace a then True else hasSpace as<br />
</haskell><br />
can be shortened to<br />
<haskell><br />
hasSpace (a:as) = isSpace a || hasSpace as<br />
</haskell><br />
(I just wanted to show the logic transform.<br />
In the particular example you would write <hask>any isSpace</hask>, of course.)<br />
The same way<br />
<haskell><br />
allPrintable (a:as)<br />
| isSpace a = False<br />
| otherwise = allPrintable as<br />
</haskell><br />
and<br />
<haskell><br />
allPrintable (a:as) = if isSpace a then False else allPrintable as<br />
</haskell><br />
can be shortened to<br />
<haskell><br />
allPrintable (a:as) = not (isSpace a) && allPrintable as<br />
</haskell><br />
(but <hask>all (not . isSpace)</hask> is even better in this particular example.)<br />
<br />
<br />
<br />
==Use syntactic sugar wisely==<br />
<br />
People who employ [[syntactic sugar]] extensively<br />
argue that it makes their code more readable.<br />
The following sections show several examples<br />
where less syntactic sugar is more readable.<br />
<br />
It is argued that a special notation is often<br />
more intuitive than a purely functional expression.<br />
But the term "intuitive notation" is always a matter of habit.<br />
You can also develop an intuition for analytic expressions<br />
that don't match your habits at the first glance.<br />
So why not making a habit of less sugar sometimes?<br />
<br />
<br />
===List comprehension===<br />
<br />
List comprehension lets you remain in imperative thinking, that is it lets you think in variables rather than transformations. Open your mind, discover the flavour of the [[pointfree]] style!<br />
<br />
Instead of<br />
<haskell><br />
[toUpper c | c <- s]<br />
</haskell><br />
write<br />
<haskell><br />
map toUpper s<br />
</haskell><br />
.<br />
<br />
<br />
Consider<br />
<haskell><br />
[toUpper c | s <- strings, c <- s]<br />
</haskell><br />
where it takes some time for the reader<br />
to discover which value depends on what other value<br />
and it is not so clear how many times<br />
the interim values <hask>s</hask> and <hask>c</hask> are used.<br />
In contrast to that<br />
<haskell><br />
map toUpper (concat strings)<br />
</haskell><br />
can't be clearer.<br />
<br />
<br />
<br />
When using higher order functions you can switch more easily from <hask>List</hask> to other data structures.<br />
<br />
Compare<br />
<haskell><br />
map (1+) list<br />
</haskell><br />
and<br />
<haskell><br />
mapSet (1+) set<br />
</haskell><br />
.<br />
If there were a standard instance for the <hask>Functor</hask> class<br />
you could use the code<br />
<haskell><br />
fmap (1+) pool<br />
</haskell><br />
for both choices.<br />
<br />
If you are not used to higher order functions for list processing<br />
you may feel you need parallel list comprehension.<br />
This is unfortunately supported by GHC now,<br />
but it is arguably superfluous since various flavours of <hask>zip</hask> already do a great job.<br />
<br />
<br />
<br />
<br />
===<hask>do</hask> notation===<br />
<br />
[[Do notation considered harmful|do notation]] is useful to express the imperative nature (e.g. a hidden state or an order of execution) of a piece of code.<br />
Nevertheless it's sometimes useful to remember that the <hask>do</hask> notation is explained in terms of functions.<br />
<br />
Instead of<br />
<haskell><br />
do<br />
text <- readFile "foo"<br />
writeFile "bar" text<br />
</haskell><br />
one can write<br />
<haskell><br />
readFile "foo" >>= writeFile "bar"<br />
</haskell><br />
.<br />
<br />
<br />
The code<br />
<haskell><br />
do<br />
text <- readFile "foo"<br />
return text<br />
</haskell><br />
can be simplified to<br />
<haskell><br />
readFile "foo"<br />
</haskell><br />
by a law that each Monad must fulfill.<br />
<br />
<br />
You certainly also agree that<br />
<haskell><br />
do<br />
text <- readFile "foobar"<br />
return (lines text)<br />
</haskell><br />
is more complicated than<br />
<haskell><br />
liftM lines (readFile "foobar")<br />
</haskell><br />
.<br />
By the way, the <hask>Functor</hask> class method <hask>fmap</hask> and the <hask>Monad</hask> based function <hask>liftM</hask> are the same (as long as both are defined, as they should be).<br />
<br />
''Be aware that "more complicated" does not imply "worse". If your do-expression was longer than this, then mixing do-notation and <hask>fmap</hask> might be precisely the wrong thing to do, because it adds one more thing to think about. Be natural. Only change it if you gain something by changing it. -- AndrewBromage''<br />
<br />
===Guards===<br />
<br />
''Disclaimer: This section is NOT advising you to avoid guards. It is advising you to prefer pattern matching to guards when both are appropriate. -- AndrewBromage''<br />
<br />
Guards look like<br />
<haskell><br />
-- Bad implementation:<br />
fac :: Integer -> Integer<br />
fac n | n == 0 = 1<br />
| n /= 0 = n * fac (n-1)<br />
</haskell><br />
which implements a factorial function. This example, like a lot of uses of guards, has a number of problems.<br />
<br />
The first problem is that it's nearly impossible for the compiler to check whether guards like this are exhaustive, as the guard conditions may be arbitrarily complex (GHC will warn you if you use the <code>-Wall</code> option). To avoid this problem and potential bugs through non exhaustive patterns you should use an <hask>otherwise</hask> guard, that will match for all remaining cases:<br />
<br />
<haskell><br />
-- Slightly improved implementation:<br />
fac :: Integer -> Integer<br />
fac n | n == 0 = 1<br />
| otherwise = n * fac (n-1)<br />
</haskell><br />
<br />
Another reason to prefer this one is its greater readability for humans and optimizability for compilers. Though it may not matter much in a simple case like this, when seeing an <hask>otherwise</hask> it's immediately clear that it's used whenever the previous guard fails, which isn't true if the "negation of the previous test" is spelled out. The same applies to the compiler: It probably will be able to optimize an <hask>otherwise</hask> (which is a synonym for <hask>True</hask>) away but cannot do that for most expressions.<br />
<br />
This can be done with even less sugar using <hask>if</hask>,<br />
<haskell><br />
-- Less sugar (though the verbosity of if-then-else can also be considered as sugar :-)<br />
fac :: Integer -> Integer<br />
fac n = if n == 0<br />
then 1<br />
else n * fac (n-1)<br />
</haskell><br />
Note that <hask>if</hask> has its own set of [[If-then-else|problems]], for example in connection with the layout rule or that nested <hask>if</hask>s are difficult to read. See [[Case]] how to avoid nested <hask>if</hask>s.<br />
<br />
But in this special case, the same can be done even more easily with pattern matching:<br />
<haskell><br />
-- Good implementation:<br />
fac :: Integer -> Integer<br />
fac 0 = 1<br />
fac n = n * fac (n-1)<br />
</haskell><br />
<br />
Actually, in this case there is an even more easier to read version, which (see above) doesn't use Explicit Recursion:<br />
<haskell><br />
-- Excellent implementation:<br />
fac :: Integer -> Integer<br />
fac n = product [1..n]<br />
</haskell><br />
This may also be more efficient as <hask>product</hask> might be optimized by the library-writer... In GHC, when compiling with optimizations turned on, this version runs in O(1) stack-space, whereas the previous versions run in O(n) stack-space.<br />
<br />
Note however, that there is a difference between this version and the previous ones: When given a negative number, the previous versions do not terminate (until StackOverflow-time), while the last implementation returns 1.<br />
<br />
<br />
Guards don't always make code clearer.<br />
Compare<br />
<haskell><br />
foo xs | not (null xs) = bar (head xs)<br />
</haskell><br />
and<br />
<haskell><br />
foo (x:_) = bar x<br />
</haskell><br />
<br />
or compare the following example using the advanced [[pattern guard]]s<br />
<haskell><br />
parseCmd ln<br />
| Left err <- parse cmd "Commands" ln<br />
= BadCmd $ unwords $ lines $ show err<br />
| Right x <- parse cmd "Commands" ln<br />
= x<br />
</haskell><br />
with this one with [[no pattern guard]]s:<br />
<haskell><br />
parseCmd ln = case parse cmd "Commands" ln of<br />
Left err -> BadCmd $ unwords $ lines $ show err<br />
Right x -> x<br />
</haskell><br />
or, if you expect your readers to be familiar with the <hask>either</hask> function:<br />
<haskell><br />
parseCmd :: -- add an explicit type signature, as this is now a pattern binding<br />
parseCmd = either (BadCmd . unwords . lines . show) id . parse cmd "Commands"<br />
</haskell><br />
<br />
<br />
Incidentally, compilers often also have problems with numerical patterns. For example, the pattern <hask>0</hask> in fact means <hask>fromInteger 0</hask>; thus it involves a computation, which is uncommon for function parameter patterns. To illustrate this, consider the following example:<br />
<haskell><br />
data Foo = Foo deriving (Eq, Show)<br />
<br />
instance Num Foo where<br />
fromInteger = error "forget it"<br />
<br />
f :: Foo -> Bool<br />
f 42 = True<br />
f _ = False<br />
</haskell><br />
<br />
<haskell><br />
*Main> f 42<br />
*** Exception: forget it<br />
</haskell><br />
<br />
Only use guards when you need to. In general, you should stick to pattern matching whenever possible.<br />
<br />
===<hask>n+k</hask> patterns===<br />
In order to allow pattern matching against numerical types, Haskell 98 provides so-called n+k patterns, as in<br />
<haskell><br />
take :: Int -> [a] -> [a]<br />
take (n+1) (x:xs) = x: take n xs<br />
take _ _ = []<br />
</haskell><br />
However, they are often criticized for hiding computational complexity and producing ambiguities, see [[/Discussion]] for details. They are subsumed by the more general [[Views]] proposal, which has unfortunately never been implemented despite being around for quite some time now.<br />
<br />
<br />
==Efficiency and infinity==<br />
<br />
A rule of thumb is:<br />
If a function makes sense for an infinite data structure but the implementation at hand fails for an infinite amount of data, then the implementation is probably also inefficient for finite data.<br />
<br />
===Don't ask for the length of a list when you don't need it===<br />
<br />
Don't write<br />
<haskell><br />
length x == 0<br />
</haskell><br />
to find out if the list <hask>x</hask> is empty.<br />
If you write it, you force Haskell to create all list nodes. It fails on an infinite list although the expression should be evaluated to <hask>False</hask> in this case. (Nevertheless the content of the list elements may not be evaluated.)<br />
<br />
In contrast<br />
<haskell><br />
x == []<br />
</haskell><br />
is faster but it requires the list <hask>x</hask> to be of type <hask>[a]</hask> where <hask>a</hask> is a type of class <hask>Eq</hask>.<br />
<br />
The best thing to do is<br />
<haskell><br />
null x<br />
</haskell><br />
<br />
Additionally, many uses of the length function are overspecifying the problem: one may only need to check that a list is ''at least'' a certain length, and not a specific length. Thus use of <haskell>length</haskell> could be replaced with an <hask>atLeast</hask> function that only checks to see that a list is greater than the required minimum length.<br />
<haskell><br />
atLeast :: Int -> [a] -> Bool<br />
atLeast 0 _ = True<br />
atLeast _ [] = False<br />
atLeast n (_:ys) = atLeast (n-1) ys<br />
</haskell><br />
or non-recursive, but less efficient because both <hask>length</hask> and <hask>take</hask> must count<br />
<haskell><br />
atLeast :: Int -> [a] -> Bool<br />
atLeast n x = n == length (take n x)<br />
</haskell><br />
or non-recursive but fairly efficient<br />
<haskell><br />
atLeast :: Int -> [a] -> Bool<br />
atLeast n =<br />
if n>0<br />
then not . null . drop (n-1)<br />
else const True<br />
</haskell><br />
or<br />
<haskell><br />
atLeast :: Int -> [a] -> Bool<br />
atLeast 0 = const True<br />
atLeast n = not . null . drop (n-1)<br />
</haskell><br />
<br />
The same problem arises if you want to shorten a list to the length of another one by<br />
<haskell><br />
take (length x) y<br />
</haskell><br />
since this is inefficient for large lists <hask>x</hask> and fails for infinite ones. But this can be useful to extract a finite prefix from an infinite list.<br />
So, instead<br />
<haskell><br />
zipWith const y x<br />
</haskell><br />
works well.<br />
<br />
It should be noted that <hask>length</hask>, <hask>take</hask><br />
can be replaced by <hask>genericLength</hask>, <hask>genericTake</hask> et.al.,<br />
which allow the usage of [[Peano numbers]].<br />
<br />
===Don't ask for the minimum when you don't need it===<br />
<br />
The function <hask>isLowerLimit</hask> checks if a number is a lower limit to a sequence.<br />
<haskell><br />
isLowerLimit :: Ord a => a -> [a] -> Bool<br />
isLowerLimit x ys = x <= minimum ys<br />
</haskell><br />
It certainly fails if <hask>ys</hask> is infinite. Is this a problem? <br />
<br />
Compare it with<br />
<haskell><br />
isLowerLimit x = all (x<=)<br />
</haskell><br />
This definition terminates for infinite lists, if <hask>x</hask> is not a lower limit. It aborts immediately if an element is found which is below <hask>x</hask>. Thus it is also faster for finite lists. Even more: It also works for empty lists.<br />
<br />
<br />
===Use sharing===<br />
<br />
If you want a list of lists with increasing length and constant content, don't write<br />
<haskell><br />
map (flip replicate x) [0..]<br />
</haskell><br />
because this needs quadratic space and run-time. If you code<br />
<haskell><br />
iterate (x:) []<br />
</haskell><br />
then the lists will share their suffixes and thus need only linear space and run-time for creation.<br />
<br />
<br />
===Choose the appropriate fold===<br />
<br />
See "[[Stack overflow]]" or "[[Foldr Foldl Foldl']]" for advice on which fold is appropriate for your situation.<br />
<br />
<br />
==Choose types properly==<br />
<br />
===Lists are not good for everything===<br />
<br />
====Lists are not arrays====<br />
<br />
Lists are not arrays, so don't treat them as such.<br />
Frequent use of <hask>(!!)</hask> should alarm you.<br />
Accessing the <hask>n</hask>th list element<br />
involves traversing through the first <hask>n</hask> nodes of the list.<br />
This is very inefficient.<br />
<br />
If you access the elements progressively, as in<br />
<haskell><br />
[x !! i - i | i <- [0..n]]<br />
</haskell><br />
you should try to get rid of indexing, as in<br />
<haskell><br />
zipWith (-) x [0..n]<br />
</haskell><br />
.<br />
<br />
If you really need random access, as in the Fourier Transform,<br />
you should switch to [[Arrays]].<br />
<br />
<br />
====Lists are not sets====<br />
<br />
If you manage data sets where each object can occur only once<br />
and the order is irrelevant,<br />
if you use list functions like<br />
<hask>sort</hask>, <hask>nub</hask>, <hask>union</hask>, <hask>elem</hask>, <hask>delete</hask>, <hask>(\\)</hask><br />
frequently,<br />
you should think about switching to sets.<br />
If you need multi-sets,<br />
i.e. data sets with irrelevant order but multiple occurrences of objects,<br />
you can use a <hask>Data.Map.Map a Int</hask>.<br />
<br />
<br />
====Lists are not finite maps====<br />
<br />
Similarly, lists are not finite maps, as mentioned in [[efficiency hints]].<br />
<br />
<br />
===Reduce type class constraints===<br />
<br />
====Eq type class====<br />
<br />
When using functions like <hask>delete</hask>, <hask>(\\)</hask>, <hask>nub</hask>, and so on you should be aware that they need types of the <hask>Eq</hask> class. There are two problems: The routines might not work as expected if a processed list contains multiple equal elements and the element type of the list may not be comparable, like functions.<br />
<br />
Example:<br />
The following function takes the input list <hask>xs</hask> and removes each element of <hask>xs</hask> once from <hask>xs</hask>.<br />
Clear what it does? No? The code is probably more understandable<br />
<haskell><br />
removeEach :: (Eq a) => [a] -> [[a]]<br />
removeEach xs = map (flip List.delete xs) xs<br />
</haskell><br />
but it should be replaced by<br />
<haskell><br />
removeEach :: [a] -> [[a]]<br />
removeEach xs =<br />
zipWith (++) (List.inits xs) (tail (List.tails xs))<br />
</haskell><br />
since this works perfectly for function types <hask>a</hask> and for equal elements in <hask>xs</hask>.<br />
<br />
<br />
===Don't use <hask>Int</hask> when you don't consider integers===<br />
<br />
Before using integers for each and everything (C style)<br />
think of more specialised types.<br />
If only the values <hask>0</hask> and <hask>1</hask> are of interest,<br />
try the type <hask>Bool</hask> instead.<br />
If there are more but predefined choices and numeric operations aren't needed try an enumeration.<br />
<br />
Instead of<br />
<haskell><br />
type Weekday = Int<br />
</haskell><br />
write<br />
<haskell><br />
data Weekday = Monday<br />
| Tuesday<br />
| Wednesday<br />
| Thursday<br />
| Friday<br />
| Saturday<br />
| Sunday<br />
deriving (Eq, Ord, Enum)<br />
</haskell><br />
<br />
It allows all sensible operations like <hask>==</hask>, <hask> < </hask>, <hask>succ</hask> and<br />
forbids all nonsensical ones like <hask>+</hask>, <hask>*</hask>.<br />
You cannot accidentally mix up weekdays with numbers and<br />
the signature of a function with weekday parameter clearly states what kind of data is expected.<br />
<br />
If an enumeration is not appropriate<br />
you can define a <hask>newtype</hask> carrying the type that is closest to what you need.<br />
E.g. if you want to associate objects with a unique identifier,<br />
you may want to choose the type <hask>Int</hask>.<br />
But you don't need arithmetic and you can make this type distinct from real <hask>Int</hask>s by defining<br />
<haskell><br />
newtype Identifier = Identifier Int deriving Eq<br />
</haskell><br />
<br />
<br />
===Avoid redundancy in data types===<br />
<br />
I often see data types with redundant fields, e.g.<br />
<haskell><br />
data XML =<br />
Element Position Name [Attribute] [XML]<br />
| Comment Position String<br />
| Text Position String<br />
</haskell><br />
<br />
I suggest to factor out the common field <hask>Position</hask><br />
since this lets you handle the text position the same way for all XML parts.<br />
<haskell><br />
data XML = XML Position Part<br />
<br />
data Part =<br />
Element Name [Attribute] [XML]<br />
| Comment String<br />
| Text String<br />
</haskell><br />
<br />
==Miscellaneous==<br />
<br />
===Separate IO and data processing===<br />
<br />
It's not good to use the IO Monad everywhere,<br />
much of the data processing can be done without IO interaction.<br />
You should separate data processing and IO<br />
because pure data processing can be done purely functionally,<br />
that is you don't have to specify an order of execution<br />
and you don't have to worry about what computations are actually necessary.<br />
Useful techniques are described in [[Avoiding IO]].<br />
<br />
===Forget about quot and rem===<br />
<br />
They complicate handling of negative dividends. <hask>div</hask> and <hask>mod</hask> are almost always the better choice. If <hask>b > 0</hask> then it always holds<br />
<haskell><br />
a == b * div a b + mod a b<br />
mod a b < b<br />
mod a b >= 0<br />
</haskell><br />
The first equation is true also for <hask>quot</hask> and <hask>rem</hask>,<br />
but the two others are true only for <hask>mod</hask>, but not for <hask>rem</hask>. That is, <hask>mod a b</hask> always wraps <hask>a</hask> to an element from <hask>[0..(b-1)]</hask>, whereas the sign of <hask>rem a b</hask> depends on the sign of <hask>a</hask>.<br />
<br />
This seems to be more an issue of experience rather than one of a superior reason. You might argue, that the sign of the dividend is more important for you, than that of the divisor. However, I have never seen such an application, but many uses of <hask>quot</hask> and <hask>rem</hask> where <hask>div</hask> and <hask>mod</hask> were clearly superior.<br />
<br />
Examples:<br />
<br />
* Conversion from a continuously counted tone pitch to the pitch class, like C, D, E etc.: <hask>mod p 12</hask><br />
<br />
* Pad a list <hask>xs</hask> to a multiple of <hask>m</hask> number of elements: <hask>xs ++ replicate (mod (- length xs) m) pad</hask><br />
<br />
* Conversion from a day counter to a week day: <hask>mod n 7</hask><br />
<br />
* Pacman runs out of the screen and re-appears at the opposite border: <hask>mod x screenWidth</hask><br />
<br />
See<br />
* Daan Leijen: [http://www.cs.uu.nl/~daan/download/papers/divmodnote-letter.pdf Division and Modulus for Computer Scientists]<br />
* Haskell-Cafe: [http://www.haskell.org/pipermail/haskell-cafe/2007-August/030394.html default for quotRem in terms of divMod?]<br />
<br />
===Partial functions like <hask>fromJust</hask> and <hask>head</hask>===<br />
<br />
Avoid functions that fail for certain input values like <hask>fromJust</hask> and <hask>head</hask>.<br />
They raise errors that can only be detected at runtime.<br />
Think about how they can be avoided by different program organization<br />
or by choosing more specific types.<br />
<br />
Instead of<br />
<haskell><br />
if i == Nothing then deflt else fromJust i<br />
</haskell><br />
write<br />
<haskell><br />
fromMaybe deflt i<br />
</haskell><br />
Please note, that <hask>(==)</hask> also requires an <hask>Eq</hask> class instance for the type of <hask>i</hask>,<br />
which <hask>fromMaybe</hask> does not require because it employs [[pattern matching]].<br />
See also [[#Reduce type class constraints]].<br />
<br />
If it is not possible to avoid <hask>fromJust</hask> this way,<br />
then use <hask>fromMaybe</hask> anyway<br />
and document with an <hask>error</hask> why you think that the value must be always <hask>Just</hask> in your situation.<br />
<haskell><br />
fromMaybe (error "Function bla: The list does always contains the searched value")<br />
(lookup key dict)<br />
</haskell><br />
<br />
The function <hask>head</hask> can be avoided by [[Non-empty list|checking with types]], that it is never empty.<br />
There is also a function which returns an existing first list element in terms of <hask>Maybe</hask>:<br />
<hask>maybeToList</hask><br />
(See [http://www.haskell.org/pipermail/haskell-cafe/2007-March/023391.html remark].)<br />
<br />
== Related Links ==<br />
<br />
=== Common Mistakes and Incorrect Beliefs By Haskell Beginners ===<br />
<br />
* [[Common Misunderstandings]]<br />
<br />
=== Some Common (and not so common!) Hugs Errors ===<br />
<br />
* [http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/errors/allErrors.html Some common Hugs error messages]<br />
<br />
<br />
[[Category:Style]]</div>ConradParkerhttps://wiki.haskell.org/HoogleHoogle2010-09-22T22:09:29Z<p>ConradParker: update ghci integration details</p>
<hr />
<div>Hoogle is a Haskell API search engine, which allows you to search many standard Haskell libraries by either function name, or by approximate type signature.<br />
<br />
* '''Online version:''' http://haskell.org/hoogle<br />
* '''Hackage page:''' http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hoogle<br />
* '''Darcs repository:''' http://code.haskell.org/hoogle<br />
* '''Bug tracker:''' http://code.google.com/p/ndmitchell/issues/list<br />
* '''Manual:''' This page.<br />
<br />
== Hoogle Use ==<br />
<br />
Hoogle can be used in several ways:<br />
<br />
* Online, with the web interface: http://haskell.org/hoogle<br />
* In the [[IRC channel|Haskell IRC channel]], using the [[Lambdabot]] plugin, <tt>@hoogle</tt> and <tt>@hoogle+</tt><br />
* With the command line version [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hoogle available on Hackage].<br />
<br />
This section describes Hoogle searches, and the flags available from the Hoogle command line tool. The information applies only to Hoogle 4, the next version of Hoogle, and is still being fleshed out.<br />
<br />
=== Searches ===<br />
<br />
Before explaining the syntax of searches, we first give a list of example searches with their meaning:<br />
<br />
* "map" Search for the text "map"<br />
* "con map" Search for the text "map" and the text "con"<br />
* "a -> a" Search for the type "a -> a"<br />
* ":: a -> a" Search for the type "a -> a"<br />
* "a" Search for the text "a"<br />
* ":: a" Search for the type "a"<br />
* "id :: a -> a" Search for the text "id" and the type "a -> a"<br />
<br />
Searches can be either textual (a list of words), or by type (a type signature) or both. A type search may optionally start with a "::" symbol. A search is considered a text search unless it contains a combination of text and symbols, or if it starts with (::). To search for both a type and a name, place a :: between them, for example "undefined :: a"<br />
<br />
Searches can be restricted to a particular module with +Module.Name, or to avoid a module with -Module.Name. The command Module.Name.Foo is treated as +Module.Name Foo.<br />
<br />
Searches can be restricted to a particular package with +packagename, or to avoid a package with -package. By default Hoogle will search a standard set of packages.<br />
<br />
==== Command Line Search Flags ====<br />
<br />
Flags can be specified as <tt>--flag</tt> or <tt>/flag</tt>. Flags requiring arguments are specified as <tt>--flag=arg</tt> or <tt>/flag=arg</tt>. Anything which is not a flag is counted as a search query. Because a console will treat <tt>-></tt> as a redirection, you can do <tt>-#</tt> to get the right character.<br />
<br />
* <tt>--version</tt> Print out version information<br />
* <tt>--help</tt> Show help on the command line flags<br />
* <tt>--include=dir</tt> Specify which directories are searched for necessary files, defaults to "." and the data directory configured with Cabal.<br />
* <tt>--color</tt> Show color output, requires an ANSI compliant terminal, defaults to false<br />
* <tt>--count=int</tt> Maximum number of results to print, defaults to showing all results<br />
* <tt>--start=int</tt> 1-based index of first result to print, defaults to 1<br />
* <tt>--info</tt> Show extended information for the first results<br />
<br />
=== Database Creation ===<br />
<br />
Hoogle has both binary databases (extension .hoo) and textual databases (extension .txt). Textual database files are a list of functions and their types, along with information about type synonyms, instances etc. The textual database files can be generated by [http://haskell.org/haddock/ Haddock] with the <tt>--hoogle</tt> flag. Support for this is now in [http://haskell.org/cabal/ Cabal] with <tt>runhaskell Setup haddock --hoogle</tt>.<br />
<br />
A more detailed tutorial style style post on database creation is available [http://neilmitchell.blogspot.com/2008/08/hoogle-database-generation.html on the author's blog].<br />
<br />
==== Converting text databases to binary databases ====<br />
<br />
A text database can be converted to a binary database with the command <tt>hoogle --convert=file.txt</tt>. Any package dependencies should be specified with <tt>+package</tt> or <tt>--data=package.hoo</tt>, and will require the binary databases for those packages. The output file can be controlled with <tt>--output=file.hoo</tt>.<br />
<br />
==== Merging binary databases ====<br />
<br />
Multiple binary databases can be merged with <tt>hoogle --combine=file1.hoo --combine=file2.hoo</tt>. As before, <tt>--output=default.hoo</tt> can be specified.<br />
<br />
==== Scope of Web Searches ====<br />
<br />
Using the standard web interface, Hoogle searches: array, arrows, base, bytestring, Cabal, cgi, containers, directory, filepath, haskell-src, HUnit, mtl, old-locale, old-time, packedstring, parallel, parsec, pretty, process, QuickCheck, random, stm, template-haskell, time, xhtml.<br />
<br />
Using the [http://haskell.org/hoogle/3/?package=gtk Gtk2hs Hoogle], Hoogle searches only in the Gtk2hs package.<br />
<br />
=== Developer Flags ===<br />
<br />
,f (ArgNone Web) ["w","web"] [PCmdLine] "Run as though it was a CGI script"<br />
,f (ArgNone Test) ["test"] [PCmdLine] "Run the regression tests"<br />
,f (ArgStr Dump) ["dump"] [PCmdLine] "Dump a database for debugging"<br />
,f (ArgFileIn DataFile ["hoo"]) ["d","data"] [PCmdLine,PMultiple] "Database file"<br />
,f (ArgNone Verbose) ["v","verbose"] [PCmdLine] "Display verbose information"<br />
,f (ArgNone Debug) ["debug"] [PCmdLine] "Debugging only"<br />
,f (ArgFileIn TestFile ["txt"]) ["testfile"] [PCmdLine,PMultiple] "Run tests from a file"<br />
,f (ArgFileIn Rank ["txt"]) ["rank"] [PCmdLine,PMultiple] "Generate ranking scores"<br />
<br />
== Hoogle Integration Modes ==<br />
<br />
Hoogle can be integrated with various programs, listed below. Most of these integration modes were contributed by users, and users are encouraged to add more programs to this list.<br />
<br />
=== Firefox Integration ===<br />
<br />
'''From the search bar:''' Go to the [http://haskell.org/hoogle/ Hoogle website] in Firefox and click on "Search plugin", top right hand corner. This will add a Hoogle entry to the search box in Firefox.<br />
<br />
'''As a keyword search:''' You can set up Hoogle as a keyword search in Firefox. This means that you can type <tt>h map</tt> directly into the location bar and you'll jump directly to the Hoogle search results page.<br />
<br />
# Visit Hoogle's web interface: http://haskell.org/hoogle<br />
# Right-click on the text input box and click "Add a Keyword for this Search..."<br />
# Give it a nice short keyword like "h".<br />
<br />
If you want to also search for special symbols in Firefox keyword search, modify the keyword search URL to be: <tt>javascript:window.location.href="http://haskell.org/hoogle?q=" + encodeURIComponent("%s")</tt><br />
<br />
=== GHCi Integration ===<br />
<br />
Ever feel like having access to hoogle whilst messing around in GHCi? It's relatively easy to integrate the two. I'm on Linux, so I don't know how well the following will work if you're on Windows.<br />
<br />
The following will install hoogle as a shell command, and configure GHCi to have a command ":hoogle":<br />
<br />
# <tt>cabal install hoogle</tt><br />
# <tt>echo >> ~/.ghci ':def hoogle \x -> return $ ":!hoogle \"" ++ x ++ "\""'</tt><br />
<br />
NB. the above wraps the argument in quotes before passing to the shell command, so there is no need to supply quotes; eg.<br />
<br />
:hoogle map<br />
:hoogle (a -> b) -> [a] -> [b]<br />
<br />
Done!<br />
<br />
==== Installation from source (without cabal) ====<br />
<br />
First, you need to download and compile Hoogle. Then, we want to move hoogle to somewhere in your system's <code>$PATH</code> (open a terminal and type <code>echo $PATH</code> to see where this is). I suggest ~/bin, although you might want to go for /usr/bin or /usr/local/bin, etc.<br />
<br />
Copy the Hoogle binary and hoogle.txt to the directory you chose. If you're using a version of hoogle pulled straight from darcs, you can ignore everything up until the 'Next, we need to integrate it into GHCi' bit. Otherwise:<br />
<br />
There's a problem in that hoogle doesn't look for hoogle.txt in the system <code>$PATH</code>, it only looks in the current directory. This is a slight pain but is easily worked around: rename the hoogle binary to hoogle-bin, then create a new text file called 'hoogle' with the following contents:<br />
<br />
#! /bin/bash<br />
hoogle-bin -l /path/to/your/chosen/directory/hoogle.txt "$@"<br />
<br />
chmod hoogle to make it executable (try <code>chmod +x hoogle</code>). Now you should be able to run hoogle requests from the shell. Try a few of the examples above.<br />
<br />
==== How it works ====<br />
<br />
Next, we need to integrate it into GHCi. We can execute shell commands with GHCi via <code>:def</code>. Load up GHCi, and type the following:<br />
<br />
:def hoogle \x -> return $ ":!hoogle " ++ x<br />
<br />
If this executes cleanly, you should be able to run hoogle commands from GHCi via <code>:hoogle</code>, i.e. <code>:hoogle map</code> or <code>:hoogle "(a -> b) -> [a] -> [b]"</code>. Be careful: you need the extra quotes when hoogling types, at least on my system. <code>:ho</code> works as an abbreviation of <code>:hoogle</code> (just <code>:h</code> clashes with <code>:help</code>).<br />
<br />
Finally, we want to make this persist across GHCi sessions. GHCi loads a file called ~/.ghci before running, so simply stick the above <code>:def</code> in that file and all should work.<br />
<br />
Contributed by [[User:DavidHouse|DavidHouse]]<br />
<br />
=== Emacs Integration ===<br />
[[Haskell_mode_for_Emacs|haskell-mode]] from versions 2.4 onwards have the function haskell-hoogle, which will hoogle the identifier at point. Setup:<br />
<br />
(require 'haskell-mode)<br />
(define-key haskell-mode-map "\C-ch" 'haskell-hoogle)<br />
;(setq haskell-hoogle-command "hoogle")<br />
<br />
You will need a web browser configured for best results. Here's an example setup for Safari:<br />
<br />
(setq browse-url-browser-function 'browse-url-safari)<br />
(defun browse-url-safari (url &optional new-window)<br />
"Open URL in a new Safari window."<br />
(interactive (browse-url-interactive-arg "URL: "))<br />
(unless<br />
(string= ""<br />
(shell-command-to-string<br />
(concat "open -a Safari " url)))<br />
(message "Starting Safari...")<br />
(start-process (concat "open -a Safari " url) nil "open -a Safari " url)<br />
(message "Starting Safari... done")))<br />
<br />
Alternately, you can build the command-line hoogle (darcs repo below) and uncomment the third line above, then results will appear in a buffer.<br />
<br />
=== Firefox Ubiquity Integration ===<br />
<br />
[https://wiki.mozilla.org/Labs/Ubiquity Ubiquity] provides a graphical command-line for Firefox. To install Ubiquity, see the [https://wiki.mozilla.org/Labs/Ubiquity/Ubiquity_0.1_User_Tutorial tutorial].<br />
<br />
To install the Ubiquity Hoogle command, visit the [http://www.randomhacks.net/git/ubiquity/hoogle/ command's home page] and click <b>Subscribe...</b> when asked whether you want to install it. You may also want to look at the [http://www.randomhacks.net/articles/2008/09/01/ubiquitous-hoogle introductory article].<br />
<br />
== Developers ==<br />
<br />
This work is licensed under the [http://www.gnu.org/copyleft/gpl.html GPL version 2.0]. By submitting any patches to Hoogle you agree to license them under the BSD license, or to assign copyright to Neil Mitchell who will include them under the GPL (either one, your choice). This is so I can relicense Hoogle under the BSD at a later date if that proves beneficial to the Haskell community.<br />
<br />
The work is intended to be helpful, open and free. If the license doesn't meet your needs then talk to me.<br />
<br />
=== The Source Code ===<br />
<br />
<tt>$ darcs get http://code.haskell.org/hoogle/</tt><br />
<br />
Contributions are most welcome. Hoogle is written in Haskell 98 + Heirarchical Modules, I do not wish to change this. Other than that, I'm pretty flexible about most aspects of Hoogle. The [http://code.google.com/p/ndmitchell/issues/list bug tracker] has many outstanding tasks, but please contact me if you have thoughts on doing something major to Hoogle, so I can give some advice.<br />
<br />
== Theoretical Foundations ==<br />
<br />
A lot of related work was done by Rittri [1] and Runciman [2] in the late 80's. Since then Di Cosmo [3] has produced a book on type isomorphisms, which is also related. Unfortunately the implementations that accompanied the earlier works were for functional languages that have since become less popular, and to my knowledge no existing functional programming language has a tool such as Hoogle.<br />
<br />
# Mikael Rittri, Using Types as Search Keys in Function Libraries. Proceedings of the fourth international conference on Functional programming languages and computer architecture: 174-183, June 1989. (http://portal.acm.org/citation.cfm?id=99384)<br />
# Colin Runciman and Ian Toyn, Retrieving reusable software components by polymorphic type. Journal of Functional Programming 1 (2): 191-211, April 1991. (http://portal.acm.org/citation.cfm?id=99383)<br />
# Roberto Di Cosmo. Isomorphisms of types: from lambda-calculus to information retrieval and language design. Birkhauser, 1995. ISBN-0-8176-3763-X (http://www.pps.jussieu.fr/~dicosmo/Publications/ISObook.html)<br />
<br />
I have given two presentations on type searching in Hoogle:<br />
<br />
* [http://www-users.cs.york.ac.uk/~ndm/downloads/slides-hoogle-08_dec_2005.pdf December 2005, York University] - information on Hoogle type searching in versions 1 to 3.<br />
* [http://www.wellquite.org/anglohaskell2008/ August 2008, AngloHaskell] - information on type searching in versions 1 to 4. Audio is also available from that link.<br />
<br />
=== Similar Tools ===<br />
<br />
I didn't know of any similar tools before starting development, and no other tool has really influenced this tool (except the first on this list). The follow are provided for comparison.<br />
<br />
* [http://www.google.com/ Google] - Google rock!<br />
* [http://holumbus.fh-wedel.de/hayoo/hayoo.html Hayoo] - Similar to Hoogle, but with less focus on type search<br />
* [http://www.krugle.com/ Krugle] - Search code, no Haskell :(<br />
<br />
== Acknowledgements ==<br />
<br />
The code is all &copy; [http://www.cs.york.ac.uk/~ndm/ Neil Mitchell] 2004-2008. The initial version was done in my own time, and further refinement and reimplementation was done as part of my PhD. During Summer 2008 I was funded to full-time on Hoogle by [http://code.google.com/soc/ Google Summer of Code] with the [http://haskell.org/ haskell.org] mentoring organisation. Various people have given lots of useful ideas, including my supervisor [http://www.cs.york.ac.uk/~colin/ Colin Runciman], and various members of the [http://www.cs.york.ac.uk/plasma/ Plasma group]. In addition the following people have also contributed some code or significant debugging work:<br />
<br />
* [http://www.cs.kent.ac.uk/people/rpg/tatd2/ Thomas "Bob" Davie]<br />
* [http://www.cse.unsw.edu.au/~dons/ Don Stewart]<br />
* Thomas Jäger<br />
* [http://gaal.livejournal.com/ Gaal Yahas]<br />
* [http://www-users.cs.york.ac.uk/~miked/ Mike Dodds]<br />
* [http://www.cs.chalmers.se/~d00nibro/ Niklas Broberg]<br />
* Esa Ilari Vuokko<br />
* Udo Stenzel<br />
* [http://members.chello.nl/hjgtuyl/ Henk-Jan van Tuyl]<br />
* Gwern Branwen<br />
* Tillmann Rendel<br />
* David Waern<br />
* Ganesh Sittampalam<br />
* Duncan Coutts<br />
* Peter Collingbourne<br />
* Andrea Vezzosi<br />
<br />
In previous versions, all the data was taken from [http://www.zvon.org/other/haskell/Outputglobal/ Zvon's Haskell Guide]. Thanks to their open and friendly policy of allowing the data to be reused, this project became possible. More recent versions use the Hierarchical Libraries as distributed with GHC, and databases generated by Haddock.<br />
<br />
[[Category:Tools]]</div>ConradParkerhttps://wiki.haskell.org/Research_papers/Functional_pearlsResearch papers/Functional pearls2010-09-17T01:28:04Z<p>ConradParker: update John Hughe's functional pearl Globals.ps URL</p>
<hr />
<div>Functional pearls are elegant, instructive examples of functional programming. They are supposed to be fun, and they teach important programming techniques and fundamental design principles. They traditionally appear in [http://journals.cambridge.org/action/displayJournal?jid=JFP The Journal of Functional Programming], and at [http://www.icfpconference.org/index.html ICFP] and affiliated workshops.<br />
<br />
The history of functional pearls is covered by:<br />
<br />
;[http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]<br />
:Richard Bird. ICFP 2006.<br />
<br />
;[http://portal.acm.org/ft_gateway.cfm?id=1159832&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Fifteen years of functional pearls]<br />
:Richard Bird. ICFP 2006.<br />
<br />
;[http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl, forty years on]<br />
:Mike Spivey, 2006.<br />
<br />
;[http://www.brics.dk/RS/07/14/index.html On Barron and Strachey's Cartesian Product Function]<br />
: Olivier Danvy and Michael Spivey, July 2007<br />
<br />
There have been many functional pearls in JFP, and some others at<br />
ICFP and the Haskell Workshop. There is also a collection of them in<br />
[http://web2.comlab.ox.ac.uk/oucl/publications/books/fop/ The Fun of Programming].<br />
<br />
The pearls tend to concentrate on:<br />
<br />
* Examples of program calculation and proof<br />
* Neat presentations of new or old data structures<br />
* Interesting applications and techniques<br />
<br />
Some advice on writing pearls for JFP is available in this [http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/ editorial].<br />
<br />
=== Online ===<br />
<br />
Functional pearls online:<br />
<br />
;[http://research.microsoft.com/en-us/people/dimitris/every-bit-counts.pdf Every Bit Counts]<br />
:Dimitrios Vytiniotis, Andrew Kennedy. 2010.<br />
<br />
;[http://www.iai.uni-bonn.de/~jv/icfp10.pdf Combining Syntactic and Semantic Bidirectionalization]<br />
:Janis Voigtländer, Zhenjiang Hu, Kazutaka Matsuda, Meng Wang. 2010.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/icfp09.pdf Free Theorems Involving Type Constructor Classes]<br />
:Janis Voigtländer. 2009.<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2009/2847/content.pdf Linear, Bounded, Functional Pretty-Printing]<br />
:S. Doaitse Sweirstra, Olaf Chitil. 2009.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl09-2.pdf Bidirectionalization for Free!]<br />
:Janis Voigtländer. 2009.<br />
<br />
;[ftp://ftp.diku.dk/diku/semantics/papers/D-582.pdf Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time]<br />
:Fritz Henglein. 2008<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl202-voigtlaender.pdf Much Ado about Two: A Pearl on Parallel Prefix Computation]<br />
:Janis Voigtländer. 2008.<br />
<br />
;[http://strictlypositive.org/CJ.pdf Clowns to the Left of me, Jokers to the Right: Dissecting Data Structures]: Conor McBride. 2008.<br />
<br />
;[http://www.ccs.neu.edu/home/dherman/research/papers/icfp07-great-escape.pdf Functional Pearl: The Great Escape: Or how to jump the border without getting caught]<br />
:David Herman. 2007.<br />
<br />
;[https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2007.pdf Scrap Your Zippers]<br />
:Michael Adams. 2007. Superseded by the [https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2010.pdf WGP 2010 version].<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.4086 A type-correct, stack-safe, provably correct expression compiler in Epigram]<br />
:James McKinna and Joel Wright. 2006.<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf Applicative Programming with Effects]<br />
:Conor McBride and Ross Paterson. 2006.<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/rationals.pdf Enumerating the rationals]<br />
:Jeremy Gibbons, David Lester and Richard Bird. 2006.<br />
<br />
;[http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf A program to solve Sudoku]<br />
:Richard Bird. 2006. (slides [http://icfp06.cs.uchicago.edu/bird-talk.pdf appear here], a Literate Haskell implementation by Graham Hutton based on this can be found [http://www.cs.nott.ac.uk/~gmh/sudoku.lhs here]).<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell]<br />
:Martin Erwig and Steve Kollmansberger. 2006. <br />
<br />
;[http://cms.brookes.ac.uk/staff/SharonCurtis/publications/marbles.ps.gz Marble mingling]<br />
:Sharon Curtis. 2006.<br />
<br />
;[http://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Strong Types for Relational Databases]<br />
:Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)<br />
<br />
;[http://okmij.org/ftp/papers/LogicT.pdf Backtracking, interleaving, and terminating monad transformers]<br />
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005. <br />
<br />
;[http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate]<br />
:James Cheney. 2005.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]<br />
:Andrew Kennedy. 2004.<br />
<br />
;[http://web.cecs.pdx.edu/~mpj/pubs/composing-fractals.pdf Composing fractals]<br />
:Mark P. Jones. 2004.<br />
<br />
;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages]<br />
:M. Douglas McIlroy. 2004.<br />
<br />
;[http://pauillac.inria.fr/~maranget/enum/pearl.ps Functional satisfaction]<br />
:Luc Maranget. 2004. ([http://pauillac.inria.fr/~maranget/enum/index.html More info]).<br />
<br />
;[http://portal.acm.org/ft_gateway.cfm?id=1017481&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Implicit configurations--or, type classes reflect the values of types]<br />
:Oleg Kiselyov, Chung-chieh Shan. 2004. ([http://www.cs.rutgers.edu/~ccshan/prepose/p1214-kiselyov.pdf also here])<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global variables in Haskell]<br />
:John Hughes. 2004. ([http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=241773 JFP])<br />
<br />
;[http://portal.acm.org/ft_gateway.cfm?id=1017477&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 I am not a number -- I am a free variable]<br />
:Conor McBride, James McKinna. 2004. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform]<br />
:Richard Bird and Shin-Cheng Mu. 2004. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/online/BirdMu2004Inverting.pdf Also here]).<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases]<br />
:Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004.<br />
<br />
;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices]<br />
:Sergio Antoy and Michael Hanus. 2004. <br />
<br />
;[http://www.ling.gu.se/~peb/pubs/Ljunglof-2004b.pdf Functional chart parsing of context-free grammars]<br />
:Peter Ljunglf. 2004.<br />
<br />
;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast]<br />
:Stephanie Weirich. 2004.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]<br />
:Andrew J. Kennedy. 2004.<br />
<br />
;[http://www.cs.chalmers.se/~koen/pubs/jfp04-parser.ps Parallel Parsing Processes]<br />
:Koen Claessen. 2004.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/1.pdf Derivation of a logarithmic time carry lookahead addition circuit]<br />
:John O'Donnell and Gudula Runger. 2004. ([http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=1030343 ACM]) ([http://journals.cambridge.org/action/displayAbstract?aid=254717 JFP]) ([http://www.informatik.uni-bonn.de/~ralf/hw2001/1.html Homepage]). <br />
<br />
;[http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest, functionally]<br />
:Jean-Christophe Fillitre and Franois Pottier. 2003.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf Trouble shared is trouble halved]<br />
:Richard Bird, Ralf Hinze. 2003<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Format.ps.gz Formatting: a class act]<br />
:Ralf Hinze. 2003.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz A fresh look at binary search trees]<br />
:Ralf Hinze. 2002.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/countdown.pdf The countdown problem]<br />
:Graham Hutton. 2002. <br />
<br />
;[http://pdos.csail.mit.edu/papers/packrat-parsing:icfp02.pdf Packrat parsing: simple, powerful, lazy, linear time, functional pearl]<br />
:Bryan Ford. 2002.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing]<br />
:Magnus Carlsson. 2002.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/wgp01/hinze-paper.pdf Haskell does it with class: Functorial unparsing]<br />
:Ralf Hinze. 2001.<br />
<br />
<br />
;[http://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms]<br />
:Richard Bird. 2001.<br />
<br />
;[http://eprints.ouls.ox.ac.uk/archive/00000862/01/bird_2001.pdf Maximum marking problems]<br />
:Richard Bird. 2001. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz Weaving a web]<br />
:Ralf Hinze and Johan Jeuring. 2001. <br />
<br />
;[http://www.brics.dk/RS/01/16/BRICS-RS-01-16.pdf Normalization by evaluation with typed abstract syntax]<br />
:Olivier Danvy, Morten Rhiger and Kristoffer H. Rose. 2001. <br />
<br />
;[http://www.brics.dk/RS/01/10/BRICS-RS-01-10.ps.gz Do we need dependent types?]<br />
:Daniel Fridlender and Mia Indrika. 2001.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-99-4.ps.gz Perfect trees and bit-reversal permutations]<br />
:Ralf Hinze. 2000.<br />
<br />
;[http://spivey.oriel.ox.ac.uk/mike/bfs/bfs.ps Combinators for breadth-first search]<br />
:Michael Spivey. 2000 <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design]<br />
:Chris Okasaki. 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers]<br />
:Ralf Hinze. 2000.<br />
<br />
;[http://www.cis.upenn.edu/~bcpierce/papers/rsr.ps Recursive subtyping revealed]<br />
:Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. 2000.<br />
<br />
;[http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/contracts-icfp.ps.gz Composing contracts: an adventure in financial engineering]<br />
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.<br />
<br />
;[http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps A poor man's concurrency monad]<br />
:Koen Claessen. 1999. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/BinomialHeaps.ps.gz Explaining binomial heaps]<br />
:Ralf Hinze. 1999. <br />
<br />
;[http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series, power serious]<br />
:M. Douglas McIlroy. 1999. <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps Red-black trees in a functional setting]<br />
:Chris Okasaki. 1999. <br />
<br />
;[http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]<br />
:Robert Harper. 1999. (see also [http://ropas.snu.ac.kr/~kwang/paper/06-jfp-yi.pdf Proof-directed debugging: revisited for a first-order version]).<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/radix.ps.gz A pointless derivation of radix sort]<br />
:Jeremy Gibbons. 1999.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell]<br />
:Graham Hutton and Erik Meijer . 1998.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6891 Polytypic unification]<br />
:Patrik Jansson and Johan Jeuring. 1998. <br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf Diets for fat sets]<br />
:Martin Erwig. 1998. <br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1673 Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?]<br />
:Chris Okasaki. 1998.<br />
<br />
;[http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper]<br />
:Gerard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]).<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096 Lazy wheel sieves and spirals of primes]<br />
:Colin Runciman. 1997. <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees]<br />
:Chris Okasaki. 1997. <br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem]<br />
:Jeremy Gibbons. 1996.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/basics.pdf Back to Basics: Deriving Representation Changers Functionally].<br />
:Graham Hutton, Erik Meijer. 1996.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees]<br />
:Andrew J. Kennedy. 1996.<br />
<br />
;[http://research.microsoft.com/~nick/newtrans.pdf Undoing Dynamic Typing]<br />
:Nick Benton. 2008.<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]<br />
:Jeremy Gibbons. 1996. (See also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report]).<br />
<br />
;[http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act]<br />
:Stephen Adams. 1993. ([http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html Data.Set]).<br />
<br />
=== Potential Pearls ===<br />
<br />
Unpublished pearls.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Quote.pdf Typed Quote/AntiQuote]<br />
:Ralf Hinze. Unpublished work in progress.<br />
<br />
;[http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf &alpha;-conversion is easy]<br />
:Thorsten Altenkirch. Unpublished draft.<br />
<br />
=== Offline ===<br />
<br />
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section!<br />
<br />
;[http://www.icfpconference.org/icfp2008/accepted/4.html Functional Pearl: Streams and Unique Fixed Points]<br />
:Ralf Hinze, ICFP 2008<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254707 Linear lambda calculus and PTIME-completeness]<br />
:Harry G. Mairson. 2004. <br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254723 Calculating the Sieve of Eratosthenes]<br />
:Lambert Meertens. Journal of Functional Programming, 14(6):759-763, 2004. ([http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting57/meertens-sieve.pdf slides])<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2001/1293/index.html Red-black trees with types]<br />
:Stefan Kahrs. 2001. ([http://journals.cambridge.org/action/displayAbstract?aid=83905 JFP]) ([http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html Code!])<br />
<br />
;On generating unique names<br />
:Lennart Augustsson, M Rittri, D Synek. 1994. ([http://www.cs.chalmers.se/~rittri/#publications Rittri's homepage])<br />
<br />
;A Symmetric Set of Efficient List Operations.<br />
:Rob R. Hoogerwoord, 1992. ([https://venus.tue.nl/ep-cgi/ep_publ.opl?taal=NL&fac_id=92&rn=19840694 Hoogerwoord's homepage]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming]<br />
:Richard Bird and Sharon Curtis. 2006. ([http://cms.brookes.ac.uk/staff/SharonCurtis/publications/index.html#celebrities See also]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254705 On tiling a chessboard]<br />
:Richard Bird. 2004. ([http://portal.acm.org/citation.cfm?id=1030333.1030336 ACM]) <br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44141 Meertens number]<br />
:Richard Bird. 1998.<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=44091 On merging and selection]<br />
:Richard Bird. 1997. (See also [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/merging.ps.gz More on Merging and Selection]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=44107 On building trees with minimum height]<br />
:Richard Bird. 1997. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird97:OnBuilding Bib]).<br />
<br />
;The Last Tail. <br />
:Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird93:Last Bib]).<br />
<br />
;Two Greedy Algorithms<br />
:Richard Bird, 1992. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#Bird92:Two Bib]).<br />
<br />
;On Removing Duplicates<br />
:Richard Bird. 1991. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#DBLP:journals/jfp/Bird91a Bib]).<br />
<br />
[[Category:Research]] [[Category:Tutorials]]</div>ConradParkerhttps://wiki.haskell.org/Global_variablesGlobal variables2010-09-17T01:25:35Z<p>ConradParker: update John Hughe's functional pearl Globals.ps URL</p>
<hr />
<div>== Question ==<br />
Is there a simple and straightforward way to use global variables in Haskell?<br />
<br />
== Answer ==<br />
<br />
(Perhaps annoyingly) the answer to this question, like so many other<br />
frequently asked questions, is a question. "What are you trying to do?"<br />
<br />
The reason for this is that haskell's abstractions are different from<br />
those of the mainstream imperative languages, and the mapping isn't 1-1.<br />
So for a particular 'C' feature, there may be 3 or 4 haskell features<br />
which achieve similar effects, and the correct choice depends on the<br />
detailed context.<br />
<br />
So, in particular, all those tasks which you use global variables for in<br />
C, can be achieved in haskell, but which solution depends what you are<br />
trying to do:<br />
<br />
# If you have some globals which are constant, then just define them at the top level. No problem.<br />
#: <hask> pi = 3.14 </hask><br />
#: <hask> progname = "MyCoolApp" </hask><br />
# If you have a global environment, which various functions read from (and you might, for example, initialise from a configuration file) then you should thread that as a parameter to your functions (after having, very likely, set it up in your 'main' action). If the explicit parameter passing annoys you, then you can 'hide' it with a [[Monad]].<br />
# If you have a need to store some global state which various of your functions modify, then you have a design issue. This style of design is frowned upon in C as well! The correct solution in C is to pass a 'bundle' of appropriate parameters (you might call it an environment) to those functions which need it. In C++, perl or python you'd very likely make this bundle an object. In haskell this bundle will be a data value in some custom type; and using Monads you can 'hide the details' of passing it around, if you wish.<br />
<br />
== Source ==<br />
<br />
* Jules Bean in [http://www.haskell.org/pipermail/haskell-cafe/2007-May/025526.html Haskell Cafe]<br />
<br />
== Meanwhile, back on Earth ==<br />
* People have been known to use [[Top level mutable state]], otherwise known as the "unsafePerformIO hack".<br />
<br />
* John Hughes has a Functional Pearl which advocates the use of [[implicit parameters]] for global variables. He also mentions the unsafePerformIO hack and the use of a Reader monad transformer, none of which are totally satisfactory: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global Variables in Haskell] (2004)<br />
<br />
<br />
[[Category:FAQ]]</div>ConradParkerhttps://wiki.haskell.org/Dealing_with_binary_dataDealing with binary data2010-07-22T06:29:55Z<p>ConradParker: remove version from binary-strict hackage links</p>
<hr />
<div>[[Category:How to]]<br />
== Handling Binary Data with Haskell ==<br />
<br />
Many programming problems call for the use of binary formats for compactness,<br />
ease-of-use, compatibility or speed. This page quickly covers some common<br />
libraries for handling binary data in Haskell.<br />
<br />
=== Bytestrings ===<br />
<br />
Everything else in this tutorial will be based on bytestrings. Normal Haskell<br />
<hask>String</hask> types are linked lists of 32-bit characters. This has a<br />
number of useful properties like coverage of the Unicode space and laziness,<br />
however when it comes to dealing with bytewise data, <hask>String</hask><br />
involves a space-inflation of about 24x and a large reduction in speed.<br />
<br />
Bytestrings are packed arrays of bytes or 8-bit chars. If you have experience<br />
in C, their memory representation would be the same as a <code>uint8_t[]</code>—although bytestrings know their length and don't allow overflows, etc.<br />
<br />
There are two major flavours of bytestrings: strict and lazy. Strict<br />
bytestrings are exactly what you would expect—a linear array of bytes in<br />
memory. Lazy bytestrings are a list of strict bytestrings; often this is called<br />
a cord in other languages. When reading a lazy bytestring from a file, the data<br />
will be read chunk by chunk and the file can be larger than the size of memory.<br />
The default chunk size is currently 32K.<br />
<br />
Within each flavour of bytestring comes the Word8 and Char8 versions. These are<br />
mostly an aid to the type system since they are fundamentally the same size of<br />
element. The Word8 unpacks as a list of <hask>Word8</hask> elements (bytes),<br />
the Char8 unpacks as a list of <hask>Char</hask>, which may be useful if you<br />
want to convert them to <hask>Strings</hask><br />
<br />
You might want to open the documentation for<br />
[http://haskell.org/ghc/docs/latest/html/libraries/bytestring/Data-ByteString.html strict bytestrings] and<br />
[http://haskell.org/ghc/docs/latest/html/libraries/bytestring/Data-ByteString-Lazy.html lazy bytestrings]<br />
in another tab so that you can follow along.<br />
<br />
==== Simple file IO ====<br />
<br />
Here's a very simple program which copies a file from standard input to<br />
standard output<br />
<br />
<haskell>module Main where<br />
<br />
import qualified Data.ByteString as B<br />
<br />
main :: IO ()<br />
main = do<br />
contents <- B.getContents<br />
B.putStr contents</haskell><br />
<br />
Note that we are using strict bytestrings here. (It's quite common to import the<br />
<code>ByteString</code> module under the names <code>B</code> or <code>BS</code>.)<br />
Since the bytestrings are strict, the code will read the whole of <code>stdin</code> into<br />
memory and then write it out. If the input was too large this would overflow<br />
the available memory and fail.<br />
<br />
Let's see the same program using lazy bytestrings. We are just changing the<br />
imported ByteString module to be the lazy one and calling the exact same<br />
functions from the new module:<br />
<br />
<haskell>module Main where<br />
<br />
import qualified Data.ByteString.Lazy as BL<br />
<br />
main :: IO ()<br />
main = do<br />
contents <- BL.getContents<br />
BL.putStr contents</haskell><br />
<br />
This code, because of the lazy bytestrings, will cope with any sized input and<br />
will start producing output before all the input has been read. You can think<br />
of the code as setting up a pipeline, rather than executing in-order, as you<br />
might expect. As <hask>putStr</hask> needs more data, it will cause the lazy<br />
bytestring <hask>contents</hask> to read more until the end of the input is<br />
found.<br />
<br />
You should review the [http://haskell.org/ghc/docs/latest/html/libraries/bytestring/Data-ByteString.html documentation]<br />
which lists all the functions which operate on ByteStrings. The documentation<br />
for the various types (lazy Word8, strict Char8, ...) are all very similar. You<br />
generally find the same functions in each, with the same names. Remember to<br />
import the modules as <code>qualified</code> and give them different names.<br />
<br />
==== The guts of ByteStrings ====<br />
<br />
I'll just mention in passing that sometimes you need to do something which would<br />
endanger the referential transparency of ByteStrings. Generally you only need<br />
to do this when using the FFI to interface with C libraries. Should such a need<br />
arise, you can have a look at the<br />
[http://haskell.org/ghc/docs/latest/html/libraries/bytestring/Data-ByteString-Internal.html internal functions] and the<br />
[http://haskell.org/ghc/docs/latest/html/libraries/bytestring/Data-ByteString-Unsafe.html unsafe functions].<br />
Remember that the last set of functions are called unsafe for a reason—misuse<br />
can crash your program!<br />
<br />
=== Binary parsing ===<br />
<br />
Once you have your data as a bytestring you'll be wanting to parse something<br />
from it. Here you need to install the<br />
<tt>[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-0.4.1 binary]</tt> package. You should read the instructions on<br />
[http://haskell.org/haskellwiki/Cabal/How_to_install_a_Cabal_package how to install a Cabal package] if you haven't done so already.<br />
<br />
The <tt>binary</tt> package has three major parts: the <code>Get</code> monad,<br />
the <code>Put</code> monad and a general serialisation for Haskell types. The<br />
latter is like the <tt>pickle</tt> module that you may know from Python—it<br />
has its own serialisation format and I won't be covering it any more here.<br />
However, if you just need to persist some Haskell data structures, it might be<br />
exactly what you want: the documentation is<br />
[http://hackage.haskell.org/packages/archive/binary/0.4.1/doc/html/Data-Binary.html here]<br />
<br />
==== The <tt>Get</tt> monad ====<br />
<br />
The <tt>Get</tt> monad is a state monad; it keeps some state and each action<br />
updates that state. The state in this case is an offset into the bytestring<br />
which is getting parsed. <tt>Get</tt> parses lazy bytestrings; this is how<br />
packages like<br />
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tar-0.1.1.1 tar]<br />
can parse files several gigabytes long in constant memory: they are using a<br />
pipeline of lazy bytestrings. However, this also has a downside. When parsing a<br />
lazy bytestring a parse failure (such as running off the end of the bytestring)<br />
is signified by an exception. Exceptions can only be caught in the IO monad<br />
and, because of laziness, might not be thrown exactly where you expect. If this<br />
is a problem, you probably want a strict version of <tt>Get</tt>, which is<br />
covered below.<br />
<br />
Here's an example of using the <tt>Get</tt> monad:<br />
<br />
<haskell>import qualified Data.ByteString.Lazy as BL<br />
import Data.Binary.Get<br />
import Data.Word<br />
<br />
deserialiseHeader :: Get (Word32, Word32, Word32)<br />
deserialiseHeader = do<br />
alen <- getWord32be<br />
plen <- getWord32be<br />
chksum <- getWord32be<br />
return (alen, plen, chksum)<br />
<br />
main :: IO ()<br />
main = do<br />
input <- BL.getContents<br />
print $ runGet deserialiseHeader input</haskell><br />
<br />
This code takes three big-endian, 32-bit unsigned numbers from the input string<br />
and returns them as a tuple. Let's try running it:<br />
<br />
<pre>% runhaskell /tmp/example.hs << EOF<br />
heredoc> 123412341235<br />
heredoc> EOF<br />
(825373492,825373492,825373493)</pre><br />
<br />
Makes sense, right? Look what happens if the input is too short:<br />
<br />
<pre>% runhaskell /tmp/example.hs << EOF<br />
tooshort<br />
EOF<br />
(1953460083,1752134260,example.hs: too few bytes. Failed reading at byte position 12</pre><br />
<br />
Here an exception was thrown because we ran out of bytes.<br />
<br />
So the <tt>Get</tt> monad consists of a set of operations like<br />
<hask>getWord32be</hask> which walk over the input and return some type of<br />
data. You can see the full list of those functions in the<br />
[http://hackage.haskell.org/packages/archive/binary/0.4.1/doc/html/Data-Binary-Get.html documentation].<br />
<br />
Here's another example; decoding an EOF-terminated list of<br />
numbers just involves recursion:<br />
<br />
<haskell>listOfWord16 = do<br />
empty <- isEmpty<br />
if empty<br />
then return []<br />
else do v <- getWord64be<br />
rest <- listOfWord16<br />
return (v : rest)</haskell><br />
<br />
==== Strict <tt>Get</tt> monad ====<br />
<br />
If you're parsing small messages then, firstly your input isn't going to be a<br />
lazy bytestring but a strict one. That's not reallly a problem because you can<br />
easilly convert between them. However, if you want to handle parse failures you<br />
either have to write your parser very carefully, or you have to deal with the<br />
fact that you can only catch exceptions in the IO monad.<br />
<br />
If this is your dilemma, then you need a strict version of the <tt>Get</tt><br />
monad. It's almost exactly the same, but a parser of type <hask>Get a</hask><br />
results in <hask>(Either String a, ByteString)</hask> as the result of<br />
<hask>runGet</hask>. That type is a tuple where the first value is ''either'' a<br />
string (an error string from the parse) or the result, and the second value is<br />
the remaining bytestring when the parser finished.<br />
<br />
Let's update the first example with this strict version of <tt>Get</tt>. You'll<br />
have to install the<br />
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-strict binary-strict]<br />
package for it to work.<br />
<br />
<haskell>import qualified Data.ByteString as B<br />
import Data.Binary.Strict.Get<br />
import Data.Word<br />
<br />
deserialiseHeader :: Get (Word32, Word32, Word32)<br />
deserialiseHeader = do<br />
alen <- getWord32be<br />
plen <- getWord32be<br />
chksum <- getWord32be<br />
return (alen, plen, chksum)<br />
<br />
main :: IO ()<br />
main = do<br />
input <- B.getContents<br />
print $ runGet deserialiseHeader input</haskell><br />
<br />
Note that all we've done is change from lazy bytestrings to strict bytestrings<br />
and change to importing <tt>Data.Binary.Strict.Get</tt>. Now we'll run<br />
it again:<br />
<br />
<pre>% runhaskell /tmp/example.hs << EOF<br />
heredoc> 123412341235<br />
heredoc> EOF<br />
(Right (825373492,825373492,825373493),"\n")</pre><br />
<br />
Now we can see that the parser was successful (we got a <tt>Right</tt>) and we<br />
can see that our shell actually added an extra newline on the input (correctly)<br />
and the parser didn't consume that, so it's also returned to us. Now we try it<br />
with a truncated input:<br />
<br />
<pre>% runhaskell /tmp/example.hs << EOF<br />
heredoc> tooshort<br />
heredoc> EOF<br />
(Left "too few bytes","\n")</pre><br />
<br />
This time we didn't get an exception, but a <tt>Left</tt> value, which can be<br />
handled in pure code. The remaining bytestring is the same because our<br />
truncated input is 9 bytes long, parsing the first two <tt>Word32</tt>'s<br />
consumed 8 bytes and parsing the third failed—at which point we had the last<br />
byte still in the input.<br />
<br />
In your parser, you can also call <hask>fail</hask>, with an error string,<br />
which will result in a <tt>Left</tt> value.<br />
<br />
That's it; it's otherwise the same as the <tt>Get</tt> monad.<br />
<br />
====Incremental parsing====<br />
<br />
If you have to deal with a protocol which isn't length prefixed, or otherwise<br />
chunkable, from the network then you are faced with the problem of knowing when<br />
you have enough data to parse something semantically useful. You could run a<br />
strict <tt>Get</tt> over what you have and catch the truncation result, but<br />
that means that you're parsing the data multiple times etc.<br />
<br />
Instead, you can use an incremental parser. There's an incremental version of<br />
the <tt>Get</tt> monad in <tt>Data.Binary.Strict.IncrementalGet</tt> (you'll<br />
need the <tt>binary-strict</tt> package).<br />
<br />
You use it as normal, but rather than returning an <tt>Either</tt> value, you<br />
get a [http://hackage.haskell.org/packages/archive/binary-strict/0.2.4/doc/html/Data-Binary-Strict-IncrementalGet.html#t%3AResult Result]. You need to go follow that link and look at the documentation for <tt>Result</tt>.<br />
<br />
It reflects the three outcomes of parsing possibly truncated data. Either the<br />
data is invalid as is, or it's complete, or it's truncated. In the truncated<br />
case you are given a function (called a continuation), to which you can pass<br />
more data, when you get it, and continue the parse. The continuation, again,<br />
returns a <tt>Result</tt> depending on the result of parsing the additional<br />
data as well.<br />
<br />
====Bit twiddling====<br />
<br />
Even with all this monadic goodness, sometimes you just need to move some bits<br />
around. That's perfectly possible in Haskell too. Just import<br />
<tt>Data.Bits</tt> and use the following table.<br />
<br />
<table><br />
<tr><th>Name</th><th>C operator</th><th>Haskell</th></tr><br />
<tr><td>AND</td><td><tt>&amp;</tt></td><td><hask>.&.</hask></td></tr><br />
<tr><td>OR</td><td><tt>|</tt></td><td><hask>.|.</hask></td></tr><br />
<tr><td>XOR</td><td><tt>^</tt></td><td><hask>`xor`</hask></td></tr><br />
<tr><td>NOT</td><td><tt>~</tt></td><td><hask>`complement`</hask></td></tr><br />
<tr><td>Left shift</td><td><tt>&lt;&lt;</tt></td><td><hask>`shiftL`</hask></td></tr><br />
<tr><td>Right shift</td><td><tt>&gt;&gt;</tt></td><td><hask>`shiftR`</hask></td></tr><br />
</table><br />
<br />
====The <tt>BitGet</tt> monad====<br />
<br />
As an alternative to bit twiddling, you can also use the <tt>BitGet</tt> monad.<br />
This is another state-like monad, like <tt>Get</tt>, but here the state<br />
includes the current bit-offset in the input. This means that you can easily pull out<br />
unaligned data. Sadly, haddock is currently breaking when trying to generate the<br />
documentation for <tt>BitGet</tt> so I'll start with an example. Again, you'll<br />
need the<br />
[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-strict binary-strict] package installed.<br />
<br />
Here's a description of the header of a DNS packet, direct from RFC 1035:<br />
<br />
<pre> 1 1 1 1 1 1<br />
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+<br />
| ID |<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+<br />
|QR| Opcode |AA|TC|RD|RA| Z | RCODE |<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+<br />
| QDCOUNT |<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+<br />
| ANCOUNT |<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+<br />
| NSCOUNT |<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+<br />
| ARCOUNT |<br />
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+</pre><br />
<br />
The actual fields don't matter, but here's a function for parsing it:<br />
<br />
<haskell>parseHeader :: G.Get Header<br />
parseHeader = do<br />
id <- G.getWord16be<br />
flags <- G.getByteString 2<br />
qdcount <- G.getWord16be >>= return . fromIntegral<br />
ancount <- G.getWord16be >>= return . fromIntegral<br />
nscount <- G.getWord16be >>= return . fromIntegral<br />
arcount <- G.getWord16be >>= return . fromIntegral<br />
<br />
let r = BG.runBitGet flags (do<br />
isquery <- BG.getBit<br />
opcode <- BG.getAsWord8 4 >>= parseEnum<br />
aa <- BG.getBit<br />
tc <- BG.getBit<br />
rd <- BG.getBit<br />
ra <- BG.getBit<br />
<br />
BG.getAsWord8 3<br />
rcode <- BG.getAsWord8 4 >>= parseEnum<br />
<br />
return $ Header id isquery opcode aa tc rd ra rcode qdcount ancount nscount arcount)<br />
<br />
case r of<br />
Left error -> fail error<br />
Right x -> return x</haskell><br />
<br />
Here you can see that only the second line (from the ASCII-art diagram) is<br />
parsed using <tt>BitGet</tt>. An outer <tt>Get</tt> monad is used for<br />
everything else and the bit fields are pulled out with<br />
<hask>getByteString</hask>. Again, <tt>BitGet</tt> is a strict monad and<br />
returns an <tt>Either</tt>, but it doesn't return the remaining bytestring,<br />
just because there's no obvious way to represent a bytestring of a fractional<br />
number of bytes.<br />
<br />
You can see the list of <tt>BitGet</tt> functions and their comments in the<br />
[http://darcs.imperialviolet.org/darcsweb.cgi?r=binary-strict;a=headblob;f=/src/Data/Binary/Strict/BitGet.hs source code].<br />
<br />
===Binary generation===<br />
<br />
In contrast to parsing binary data, you might want to generate it. This is the<br />
job of the <tt>Put</tt> monad. Follow along with the<br />
[http://hackage.haskell.org/packages/archive/binary/0.4.1/doc/html/Data-Binary-Put.html documentation]<br />
if you like.<br />
<br />
The <tt>Put</tt> monad is another state-like monad, but the state is an offset<br />
into a series of buffers where the generated data is placed. All the buffer<br />
creation and handling is done for you, so you can just forget about it. It<br />
results in a lazy bytestring (so you can generate outputs that are larger than memory).<br />
<br />
Here's the reverse of our simple <tt>Get</tt> example:<br />
<br />
<haskell>import qualified Data.ByteString.Lazy as BL<br />
import Data.Binary.Put<br />
<br />
serialiseSomething :: Put<br />
serialiseSomething = do<br />
putWord32be 1<br />
putWord16be 2<br />
putWord8 3<br />
<br />
main :: IO ()<br />
main = BL.putStr $ runPut serialiseSomething</haskell><br />
<br />
And running it shows that it's generating the correct serialisation:<br />
<br />
<pre>% runhaskell /tmp/example.hs| hexdump -C<br />
00000000 00 00 00 01 00 02 03 |.......|</pre><br />
<br />
If you want the output of <tt>runPut</tt> to be a strict bytestring, you just<br />
need to convert it with <hask>B.concat $ BL.toChunks $ runPut xyz</hask>.<br />
<br />
One limitation of <tt>Put</tt>, due to the nature of the <tt>Builder</tt> monad<br />
which it works with, is that you can't get the current offset into the output.<br />
This can be an issue with some formats which require you to encode byte offsets<br />
into the file. You have to calculate these byte offsets yourself.<br />
<br />
=== Other useful packages ===<br />
<br />
There are other packages which you should know about, but which are mostly<br />
covered by their documentation:<br />
<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/network-bytestring-0.1.1 network-bytestring]: for reading and writing bytestring from the network<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/zlib-0.4.0.2 zlib] and [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bzlib-0.4.0.1 bzlib]: for compressed formats<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/encoding-0.3 encoding]: for dealing with character encodings<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tar-0.1.1.1 tar]: as an example of lazy parsing/serialisation</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2008-06-01T07:46:23Z<p>ConradParker: update links to my projects / articles</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I'm a PhD student at Kyoto University in Japan.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* <strike>[[User:ConradParker/SoC2008 | Summer of Code 2008]]</strike><br />
* [http://blog.kfish.org/labels/haskell.html Blog articles]:<br />
** [http://blog.kfish.org/2006/12/introductory-haskell-programming-in.html Introductory Haskell Programming in the Unix Environment], examining laziness with <tt>strace</tt><br />
** [http://blog.kfish.org/2007/06/review-tagsoup.html Review: TagSoup]<br />
** [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Haskell Unicode Support], a comparative review of three Unicode libraries (''iconv'', ''utf8-string'' and ''encoding'')<br />
** [http://blog.kfish.org/2008/04/continuation-fest-2008-continuations.html Continuation Fest 2008: Continuations for video decoding and scrubbing]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/SoC2008User:ConradParker/SoC20082008-03-24T21:30:44Z<p>ConradParker: strike out consideration</p>
<hr />
<div>= Project: Improved support for Unicode (in Haskell tools and libraries) =<br />
<br />
I've created this page to collect some ideas for improving Unicode support in Haskell. <strike>I'm considering applying to do this as a Google Summer of Code project in 2008</strike>.<br />
<br />
Please feel free to edit this page! I want to get feedback on what would be useful and feasible, what tasks have been done already, links to useful documents and so on.<br />
<br />
= Earlier work =<br />
<br />
I've been looking into this problem on and off over the past year or so:<br />
<br />
* [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Survey: Haskell Unicode support]<br />
* [http://haskell.org/~duncan/iconv/examples/hiconv.hs hiconv]<br />
* [http://bother.kfish.org/wiki/HaskellUTF8 Notes on UTF8 in source]<br />
<br />
= Ideas =<br />
<br />
Some project ideas:<br />
<br />
* locale-based charset conversion in GHC<br />
* Unicode ByteString<br />
* Unicode ByteString Parsec<br />
* cabal integration for gettext<br />
* Documentation (best practices)<br />
<br />
= Links =<br />
<br />
* http://hackage.haskell.org/trac/summer-of-code/</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2008-02-29T07:18:55Z<p>ConradParker: add a link to my SoC2008 page</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I'm a PhD student at Kyoto University in Japan.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
* [[User:ConradParker/SoC2008 | Summer of Code 2008]]<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/SoC2008User:ConradParker/SoC20082008-02-28T01:18:47Z<p>ConradParker: create page, random ideas</p>
<hr />
<div>= Project: Improved support for Unicode (in Haskell tools and libraries) =<br />
<br />
I've created this page to collect some ideas for improving Unicode support in Haskell. I'm considering applying to do this as a Google Summer of Code project in 2008.<br />
<br />
Please feel free to edit this page! I want to get feedback on what would be useful and feasible, what tasks have been done already, links to useful documents and so on.<br />
<br />
= Earlier work =<br />
<br />
I've been looking into this problem on and off over the past year or so:<br />
<br />
* [http://blog.kfish.org/2007/10/survey-haskell-unicode-support.html Survey: Haskell Unicode support]<br />
* [http://haskell.org/~duncan/iconv/examples/hiconv.hs hiconv]<br />
* [http://bother.kfish.org/wiki/HaskellUTF8 Notes on UTF8 in source]<br />
<br />
= Ideas =<br />
<br />
Some project ideas:<br />
<br />
* locale-based charset conversion in GHC<br />
* Unicode ByteString<br />
* Unicode ByteString Parsec<br />
* cabal integration for gettext<br />
* Documentation (best practices)<br />
<br />
= Links =<br />
<br />
* http://hackage.haskell.org/trac/summer-of-code/</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-11-12T08:21:45Z<p>ConradParker: add links to C++ template and D type-level versions</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.<br />
<br />
----<br />
<br />
Patryk Zadarnowski offered the following during an email discussion:<br />
<br />
''> Are overlapping and undecidable instances different things?''<br />
<br />
Yep, quite different. Both try to add general programming to the type<br />
level.<br />
Overlapping instances do that by allowing things like:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (a, b) where ...<br />
</haskell><br />
and devising rules fo choosing (1) over (2) whenever possible. Right<br />
now,<br />
this is very, very clunky, under-specified and likely to go away once<br />
Manuel<br />
finishes his [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] implementation. :) For example,<br />
what is<br />
GHC supposed to do with:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (Int, b) where ...<br />
</haskell><br />
Undecidable instances basically means that general recursion is allowed<br />
at the type level. So the above will be accepted (I think) and, more<br />
likely<br />
than not, result in GHC's typechecker spinning into an infinite loop<br />
when<br />
it tries to resolve all these instance declarations. Hence the name; if<br />
the instance declarations are allowed to express any patterns, they<br />
provide<br />
a Turing complete language, and if they provide a Turing complete<br />
language,<br />
than it's impossible to decide whether any given type-level program will<br />
terminate (i.e. is OK) or not. If you're using<br />
<tt>-fallow-undecidable-instances</tt><br />
than yes, your haskell type system is Turing-complete :)<br />
<br />
BTW, the way GHC solves this is by declaring a fixed-depth stack for<br />
"evaluation" of instance declarations. It's something small like 5-deep<br />
by default. If it gets exceeded, GHC will bail out with an error<br />
message.<br />
You can increase the stack depth using some other <tt>-f</tt> on the command<br />
line :)<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 10 September 2007 (UTC)<br />
<br />
On that note, [[User:Mnislaih | Pepe Iborra]] pasted a version of [http://hpaste.org/2689 Instant Insanity with type families].<br />
<br />
[[User:ConradParker|ConradParker]] 06:53, 12 September 2007 (UTC)<br />
<br />
There was a further discussion about termination of type-checking, and about associated types in the thread<br />
[http://www.haskell.org/pipermail/haskell-cafe/2007-September/thread.html#31757 Monad.Reader 8: Haskell, the new C++] on the haskell-cafe mailing list.<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 25 September 2007 (UTC)<br />
<br />
Alex Rubinsteyn posted [http://www.rubinsteyn.com/template_insanity.html Almost Solving Instant Insanity with C++ templates].<br />
This was followed up (in the [http://programming.reddit.com/info/609y7/comments/ proggit discussion]) by a<br />
[http://paste.dprogramming.com/dps43zro D version].<br />
<br />
[[User:ConradParker|ConradParker]] 08:21, 12 November 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-11-07T10:26:26Z<p>ConradParker: add BibTex entry</p>
<hr />
<div>[[Category:Tutorials]]<br />
[[Category:Type-level_programming]]<br />
<br />
'''Type-Level Instant Insanity'''<br />
<br />
<blockquote><br />
We illuminate some of the techniques used to perform computations in the Haskell<br />
Type System by presenting a complete type-level program. Programming at this<br />
level is often considered an obscure art with little practical value, but it need not be so. We tame this magic for the purpose of practical Haskell programming.<br />
</blockquote><br />
<br />
Familiarity with the syntax of the Haskell Type System is a prerequisite for<br />
understanding the details of general Haskell programming. What better way to<br />
build familiarity with something than to hack it to bits?<br />
<br />
* This tutorial was published in [[Media:TMR-Issue8.pdf#page=21|The Monad.Reader Issue 8]] (PDF)<br />
<br />
* [http://sneezy.cs.nott.ac.uk/darcs/TMR/Issue8/instant-insanity.lhs Literate Haskell source]<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]<br />
<br />
=== BibTex Entry ===<br />
<br />
<pre><br />
@article{parker:tlii,<br />
Author = {Conrad Parker},<br />
Journal = {The Monad.Reader},<br />
Month = {September},<br />
Title = {{Type-Level Instant Insanity}},<br />
Volume = {Issue Eight},<br />
Year = {2007}<br />
}<br />
</pre></div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-09-25T02:37:59Z<p>ConradParker: add link to haskell-cafe discussion</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.<br />
<br />
----<br />
<br />
Patryk Zadarnowski offered the following during an email discussion:<br />
<br />
''> Are overlapping and undecidable instances different things?''<br />
<br />
Yep, quite different. Both try to add general programming to the type<br />
level.<br />
Overlapping instances do that by allowing things like:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (a, b) where ...<br />
</haskell><br />
and devising rules fo choosing (1) over (2) whenever possible. Right<br />
now,<br />
this is very, very clunky, under-specified and likely to go away once<br />
Manuel<br />
finishes his [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] implementation. :) For example,<br />
what is<br />
GHC supposed to do with:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (Int, b) where ...<br />
</haskell><br />
Undecidable instances basically means that general recursion is allowed<br />
at the type level. So the above will be accepted (I think) and, more<br />
likely<br />
than not, result in GHC's typechecker spinning into an infinite loop<br />
when<br />
it tries to resolve all these instance declarations. Hence the name; if<br />
the instance declarations are allowed to express any patterns, they<br />
provide<br />
a Turing complete language, and if they provide a Turing complete<br />
language,<br />
than it's impossible to decide whether any given type-level program will<br />
terminate (i.e. is OK) or not. If you're using<br />
<tt>-fallow-undecidable-instances</tt><br />
than yes, your haskell type system is Turing-complete :)<br />
<br />
BTW, the way GHC solves this is by declaring a fixed-depth stack for<br />
"evaluation" of instance declarations. It's something small like 5-deep<br />
by default. If it gets exceeded, GHC will bail out with an error<br />
message.<br />
You can increase the stack depth using some other <tt>-f</tt> on the command<br />
line :)<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 10 September 2007 (UTC)<br />
<br />
On that note, [[User:Mnislaih | Pepe Iborra]] pasted a version of [http://hpaste.org/2689 Instant Insanity with type families].<br />
<br />
[[User:ConradParker|ConradParker]] 06:53, 12 September 2007 (UTC)<br />
<br />
There was a further discussion about termination of type-checking, and about associated types in the thread<br />
[http://www.haskell.org/pipermail/haskell-cafe/2007-September/thread.html#31757 Monad.Reader 8: Haskell, the new C++] on the haskell-cafe mailing list.<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 25 September 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/BooksBooks2007-09-12T07:24:43Z<p>ConradParker: typo (funtional -> functional :-)</p>
<hr />
<div>Books and tutorials covering many aspects of Haskell.<br />
<br />
==Language and library definition==<br />
<br />
<DL><br />
<DT>[[Image:Haskell_98_Language_and_Libraries.jpg|Cover]]<br />
Simon Peyton Jones: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521826144 "Haskell 98 language and libraries: the Revised Report"], Cambridge University Press, 2003, Hardback, 272 pages, ISBN 0521826144, £45.00<br />
<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
Haskell is the world's leading lazy functional programming language,<br />
widely used for teaching, research, and applications. The language<br />
continues to develop rapidly, but in 1998 the community decided to<br />
capture a stable snapshot of the language: Haskell 98. All Haskell<br />
compilers support Haskell 98, so practitioners and educators alike<br />
have a stable base for their work. This book constitutes the agreed<br />
definition of the Haskell 98, both the language itself and its<br />
supporting libraries. It has been considerably revised and refined<br />
since the original definition, and appears in print for the first<br />
time. It should be a standard reference work for anyone involved in<br />
research, teaching, or application of Haskell.<br />
</BLOCKQUOTE> <br />
The entire language definition is also available online:<br />
[[Language_and_library_specification|Language and library<br />
specification]].<br />
</DT><br />
</DL><br />
<br />
==Textbooks==<br />
<br />
<DL><br />
<br />
<dt>[[Image:Programming_in_Haskell.jpg|Cover]] Graham Hutton: [http://www.cs.nott.ac.uk/~gmh/book.html <em>Programming in Haskell</em>], Paperback: 200 pages, Cambridge University Press (January 31, 2007), English, ISBN 0521692695<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
Haskell is one of the leading languages for teaching functional<br />
programming, enabling students to write simpler and cleaner code, and to<br />
learn how to structure and reason about programs. This introduction is<br />
ideal for beginners: it requires no previous programming experience and<br />
all concepts are explained from first principles via carefully chosen<br />
examples. Each chapter includes exercises that range from the<br />
straightforward to extended projects, plus suggestions for further<br />
reading on more advanced topics. The author is a leading Haskell<br />
researcher and instructor, well-known for his teaching skills. The<br />
presentation is clear and simple, and benefits from having been refined<br />
and class-tested over several years. The result is a text that can be<br />
used with courses, or for self-learning. Features include: freely<br />
accessible Powerpoint slides for each chapter; solutions to exercises,<br />
and examination questions (with solutions) available to instructors;<br />
downloadable code that's fully compliant with the latest Haskell<br />
release.<br />
</blockquote><br />
<br />
<DT>[[Image:The_Haskell_School_of_Expression.jpg|Cover]] Paul Hudak: [http://www.haskell.org/soe <EM>The Haskell School of Expression: Learning Functional Programming through Multimedia</EM>], Cambridge University Press, New York, 2000, 416<br />
pp, 15 line diagrams, 75 exercises, Paperback $29.95, ISBN 0521644089, Hardback $74.95, ISBN 0521643384<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
This book teaches functional programming as a way of thinking and<br />
problem solving, using Haskell, the most popular purely functional<br />
language. Rather than using the conventional mathematical examples<br />
commonly found in other programming language textbooks, the author<br />
draws examples from multimedia applications, including graphics,<br />
animation, and computer music, thus rewarding the reader with working<br />
programs for inherently more interesting applications. Aimed at both<br />
beginning and advanced programmers, this tutorial begins with a gentle<br />
introduction to functional programming and moves rapidly on to more<br />
advanced topics. An underlying theme is the design and implementation<br />
of domain specific languages, using three examples: FAL (a Functional<br />
Animation Language), IRL (an Imperative Robot Language), and MDL (a<br />
Music Description Language). Details about programming in Haskell<br />
are presented in boxes throughout the text so they can be easily<br />
referred to and found quickly.<br />
<br />
The book's [http://plucky.cs.yale.edu/CS429F04 Web Site] contains source files for all programs in the text, as well as the graphics libraries to run them under Windows and<br />
Linux platforms. It also contains PowerPoint slides useful for<br />
teaching a course using the textbook.<br />
</blockquote><br />
<DT>[[Image:The_Craft_of_Functional_Programming.jpg|Cover]] Simon Thompson: [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/ <EM>Haskell: The Craft of Functional Programming</EM>], Second Edition,<br />
Addison-Wesley, 507&nbsp;pages, paperback, 1999. ISBN 0-201-34275-8.<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
The second edition of Haskell: The Craft of Functional Programming is essential reading for beginners to functional programming and newcomers to the Haskell programming language. The emphasis is on the process of crafting programs and the text contains many examples and running case studies, as well as advice an program design, testing, problem solving and how to avoid common pitfalls. <br />
<br />
Building on the strengths of the first edition, the book includes many new and improved features: <br />
*Complete coverage of Haskell 98, the standard version of Haskell which will be stable and supported by implementations for years to come. <br />
*An emphasis on software engineering principles, encouraging a disciplined approach to building reusable libraries of software components. <br />
*Detailed coverage of the Hugs interpreter with an appendix covering other implementations. <br />
*A running case study of pictures emphasizes the built-in functions which appear in the standard prelude and libraries. It is also used to give an early preview of some of the more complex language features, such as high-order functions. <br />
*List comprehensions and the standard functions over lists are covered before recursion. <br />
*Early coverage of polymorphism supporting the "toolkit" approach and encouraging the resuse of built-in functions and types. <br />
*Extensive reference material containing details of further reading in books, journals and on the World Wide Web. <br />
*Accompanying Web Site supporting the book, containing all the program code, further teaching materials and other useful resources. <br />
<B>Synopsis</B><BR> <br />
This books introduces Haskell at a level appropriate for those with little or no prior experience of functional programming. The emphasis is on the process of crafting programs, solving problems, and avoiding common errors.<br />
</blockquote><br />
<br />
<DT>[[Image:Introduction_to_Functional_Programming.jpg|Cover]] Richard Bird: [http://www.prenhall.com/allbooks/ptr_0134843460.html <EM>Introduction to Functional Programming using Haskell</EM>], 2nd edition, Prentice Hall Press, 1998, 460 pp., ISBN 0-13-484346-0.<br />
<blockquote><br />
From the cover:<br />
<br />
After the success of the first edition, Introduction to Functional Programming using Haskell has been thoroughly updated and revised to provide a complete grounding in the principles and techniques of programming with functions.<br />
<br />
The second edition uses the popular language Haskell to express functional programs. There are new chapters on program optimisation, abstract datatypes in a functional setting, and programming in a monadic style. There are completely new case studies, and many new exercises.<br />
<br />
As in the first edition, there is an emphasis on the fundamental techniques for reasoning about functional programs, and for deriving them systematically from their specifications.<br />
<br />
The book is self-contained, assuming no prior knowledge of programming, and is suitable as an introductory undergraduate text for first- or second-year students.<br />
</blockquote><br />
<br />
<br />
<DT>[[Image:Introduction_to_Functional_Programming_Systems_Using_Haskell.jpg|Cover]] Antony Davie: [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521277248 <EM>An Introduction to Functional Programming Systems Using Haskell</EM>], Cambridge University Press, 1992. ISBN 0-521-25830-8 (hardback). ISBN 0-521-27724-8 (paperback).<br />
<blockquote><br />
Cover:<br />
<br />
Functional programming is a style of programming that has become increasingly popular during the past few years.<br />
Applicative programs have the advantage of being almost immediately expressible as functional descriptions; they can<br />
be proved correct and transformed through the referential transparency property.<br />
<br />
This book presents the basic concepts of functional programming, using the language Haskell for examples. The author<br />
incorporates a discussion of lambda calculus and its relationship with Haskell, exploring the implications for<br />
raparallelism. Contents: SASL for Beginners / Examples of SASL Programming / More Advanced Applicative Programming<br />
Techniques / Lambda Calculus / The Relationship Between Lambda Calculus and SASL / Program Transformation and<br />
Efficiency / Correctness, Equivalence and Program Verification / Landin's SECD Machine and Related<br />
Implementations / Further Implementation Techniques / Special Purpose Hardware / The Applicative Style of<br />
Semantics / Other Applicative Languages / Implications for Parallelism / Functional Programming in Von Neumann<br />
Languages <br />
</blockquote><br />
<br />
<DT>[[Image:Algorithms_A_Functional_Approach.jpg|Cover]] Fethi Rabhi and Guy Lapalme: [http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html <EM> Algorithms: A functional programming approach</EM>], <br />
Addison-Wesley, 235&nbsp;pages, paperback, 1999. ISBN 0-201-59604-0<BR><br />
<BLOCKQUOTE><br />
<B>Book Description</B><BR> <br />
The authors challenge more traditional methods of teaching algorithms<br />
by using a functional programming context, with Haskell as an<br />
implementation language. This leads to smaller, clearer and more<br />
elegant programs which enable the programmer to understand the<br />
algorithm more quickly and to use that understanding to explore<br />
alternative solutions. <br><br />
<b>Key features:</b><br />
*Most chapters are self-contained and can be taught independently from each other.<br />
*All programs are in Haskell'98 and provided on a WWW site.<br />
*End of chapter exercises throughout.<br />
*Comprehensive index and bibliographical notes.<br />
<B>Synopsis</B><BR> <br />
The book is organised as a classic algorithms book according to topics<br />
such as Abstract Data Types, sorting and searching. It uses a<br />
succession of practical programming examples to develop in the reader<br />
problem-solving skills which can be easily transferred to other<br />
language paradigms. It also introduces the idea of capturing<br />
algorithmic design strategies (e.g. Divide-and-Conquer, Dynamic<br />
Programming) through higher-order functions.<br><br />
<b>Target audience</b><br><br />
The book is intended for computer science students taking algorithms<br />
and/or (basic or advanced) functional programming courses.<br />
</BLOCKQUOTE><br />
<br />
<dt>[[Image:Fun_of_Programming.jpg|Cover]] Jeremy Gibbons and Oege de Moor (eds.): [http://www.palgrave.com/catalogue/catalogue.asp?Title_Id=0333992857 <em>The Fun of Programming</em>],Palgrave, 2002, 288 pages. ISBN 0333992857.<br />
<blockquote><br />
<b>Book description:</b><br><br />
In this textbook, leading researchers give tutorial expositions on the current state of the art of functional<br />
programming. The text is suitable for an undergraduate course immediately following an introduction to<br />
functional programming, and also for self-study. All new concepts are illustrated by plentiful examples,<br />
as well as exercises. A website gives access to accompanying software.<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones: [http://research.microsoft.com/Users/simonpj/Papers/slpj-book-1987/index.htm <em>Implementation of Functional Programming] Language</em>], 500 pages, Prentice-Hall, 1987. ISBN 0134533259.<br />
<blockquote><br />
This 1987 book is now out of print, but it is now available [http://research.microsoft.com/Users/simonpj/Papers/slpj-book-1987/index.htm online] in its entirety.<br />
</blockquote><br />
<br />
<dt>Simon Peyton Jones, David Lester: [http://www.amazon.com/Implementing-Functional-Languages-Prentice-Hall-International/dp/0137219520/sr=1-1/qid=1162002704/ref=sr_1_1/104-0009163-6568732?ie=UTF8&s=books <em>Implementing Functional Languages</em>], Paperback: 288 pages, Prentice Hall (August 1992), English, ISBN 0137219520 <br><br />
<blockquote><br />
The book is out of print. The full sources and a postscript version are <br />
[http://research.microsoft.com/Users/simonpj/Papers/papers.html available for free].<br />
<br />
This book gives a practical approach to understanding the<br />
implementations of non-strict functional languages using lazy graph<br />
reduction. The emphasis of the book is on building working prototypes of<br />
several functional language implementations (template- instantiation,<br />
G-Machine, TIM, parallel G-Machine. In each case the authors provide a<br />
complete working prototype of a particular implementation, and then lead<br />
the reader through a sequence of improvements which expand its scope.<br />
This enables readers to develop, modify and experiment with their own<br />
implementations and for use as a source of practical laboratory work<br />
material.<br />
</blockquote><br />
<br />
<dt>[[Image:TTFP.jpg|Cover]] Simon Thompson: [http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201416670/sr=1-1/qid=1162002856/ref=sr_1_1/104-0009163-6568732?ie=UTF8&s=books <em>Type Theory and Functional Programming</em>], Addison-Wesley, 1991. ISBN 0-201-41667-0. Hardcover: 388 pages.<br />
<blockquote><br />
Now out of print, the original version is available [http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ here].<br />
<br />
<em>Preface</em>:<br />
Constructive Type theory has been a topic of research interest to computer scientists,<br />
mathematicians, logicians and philosophers for a number of years. For computer scientists it provides<br />
a framework which brings together logic and programming languages in a most elegant and fertile way:<br />
program development and verification can proceed within a single system. Viewed in a different way,<br />
type theory is a functional programming language with some novel features, such as the totality of<br />
all its functions, its expressive type system allowing functions whose result type depends upon the<br />
value of its input, and sophisticated modules and abstract types whose interfaces can contain logical<br />
assertions as well as signature information. A third point of view emphasizes that programs (or<br />
functions) can be extracted from proofs in the logic.<br />
</blockquote><br />
<br />
<DT>[[Image:Uma_Abordagem_Pratica.jpg|Cover]] Claudio Cesar de Sá and Marcio Ferreira da Silva: <em> Haskell: Uma Abordagem Prática</em>, [http://www.novatec.com.br Novatec Editora Ltda.], 2006, 296 pages, ISBN 85-7522-095-0. The price is R$ 62,00 (in Reais). Language: Portugese<br />
<blockquote><br />
This book is being published by Novatec Editora Ltda. You can access directly [http://www.novateceditora.com.br/livros/haskell/ here].<br />
<br><br />
<b>Book description:</b><br><br />
This book brings a comprehensive vision of Haskell language. No <br />
knowledge in another functional programming language is expected. In <br />
addition, no background in programming is required. The book presents <br />
issues from basic up to an intermediate level; it also includes some <br />
advanced aspects of Haskell. The title of the book, <em>Haskell: Uma <br />
Abordagem Prática</em>, in English <em>Haskell: A Practical Approach</em>, is the essence of the book.<br />
The result is a text that can be used in courses of programming and paradigms languages.<br />
Finally, many practical examples can be found <br />
throughout the book.<br />
<br />
An additional page containing comments on this book is found here:<br />
[http://www2.joinville.udesc.br/~coca/index.php/Main/PaginaDoLivroDeHaskell].<br />
Other data as bibtex entry, cover's book in several formats, <br />
Winhugs-2001 for download, and so on. This page is Portugese.<br />
</blockquote><br />
<br />
<dt>[[Image:portada.jpg|Cover]] Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo. [http://www.lcc.uma.es/~pepeg/pfHaskell/index.html <em>Razonando con Haskell</em>], Thompson 2004. ISBN 84-9732-277-0. Language: Spanish<br />
<blockquote><br />
Descripción El objetivo principal de este libro es el de servir como<br />
libro de texto de las asignaturas de Programación Declarativa<br />
correspondientes a los estudios de Informática o Ciencias de la<br />
Computación, y otras ciencias en general ( Matemáticas, Física, etc.).<br />
El texto es fruto de una larga experiencia docente de los autores dentro<br />
de las distintas asignaturas que desarrollan la Programación Funcional<br />
en distintas titulaciones de la Universidad de Málaga. Aún así, su<br />
lectura no queda condicionada a un conocimiento previo sobre lenguajes<br />
de programación (de computadores), ni sobre Informática. De esta forma,<br />
el libro puede ser utilizado por todo aquel que desee tener un<br />
conocimiento amplio sobre la Programación Funcional. <br />
</blockquote><br />
<br />
<dt>[[Image:haskell-jp.jpg|Cover]] [http://www.amazon.co.jp/gp/product/4839919623 Haskell Primer: The first functional language to learn]. Jun Mukai. In Japanese. Yen 2,730.<br />
<blockquote><br />
</blockquote><br />
<br />
<dt>[[Image:Haskell-jp-2.jpg|Cover]] [http://www.amazon.co.jp/gp/product/4797336021 Practical Haskell Programming], Minero Aoki and Nobuo Yamashita. A primer on functional programming for real world programs. In Japanese. Yen 2,940. <br />
<blockquote><br />
</blockquote><br />
<br />
<dt>[[Image:Purely_Functional_Data_Structures.jpg|Cover]] [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521663504 Purely Functional Data Structures]<br />
:[http://www.cs.columbia.edu/~cdo/ Chris Okasaki], 232 pp., Cambridge University Press, 1998. ISBN 0-521-63124-6<BR> From the cover: <BLOCKQUOTE> Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study. [http://www.cs.columbia.edu/~cdo/pfds-haskell.tar.gz Haskell source code for the book] </BLOCKQUOTE><br />
</DL><br />
<br />
<DT>[[Image:Fp_in_haskell.gif|Cover]] Р. В. Душкин. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2006. 608 . ISBN 5-94074-335-8<br />
<br />
(Roman V. Dushkin. Functional Programming in Haskell. Moscow: DMK Press, 2006. 608 pp. ISBN 5-94074-335-8)<br />
<br />
<blockquote><br />
<B>Book Description</B><BR> <br />
Данная книга является первым в России изданием, рассматривающим функциональное программирование в полном объеме, достаточном для понимания новичку и для использования книги в качестве справочного пособия теми, кто уже использует парадигму функционального программирования в своей практике. Изучение прикладных основ показано на примере языка Haskell, на сегодняшний день являющегося самым мощным и развитым инструментом функционального программирования. Издание можно использовать и в качестве учебника по функциональному программированию, и в качестве самостоятельного учебного пособия по смежным дисциплинам, в первую очередь по комбинаторной логике и ?-исчислению. Также книга будет интересна тем, кто всерьез занимается изучением новых компьютерных технологий, искусственного интеллекта и экспертных систем. К книге прилагается компакт-диск с транслятором Haskell, а также различными библиотеками к нему, дополнительными утилитами и рабочими примерами программ, рассмотренных в книге.<br />
</blockquote><br />
<br />
<dt> <br />
[[Image:Cartea-lui-Dan-Popa-coperta-1.png|Cover]][http://www.haskell.org/sitewiki/images/0/0f/Cartea-lui-Dan-Popa-coperta-1.png]<br />
[http://www.edusoft.ro/detalii.php?id=81 Introducere in Haskell 98 prin exemple ]: Dan Popa, 230 pp., Edusoft Bacau, Romania, (Ian, 31, 2007),Romanian, ISBN 978-973-8934-48-1 <BR> De pe coperta: <BLOCKQUOTE> Cartea este simultan un manual introductiv de Haskell si o carte auxiliara pentru studentii de la cursul de limbaje formale. Veti avea satisfactia cunoasterii unui limbaj modern (...) in care algoritmul de sortare Quicksort se scrie pe 6 randuri, asa cum se poate vedea de altfel si in imaginea de pe coperta I. (...) Cartea cuprinde o serie de capitole folosite la Universitatea Bacau in calitate de auxiliare de laborator la disciplina Limbaje Formale si Automate. </BLOCKQUOTE><br />
<br />
<br />
===Foundations===<br />
<br />
;[[Image:TaPL.jpg|Cover]]<br />
[http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=pd_sim_b_4/104-0009163-6568732 Types and Programming Languages]<br />
:Benjamin C. Pierce. 645 pages, The MIT Press, (February 1, 2002), English. ISBN 0262162091<br>From the cover:<br />
<blockquote> A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective-has important applications in software engineering, language design, high-performance compilers, and security. This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material. The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.</blockquote><br />
<br />
;[[Image:Advanced_TaPL.jpg|Cover]] [http://www.amazon.com/Advanced-Topics-Types-Programming-Languages/dp/0262162288/ref=pd_sim_b_1/104-0009163-6568732 Advanced Topics in Types and Programming Languages]<br />
:Benjamin C. Pierce (Editor), Hardcover: 608 pages, The MIT Press (December 23, 2004), Language: English, ISBN 0262162288.<br>From the cover:<br />
<blockquote> The study of type systems for programming languages now touches many areas of computer science, from language design and implementation to software engineering, network security, databases, and analysis of concurrent and distributed systems. This book offers accessible introductions to key ideas in the field, with contributions by experts on each topic. The topics covered include precise type analyses, which extend simple type systems to give them a better grip on the run time behavior of systems; type systems for low-level languages; applications of types to reasoning about computer programs; type theory as a framework for the design of sophisticated module systems; and advanced techniques in ML-style type inference. Advanced Topics in Types and Programming Languages builds on Benjamin Pierce's Types and Programming Languages (MIT Press, 2002); most of the chapters should be accessible to readers familiar with basic notations and techniques of operational semantics and type systems -- the material covered in the first half of the earlier book. Advanced Topics in Types and Programming Languages can be used in the classroom and as a resource for professionals. Most chapters include exercises, ranging in difficulty from quick comprehension checks to challenging extensions, many with solutions.<br />
</blockquote><br />
<br />
;[http://www-2.cs.cmu.edu/~rwh/plbook/ Programming Languages: Theory and Practice]<br />
:Robert Harper. (Draft). <blockquote> A working draft of a planned book on the theoretical foundations of practical programming languages. </blockquote><br />
<br />
;[http://homepages.cwi.nl/~jve/cs/ Computational Semantics and Type Theory]<br />
:Jan van Eijck. Draft. [http://www.cwi.nl/~jve/cs/cs.pdf Text online].<br />
<br />
;[http://www.cs.man.ac.uk/~pt/stable/Proofs+Types.html Proofs and Types]<br />
:By Jean-Yves Girard, translated and with appendices by Paul Taylor and Yves Lafont. Based on a short graduate course on typed lambda-calculus given at the Universit Paris VII in the autumn term of 1986-7.<br />
<br />
;[http://homepages.cwi.nl/~atanasso/ref Programming language theory texts online]<br />
:Collection of online programming language theory texts maintained by Frank Atanassow<br />
<br />
;[http://www.cs.chalmers.se/Cs/Research/Logic/book/ Programming in Martin-Löf's Type Theory: An Introduction]<br />
:Bengt Nordström, Kent Petersson and Jan M. Smith. 1990.<br />
<br />
===Mathematics===<br />
<br />
See [[Books and tutorials/Mathematics]]<br />
<br />
==Tutorials==<br />
<br />
===Introductions to Haskell===<br />
<br />
These are the recommended places to start learning, short of buying a textbook.<br />
<br />
==== Best places to start ====<br />
<br />
;[http://darcs.haskell.org/yaht/yaht.pdf Yet Another Haskell Tutorial]<br />
:By Hal Daume III et al. A recommended tutorial for Haskell that is still under construction but covers already much ground. Also a classic text. Now available [http://en.wikibooks.org/wiki/Haskell/YAHT as a wikibook].<br />
<br />
;[http://en.wikibooks.org/wiki/Haskell Haskell Wikibook] <br />
:A communal effort by several authors to produce the definitive Haskell textbook. Its very much a work in progress at the moment, and contributions are welcome.<br />
<br />
;[http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/overview.html Write Yourself a Scheme in 48 Hours in Haskell]<br />
:A Haskell Tutorial, by Jonathan Tang. Most Haskell tutorials on the web seem to take a language-reference-manual approach to teaching. They show you the syntax of the language, a few language constructs, and then have you construct a few simple functions at the interactive prompt. The "hard stuff" of how to write a functioning, useful program is left to the end, or sometimes omitted entirely. This tutorial takes a different tack. You'll start off with command-line arguments and parsing, and progress to writing a fully-functional Scheme interpreter that implements a good-sized subset of R5RS Scheme. Along the way, you'll learn Haskell's I/O, mutable state, dynamic typing, error handling, and parsing features. By the time you finish, you should be fairly fluent in both Haskell and Scheme.<br />
<br />
==== More tutorials ====<br />
<br />
;[http://www.haskell.org/tutorial/ A Gentle Introduction to Haskell] :By Paul Hudak, John Peterson, and Joseph H. Fasel. The title is misleading. Some knowledge of another functional programming language is expected. The emphasis is on the type system and those features which are really new in Haskell (compared to other functional programming languages). A classic, but not for the faint of heart (its not so gentle). Also available in [http://gorgonite.developpez.com/livres/traductions/haskell/gentle-haskell/ French] and [http://www.rsdn.ru/article/haskell/haskell_part1.xml Russian].<br />
<br />
;[[H-99: Ninety-Nine Haskell Problems]]<br />
:A collection of programming puzzles, with Haskell solutions. Solving these is a great way to get into Haskell programming.<br />
<br />
;[http://www.haskell.org/~pairwise/intro/intro.html Haskell Tutorial for C Programmers]<br />
:By Eric Etheridge. From the intro: "This tutorial assumes that the reader is familiar with C/C++, Python, Java, or Pascal. I am writing for you because it seems that no other tutorial was written to help students overcome the difficulty of moving from C/C++, Java, and the like to Haskell."<br />
<br />
;[http://www-106.ibm.com/developerworks/edu/os-dw-linuxhask-i.html Beginning Haskell] <br />
:From IBM developerWorks. This tutorial targets programmers of imperative languages wanting to learn about functional programming in the language Haskell. If you have programmed in languages such as C, Pascal, Fortran, C++, Java, Cobol, Ada, Perl, TCL, REXX, JavaScript, Visual Basic, or many others, you have been using an imperative paradigm. This tutorial provides a gentle introduction to the paradigm of functional programming, with specific illustrations in the Haskell 98 language. (Free registration required.)<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/teaching/Hskurs_toc.html Online Haskell Course] <br />
:By Ralf Hinze (in German).<br />
<br />
;[http://www.cs.chalmers.se/~rjmh/tutorials.html Tutorial Papers in Functional Programming].<br />
:A collection of links to other Haskell tutorials, from John Hughes.<br />
<br />
;[http://www.cs.ou.edu/cs1323h/textbook/haskell.shtml Two Dozen Short Lessons in Haskell] <br />
:By Rex Page. A draft of a textbook on functional programming, available by ftp. It calls for active participation from readers by omitting material at certain points and asking the reader to attempt to fill in the missing information based on knowledge they have already acquired. The missing information is then supplied on the reverse side of the page. <br />
<br />
;[ftp://ftp.geoinfo.tuwien.ac.at/navratil/HaskellTutorial.pdf Haskell-Tutorial] <br />
:By Damir Medak and Gerhard Navratil. The fundamentals of functional languages for beginners. <br />
<br />
;[http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung Video Lectures] <br />
:Lectures (in English) by Jürgen Giesl. About 30 hours in total, and great for learning Haskell. The lectures are 2005-SS-FP.V01 through 2005-SS-FP.V26. Videos 2005-SS-FP.U01 through 2005-SS-FP.U11 are exercise answer sessions, so you probably don't want those.<br />
<br />
;[http://www.cs.utoronto.ca/~trebla/fp/ Albert's Functional Programming Course] <br />
:A 15 lesson introduction to most aspects of Haskell.<br />
<br />
;[http://www.iceteks.com/articles.php/haskell/1 Introduction to Haskell]<br />
:By Chris Dutton, An "attempt to bring the ideas of functional programming to the masses here, and an experiment in finding ways to make it easy and interesting to follow".<br />
<br />
;[http://www.csc.depauw.edu/~bhoward/courses/0203Spring/csc122/haskintro/ An Introduction to Haskell]<br />
:A brief introduction, by Brian Howard.<br />
<br />
;[http://web.syntaxpolice.org/lectures/haskellTalk/slides/index.html Introduction to Haskell]<br />
:By Isaac Jones (2003).<br />
<br />
;[http://www.linuxjournal.com/article/9096 Translating Haskell into English]<br />
:By Shannon Behrens, a glimpse of the Zen of Haskell, without requiring that they already be Haskell converts.<br />
<br />
;[http://www.shlomifish.org/lecture/Perl/Haskell/slides/ Haskell for Perl Programmers]<br />
:Brief introduction to Haskell, with a view to what perl programmers are interested in<br />
<br />
=== Motivation for using Haskell ===<br />
<br />
;[http://www.md.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters] <br />
:By [http://www.md.chalmers.se/~rjmh/ John Hughes], The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.<BR> Exposes the advantages of functional programming languages. Demonstrates how higher-order functions and lazy evaluation enable new forms of modularization of programs.<br />
<br />
;[[Why Haskell matters]] <br />
:Discussion of the advantages of using Haskell in particular. An excellent article.<br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/224/index.html Higher-order + Polymorphic = Reusable] <br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. Unpublished, May 1997.<BR> <STRONG>Abstract:</STRONG> This paper explores how certain ideas in object oriented languages have their correspondents in functional languages. In particular we look at the analogue of the iterators of the C++ standard template library. We also give an example of the use of constructor classes which feature in Haskell 1.3 and Gofer.<br />
<br />
;[http://www-128.ibm.com/developerworks/java/library/j-cb07186.html Explore functional programming with Haskell]<br />
:Introduction to the benefits of functional programming in Haskell by Bruce Tate.<br />
<br />
=== Blog articles ===<br />
<br />
There are a large number of tutorials covering diverse Haskell topics<br />
published as blogs. Some of the best of these articles are collected<br />
here:<br />
<br />
;[[Blog articles]]<br />
<br />
===Practical Haskell===<br />
<br />
These tutorials examine using Haskell to writing complex real-world applications<br />
<br />
;[http://research.microsoft.com/%7Esimonpj/Papers/marktoberdorf Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell]<br />
:Simon Peyton Jones. Presented at the 2000 Marktoberdorf Summer School. In "Engineering theories of software construction", ed Tony Hoare, Manfred Broy, Ralf Steinbruggen, IOS Press, ISBN 1-58603-1724, 2001, pp47-96. The standard reference for monadic IO in GHC/Haskell. <br><strong>Abstract:</strong>Functional programming may be beautiful, but to write real applications we must grapple with awkward real-world issues: input/output, robustness, concurrency, and interfacing to programs written in other languages.<br />
<br />
;[[Hitchhikers Guide to the Haskell]]<br />
: Tutorial for C/Java/OCaml/... programers by Dmitry Astapov. From the intro: "This text intends to introduce the reader to the practical aspects of Haskell from the very beginning (plans for the first chapters include: I/O, darcs, Parsec, QuickCheck, profiling and debugging, to mention a few)".<br />
<br />
;[http://haskell.org/haskellwiki/IO_inside Haskell I/O inside: Down the Rabbit's Hole]<br />
:By Bulat Ziganshin (2006), a comprehensive tutorial on using IO monad.<br />
<br />
;[http://web.archive.org/web/20060622030538/http://www.reid-consulting-uk.ltd.uk/docs/ffi.html A Guide to Haskell's Foreign Function Interface]<br />
:A guide to using the foreign function interface extension, using the rich set of functions in the Foreign libraries, design issues, and FFI preprocessors.<br />
<br />
;[http://blogs.nubgames.com/code/?p=22 Haskell IO for imperative programmers]<br />
:A short introduction to IO from the perspective of an imperative programmer.<br />
<br />
;[[A brief introduction to Haskell|A Brief Introduction to Haskell]]<br />
:A translation of the article, [http://www.cs.jhu.edu/~scott/pl/lectures/caml-intro.html Introduction to OCaml], to Haskell.<br />
<br />
;[[Roll your own IRC bot]]<br />
:This tutorial is designed as a practical guide to writing real world code in Haskell and hopes to intuitively motivate and introduce some of the advanced features of Haskell to the novice programmer, including monad transformers. Our goal is to write a concise, robust and elegant IRC bot in Haskell.<br />
<br />
;[http://j-van-thiel.speedlinq.nl/EddyAhmed/GladeGtk2Hs.html Developing Gnome Apps with Glade]<br />
:For the absolute beginner in both Glade and Gtk2Hs and covers the basics of Glade and how to access a .glade file and widgets in Gtk2Hs. Estimated learning time: 2 hours.<br />
<br />
;Applications of Functional Programming<br />
:Colin Runciman and David Wakeling (ed.), UCL Press, 1995, ISBN 1-85728-377-5 HB. From the cover:<blockquote>This book is unique in showcasing real, non-trivial applications of functional programming using the Haskell language. It presents state-of-the-art work from the FLARE project and will be an invaluable resource for advanced study, research and implementation.</blockquote><br />
<br />
====Testing====<br />
<br />
;[http://blog.moertel.com/articles/2006/10/31/introductory-haskell-solving-the-sorting-it-out-kata Small overview of QuickCheck]<br />
<br />
;[[Introduction to QuickCheck]]<br />
<br />
===Reference material===<br />
<br />
;[http://haskell.org/haskellwiki/Category:Tutorials A growing list of Haskell tutorials on a diverse range of topics]<br />
:Available on this wiki<br />
<br />
;[http://undergraduate.csse.uwa.edu.au/units/230.301/lectureNotes/tourofprelude.html A Tour of the Haskell Prelude (basic functions)] <br />
:By Bernie Pope and Arjan van IJzendoorn.<br />
<br />
;[http://cs.anu.edu.au/Student/comp1100/haskell/tourofsyntax.html Tour of the Haskell Syntax] <br />
:By Arjan van IJzendoorn.<br />
<br />
;[http://zvon.org/other/haskell/Outputglobal/index.html Haskell Reference] <br />
:By Miloslav Nic.<br />
<br />
;[http://members.chello.nl/hjgtuyl/tourdemonad.html A tour of the Haskell Monad functions]<br />
:By Henk-Jan van Tuyl.<br />
<br />
;[http://www.cse.unsw.edu.au/~en1000/haskell/inbuilt.html Useful Haskell functions]<br />
:An explanation for beginners of many Haskell functions that are predefined in the Haskell Prelude.<br />
<br />
;[http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/ListDoc/ Haskell's Standard List Functions]<br />
:A tour of the standard Haskell functions, directed by what you want to achieve<br />
<br />
;[http://haskell.org/ghc/docs/latest/html/libraries/ Documentation for the standard libraries]<br />
:Complete documentation of the standard Haskell libraries.<br />
<br />
;[http://www.haskell.org/haskellwiki/Category:Idioms Haskell idioms]<br />
:A collection of articles describing some common Haskell idioms. Often quite advanced.<br />
<br />
;[http://www.haskell.org/haskellwiki/Blow_your_mind Useful idioms]<br />
:A collection of short, useful Haskell idioms.<br />
<br />
;[http://www.haskell.org/haskellwiki/Programming_guidelines Programming guidelines]<br />
:Some Haskell programming and style conventions.<br />
<br />
;[http://www.md.chalmers.se/~rjmh/Combinators/LightningTour/index.htm Lightning Tour of Haskell]<br />
:By John Hughes, as part of a Chalmers programming course<br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/manuals/haskeller.dvi.gz The Little Haskeller] <br />
:By Cordelia Hall and John Hughes. 9. November 1993, 26 pages. An introduction using the Chalmers Haskell B interpreter (hbi). Beware that it relies very much on the user interface of hbi which is quite different for other Haskell systems, and the tutorials cover Haskell 1.2 , not Haskell 98.<br />
<br />
;[http://www.cs.uu.nl/people/jeroen/courses/fp-eng.pdf Functional Programming]<br />
:By Jeroen Fokker, 1995. (153 pages, 600 KB). Textbook for learning functional programming with Gofer (an older implementation of Haskell). Here without Chapters&nbsp;6 and&nbsp;7.<br />
<br />
=== Comparisons to other languages ===<br />
<br />
Articles constrasting feature of Haskell with other languages.<br />
<br />
;[http://programming.reddit.com/goto?id=nq1k Haskell versus Scheme]<br />
:Mark C. Chu-Carroll, Haskell and Scheme: Which One and Why?<br />
<br />
;[http://wiki.python.org/moin/PythonVsHaskell Comparing Haskell and Python]<br />
:A short overview of similarities and differences between Haskell and Python.<br />
<br />
;[http://programming.reddit.com/goto?id=nwm2 Monads in OCaml]<br />
:Syntax extension for monads in OCaml<br />
<br />
;[http://www.shlomifish.org/lecture/Perl/Haskell/slides/ Haskell for Perl programmers]<br />
:Short intro for perlers<br />
<br />
;[[A_brief_introduction_to_Haskell|Introduction to Haskell]] versus [http://www.cs.jhu.edu/~scott/pl/lectures/caml-intro.html Introduction to OCaml].<br />
<br />
;[http://www.thaiopensource.com/relaxng/derivative.html An algorithm for RELAX NG validation]<br />
:by James Clark (of RELAX NG fame). Describes an algorithm for validating an XML document against a RELAX NG schema, uses Haskell to describe the algorithm. The algorithm in Haskell and Java is then [http://www.donhopkins.com/drupal/node/117 discussed here].<br />
<br />
;[http://mult.ifario.us/articles/2006/10/11/first-steps-with-haskell-for-web-applications Haskell + FastCGI versus Ruby on Rails]<br />
:A short blog entry documenting performance results with ruby on rails and Haskell with fastcgi<br />
<br />
;[http://haskell.org/papers/NSWC/jfp.ps Haskell vs. Ada vs. C++ vs. Awk vs. ..., An Experiment in Software Prototyping Productivity] (postscript)<br />
:Paul Hudak and Mark P. Jones, 16 pages.<blockquote>Description of the results of an experiment in which several conventional programming languages, together with the functional language Haskell, were used to prototype a Naval Surface Warfare Center requirement for Geometric Region Servers. The resulting programs and development metrics were reviewed by a committee chosen by the US Navy. The results indicate that the Haskell prototype took significantly less time to develop and was considerably more concise and easier to understand than the corresponding prototypes written in several different imperative languages, including Ada and C++. </blockquote> <br />
<br />
;[http://www.osl.iu.edu/publications/prints/2003/comparing_generic_programming03.pdf A Comparative Study of Language Support for Generic Programming] (pdf)<br />
:Ronald Garcia, Jaakko Jrvi, Andrew Lumsdaine, Jeremy G. Siek, and Jeremiah Willcock. In Proceedings of the 2003 ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA'03), October 2003.<blockquote>An interesting comparison of generic programming support across languages, including: Haskell, SML, C++, Java, C#. Haskell supports all constructs described in the paper -- the only language to do so. </blockquote><br />
<br />
;[http://homepages.inf.ed.ac.uk/wadler/realworld/index.html Functional Programming in the Real World]<br />
:A list of functional programs applied to real-world tasks. The main criterion for being real-world is that the program was written primarily to perform some task, not primarily to experiment with functional programming. Functional is used in the broad sense that includes both `pure' programs (no side effects) and `impure' (some use of side effects). Languages covered include CAML, Clean, Erlang, Haskell, Miranda, Scheme, SML, and others.<br />
<br />
;[http://www.defmacro.org/ramblings/lisp-in-haskell.html Lisp in Haskell]<br />
:Writing A Lisp Interpreter In Haskell, a tutorial<br />
<br />
=== Teaching Haskell ===<br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1997/208/index.html Where do I begin? A problem solving approach to teaching functional programming]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson]. In Krzysztof Apt, Pieter Hartel, and Paul Klint, editors, First International Conference on Declarative Programming Languages in Education. Springer-Verlag, September 1997. <br> <STRONG>Abstract:</STRONG> This paper introduces a problem solving method for teaching functional programming, based on Polya's `How To Solve It', an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study. <br />
<br />
;[http://www.cs.ukc.ac.uk/pubs/1995/214/index.html Functional programming through the curriculum]<br />
:By [http://www.cs.ukc.ac.uk/people/staff/sjt/index.html Simon Thompson] and Steve Hill. In Pieter H. Hartel and Rinus Plasmeijer, editors, Functional Programming Languages in Education, LNCS 1022, pages 85-102. Springer-Verlag, December 1995. <br> <STRONG>Abstract:</STRONG> This paper discusses our experience in using a functional language in topics across the computer science curriculum. After examining the arguments for taking a functional approach, we look in detail at four case studies from different areas: programming language semantics, machine architectures, graphics and formal languages. <br />
<br />
;[http://www.cse.unsw.edu.au/~chak/papers/CK02a.html The Risks and Benefits of Teaching Purely Functional Programming in First Year]<br />
:By [http://www.cse.unsw.edu.au/~chak Manuel M. T. Chakravarty] and [http://www.cse.unsw.edu.au/~keller Gabriele Keller]. Journal of Functional Programming 14(1), pp 113-123, 2004. An earlier version of this paper was presented at Functional and Declarative Programming in Education (FDPE02). <br> <strong>Abstract</strong> We argue that teaching purely functional programming as such in freshman courses is detrimental to both the curriculum as well as to promoting the paradigm. Instead, we need to focus on the more general aims of teaching elementary techniques of programming and essential concepts of computing. We support this viewpoint with experience gained during several semesters of teaching large first-year classes (up to 600 students) in Haskell. These classes consisted of computer science students as well as students from other disciplines. We have systematically gathered student feedback by conducting surveys after each semester. This article contributes an approach to the use of modern functional languages in first year courses and, based on this, advocates the use of functional languages in this setting.<br />
<br />
===Using monads===<br />
<br />
See also the [[Monad]] HaskellWiki page.<br />
<br />
====Recommended tutorials====<br />
<br />
;[http://www.haskell.org/all_about_monads/html/index.html All About Monads] <br />
:By Jeff Newbern. This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. <br />
<br />
;[http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html Monad Transformers Step by Step]<br />
:Martin Grabm&uuml;ller: a small tutorial on using monad transformers. In contrast to others found on the web, it concentrates on using them, not on their implementation.<br />
<br />
====More tutorials====<br />
<br />
;[http://stefan-klinger.de/files/monadGuide.pdf The Haskell Programmer's Guide to the IO Monad - Don't Panic.] <br />
:Stefan Klinger. This report scratches the surface of category theory, an abstract branch of algebra, just deep enough to find the monad structure. It seems well written.<br />
<br />
;[http://www.prairienet.org/~dsb/monads.htm A (hopefully) painless introduction to monads] <br />
:By Dan Bensen. A brief beginner's guide to using the IO monad in Haskell.<br />
<br />
;[http://www-users.mat.uni.torun.pl/~fly/materialy/fp/haskell-doc/Monads.html What the hell are Monads?] <br />
:By Noel Winstanley. A basic introduction to monads, monadic programming and IO. This introduction is presented by means of examples rather than theory, and assumes a little knowledge of Haskell. <br />
<br />
;[http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm Monads for the Working Haskell Programmer -- a short tutorial]<br />
:By Theodore Norvell. <br />
<br />
;[http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.)]<br />
:A short tutorial on monads, introduced from a pragmatic approach, with less category theory references <br />
<br />
;[http://www.cs.chalmers.se/~augustss/AFP/monads.html Systematic Design of Monads]<br />
:John Hughes & Magnus Carlsson. Many useful monads can be designed in a systematic way, by successively adding facilities to a trivial monad. The capabilities that can be added in this way include state, exceptions, backtracking, and output. Here we give a brief description of the trivial monad, each kind of extension, and sketches of some interesting operations that each monad supports.<br />
<br />
;[[Meet Bob The Monadic Lover]]<br />
:by Andrea Rossato. A by-the-author-supposed-to-be funny and short introduction to Monads, with code but without any reference to category theory: what monads look like and what they are useful for, from the perspective of a ... lover. (There is also the slightly more serious [[The Monadic Way]] by the same author.)<br />
<br />
;[http://www.haskell.org/pipermail/haskell-cafe/2006-November/019190.html Monstrous Monads]<br />
:Andrew Pimlott's humourous introduction to monads, using the metaphor of "monsters".<br />
<br />
;Computational monads [http://programming.reddit.com/info/ox6s/comments/coxiv part 1] and [http://programming.reddit.com/info/ox6s/comments/coxoh part 2].<br />
<br />
See also [[Research papers/Monads and arrows]]<br />
<br />
===Workshops on advanced functional programming===<br />
<br />
;[http://compilers.iecc.com/comparch/article/95-04-024 Advanced Functional Programming: 1st International Spring School on Advanced Functional Programming Techniques], Bastad, Sweden, May 24 - 30, 1995. Tutorial Text (Lecture Notes in Computer Science) <br />
<br />
;[http://www.cse.ogi.edu/PacSoft/conf/summerschool96.html Advanced Functional Programming: 2nd International School], Olympia, Wa, Usa, August 26-30, 1996 Tutorial Text (Lecture Notes in Computer Science) <br />
<br />
;[http://alfa.di.uminho.pt/~afp98/ Advanced Functional Programming: 3rd International School], AFP'98, Braga, Portugal, September 12-19, 1998, Revised Lectures (Lecture Notes in Computer Science) <br />
<br />
;[http://www.cs.uu.nl/~johanj/afp/afp4/ Advanced Functional Programming: 4th International School], AFP 2002, Oxford, UK, August 19-24, 2002, Revised Lectures (Lecture Notes in Computer Science) <br />
<br />
;[http://www.cs.ut.ee/afp04/ Advanced Functional Programming: 5th International School], AFP 2004, Tartu, Estonia, August 14-21, 2004, Revised Lectures (Lecture Notes in Computer Science) <br />
<br />
More advanced materials available from the [[Conferences|conference proceedings]], and the [[Research papers]] collection.<br />
<br />
==Foundations==<br />
<br />
Some books and links listed here can be found also in the articles of ''Theoretical foundations'' category<br />
* see [[Mathematics]]<br />
* or browse ''Theoretical foundations'' among [[Special:Categories]].<br />
<br />
;[http://www.dcs.qmul.ac.uk/~pt/Practical_Foundations/ Practical Foundations of Mathematics]<br />
:Paul Taylor. Cambridge University Press, ISBN: 0-521-63107-6, xii+576 pages, September 2000.<br />
<br />
;[http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]<br />
:Michael Barr and Charles Wells. The revised version of their formerly Springer Verlag published book is online for free download. Note that they use the name ''triple'' instead of ''monad''.<br />
<br />
==Research papers==<br />
<br />
* [[Research papers|Haskell research papers]] are collected on haskell.org<br />
* Also, [http://haskell.readscheme.org/ an online bibliography of Haskell research] at ReadScheme.org<br />
<br />
==Formal Languages and Automata, Grammars and Parsing using Haskell==<br />
* Grammars and Parsing by Johan Jeuring and Doaitse Swierstra is available:<br />
[http://lampwww.epfl.ch/~michelou/links/compiler/files/MAIN.pdf - Download and take a look to the following:]<br />
** 3.1 The type 'Parser' pp 47<br />
** 3.2 Elementary parsers pp 49<br />
** 3.3 Parser combinator pp 52<br />
** 5.1 Finite state automata pp 85<br />
<br />
[[Category:Tutorials]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2007-09-12T07:15:55Z<p>ConradParker: flesh out introduction and project links</p>
<hr />
<div>Hi, I'm [http://www.kfish.org/ Conrad Parker], <tt>kfish</tt> on #haskell.<br />
I'm a PhD student at Kyoto University in Japan.<br />
<br />
Haskell stuff:<br />
<br />
* [[User:ConradParker/InstantInsanity | Type-Level Instant Insanity]], an introductory tutorial about type-level programming.<br />
* [http://www.kfish.org/software/hogg/ HOgg], a library and a commandline tool for manipulating Ogg files.<br />
<br />
Personal web sites:<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-09-12T06:55:18Z<p>ConradParker: mnislaih -> Pepe Iborra (link to user page)</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.<br />
<br />
----<br />
<br />
Patryk Zadarnowski offered the following during an email discussion:<br />
<br />
''> Are overlapping and undecidable instances different things?''<br />
<br />
Yep, quite different. Both try to add general programming to the type<br />
level.<br />
Overlapping instances do that by allowing things like:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (a, b) where ...<br />
</haskell><br />
and devising rules fo choosing (1) over (2) whenever possible. Right<br />
now,<br />
this is very, very clunky, under-specified and likely to go away once<br />
Manuel<br />
finishes his [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] implementation. :) For example,<br />
what is<br />
GHC supposed to do with:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (Int, b) where ...<br />
</haskell><br />
Undecidable instances basically means that general recursion is allowed<br />
at the type level. So the above will be accepted (I think) and, more<br />
likely<br />
than not, result in GHC's typechecker spinning into an infinite loop<br />
when<br />
it tries to resolve all these instance declarations. Hence the name; if<br />
the instance declarations are allowed to express any patterns, they<br />
provide<br />
a Turing complete language, and if they provide a Turing complete<br />
language,<br />
than it's impossible to decide whether any given type-level program will<br />
terminate (i.e. is OK) or not. If you're using<br />
<tt>-fallow-undecidable-instances</tt><br />
than yes, your haskell type system is Turing-complete :)<br />
<br />
BTW, the way GHC solves this is by declaring a fixed-depth stack for<br />
"evaluation" of instance declarations. It's something small like 5-deep<br />
by default. If it gets exceeded, GHC will bail out with an error<br />
message.<br />
You can increase the stack depth using some other <tt>-f</tt> on the command<br />
line :)<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 10 September 2007 (UTC)<br />
<br />
On that note, [[User:Mnislaih | Pepe Iborra]] pasted a version of [http://hpaste.org/2689 Instant Insanity with type families].<br />
<br />
[[User:ConradParker|ConradParker]] 06:53, 12 September 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-09-12T06:53:27Z<p>ConradParker: add link to instant insanity with type families</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.<br />
<br />
----<br />
<br />
Patryk Zadarnowski offered the following during an email discussion:<br />
<br />
''> Are overlapping and undecidable instances different things?''<br />
<br />
Yep, quite different. Both try to add general programming to the type<br />
level.<br />
Overlapping instances do that by allowing things like:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (a, b) where ...<br />
</haskell><br />
and devising rules fo choosing (1) over (2) whenever possible. Right<br />
now,<br />
this is very, very clunky, under-specified and likely to go away once<br />
Manuel<br />
finishes his [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] implementation. :) For example,<br />
what is<br />
GHC supposed to do with:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (Int, b) where ...<br />
</haskell><br />
Undecidable instances basically means that general recursion is allowed<br />
at the type level. So the above will be accepted (I think) and, more<br />
likely<br />
than not, result in GHC's typechecker spinning into an infinite loop<br />
when<br />
it tries to resolve all these instance declarations. Hence the name; if<br />
the instance declarations are allowed to express any patterns, they<br />
provide<br />
a Turing complete language, and if they provide a Turing complete<br />
language,<br />
than it's impossible to decide whether any given type-level program will<br />
terminate (i.e. is OK) or not. If you're using<br />
<tt>-fallow-undecidable-instances</tt><br />
than yes, your haskell type system is Turing-complete :)<br />
<br />
BTW, the way GHC solves this is by declaring a fixed-depth stack for<br />
"evaluation" of instance declarations. It's something small like 5-deep<br />
by default. If it gets exceeded, GHC will bail out with an error<br />
message.<br />
You can increase the stack depth using some other <tt>-f</tt> on the command<br />
line :)<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 10 September 2007 (UTC)<br />
<br />
On that note, mnislaih pasted a version of [http://hpaste.org/2689 Instant Insanity with type families].<br />
<br />
[[User:ConradParker|ConradParker]] 06:53, 12 September 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-09-12T05:46:08Z<p>ConradParker: add pdf anchor</p>
<hr />
<div>[[Category:Tutorials]]<br />
[[Category:Type-level_programming]]<br />
<br />
'''Type-Level Instant Insanity'''<br />
<br />
<blockquote><br />
We illuminate some of the techniques used to perform computations in the Haskell<br />
Type System by presenting a complete type-level program. Programming at this<br />
level is often considered an obscure art with little practical value, but it need not be so. We tame this magic for the purpose of practical Haskell programming.<br />
</blockquote><br />
<br />
Familiarity with the syntax of the Haskell Type System is a prerequisite for<br />
understanding the details of general Haskell programming. What better way to<br />
build familiarity with something than to hack it to bits?<br />
<br />
* This tutorial was published in [[Media:TMR-Issue8.pdf#page=21|The Monad.Reader Issue 8]] (PDF)<br />
<br />
* [http://sneezy.cs.nott.ac.uk/darcs/TMR/Issue8/instant-insanity.lhs Literate Haskell source]<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParkerUser:ConradParker2007-09-11T10:15:24Z<p>ConradParker: add links to my user pages elsewhere</p>
<hr />
<div>= Conrad Parker =<br />
<br />
* [http://www.kfish.org/ www.kfish.org] -- Homepage<br />
* [http://blog.kfish.org/ blog.kfish.org] -- Blog<br />
* [http://bother.kfish.org/ bother.kfish.org] -- Bug tracking, wiki<br />
<br />
I hereby license all my contributions to this wiki under the simple<br />
permissive license on [[HaskellWiki:Copyrights]].<br />
<br />
* [[User:ConradParker/InstantInsanity]]<br />
<br />
My wiki user pages elsewhere:<br />
<br />
* [http://en.wikipedia.org/wiki/User:ConradParker Wikipedia]<br />
* [http://wiki.xiph.org/index.php/User:Conrad Xiph.Org]</div>ConradParkerhttps://wiki.haskell.org/Functional_dependenciesFunctional dependencies2007-09-11T04:11:39Z<p>ConradParker: add links to tutorials about fundeps</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 />
== 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)</div>ConradParkerhttps://wiki.haskell.org/Talk:The_Monad.ReaderTalk:The Monad.Reader2007-09-10T12:23:00Z<p>ConradParker: add link to talk page for instant insanity</p>
<hr />
<div>I'd welcome any feedback and discussion about The Monad.Reader. Don't like the class file? Love the articles? Shout it out!<br />
--[[User:WouterSwierstra|WouterSwierstra]] 10:38, 31 January 2007 (UTC)<br />
<br />
<br />
== The layout ==<br />
<br />
I think the <tt>twosided</tt> should be dropped from the latex class file, that would make it a lot more pleasant to read on a screen.<br />
<br />
--[[User:Twanvl|Twanvl]] 13:50, 31 January 2007 (UTC)<br />
<br />
Although those of use with wide screens quite like putting the pdf up in 2-page side-by-side mode in which the twosided option looks better!<br />
<br />
--[[User:Pharm|Pharm]] 11:26, 1 February 2007 (UTC) (I have an ordinary 4:3 screen at home though. TBH the twosided thing doesn't bother me either way...)<br />
<br />
== The format ==<br />
<br />
--[[User:Yang|Yang]] 17:04, 5 March 2007 (EST)<br />
Great publication, keep them coming! Please consider setting up an RSS/Atom/etc. feed for this.<br />
<br />
--[[User:raould|raould]] June 6 2007<br />
Any chance of an HTML version (no matter how lame the results of an automated PDF2HTML might be)?<br />
<br />
== The content ==<br />
<br />
--[[User:Mnislaih|Mnislaih]] 13:50, 3 February 2007 (UTC)<br />
Wow! This issue of TMR is excellent. I am loving the tutorial style of all the three articles. Right now I'm in section 2 of Russell's excellent assembler and found that the newtype definition for the AssemblyCodeMonad needs to be:<br />
<haskell><br />
newtype AssemblyCodeMonad a = <br />
AssemblyCodeMonad<br />
(RWS [(Label,Location)]<br />
[Either (Instruction Register) (Label,Location)]<br />
(Location, Integer)<br />
a)<br />
deriving (Monad, MonadReader [(Label,Location)], <br />
MonadWriter [Either (Instruction Register) (Label,Location)],<br />
MonadState (Location, Integer))<br />
</haskell><br />
<br />
'''TMR8''': Please note that there is a separate talk page for the article [[User_talk:ConradParker/InstantInsanity | Type-Level Instant Insanity]]<br />
--[[User:ConradParker|ConradParker]] 12:23, 10 September 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/Talk:The_Monad.ReaderTalk:The Monad.Reader2007-09-10T12:16:04Z<p>ConradParker: add headings for format, content</p>
<hr />
<div>I'd welcome any feedback and discussion about The Monad.Reader. Don't like the class file? Love the articles? Shout it out!<br />
--[[User:WouterSwierstra|WouterSwierstra]] 10:38, 31 January 2007 (UTC)<br />
<br />
<br />
== The layout ==<br />
<br />
I think the <tt>twosided</tt> should be dropped from the latex class file, that would make it a lot more pleasant to read on a screen.<br />
<br />
--[[User:Twanvl|Twanvl]] 13:50, 31 January 2007 (UTC)<br />
<br />
Although those of use with wide screens quite like putting the pdf up in 2-page side-by-side mode in which the twosided option looks better!<br />
<br />
--[[User:Pharm|Pharm]] 11:26, 1 February 2007 (UTC) (I have an ordinary 4:3 screen at home though. TBH the twosided thing doesn't bother me either way...)<br />
<br />
== The format ==<br />
<br />
--[[User:Yang|Yang]] 17:04, 5 March 2007 (EST)<br />
Great publication, keep them coming! Please consider setting up an RSS/Atom/etc. feed for this.<br />
<br />
--[[User:raould|raould]] June 6 2007<br />
Any chance of an HTML version (no matter how lame the results of an automated PDF2HTML might be)?<br />
<br />
== The content ==<br />
<br />
--[[User:Mnislaih|Mnislaih]] 13:50, 3 February 2007 (UTC)<br />
Wow! This issue of TMR is excellent. I am loving the tutorial style of all the three articles. Right now I'm in section 2 of Russell's excellent assembler and found that the newtype definition for the AssemblyCodeMonad needs to be:<br />
<haskell><br />
newtype AssemblyCodeMonad a = <br />
AssemblyCodeMonad<br />
(RWS [(Label,Location)]<br />
[Either (Instruction Register) (Label,Location)]<br />
(Location, Integer)<br />
a)<br />
deriving (Monad, MonadReader [(Label,Location)], <br />
MonadWriter [Either (Instruction Register) (Label,Location)],<br />
MonadState (Location, Integer))<br />
</haskell></div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-09-10T12:03:03Z<p>ConradParker: add to categories Tutorials and Type-level programming</p>
<hr />
<div>[[Category:Tutorials]]<br />
[[Category:Type-level_programming]]<br />
<br />
'''Type-Level Instant Insanity'''<br />
<br />
<blockquote><br />
We illuminate some of the techniques used to perform computations in the Haskell<br />
Type System by presenting a complete type-level program. Programming at this<br />
level is often considered an obscure art with little practical value, but it need not be so. We tame this magic for the purpose of practical Haskell programming.<br />
</blockquote><br />
<br />
Familiarity with the syntax of the Haskell Type System is a prerequisite for<br />
understanding the details of general Haskell programming. What better way to<br />
build familiarity with something than to hack it to bits?<br />
<br />
* This tutorial was published in [[Media:TMR-Issue8.pdf|The Monad.Reader Issue 8]] (PDF)<br />
<br />
* [http://sneezy.cs.nott.ac.uk/darcs/TMR/Issue8/instant-insanity.lhs Literate Haskell source]<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-09-10T11:59:26Z<p>ConradParker: update links to point to TMR</p>
<hr />
<div>'''Type-Level Instant Insanity'''<br />
<br />
<blockquote><br />
We illuminate some of the techniques used to perform computations in the Haskell<br />
Type System by presenting a complete type-level program. Programming at this<br />
level is often considered an obscure art with little practical value, but it need not be so. We tame this magic for the purpose of practical Haskell programming.<br />
</blockquote><br />
<br />
Familiarity with the syntax of the Haskell Type System is a prerequisite for<br />
understanding the details of general Haskell programming. What better way to<br />
build familiarity with something than to hack it to bits?<br />
<br />
* This tutorial was published in [[Media:TMR-Issue8.pdf|The Monad.Reader Issue 8]] (PDF)<br />
<br />
* [http://sneezy.cs.nott.ac.uk/darcs/TMR/Issue8/instant-insanity.lhs Literate Haskell source]<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-09-10T02:37:03Z<p>ConradParker: add notes about overlapping and undecidable instances from patryk z</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.<br />
<br />
----<br />
<br />
Patryk Zadarnowski offered the following during an email discussion:<br />
<br />
''> Are overlapping and undecidable instances different things?''<br />
<br />
Yep, quite different. Both try to add general programming to the type<br />
level.<br />
Overlapping instances do that by allowing things like:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (a, b) where ...<br />
</haskell><br />
and devising rules fo choosing (1) over (2) whenever possible. Right<br />
now,<br />
this is very, very clunky, under-specified and likely to go away once<br />
Manuel<br />
finishes his [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] implementation. :) For example,<br />
what is<br />
GHC supposed to do with:<br />
<haskell><br />
instance Foo (a, Int) where ...<br />
instance Foo (Int, b) where ...<br />
</haskell><br />
Undecidable instances basically means that general recursion is allowed<br />
at the type level. So the above will be accepted (I think) and, more<br />
likely<br />
than not, result in GHC's typechecker spinning into an infinite loop<br />
when<br />
it tries to resolve all these instance declarations. Hence the name; if<br />
the instance declarations are allowed to express any patterns, they<br />
provide<br />
a Turing complete language, and if they provide a Turing complete<br />
language,<br />
than it's impossible to decide whether any given type-level program will<br />
terminate (i.e. is OK) or not. If you're using<br />
<tt>-fallow-undecidable-instances</tt><br />
than yes, your haskell type system is Turing-complete :)<br />
<br />
BTW, the way GHC solves this is by declaring a fixed-depth stack for<br />
"evaluation" of instance declarations. It's something small like 5-deep<br />
by default. If it gets exceeded, GHC will bail out with an error<br />
message.<br />
You can increase the stack depth using some other <tt>-f</tt> on the command<br />
line :)<br />
<br />
[[User:ConradParker|ConradParker]] 02:37, 10 September 2007 (UTC)</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-09-05T15:44:59Z<p>ConradParker: update abstract</p>
<hr />
<div>'''Type-Level Instant Insanity'''<br />
<br />
<blockquote><br />
We illuminate some of the techniques used to perform computations in the Haskell<br />
Type System by presenting a complete type-level program. Programming at this<br />
level is often considered an obscure art with little practical value, but it need not be so. We tame this magic for the purpose of practical Haskell programming.<br />
</blockquote><br />
<br />
Familiarity with the syntax of the Haskell Type System is a prerequisite for<br />
understanding the details of general Haskell programming. What better way to<br />
build familiarity with something than to hack it to bits?<br />
<br />
* http://seq.kfish.org/instant-insanity/instant-insanity.pdf (Draft)<br />
<br />
* darcs get http://seq.kfish.org/instant-insanity/<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/TMRTMR2007-09-05T15:17:27Z<p>ConradParker: redirect to The Monad.Reader</p>
<hr />
<div>#REDIRECT [[The Monad.Reader]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-09-05T14:13:58Z<p>ConradParker: update abstract</p>
<hr />
<div>'''Type-Level Instant Insanity'''<br />
<br />
<blockquote><br />
We illuminate some of the techniques used to perform computations in the Haskell<br />
Type System by presenting a complete type-level program. Programming at this<br />
level is often considered an obscure art with little practical value, but it need not be so.<br />
</blockquote><br />
<br />
Familiarity with the syntax of the Haskell Type System is a prerequisite for<br />
understanding the details of general Haskell programming. What better way to<br />
build familiarity with something than to hack it to bits?<br />
<br />
* http://seq.kfish.org/instant-insanity/instant-insanity.pdf (Draft)<br />
<br />
* darcs get http://seq.kfish.org/instant-insanity/<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-09-03T13:57:32Z<p>ConradParker: add link to draft PDF</p>
<hr />
<div>'''Type-Level Instant Insanity'''<br />
<br />
We illuminate some of the techniques used to perform computations in The Haskell Type System by presenting a complete type-level program.<br />
Programming at this level is often considered an obscure art with little<br />
practical value, but it need not be so.<br />
We introduce constructs equivalent to list comprehensions, maps and filters<br />
of conventional functional programming, and in so doing make clear the<br />
mechanical techniques required to construct programs in this manner.<br />
Only after building an understanding of the syntactical oddities and<br />
transformations involved in programming in The Haskell Type System do we consider the practical aspects of using these techniques in conventional Haskell programming.<br />
<br />
* http://seq.kfish.org/instant-insanity/instant-insanity.pdf (Draft)<br />
<br />
* darcs get http://seq.kfish.org/instant-insanity/<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-08-30T04:20:54Z<p>ConradParker: add link to wiki talk page</p>
<hr />
<div>'''Type-Level Instant Insanity'''<br />
<br />
We illuminate some of the techniques used to perform computations in The Haskell Type System by presenting a complete type-level program.<br />
Programming at this level is often considered an obscure art with little<br />
practical value, but it need not be so.<br />
We introduce constructs equivalent to list comprehensions, maps and filters<br />
of conventional functional programming, and in so doing make clear the<br />
mechanical techniques required to construct programs in this manner.<br />
Only after building an understanding of the syntactical oddities and<br />
transformations involved in programming in The Haskell Type System do we consider the practical aspects of using these techniques in conventional Haskell programming.<br />
<br />
<br />
* darcs get http://seq.kfish.org/instant-insanity/<br />
<br />
* [[User_talk:ConradParker/InstantInsanity|Wiki talk page for discussion]]</div>ConradParkerhttps://wiki.haskell.org/User:ConradParker/InstantInsanityUser:ConradParker/InstantInsanity2007-08-30T04:13:16Z<p>ConradParker: add link to darcs repo</p>
<hr />
<div>'''Type-Level Instant Insanity'''<br />
<br />
We illuminate some of the techniques used to perform computations in The Haskell Type System by presenting a complete type-level program.<br />
Programming at this level is often considered an obscure art with little<br />
practical value, but it need not be so.<br />
We introduce constructs equivalent to list comprehensions, maps and filters<br />
of conventional functional programming, and in so doing make clear the<br />
mechanical techniques required to construct programs in this manner.<br />
Only after building an understanding of the syntactical oddities and<br />
transformations involved in programming in The Haskell Type System do we consider the practical aspects of using these techniques in conventional Haskell programming.<br />
<br />
<br />
* darcs get http://seq.kfish.org/instant-insanity/</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-08-30T03:52:58Z<p>ConradParker: cleanup</p>
<hr />
<div>This is a discussion page for the paper [[User:ConradParker/InstantInsanity|Type-Level Instant Insanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.</div>ConradParkerhttps://wiki.haskell.org/User_talk:ConradParker/InstantInsanityUser talk:ConradParker/InstantInsanity2007-08-30T03:51:50Z<p>ConradParker: snarf text from SPJ's talk pages</p>
<hr />
<div>= Talk page for "Type-Level Instant Insanity" =<br />
<br />
This is a discussion page for the paper [[User:ConradParker/InstantInsanity]].<br />
<br />
If you are kind enough to read this paper, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. <br />
<br />
You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:<br />
<br />
:[[User:ConradParker|ConradParker]] 03:51, 30 August 2007 (UTC) Note from Conrad<br />
<br />
If you say who you are in this way, we'll be able to acknowledge your help in a revised version of the paper.</div>ConradParker