https://wiki.haskell.org/api.php?action=feedcontributions&user=Abrim&feedformat=atomHaskellWiki - User contributions [en]2024-03-28T10:04:50ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Structure_of_a_Haskell_project&diff=11019Structure of a Haskell project2007-02-04T06:21:31Z<p>Abrim: add reference to 'How to write a Haskell program'</p>
<hr />
<div>[[Category:Applications]]<br />
The intention behind this page is to flesh out some semi-standard for<br />
the directory structure, and the tool-setup for medium to large-sized<br />
Haskell projects. It is intended to make it easier for newcomers to<br />
start up projects, and for everybody to navigate others projects. Newcomers should also read [[How to write a Haskell program]] for more detailed instructions on setting up a new project.<br />
<br />
Especially I hope some focus can be made on how to make the different<br />
tools play well together, and giving the project structure that allows<br />
scaling.<br />
<br />
Hopefully someone more qualified than I (the initiator of this page)<br />
will be summoned and write their advices, change the faults, add<br />
missing bits and discuss differences in opinions.<br />
<br />
And perhaps a sample project (in the spirit of HNop, but with broader<br />
ambitions) should be made, so that can be used as a template.<br />
<br />
== Tools ==<br />
It is recommended to make use the following tool chain:<br />
* [[Darcs]] for revision control<br />
* [[Cabal]] for managing builds, tests and haddock'ing <br />
* [[QuickCheck]] and [[SmallCheck]] for auto-generated test-cases<br />
* [[HUnit]] for hand-coded tests<br />
* [[Haddock]] for generating API documents '''or''' [[Literate programming]] combined with latex for thorough documentation of the code<br />
<br />
== Directory Structure ==<br />
<br />
For a project called app an outline the directory structure should<br />
look like this (inspired by looking at projects like GHC, PUGS, Yi,<br />
Haskore, Hmp3, Fps):<br />
<br />
<pre><br />
app/ -- Root-dir<br />
src/ -- For keeping the sourcecode<br />
Main.lhs -- The main-module<br />
App/ -- Use hierarchical modules<br />
...<br />
Win32/ -- For system dependent stuff<br />
Unix/<br />
cbits/ -- For C code to be linked to the haskell program<br />
testsuite/ -- Contains the testing stuff<br />
runtests.sh -- Will run all tests<br />
tests/ -- For unit-testing and checking<br />
App/ -- Clone the module hierarchy, so that there is one <br />
testfile per sourcefile<br />
benchmarks/ -- For testing performance<br />
doc/ -- Contains the manual, and other documentation<br />
examples/ -- Example inputs for the program<br />
dev/ -- Information for new developers about the project, <br />
and eg. related litterature<br />
util/ -- Auxiliary scripts for various tasks<br />
dist/ -- Directory containing what end-users should get<br />
build/ -- Contains binary files, created by cabal<br />
doc/ -- The haddock documentation goes here, created by cabal<br />
resources/ -- Images, soundfiles and other non-source stuff<br />
used by the program<br />
_DARCS/ <br />
README -- Textfile with short introduction of the project<br />
INSTALL -- Textfile describing how to build and install<br />
TODO -- Textfile describing things that ought to be done<br />
AUTHORS -- Textfile containing info on who does and has done <br />
what in this project, and their contact info<br />
LICENSE -- Textfile describing licensing terms for this project<br />
app.cabal -- Project-description-file for cabal<br />
Setup.hs -- Program for running cabal commands<br />
</pre><br />
<br />
== Technicalities ==<br />
=== The sourcefiles ===<br />
<br />
* It is recommended to write sourcefiles in plain ascii or UTF-8 with unix line-endings using only spaces (and not tabs) for indentation.<br />
* The interface (everything a module exports) should be commented in english with haddock comments.<br />
* All of the code should be a large latex document going through the code and explaining it. The latex markup should be kept light, so that it is stil readable in an editor. The main module should include all of the files somehow.<br />
* The modules should have explicit export-lists<br />
* Explicit type-annotations should be given for all top-level definitions.<br />
<br />
== Discussions ==<br />
=== Why not use lhs2Tex ===<br />
<br />
Some short experiments showed that lhs2Tex is not too happy about<br />
haddock-comments, and since these two techniques of commenting are<br />
orthogonal something else should be chosen. Eg. [[http://www.acooke.org/jara/pancito/haskell.sty latex.sty]]<br />
<br />
=== How is the testing framework best made? ===<br />
<br />
Here should be a recipe for making a test-framework with both<br />
HUnit-tests an QuickCheck properties, that can all be run with a<br />
simple command, and how to make darcs use that for testing before<br />
recording.</div>Abrimhttps://wiki.haskell.org/index.php?title=How_to_write_a_Haskell_program&diff=11018How to write a Haskell program2007-02-04T06:14:05Z<p>Abrim: add reference to 'Structure of a Haskell project' page</p>
<hr />
<div>A guide to the best practice for creating a new Haskell project or<br />
program.<br />
<br />
== Recommended tools ==<br />
<br />
Almost all new Haskell projects use the following tools. Each is<br />
intrinsically useful, but using a set of common tools also benefits<br />
everyone by increasing productivity, and you're more likely to get<br />
patches.<br />
<br />
=== Revision control ===<br />
<br />
Use [http://darcs.net Darcs] unless you have a specific reason not to.<br />
It's much more powerful than most competing systems (and it's written in Haskell).<br />
<br />
=== Build system ===<br />
<br />
[[Image:Cabal-With-Text-small.png|frame|Built with Cabal]]<br />
<br />
Use [http://haskell.org/cabal Cabal].<br />
You should read at least the start of section 2 of the [http://www.haskell.org/ghc/docs/latest/html/Cabal/index.html Cabal User's Guide].<br />
<br />
=== Documentation ===<br />
<br />
For libraries, use [http://haskell.org/haddock Haddock]. We recommend<br />
using the latest version of haddock (currently 0.8).<br />
<br />
=== Testing ===<br />
<br />
Pure code can be tested using [http://www.md.chalmers.se/~rjmh/QuickCheck/ QuickCheck] or [http://www.mail-archive.com/haskell@haskell.org/msg19215.html SmallCheck], impure code with [http://hunit.sourceforge.net/ HUnit]. <br />
<br />
To get started, try [[Introduction to QuickCheck]]. For a slightly more advanced introduction, [http://blog.codersbase.com/2006/09/01/simple-unit-testing-in-haskell/ Simple Unit Testing in Haskell] is a blog article about creating a testing framework for QuickCheck using some Template Haskell.<br />
<br />
== Structure of a simple project ==<br />
<br />
The basic structure of a new Haskell project can be adopted from<br />
[http://semantic.org/hnop/ HNop], the minimal Haskell project. It<br />
consists of the following files, for the mythical project "haq".<br />
<br />
* Haq.hs -- the main haskell source file<br />
* haq.cabal -- the cabal build description<br />
* Setup.hs -- build script itself<br />
* _darcs -- revision control<br />
* README -- info<br />
* LICENSE -- license<br />
<br />
You can of course elaborate on this, with subdirectories and multiple<br />
modules. See [[Structure of a Haskell project]] for an example of a larger project's directory structure.<br />
<br />
Here is a transcript on how you'd create a minimal darcs and cabalised<br />
Haskell project, for the cool new Haskell program "haq", build it,<br />
install it and release.<br />
<br />
The new tool 'mkcabal' automates all this for you, but its important to<br />
understand all the parts first. <br />
<br />
We will now walk through the creation of the infrastructure for a simple<br />
Haskell executable. Advice for libraries follows after.<br />
<br />
=== Create a directory ===<br />
<br />
Create somewhere for the source:<br />
<br />
<haskell><br />
$ mkdir haq<br />
$ cd haq<br />
</haskell><br />
<br />
=== Write some Haskell source ===<br />
<br />
Write your program:<br />
<br />
<haskell><br />
$ cat > Haq.hs<br />
--<br />
-- Copyright (c) 2006 Don Stewart - http://www.cse.unsw.edu.au/~dons<br />
-- GPL version 2 or later (see http://www.gnu.org/copyleft/gpl.html)<br />
--<br />
import System.Environment<br />
<br />
-- | 'main' runs the main program<br />
main :: IO ()<br />
main = getArgs >>= print . haqify . head<br />
<br />
haqify s = "Haq! " ++ s<br />
</haskell><br />
<br />
=== Stick it in darcs ===<br />
<br />
Place the source under revision control:<br />
<br />
<haskell><br />
$ darcs init<br />
$ darcs add Haq.hs <br />
$ darcs record<br />
addfile ./Haq.hs<br />
Shall I record this change? (1/?) [ynWsfqadjkc], or ? for help: y<br />
hunk ./Haq.hs 1<br />
+--<br />
+-- Copyright (c) 2006 Don Stewart - http://www.cse.unsw.edu.au/~dons<br />
+-- GPL version 2 or later (see http://www.gnu.org/copyleft/gpl.html)<br />
+--<br />
+import System.Environment<br />
+<br />
+-- | 'main' runs the main program<br />
+main :: IO ()<br />
+main = getArgs >>= print . haqify . head<br />
+<br />
+haqify s = "Haq! " ++ s<br />
Shall I record this change? (2/?) [ynWsfqadjkc], or ? for help: y<br />
What is the patch name? Import haq source<br />
Do you want to add a long comment? [yn]n<br />
Finished recording patch 'Import haq source'<br />
</haskell><br />
<br />
And we can see that darcs is now running the show:<br />
<br />
<haskell><br />
$ ls<br />
Haq.hs _darcs<br />
</haskell><br />
<br />
=== Add a build system ===<br />
<br />
Create a .cabal file describing how to build your project:<br />
<br />
<haskell><br />
$ cat > haq.cabal<br />
Name: haq<br />
Version: 0.0<br />
Description: Super cool mega lambdas<br />
License: GPL<br />
License-file: LICENSE<br />
Author: Don Stewart<br />
Maintainer: dons@cse.unsw.edu.au<br />
Build-Depends: base<br />
<br />
Executable: haq<br />
Main-is: Haq.hs<br />
ghc-options: -O<br />
</haskell><br />
<br />
(If your package uses other packages, e.g. <tt>haskell98</tt>, you'll need to add them to the <tt>Build-Depends:</tt> field.)<br />
Add a <tt>Setup.lhs</tt> that will actually do the building:<br />
<br />
<haskell><br />
$ cat > Setup.lhs<br />
#! /usr/bin/env runhaskell<br />
<br />
> import Distribution.Simple<br />
> main = defaultMain<br />
</haskell><br />
Cabal allows either <tt>Setup.hs</tt> or <tt>Setup.lhs</tt>, but we recommend writing the setup file this way so that it can be executed directly by Unix shells.<br />
<br />
Record your changes:<br />
<br />
<haskell><br />
$ darcs add haq.cabal Setup.lhs<br />
$ darcs record --all<br />
What is the patch name? Add a build system<br />
Do you want to add a long comment? [yn]n<br />
Finished recording patch 'Add a build system'<br />
</haskell><br />
<br />
=== Build your project ===<br />
<br />
Now build it!<br />
<br />
<haskell><br />
$ runhaskell Setup.lhs configure --prefix=$HOME<br />
$ runhaskell Setup.lhs build<br />
$ runhaskell Setup.lhs install<br />
</haskell><br />
<br />
=== Run it ===<br />
<br />
And now you can run your cool project:<br />
<haskell><br />
$ haq me<br />
"Haq! me"<br />
</haskell><br />
<br />
You can also run it in-place, avoiding the install phase:<br />
<haskell><br />
$ dist/build/haq/haq you<br />
"Haq! you"<br />
</haskell><br />
<br />
=== Build some haddock documentation ===<br />
<br />
Generate some API documentation into dist/doc/*<br />
<br />
<haskell><br />
$ runhaskell Setup.lhs haddock<br />
</haskell><br />
<br />
which generates files in dist/doc/ including:<br />
<br />
<haskell><br />
$ w3m -dump dist/doc/html/haq/Main.html<br />
haq Contents Index<br />
Main<br />
<br />
Synopsis<br />
main :: IO ()<br />
<br />
Documentation<br />
<br />
main :: IO ()<br />
main runs the main program<br />
<br />
Produced by Haddock version 0.7<br />
</haskell><br />
<br />
No output? Make sure you have actually installed haddock. It is a separate program, not something that comes with Cabal.<br />
<br />
=== Add some automated testing: QuickCheck ===<br />
<br />
We'll use QuickCheck to specify a simple property of our Haq.hs code. Create a tests module, Tests.hs, with some QuickCheck boilerplate:<br />
<br />
<haskell><br />
$ cat > Tests.hs<br />
import Char<br />
import List<br />
import Test.QuickCheck<br />
import Text.Printf<br />
<br />
main = mapM_ (\(s,a) -> printf "%-25s: " s >> a) tests<br />
<br />
instance Arbitrary Char where<br />
arbitrary = choose ('\0', '\128')<br />
coarbitrary c = variant (ord c `rem` 4)<br />
</haskell><br />
<br />
Now let's write a simple property:<br />
<br />
<haskell><br />
$ cat >> Tests.hs <br />
-- reversing twice a finite list, is the same as identity<br />
prop_reversereverse s = (reverse . reverse) s == id s<br />
where _ = s :: [Int]<br />
<br />
-- and add this to the tests list<br />
tests = [("reverse.reverse/id", test prop_reversereverse)]<br />
</haskell><br />
<br />
We can now run this test, and have QuickCheck generate the test data:<br />
<br />
<haskell><br />
$ runhaskell Tests.hs<br />
reverse.reverse/id : OK, passed 100 tests.<br />
</haskell><br />
<br />
Let's add a test for the 'haqify' function:<br />
<br />
<haskell><br />
-- Dropping the "Haq! " string is the same as identity<br />
prop_haq s = drop (length "Haq! ") (haqify s) == id s<br />
where haqify s = "Haq! " ++ s<br />
<br />
tests = [("reverse.reverse/id", test prop_reversereverse)<br />
,("drop.haq/id", test prop_haq)]<br />
</haskell><br />
<br />
and let's test that:<br />
<br />
<haskell><br />
$ runhaskell Tests.hs<br />
reverse.reverse/id : OK, passed 100 tests.<br />
drop.haq/id : OK, passed 100 tests.<br />
</haskell><br />
<br />
Great!<br />
<br />
=== Running the test suite from darcs ===<br />
<br />
We can arrange for darcs to run the test suite on every commit:<br />
<br />
<haskell><br />
$ darcs setpref test "runhaskell Tests.hs"<br />
Changing value of test from '' to 'runhaskell Tests.hs'<br />
</haskell><br />
<br />
will run the full set of QuickChecks. (If your test requires it you may need to ensure other things are built too eg: <tt>darcs setpref test "alex Tokens.x;happy Grammar.y;runhaskell Tests.hs"</tt>).<br />
<br />
Let's commit a new patch:<br />
<br />
<haskell><br />
$ darcs add Tests.hs<br />
$ darcs record --all<br />
What is the patch name? Add testsuite<br />
Do you want to add a long comment? [yn]n<br />
Running test...<br />
reverse.reverse/id : OK, passed 100 tests.<br />
drop.haq/id : OK, passed 100 tests.<br />
Test ran successfully.<br />
Looks like a good patch.<br />
Finished recording patch 'Add testsuite'<br />
</haskell><br />
<br />
Excellent, now patches must pass the test suite before they can be<br />
committed.<br />
<br />
=== Tag the stable version, create a tarball, and sell it! ===<br />
<br />
Tag the stable version:<br />
<br />
<haskell><br />
$ darcs tag<br />
What is the version name? 0.0<br />
Finished tagging patch 'TAG 0.0'<br />
</haskell><br />
<br />
==== Tarballs via Cabal ====<br />
<br />
Since the code is cabalised, we can create a tarball with Cabal<br />
directly:<br />
<br />
<haskell><br />
$ runhaskell Setup.lhs sdist<br />
Building source dist for haq-0.0...<br />
Source tarball created: dist/haq-0.0.tar.gz<br />
</haskell><br />
This has the advantage that Cabal will do a bit more checking, and<br />
ensure that the tarball has the structure expected by HackageDB.<br />
It packages up the files needed to build the project; to include other files (such as <tt>Test.hs</tt> in the above example), we need to add:<br />
<br />
<haskell><br />
extra-source-files: Tests.hs<br />
</haskell><br />
<br />
to the .cabal file to have everything included.<br />
<br />
==== Tarballs via darcs ====<br />
<br />
Alternatively, you can use darcs:<br />
<haskell><br />
$ darcs dist -d haq-0.0<br />
Created dist as haq-0.0.tar.gz<br />
</haskell><br />
<br />
And you're all set up!<br />
<br />
==== Upload your package to Hackage ====<br />
<br />
Whichever of the above methods you've used to create your package, you can upload it to the Hackage package collection via a [http://hackage.haskell.org/packages/upload.html web interface].<br />
You may wish to use the package checking interface there first, and fix things it warns about, before uploading your package.<br />
<br />
=== Summary ===<br />
<br />
The following files were created:<br />
<br />
$ ls<br />
Haq.hs Tests.hs dist haq.cabal<br />
Setup.lhs _darcs haq-0.0.tar.gz<br />
<br />
== Libraries ==<br />
<br />
The process for creating a Haskell library is almost identical. The differences<br />
are as follows, for the hypothetical "ltree" library:<br />
<br />
=== Hierarchical source ===<br />
<br />
The source should live under a directory path that fits into the<br />
existing [http://www.haskell.org/~simonmar/lib-hierarchy.html module layout guide].<br />
So we would create the following directory structure, for the module<br />
Data.LTree:<br />
<br />
$ mkdir Data<br />
$ cat > Data/LTree.hs <br />
module Data.LTree where<br />
<br />
So our Data.LTree module lives in Data/LTree.hs<br />
<br />
=== The Cabal file ===<br />
<br />
Cabal files for libraries list the publically visible modules, and have<br />
no executable section:<br />
<br />
$ cat ltree.cabal <br />
Name: ltree<br />
Version: 0.1<br />
Description: Lambda tree implementation<br />
License: BSD3<br />
License-file: LICENSE<br />
Author: Don Stewart<br />
Maintainer: dons@cse.unsw.edu.au<br />
Build-Depends: base<br />
Exposed-modules: Data.LTree<br />
ghc-options: -Wall -O<br />
<br />
We can thus build our library:<br />
<br />
$ runhaskell Setup.lhs configure --prefix=$HOME<br />
$ runhaskell Setup.lhs build <br />
Preprocessing library ltree-0.1...<br />
Building ltree-0.1...<br />
[1 of 1] Compiling Data.LTree ( Data/LTree.hs, dist/build/Data/LTree.o )<br />
/usr/bin/ar: creating dist/build/libHSltree-0.1.a<br />
<br />
and our library has been created as a object archive. Now install it:<br />
<br />
$ runhaskell Setup.lhs install<br />
Installing: /home/dons/lib/ltree-0.1/ghc-6.6 & /home/dons/bin ltree-0.1...<br />
Registering ltree-0.1...<br />
Reading package info from ".installed-pkg-config" ... done.<br />
Saving old package config file... done.<br />
Writing new package config file... done.<br />
<br />
And we're done! You can use your new library from, for example, ghci:<br />
<br />
$ ghci -package ltree<br />
Prelude> :m + Data.LTree<br />
Prelude Data.LTree> <br />
<br />
The new library is in scope, and ready to go.<br />
<br />
=== More complex build systems ===<br />
<br />
For larger projects it is useful to have source trees stored in<br />
subdirectories. This can be done simply by creating a directory, for<br />
example, "src", into which you will put your src tree.<br />
<br />
To have Cabal find this code, you add the following line to your Cabal<br />
file:<br />
<br />
hs-source-dirs: src<br />
<br />
Cabal can set up to also run configure scripts, along with a range of<br />
other features. For more information consult the<br />
[http://www.haskell.org/ghc/docs/latest/html/Cabal/index.html Cabal documentation].<br />
<br />
== Automation ==<br />
<br />
A tool to automatically populate a new cabal project is available<br />
(beta!):<br />
<br />
darcs get http://www.cse.unsw.edu.au/~dons/code/mkcabal<br />
<br />
Usage is:<br />
<br />
<haskell><br />
$ mkcabal<br />
Project name: haq<br />
What license ["GPL","LGPL","BSD3","BSD4","PublicDomain","AllRightsReserved"] ["BSD3"]: <br />
What kind of project [Executable,Library] [Executable]: <br />
Is this your name? - "Don Stewart " [Y/n]: <br />
Is this your email address? - "<dons@cse.unsw.edu.au>" [Y/n]: <br />
Created Setup.lhs and haq.cabal<br />
$ ls<br />
Haq.hs LICENSE Setup.lhs _darcs dist haq.cabal<br />
</haskell><br />
<br />
which will fill out some stub Cabal files for the project 'haq'. <br />
<br />
To create an entirely new project tree:<br />
<br />
<haskell><br />
$ mkcabal --init-project<br />
Project name: haq<br />
What license ["GPL","LGPL","BSD3","BSD4","PublicDomain","AllRightsReserved"] ["BSD3"]: <br />
What kind of project [Executable,Library] [Executable]: <br />
Is this your name? - "Don Stewart " [Y/n]: <br />
Is this your email address? - "<dons@cse.unsw.edu.au>" [Y/n]: <br />
Created new project directory: haq<br />
$ cd haq<br />
$ ls<br />
Haq.hs LICENSE README Setup.lhs haq.cabal<br />
</haskell><br />
<br />
== Licenses ==<br />
<br />
Code for the common base library package must be BSD licensed. Otherwise, it<br />
is entirely up to you as the author.<br />
Choose a licence (inspired by [http://www.dina.dk/~abraham/rants/license.html this]).<br />
Check the licences of things you use, both other Haskell packages and C<br />
libraries, since these may impose conditions you must follow.<br />
Use the same licence as related projects, where possible. The Haskell community is<br />
split into 2 camps, roughly, those who release everything under BSD, and<br />
(L)GPLers. Some Haskellers recommend avoiding LGPL, due to cross module optimisation<br />
issues. Like many licensing questions, this advice is controversial. Several Haskell projects<br />
(wxHaskell, HaXml, etc) use the LGPL with an extra permissive clause which gets round the<br />
cross-module optimisation thing.<br />
<br />
== Releases ==<br />
<br />
It's important to release your code as stable, tagged tarballs. Don't<br />
just [http://awayrepl.blogspot.com/2006/11/we-dont-do-releases.html rely on darcs for distribution].<br />
<br />
* '''darcs dist''' generates tarballs directly from a darcs repository<br />
<br />
For example:<br />
<br />
$ cd fps<br />
$ ls <br />
Data LICENSE README Setup.hs TODO _darcs cbits dist fps.cabal tests<br />
$ darcs dist -d fps-0.8<br />
Created dist as fps-0.8.tar.gz<br />
<br />
You can now just post your fps-0.8.tar.gz<br />
<br />
You can also have darcs do the equivalent of 'daily snapshots' for you by using a post-hook.<br />
<br />
put the following in _darcs/prefs/defaults:<br />
apply posthook darcs dist<br />
apply run-posthook<br />
<br />
Advice:<br />
* Tag each release using '''darcs tag'''. For example:<br />
<br />
$ darcs tag 0.8<br />
Finished tagging patch 'TAG 0.8'<br />
<br />
Then people can <tt>darcs pull --partial -t 0.8</tt>, to get just the tagged version (and not the entire history).<br />
<br />
== Hosting ==<br />
<br />
A Darcs repository can be published simply by making it available from a<br />
web page. If you don't have an account online, or prefer not to do this<br />
yourself, source can be hosted on darcs.haskell.org (you will need to <br />
email [http://research.microsoft.com/~simonmar/ Simon Marlow] to do this). <br />
haskell.org itself has some user accounts available.<br />
<br />
There are also many free hosting places for open source, such as<br />
* [http://code.google.com/hosting/ Google Project Hosting]<br />
* [http://sourceforge.net/ SourceForge].<br />
<br />
== Web page ==<br />
<br />
Create a web page documenting your project! An easy way to do this is to<br />
add a project specific page to [[Haskell|the Haskell wiki]]<br />
<br />
== The user experience ==<br />
<br />
When developing a new Haskell library, it is important to keep in mind<br />
the user's expectations for how the library is to be built and used.<br />
<br />
=== Introductory information and build guide ===<br />
<br />
The intended approach for a user of a library is roughly:<br />
<br />
# Visit [[Haskell|Haskell.org]]<br />
# Find the library/program they are looking for:<br />
## if not found, try mailing list; <br />
## if it is hidden, try improving the documentation on haskell.org;<br />
## if it does not exist, try contributing code and documentation) <br />
# Download<br />
# Build and install<br />
# Enjoy<br />
<br />
Each of these steps can pose potential road blocks, and code authors can<br />
do a lot to help code users avoid such blocks. Even if steps 1..2 are<br />
successful, and ensuring step 5 is the main concern of code authors and<br />
users, it is often steps 3..4 that get in the way. In particular, the<br />
following questions should have clear answers:<br />
<br />
* Which is the latest version? <br />
* What state is it in? <br />
* What are its aims? <br />
* Where is the documentation?<br />
* Which is the right version for given OS and Haskell implementation?<br />
* How is it packaged, and what tools are needed to get and unpack it?<br />
* How is it installed, and what tools are needed to install it?<br />
* How do we handle dependencies?<br />
* How do we provide/acquire the knowledge and tool-chains needed?<br />
<br />
The best place to answer these questions is with a README file,<br />
distributed with the library or application, and often accompanied with<br />
similar text on a more extensive web page.<br />
<br />
=== Tutorials ===<br />
<br />
Generated haddock documentation is not enough, usually, for new<br />
programmers to learn how to use a library. It is critical to also<br />
provide accompanying examples, and even tutorials on the use of the<br />
library.<br />
<br />
Please consider providing example, type correct code, with commentary,<br />
on the use of your library (or application).<br />
<br />
== Program structure ==<br />
<br />
Monad transformers are very useful for programming in the large,<br />
encapsulating state, and controlling side effects. To learn more about this approach, try [http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html Monad Transformers Step by Step].<br />
<br />
== Publicity ==<br />
<br />
The best code in the world is meaningless if nobody knows about it. The<br />
process to follow once you've tagged and released your code is:<br />
<br />
=== Join the community ===<br />
<br />
If you haven't already, join the community. The best way to do this is to [http://haskell.org/haskellwiki/Mailing_lists subscribe] to at least haskell-cafe@ and haskell@ mailing lists. Joining the [[IRC_channel|#haskell IRC channel]] is also an excellent idea.<br />
<br />
=== Announce your project on haskell@ ===<br />
<br />
Most important: announce your project releases to the haskell@haskell.org mailing list. Tag your email subject line with "ANNOUNCE: ...". This ensure it will then make it into the [http://haskell.org/haskellwiki/HWN Haskell Weekly News]. To be doubly sure, you can email the release text to the [[HWN|HWN editor]].<br />
<br />
=== Add your code to the public collections ===<br />
<br />
* Add your library or application to the [[Libraries and tools]] page, under the relevant category, so people can find it.<br />
<br />
* If your release is a Cabal package, add it to the [http://hackage.haskell.org/packages/hackage.html Hackage database] (Haskell's CPAN wanna-be).<br />
<br />
=== Blog about it ===<br />
<br />
Blog about it! Blog about your new code on [http://planet.haskell.org Planet Haskell].<br />
Write about your project in your blog, then email the [http://planet.haskell.org/ Planet Haskell] maintainer (ibid on [[IRC channel|#haskell]]) the RSS feed url for your blog<br />
<br />
== Example ==<br />
<br />
[http://www.cse.unsw.edu.au/~dons/blog/2006/12/11#release-a-library-today A complete example] of writing, packaging and releasing a new Haskell library under this process has been documented.<br />
<br />
[[Category:Community]]<br />
[[Category:Tutorials]]</div>Abrimhttps://wiki.haskell.org/index.php?title=Stack_overflow&diff=8640Stack overflow2006-11-24T03:56:20Z<p>Abrim: </p>
<hr />
<div>First, read TailRecursive. If you are not writing your code tail-recursively, then that is why you are getting stack overflows. However, as the bottom of that page suggests, making code tail-recursive in a lazy language is not quite the same as in a eager language. This page is more geared to the latter case using foldr/l as the prime culprit/example. As such WhatIsaFold may be helpful, but isn't too critical. Also knowing what seq and ($!) do as briefly covered in ForcingEagerEvaluation or in the [WWW]Haskell Report is necessary.<br />
<br />
The definitions of the three folds we'll be looking at are as follows,<br />
<haskell><br />
foldr f z [] = z<br />
foldr f z (x:xs) = f x (foldr f z xs)<br />
<br />
foldl f z [] = z<br />
foldl f z (x:xs) = foldl f (f z x) xs<br />
<br />
foldl' f z [] = z<br />
foldl' f z (x:xs) = (foldl' f $! f z x) xs<br />
<br />
foldl' (found in e.g. Data.List) is just a stricter version of foldl.<br />
</haskell><br />
The one-line summary for folds: if the binary operation is strict use foldl' otherwise use foldr.<br />
<br />
----<br />
<br />
Common newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldr (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
If you've read TailRecursive, you should immediately see the problem from the definition of foldr above. Quite simply, foldr isn't tail-recursive! But,<br />
<haskell><br />
concat xss = foldr (++) [[]] xss<br />
</haskell><br />
This is from the Haskell Report. Surely they know what they are doing! And sure enough,<br />
<haskell><br />
main = print (length (concat [[x] | x <- [1..1000000]]))<br />
</haskell><br />
works fine.<br />
<br />
Common less newbie stack overflowing code:<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
So what's going on here. Looking at the code for foldl, it looks tail-recursive. Well, much like you can see the problem with a non-tail-recursive factorial by unfolding a few iterations, let's do the same for our foldl definition of sum, but making sure to use a call-by-name/need evaluation order. Here is the unfolding,<br />
<haskell><br />
mysum [1..10] -><br />
foldl (+) 0 (1:[2..10]) -><br />
foldl (+) (0+1) (2:[3..10]) -><br />
foldl (+) (0+1+2) (3:[4..10]) -><br />
foldl (+) (0+1+2+3) (4:[5..10]) -> ...<br />
</haskell><br />
I think you get the idea. The problem is that we are building up a chain of thunks that will evaluate the sum instead of just maintaining a running sum. What we need to do is to force the addition before recursing. This is exactly what foldl' does.<br />
<br />
Just to check,<br />
<haskell><br />
mysum :: [Integer] -> Integer<br />
mysum = foldl' (+) 0<br />
<br />
main = print (mysum [1..1000000])<br />
</haskell><br />
works fine.<br />
<br />
Now let's go back to the foldr sum and concat. What's the difference between sum and concat that makes the sum definition wrong, but the concat definition right. Again, let's evaluate each by hand.<br />
<haskell><br />
mysum (+) 0 [1..10] -><br />
foldr (+) 0 (1:[2..10]) -><br />
1+foldr (+) 0 (2:[3..10]) -><br />
1+(2+foldr (+) 0 (3:[4..10])) -> ...<br />
</haskell><br />
Okay, no surprise there.<br />
<haskell><br />
concat [[1],[2],[3],...] -><br />
foldr (++) [[]] ([1]:[[2],[3],...]) -><br />
(1:[])++foldr (++) [[]] [[2],[3],...] -><br />
1:([]++foldr (++) [[]] [[2],[3],...])<br />
</haskell><br />
Notice that there is no '-> ...' at the end. That was the complete evaluation. There is no reason to do anything more unless we look at the more of the result. We may well GC the 1 before we look at the tail, and GC the first cons cell before we look at the second. So, concat runs in a constant amount of stack and further can handle infinite lists (as a note, it's immediately obvious foldl(') can never work on infinite lists because we'll always be in the (:) case and that always immediately recurses). The differentiator between mysum and concat is that (++) is not strict* in its second argument; we don't have to evaluate the rest of the foldr to know the beginning of concat. In mysum, since (+) is strict in its second argument we need the results of the whole foldr before we can compute the final result.<br />
<br />
So, we arrive at the one-line summary: A function strict in its second argument will always* require linear stack space with foldr, so foldl' should be used instead in that case. If the function is lazy/non-strict in its second argument we should use foldr to 1) support infinite lists and 2) to allow a streaming use of the input list where only part of it needs to be in memory at a time.<br />
<br />
Okay, both here and in the one-line summary, there is no mention of foldl. When should foldl be used? The pragmatic answer is: by and far it shouldn't be used. A case where it makes a difference is if the function is conditionally strict in its first argument depending on its second, where I use conditionally strict to mean a function that is strict or not in one argument depending on another argument(s). For an example, consider a definition of (*) that builds up ASTs of arithmetic expressions and incorporates a simplification (a*0 = 0 and then 0*a = 0); then if product is defined by foldl (*) 1, product [_|_,0] will terminate with 0 while a definition in terms of foldl' wouldn't. However, I can't think of a really convincing example. In most cases, foldl' is what you want.<br />
<br />
* A strict function is a function, f such that f _|_ = _|_. Typically, we think of a function "being strict" in an argument as a function that "forces" its argument, but the above definition of strict should immediately suggest another function that is strict and doesn't "force" it's argument in the intuitive sense, namely id. ([]++) = id and therefore is a strict function. Sure enough, if you were to evaluate (concat (repeat [])) it would not terminate. As such (++) is a conditionally strict function. This also makes the "always" slightly imprecise, a function that is strict because it just returns it's argument will not use up stack space (but is, as I mentioned, still an issue for infinitely long lists).</div>Abrim