https://wiki.haskell.org/api.php?action=feedcontributions&user=Nedervold&feedformat=atomHaskellWiki - User contributions [en]2019-10-17T14:27:19ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Hoed&diff=60457Hoed2015-12-22T02:14:13Z<p>Nedervold: some spelling and punctuation changes</p>
<hr />
<div>Hoed is a lightweight tracer and algorithmic debugger that is practical to use for real-world programs.<br />
<br />
== Installing Hoed ==<br />
<br />
Hoed is available and can be installed with<br />
<pre><br />
cabal install Hoed<br />
</pre><br />
<br />
We also made several defective example programs available. These can be installed by downloading the tarball under the header Downloads from http://hackage.haskell.org/package/Hoed. After unpacking the tarball you can build Hoed and some example programs with<br />
<pre><br />
sh configure.Demo<br />
cabal build<br />
</pre><br />
with the run script you are given a list of example programs to chose from to execute<br />
<pre><br />
sh run<br />
</pre><br />
<br />
== Using Hoed ==<br />
<br />
To locate a defect with Hoed you annotate suspected functions and compile as usual. Then when you run your program, information about the annotated functions is collected. Finally you connect to a debugging session using a web browser.<br />
<br />
Let us consider the following program: a defective implementation of a parity function with a test property.<br />
<br />
<pre><br />
isOdd :: Int -> Bool<br />
isOdd n = isEven (plusOne n)<br />
<br />
isEven :: Int -> Bool<br />
isEven n = mod2 n == 0<br />
<br />
plusOne :: Int -> Int<br />
plusOne n = n + 1<br />
<br />
mod2 :: Int -> Int<br />
mod2 n = div n 2<br />
<br />
prop_isOdd :: Int -> Bool<br />
prop_isOdd x = isOdd (2*x+1)<br />
</pre><br />
<br />
<br />
Using the property-based test tool QuickCheck we find the counterexample #1 for our property.<br />
<br />
<pre><br />
> quickCheck prop_isOdd<br />
*** Failed! Falsifiable (after 1 test): 1<br />
</pre><br />
<br />
Hoed can help us determine which function is defective. We annotate the functions isOdd, isEven, plusOne and mod2 as follows:<br />
<br />
<pre><br />
import Debug.Hoed.Pure<br />
<br />
isOdd :: Int -> Bool<br />
isOdd = observe "isOdd" isOdd'<br />
isOdd' n = isEven (plusOne n)<br />
<br />
isEven :: Int -> Bool<br />
isEven = observe "isEven" isEven'<br />
isEven' n = mod2 n == 0<br />
<br />
plusOne :: Int -> Int<br />
plusOne = observe "plusOne" plusOne'<br />
plusOne' n = n + 1<br />
<br />
mod2 :: Int -> Int<br />
mod2 = observe "mod2" mod2'<br />
mod2' n = div n 2<br />
<br />
prop_isOdd :: Int -> Bool<br />
prop_isOdd x = isOdd (2*x+1)<br />
</pre><br />
<br />
Now we use the combinator testO to trace our program for the counterexample of our property.<br />
After running the program a computation tree is constructed and displayed in a web browser.<br />
<br />
<br />
<pre><br />
> testO prop_isOdd 1<br />
*** Failed! Falsifiable: 1<br />
Listening on http://127.0.0.1:10000/<br />
</pre><br />
<br />
<br />
You can freely browse this tree to get a better understanding of your program. If your program misbehaves, you can judge the computation statements in the tree as 'right' or 'wrong' according to your intention. When enough statements are judged the debugger tells you the location of the fault in your code.<br />
<br />
== Annotating Functions ==<br />
<br />
A function is annotated using an observe primitive with a String. An arbitrary value can be used, but we use the function name to have it in the trace for constructing the computation tree. For example, the function<br />
<pre><br />
isOdd n = isEven (plusOne n)<br />
</pre><br />
can be annotated as follows<br />
<pre><br />
isOdd = observe "isOdd" isOdd'<br />
isOdd' n = isEven (plusOne n)<br />
</pre><br />
<br />
To observe a function its argument and result type need to be of typeclass <code>Observable</code>. Hoed comes with instances for the base types and several other commonly used types.<br />
<br />
It is easy to make your own types <code>Observable</code> because Hoed also provides a type-generic instance. For example:<br />
<pre><br />
data Person = Person String Int deriving Generic<br />
instance Observable Person<br />
<br />
data Tree a = Node a [Tree a] | Leaf deriving Generic<br />
instance Observable a => Observable (Tree a)<br />
</pre><br />
<br />
== Views ==<br />
<br />
Hoed offers several views on the collected debugging information.<br />
<br />
'''Algorithmic Debugging''': Hoed uses Hood's observe technique to record information during a program execution that shows unintended behaviour. Hoed's post-mortem algorithmic debugging view presents the user with questions about intermediate computation statements. The user has to judge whether these statements agree with their intentions. After some questions and answers, the debugger locates a defect in a slice (i.e.\ part) of the program.<br />
<br />
[[File:HoedAlgorithmicDebugging.png|780px]]<br />
<br />
'''Explore''': Hoed organizes the computation statements in a tree. In this mode the computation tree can be freely explored.<br />
[[File:HoedExplore.png|780px]]<br />
<br />
'''Observe''': A list view of the computation statements that can be searched with a simple keyword or a regular expression. One of the computation statements can be selected and used as starting point for one of the other modes.<br />
[[File:HoedObserve.png|780px]]<br />
<br />
== Comparison with Other Tracers and Debuggers ==<br />
<br />
Hat is probably the most advanced tracer tool for Haskell. It traces every reduction and provides many tools for viewing this trace. Hat requires a transformation of every module, even libraries we are not interested in. The transformation does not support as many language features as GHC and in practice many programs cannot be debugged with Hat. In contrast, Hoed is just a library and only functions we are interested in need to be annotated. Many programs that are difficult to debug with Hat can be debugged with Hoed.<br />
<br />
Most Haskell implementations come with a <code>trace</code> primitive that can be used for printf style debugging. However, the primitive can force evaluation. Consider for example applying the function <code>headDoubler> to <code>[1..]</code> in<br />
<pre><br />
headDoubler xs = trace ("headDoubler " ++ show xs) (2 * head (xs) : tail xs)<br />
<br />
main = print (take 3 (headDoubler [1..]))<br />
</pre><br />
<br />
HOOD can be used like Debug.Trace for printf-style debugging while respecting evaluation order. Observing headDoubler in above example gives <code>headDoubler (1:2:3:_) = 2:2:3:_</code>. Hoed is based on HOOD, but gives a relation between computation statements and adds an algorithmic debugger.<br />
<br />
<br />
[[Category:Tools]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Taking_over_a_package&diff=57525Taking over a package2014-02-01T15:57:48Z<p>Nedervold: mostly formatting</p>
<hr />
<div>There can be situations where a certain package on Hackage is in the need of an update (a typical example: a package cannot be compiled with some of the versions of the dependencies; or, on the contrary, dependencies list needs a version bump), but the maintainer of the package is unavailable. Luckily, there is a general policy that allows users to submit patched versions of the packages or even completely take over unmaintained packages.<br />
<br />
# Try to contact the maintainer. Give him/her reasonable time to respond.<br />
# State your intention to take over the package in a public forum (e.g., the haskell-cafe/libraries list). CC the maintainer.<br />
# Wait a while.<br />
# Send an email to the Hackage admin list, with a link to the public email thread.<br />
# The admins or trustees will grant you maintenance rights or upload a patched version for you.<br />
<br />
There is a faster way of gaining maintainership of a package, but it requires the current maintainer to be reachable:<br />
<br />
* The original maintainer can just give you access at http://hackage.haskell.org/package/<package>/maintainers/ <br />
<br />
''OR''<br />
<br />
* The maintainer emails the Hackage admin list, saying s/he wants you to take over the package.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Mac_OS_X&diff=37132Mac OS X2010-10-04T23:25:43Z<p>Nedervold: </p>
<hr />
<div>There is also now the [[Mac OS X Strike Force]] that aims to improve using Haskell on OS X.<br />
<br />
== The Haskell Platform ==<br />
<br />
There are Mac OS X installers of the full Haskell Platform development environment. We recommend it:<br />
<br />
[http://haskell.org/platform/ http://haskell.org/platform/icons/button-100.png]<br />
<br />
== GHC ==<br />
<br />
==== Important notes ====<br />
<br />
To get the most out of your GHC environment, you should add '~/.cabal/bin' to your PATH environment variable before the path where you have GHC installed. This will allow you to get and use cabal-updates, as well as other programs shipped with GHC like hsc2hs.<br />
<br />
In your ~/.profile, add the line:<br />
<br />
<code>export PATH="~/.cabal/bin:$PATH";</code><br />
<br />
<br />
=== Mac OS X 10.5 (Leopard) ===<br />
<br />
To install GHC on Mac OS X 10.5 (Leopard), there are the following options:<br />
* install the [http://hackage.haskell.org/platform/ Haskell Platform]<br />
* install [http://www.macports.org MacPort]'s [http://trac.macports.org/browser/trunk/dports/lang/ghc/Portfile ghc] package<br />
<br />
=== Mac OS X 10.6 (Snow Leopard) ===<br />
<br />
* Install the [http://hackage.haskell.org/platform/ Haskell Platform]<br />
<br />
To uninstall ghc call:<br />
<code><br />
sudo /Library/Frameworks/GHC.framework/Tools/Uninstaller<br />
</code><br />
<br />
== HUGS ==<br />
<br />
* install [http://www.macports.org MacPort]'s [http://trac.macports.org/browser/trunk/dports/lang/hugs98/Portfile hugs98] package.<br />
<br />
<br />
== Installing libraries with external C bindings ==<br />
<br />
Haskell libraries are installed with the <code>cabal</code> command line tool.<br />
<br />
Some libraries depend on external C libraries, which are best installed with [http://macports.org MacPorts]. However, you have to tell cabal to include the <code>/opt/local/</code> directories when searching for external libraries. The following shell script does that by wrapping the <code>cabal</code> utility<br />
<br />
> cat cabal-macports<br />
#!/bin/bash<br />
export CPPFLAGS=-I/opt/local/include<br />
export LDFLAGS=-L/opt/local/lib<br />
cabal $@ --extra-include-dirs=/opt/local/include \<br />
--extra-lib-dirs=/opt/local/lib<br />
<br />
> cabal-macports install foobar<br />
<br />
== Editors with Haskell support ==<br />
<br />
=== Open Source ===<br />
<br />
* [http://aquamacs.org/ AquaMacs], a graphical Emacs version<br />
* [http://eclipsefp.sourceforge.net/ Eclipse] with the [http://eclipsefp.sourceforge.net/ EclipseFP] plugin<br />
* [http://www.gnu.org/software/emacs/ Emacs], is installed on every Mac<br />
* [http://leksah.org/ Leksah]<br />
* [http://code.google.com/p/macvim/ MacVim], a graphical Vim version<br />
* [http://www.vim.org/ Vim], is installed on every Mac<br />
* [http://haskell.org/haskellwiki/Yi Yi] (written in Haskell itself!), is available through cabal-install<br />
<br />
=== Commercial ===<br />
<br />
[http://www.codingmonkeys.de/subethaedit/ SubEthaEdit]:<br />
<br />
[[Image:SubEthaEdit.png]]<br />
<br />
[http://macromates.com/ TextMate]:<br />
<br />
[[Image:TextMate.png]]<br />
<br />
and [http://tuppis.com/smultron/ Smultron]:<br />
<br />
[[Image:Smultron.png]]<br />
<br />
TextEdit is Mac's default text editor, a very basic editor that works fine for most uses, you must however be careful to put it into plain text mode using the Format menu.<br />
<br />
== Shipping Installable Haskell Applications ==<br />
<br />
* [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/mkbndl mkbndl] builds installable Mac OSX applications from your Haskell project.<br />
<br />
== Links ==<br />
* [[Using Haskell in an Xcode Cocoa project]]; a description of how to add a Haskell module (callable from C) to an Xcode/Cocoa/Interface builder project on your Mac.<br />
* [[Mac OS X Common Installation Paths]]: an effort to standardize where things go on a Mac OS X installation<br />
[[Category:OS]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=GHC/Type_families&diff=33279GHC/Type families2010-01-25T06:45:42Z<p>Nedervold: fixed typo</p>
<hr />
<div>[[Category:GHC|Indexed types]]<br />
<br />
== What are type families? ==<br />
<br />
Indexed type families, or type families for short, are type constructors that represent ''sets of types.'' Set members are denoted by supplying the type family constructor with type parameters, which are called ''type indices''. The difference between vanilla parametrised type constructors and family constructors is much like between parametrically polymorphic functions and (ad-hoc polymorphic) methods of type classes. Parametric polymorphic functions behave the same at all type instances, whereas class methods can change their behaviour in dependence on the class type parameters. Similarly, vanilla type constructors imply the same data representation for all type instances, but family constructors can have varying representation types for varying type indices.<br />
<br />
Indexed type families come in two flavours: ''data families'' and ''type synonym families''. They are the indexed family variants of algebraic data types and type synonyms, respectively. The instances of data families can be data types and newtypes.<br />
<br />
== Type families in GHC ==<br />
<br />
Indexed type families are a new GHC extension to facilitate type-level programming. Type families are a generalisation of [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] and [http://www.cse.unsw.edu.au/~chak/papers/CKP05.html associated type synonyms], and are described in a [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html recent ICFP paper]. They essentially provide type-indexed data types and named functions on types, which are useful for generic programming and highly parameterised library interfaces as well as interfaces with enhanced static information, much like dependent types. They might also be regarded as an alternative to functional dependencies, but provide a more functional style of type-level programming than the relational style of functional dependencies.<br />
<br />
== What do I need to use type families? ==<br />
<br />
The first stable release of GHC that properly supports type families is 6.10.1. (An early partial implementation was part of the 6.8 release, but its use is deprecated.) Please [http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status=reopened&group=priority&type=bug&order=id&desc=1 report bugs] via the GHC bug tracker, ideally accompanied by a small example program that demonstrates the problem. Use the [mailto:glasgow-haskell-users@haskell.org GHC mailing list] for questions or for a discussion of this language extension and its description on this wiki page.<br />
<br />
== An associated data type example ==<br />
<br />
As an example, consider Ralf Hinze's [http://www.informatik.uni-bonn.de/~ralf/publications.html#J4 generalised tries], a form of generic finite maps. <br />
<br />
=== The class declaration ===<br />
<br />
We define a type class whose instances are the types that we can use as keys in our generic maps:<br />
<haskell><br />
class GMapKey k where<br />
data GMap k :: * -> *<br />
empty :: GMap k v<br />
lookup :: k -> GMap k v -> Maybe v<br />
insert :: k -> v -> GMap k v -> GMap k v<br />
</haskell><br />
The interesting part is the ''associated data family'' declaration of the class. It gives a [http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html#sec-kinding ''kind signature''] (here <hask>* -> *</hask>) for the associated data type <hask>GMap k</hask> - analog to how methods receive a type signature in a class declaration.<br />
<br />
What it is important to notice is that the first parameter of the associated type <hask>GMap</hask> coincides with the class parameter of <hask>GMapKey</hask>. This indicates that also in all instances of the class, the instances of the associated data type need to have their first argument match up with the instance type. In general, the type arguments of an associated type can be a subset of the class parameters (in a multi-parameter type class) and they can appear in any order, possibly in an order other than in the class head. The latter can be useful if the associated data type is partially applied in some contexts.<br />
<br />
The second important point is that as <hask>GMap k</hask> has kind <hask>* -> *</hask> and <hask>k</hask> (implicitly) has kind <hask>*</hask>, the type constructor <hask>GMap</hask> (without an argument) has kind <hask>* -> * -> *</hask>. Consequently, we see that <hask>GMap</hask> is applied to two arguments in the signatures of the methods <hask>empty</hask>, <hask>lookup</hask>, and <hask>insert</hask>.<br />
<br />
=== An Int instance ===<br />
<br />
To use Ints as keys into generic maps, we declare an instance that simply uses <hask>Data.Map</hask>, thusly:<br />
<haskell><br />
instance GMapKey Int where<br />
data GMap Int v = GMapInt (Data.Map.Map Int v)<br />
empty = GMapInt Data.Map.empty<br />
lookup k (GMapInt m) = Data.Map.lookup k m<br />
insert k v (GMapInt m) = GMapInt (Data.Map.insert k v m)<br />
</haskell><br />
The <hask>Int</hask> instance of the associated data type <hask>GMap</hask> needs to have both of its parameters, but as only the first one corresponds to a class parameter, the second needs to be a type variable (here <hask>v</hask>). As mentioned before, any associated type parameter that corresponds to a class parameter must be identical to the class parameter in each instance. The right hand side of the associated data declaration is like that of any other data type.<br />
<br />
NB: At the moment, GADT syntax is not allowed for associated data types (or other indexed types). This is not a fundamental limitation, but just a shortcoming of the current implementation, which we expect to lift in the future.<br />
<br />
As an exercise, implement an instance for <hask>Char</hask> that maps back to the <hask>Int</hask> instance using the conversion functions <hask>Char.ord</hask> and <hask>Char.chr</hask>.<br />
<br />
=== A unit instance ===<br />
<br />
Generic definitions, apart from elementary types, typically cover units, products, and sums. We start here with the unit instance for <hask>GMap</hask>:<br />
<haskell><br />
instance GMapKey () where<br />
data GMap () v = GMapUnit (Maybe v)<br />
empty = GMapUnit Nothing<br />
lookup () (GMapUnit v) = v<br />
insert () v (GMapUnit _) = GMapUnit $ Just v<br />
</haskell><br />
For unit, the map is just a <hask>Maybe</hask> value.<br />
<br />
=== Product and sum instances ===<br />
<br />
Next, let us define the instances for pairs and sums (i.e., <hask>Either</hask>):<br />
<haskell><br />
instance (GMapKey a, GMapKey b) => GMapKey (a, b) where<br />
data GMap (a, b) v = GMapPair (GMap a (GMap b v))<br />
empty = GMapPair empty<br />
lookup (a, b) (GMapPair gm) = lookup a gm >>= lookup b <br />
insert (a, b) v (GMapPair gm) = GMapPair $ case lookup a gm of<br />
Nothing -> insert a (insert b v empty) gm<br />
Just gm2 -> insert a (insert b v gm2 ) gm<br />
<br />
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where<br />
data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
empty = GMapEither empty empty<br />
lookup (Left a) (GMapEither gm1 _gm2) = lookup a gm1<br />
lookup (Right b) (GMapEither _gm1 gm2 ) = lookup b gm2<br />
insert (Left a) v (GMapEither gm1 gm2) = GMapEither (insert a v gm1) gm2<br />
insert (Right b) v (GMapEither gm1 gm2) = GMapEither gm1 (insert b v gm2)<br />
</haskell><br />
If you find this code algorithmically surprising, I'd suggest to have a look at [http://www.informatik.uni-bonn.de/~ralf/publications.html#J4 Ralf Hinze's paper]. The only novelty concerning associated types, in these two instances, is that the instances have a context <hask>(GMapKey a, GMapKey b)</hask>. Consequently, the right hand sides of the associated type declarations can use <hask>GMap</hask> recursively at the key types <hask>a</hask> and <hask>b</hask> - not unlike the method definitions use the class methods recursively at the types for which the class is given in the instance context.<br />
<br />
=== Using a generic map ===<br />
<br />
Finally, some code building and querying a generic map:<br />
<haskell><br />
myGMap :: GMap (Int, Either Char ()) String<br />
myGMap = insert (5, Left 'c') "(5, Left 'c')" $<br />
insert (4, Right ()) "(4, Right ())" $<br />
insert (5, Right ()) "This is the one!" $<br />
insert (5, Right ()) "This is the two!" $<br />
insert (6, Right ()) "(6, Right ())" $<br />
insert (5, Left 'a') "(5, Left 'a')" $<br />
empty<br />
main = putStrLn $ maybe "Couldn't find key!" id $ lookup (5, Right ()) myGMap<br />
</haskell><br />
<br />
=== Download the code ===<br />
<br />
If you want to play with this example without copying it off the wiki, just download the [http://darcs.haskell.org/testsuite/tests/ghc-regress/indexed-types/should_run/GMapAssoc.hs source code for <hask>GMap</hask>] from GHC's test suite.<br />
<br />
== Detailed definition of data families ==<br />
<br />
Data families appear in two flavours: (1) they can be defined on the toplevel or (2) they can appear inside type classes (in which case they are known as associated types). The former is the more general variant, as it lacks the requirement for the type-indices to coincide with the class parameters. However, the latter can lead to more clearly structured code and compiler warnings if some type instances were - possibly accidentally - omitted. In the following, we always discuss the general toplevel form first and then cover the additional constraints placed on associated types.<br />
<br />
=== Family declarations ===<br />
<br />
Indexed data families are introduced by a signature, such as <br />
<haskell><br />
data family GMap k :: * -> *<br />
</haskell><br />
The special <hask>family</hask> distinguishes family from standard data declarations. The result kind annotation is optional and, as usual, defaults to <hask>*</hask> if omitted. An example is<br />
<haskell><br />
data family Array e<br />
</haskell><br />
Named arguments can also be given explicit kind signatures if needed. Just as with [http://www.haskell.org/ghc/docs/latest/html/users_guide/gadt.html GADT declarations] named arguments are entirely optional, so that we can declare <hask>Array</hask> alternatively with<br />
<haskell><br />
data family Array :: * -> *<br />
</haskell><br />
<br />
==== Associated family declarations ====<br />
<br />
When a data family is declared as part of a type class, we drop the <hask>family</hask> keyword. The <hask>GMap</hask> declaration takes the following form<br />
<haskell><br />
class GMapKey k where<br />
data GMap k :: * -> *<br />
...<br />
</haskell><br />
In contrast to toplevel declarations, named arguments must be used for all type parameters that are to be used as type-indices. Moreover, the argument names must be class parameters. Each class parameter may only be used at most once per associated type, but some may be omitted and they may be in an order other than in the class head. In other words: '''the named type parameters of the data declaration must be a permutation of a subset of the class variables'''. <br />
<br />
Example is admissible:<br />
<haskell><br />
class C a b c where { data T c a :: * } -- OK<br />
class C a b c where { data T a a :: * } -- Bad: repeated variable<br />
class D a where { data T a x :: * } -- Bad: x is not a class variable<br />
class D a where { data T a :: * -> * } -- OK<br />
</haskell><br />
<br />
=== Instance declarations ===<br />
<br />
Instance declarations of data and newtype families are very similar to standard data and newtype declarations. The only two differences are that the keyword <hask>data</hask> or <hask>newtype</hask> is followed by <hask>instance</hask> and that some or all of the type arguments can be non-variable types, but may not contain forall types or type synonym families. However, data families are generally allowed in type parameters, and type synonyms are allowed as long as they are fully applied and expand to a type that is itself admissible - exactly as this is required for occurrences of type synonyms in class instance parameters. For example, the <hask>Either</hask> instance for <hask>GMap</hask> is<br />
<haskell><br />
data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
</haskell><br />
In this example, the declaration has only one variant. In general, it can be any number.<br />
<br />
Data and newtype instance declarations are only legit when an appropriate family declaration is in scope - just like class instances require the class declaration to be visible. Moreover, each instance declaration has to conform to the kind determined by its family declaration. This implies that the number of parameters of an instance declaration matches the arity determined by the kind of the family. Although all data families are declared with the <hask>data</hask> keyword, instances can be either <hask>data</hask> or <hask>newtype</hask>s, or a mix of both.<br />
<br />
Even if type families are defined as toplevel declarations, functions that perform different computations for different family instances still need to be defined as methods of type classes. In particular, the following is not possible:<br />
<haskell><br />
data family T a<br />
data instance T Int = A<br />
data instance T Char = B<br />
nonsense :: T a -> Int<br />
nonsense A = 1 -- WRONG: These two equations together...<br />
nonsense B = 2 -- ...will produce a type error.<br />
</haskell><br />
Given the functionality provided by GADTs (Generalised Algebraic Data Types), it might seem as if a definition, such as the above, should be feasible. However, type families - in contrast to GADTs - are ''open''; i.e., new instances can always be added, possibly in other modules. Supporting pattern matching across different data instances would require a form of extensible case construct.<br />
<br />
==== Associated type instances ====<br />
<br />
When an associated family instance is declared within a type class instance, we drop the <hask>instance</hask> keyword in the family instance. So, the <hask>Either</hask> instance for <hask>GMap</hask> becomes:<br />
<haskell><br />
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where<br />
data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v<br />
...<br />
</haskell><br />
The most important point about associated family instances is that the type indices corresponding to class parameters must be identical to the type given in the instance head; here this is the first argument of <hask>GMap</hask>, namely <hask>Either a b</hask>, which coincides with the only class parameter. Any parameters to the family constructor that do not correspond to class parameters, need to be variables in every instance; here this is the variable <hask>v</hask>.<br />
<br />
Instances for an associated family can only appear as part of instance declarations of the class in which the family was declared - just as with the equations of the methods of a class. Also in correspondence to how methods are handled, declarations of associated types can be omitted in class instances. If an associated family instance is omitted, the corresponding instance type is not inhabited; i.e., only diverging expressions, such as <hask>undefined</hask>, can assume the type.<br />
<br />
==== Scoping of class parameters ====<br />
<br />
In the case of multi-parameter type classes, the visibility of class parameters in the right-hand side of associated family instances depends ''solely'' on the parameters of the data family. As an example, consider the simple class declaration<br />
<haskell><br />
class C a b where<br />
data T a<br />
</haskell><br />
Only one of the two class parameters is a parameter to the data family. Hence, the following instance declaration is invalid:<br />
<haskell><br />
instance C [c] d where<br />
data T [c] = MkT (c, d) -- WRONG!! 'd' is not in scope<br />
</haskell><br />
Here, the right-hand side of the data instance mentions the type variable <hask>d</hask> that does not occur in its left-hand side. We cannot admit such data instances as they would compromise type safety.<br />
<br />
==== Type class instances of family instances ====<br />
<br />
Type class instances of instances of data families can be defined as usual, and in particular data instance declarations can have <hask>deriving</hask> clauses. For example, we can write<br />
<haskell><br />
data GMap () v = GMapUnit (Maybe v)<br />
deriving Show<br />
</haskell><br />
which implicitly defines an instance of the form<br />
<haskell><br />
instance Show v => Show (GMap () v) where ...<br />
</haskell><br />
<br />
Note that class instances are always for particular ''instances'' of a data family and never for an entire family as a whole. This is for essentially the same reasons that we cannot define a toplevel function that performs pattern matching on the data constructors of ''different'' instances of a single type family. It would require a form of extensible case construct.<br />
<br />
==== Overlap ====<br />
<br />
The instance declarations of a data family used in a single program may not overlap at all, independent of whether they are associated or not. In contrast to type class instances, this is not only a matter of consistency, but one of type safety.<br />
<br />
=== Import and export ===<br />
<br />
The association of data constructors with type families is more dynamic than that is the case with standard data and newtype declarations. In the standard case, the notation <hask>T(..)</hask> in an import or export list denotes the type constructor and all the data constructors introduced in its declaration. However, a family declaration never introduces any data constructors; instead, data constructors are introduced by family instances. As a result, which data constructors are associated with a type family depends on the currently visible instance declarations for that family. Consequently, an import or export item of the form <hask>T(..)</hask> denotes the family constructor and all currently visible data constructors - in the case of an export item, these may be either imported or defined in the current module. The treatment of import and export items that explicitly list data constructors, such as <hask>GMap(GMapEither)</hask>, is analogous.<br />
<br />
==== Associated families ====<br />
<br />
As expected, an import or export item of the form <hask>C(..)</hask> denotes all of the class' methods and associated types. However, when associated types are explicitly listed as subitems of a class, we need some new syntax, as uppercase identifiers as subitems are usually data constructors, not type constructors. To clarify that we denote types here, each associated type name needs to be prefixed by the keyword <hask>type</hask>. So for example, when explicitly listing the components of the <hask>GMapKey</hask> class, we write <hask>GMapKey(type GMap, empty, lookup, insert)</hask>.<br />
<br />
==== Examples ====<br />
<br />
Assuming our running <hask>GMapKey</hask> class example, let us look at some export lists and their meaning:<br />
<br />
* <hask>module GMap (GMapKey) where...</hask>: Exports just the class name.<br />
* <hask>module GMap (GMapKey(..)) where...</hask>: Exports the class, the associated type <hask>GMap</hask> and the member functions <hask>empty</hask>, <hask>lookup</hask>, and <hask>insert</hask>. None of the data constructors is exported.<br />
* <hask>module GMap (GMapKey(..), GMap(..)) where...</hask>: As before, but also exports all the data constructors <hask>GMapInt</hask>, <hask>GMapChar</hask>, <hask>GMapUnit</hask>, <hask>GMapPair</hask>, and <hask>GMapEither</hask>.<br />
* <hask>module GMap (GMapKey(empty, lookup, insert), GMap(..)) where...</hask>: As before.<br />
* <hask>module GMap (GMapKey, empty, lookup, insert, GMap(..)) where...</hask>: As before.<br />
<br />
Finally, you can write <hask>GMapKey(type GMap)</hask> to denote both the class <hask>GMapKey</hask> as well as its associated type <hask>GMap</hask>. However, you cannot write <hask>GMapKey(type GMap(..))</hask> &mdash; i.e., sub-component specifications cannot be nested. To specify <hask>GMap</hask>'s data constructors, you have to list it separately.<br />
<br />
==== Instances ====<br />
<br />
Family instances are implicitly exported, just like class instances. However, this applies only to the heads of instances, not to the data constructors an instance defines.<br />
<br />
== An associated type synonym example ==<br />
<br />
Type synonym families are an alternative to functional dependencies, which makes functional dependency examples well suited to introduce type synonym families. In fact, type families are a more functional way to express the same as functional dependencies (despite the name!), as they replace the relational notation of functional dependencies by an expression-oriented notation; i.e., functions on types are really represented by functions and not relations.<br />
<br />
=== The <hask>class</hask> declaration ===<br />
<br />
Here's an example from Mark Jones' seminal paper on functional dependencies:<br />
<haskell><br />
class Collects e ce | ce -> e where<br />
empty :: ce<br />
insert :: e -> ce -> ce<br />
member :: e -> ce -> Bool<br />
toList :: ce -> [e]<br />
</haskell><br />
<br />
With associated type synonyms we can write this as<br />
<haskell><br />
class Collects ce where<br />
type Elem ce<br />
empty :: ce<br />
insert :: Elem ce -> ce -> ce<br />
member :: Elem ce -> ce -> Bool<br />
toList :: ce -> [Elem ce]<br />
</haskell><br />
Instead of the multi-parameter type class, we use a single parameter class, and the parameter <hask>e</hask><br />
turned into an associated type synonym <hask>Elem ce</hask>.<br />
<br />
=== An <hask>instance</hask>===<br />
<br />
Instances change correspondingly. An instance of the two-parameter class<br />
<haskell><br />
instance Eq e => Collects e [e] where<br />
empty = []<br />
insert e l = (e:l)<br />
member e [] = False<br />
member e (x:xs) <br />
| e == x = True<br />
| otherwise = member e xs<br />
toList l = l<br />
</haskell><br />
becomes an instance of a single-parameter class, where the dependent type parameter turns into an associated type instance declaration:<br />
<haskell><br />
instance Eq e => Collects [e] where<br />
type Elem [e] = e<br />
empty = []<br />
insert e l = (e:l)<br />
member e [] = False<br />
member e (x:xs) <br />
| e == x = True<br />
| otherwise = member e xs<br />
toList l = l<br />
</haskell><br />
<br />
=== Using generic collections ===<br />
<br />
With Functional Dependencies the code would be:<br />
<haskell><br />
sumCollects :: (Collects e c1, Collects e c2) => c1 -> c2 -> c2<br />
sumCollects c1 c2 = foldr insert c2 (toList c1)<br />
</haskell><br />
<br />
In contrast, with associated type synonyms, we get:<br />
<haskell><br />
sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2<br />
sumCollects c1 c2 = foldr insert c2 (toList c1)<br />
</haskell><br />
<br />
== Detailed definition of type synonym families ==<br />
<br />
Type families appear in two flavours: (1) they can be defined on the toplevel or (2) they can appear inside type classes (in which case they are known as associated type synonyms). The former is the more general variant, as it lacks the requirement for the type-indices to coincide with the class parameters. However, the latter can lead to more clearly structured code and compiler warnings if some type instances were - possibly accidentally - omitted. In the following, we always discuss the general toplevel form first and then cover the additional constraints placed on associated types.<br />
<br />
=== Family declarations ===<br />
<br />
Indexed type families are introduced by a signature, such as <br />
<haskell><br />
type family Elem c :: *<br />
</haskell><br />
The special <hask>family</hask> distinguishes family from standard type declarations. The result kind annotation is optional and, as usual, defaults to <hask>*</hask> if omitted. An example is<br />
<haskell><br />
type family Elem c<br />
</haskell><br />
Parameters can also be given explicit kind signatures if needed. We call the number of parameters in a type family declaration, the family's arity, and all applications of a type family must be fully saturated w.r.t. to that arity. This requirement is unlike ordinary type synonyms and it implies that the kind of a type family is not sufficient to determine a family's arity, and hence in general, also insufficient to determine whether a type family application is well formed. As an example, consider the following declaration:<br />
<haskell><br />
type family F a b :: * -> * -- F's arity is 2, <br />
-- although its overall kind is * -> * -> * -> *<br />
</haskell><br />
Given this declaration the following are examples of well-formed and malformed types:<br />
<haskell><br />
F Char [Int] -- OK! Kind: * -> *<br />
F Char [Int] Bool -- OK! Kind: *<br />
F IO Bool -- WRONG: kind mismatch in the first argument<br />
F Bool -- WRONG: unsaturated application<br />
</haskell><br />
<br />
==== Associated family declarations ====<br />
<br />
When a type family is declared as part of a type class, we drop the <hask>family</hask> special. The <hask>Elem</hask> declaration takes the following form<br />
<haskell><br />
class Collects ce where<br />
type Elem ce :: *<br />
...<br />
</haskell><br />
Exactly as in the case of an associated data declaration, '''the named type parameters must be a permutation of a subset of the class parameters'''. Examples<br />
<haskell><br />
class C a b c where { type T c a :: * } -- OK<br />
class D a where { type T a x :: * } -- No: x is not a class parameter<br />
class D a where { type T a :: * -> * } -- OK<br />
</haskell><br />
<br />
=== Instance declarations ===<br />
<br />
Instance declarations of type families are very similar to standard type synonym declarations. The only two differences are that the keyword <hask>type</hask> is followed by <hask>instance</hask> and that some or all of the type arguments can be non-variable types, but may not contain forall types or type synonym families. However, data families are generally allowed, and type synonyms are allowed as long as they are fully applied and expand to a type that is admissible - these are the exact same requirements as for data instances. For example, the <hask>[e]</hask> instance for <hask>Elem</hask> is<br />
<haskell><br />
type instance Elem [e] = e<br />
</haskell><br />
<br />
A type family instance declaration must satisfy the following rules:<br />
* An appropriate family declaration is in scope - just like class instances require the class declaration to be visible. <br />
* The instance declaration conforms to the kind determined by its family declaration<br />
* The number of type parameters in an instance declaration matches the number of type parameters in the family declaration.<br />
* The right-hand side of a type instance must be a monotype (i.e., it may not include foralls) and after the expansion of all saturated vanilla type synonyms, no synonyms, except family synonyms may remain.<br />
<br />
Here are some examples of admissible and illegal type instances:<br />
<haskell><br />
type family F a :: *<br />
type instance F [Int] = Int -- OK!<br />
type instance F String = Char -- OK!<br />
type instance F (F a) = a -- WRONG: type parameter mentions a type family<br />
type instance F (forall a. (a, b)) = b -- WRONG: a forall type appears in a type parameter<br />
type instance F Float = forall a.a -- WRONG: right-hand side may not be a forall type<br />
<br />
type family G a b :: * -> *<br />
type instance G Int = (,) -- WRONG: must be two type parameters<br />
type instance G Int Char Float = Double -- WRONG: must be two type parameters<br />
</haskell><br />
<br />
==== Associated type instances ====<br />
<br />
When an associated family instance is declared within a type class instance, we drop the <hask>instance</hask> keyword in the family instance. So, the <hask>[e]</hask> instance for <hask>Elem</hask> becomes:<br />
<haskell><br />
instance (Eq (Elem [e])) => Collects ([e]) where<br />
type Elem [e] = e<br />
...<br />
</haskell><br />
The most important point about associated family instances is that the type indexes corresponding to class parameters must be identical to the type given in the instance head; here this is <hask>[e]</hask>, which coincides with the only class parameter.<br />
<br />
Instances for an associated family can only appear as part of instance declarations of the class in which the family was declared - just as with the equations of the methods of a class. Also in correspondence to how methods are handled, declarations of associated types can be omitted in class instances. If an associated family instance is omitted, the corresponding instance type is not inhabited; i.e., only diverging expressions, such as <hask>undefined</hask>, can assume the type.<br />
<br />
==== Overlap ====<br />
<br />
The instance declarations of a type family used in a single program may only overlap if the right-hand sides of the overlapping instances coincide for the overlapping types. More formally, two instance declarations overlap if there is a substitution that makes the left-hand sides of the instances syntactically the same. Whenever that is the case, the right-hand sides of the instances must also be syntactically equal under the same substitution. This condition is independent of whether the type family is associated or not, and it is not only a matter of consistency, but one of type safety.<br />
<br />
Here are two examples to illustrate the condition under which overlap is permitted.<br />
<haskell><br />
type instance F (a, Int) = [a]<br />
type instance F (Int, b) = [b] -- overlap permitted<br />
<br />
type instance G (a, Int) = [a]<br />
type instance G (Char, a) = [a] -- ILLEGAL overlap, as [Char] /= [Int]<br />
</haskell><br />
<br />
==== Decidability ====<br />
<br />
In order to guarantee that type inference in the presence of type families is decidable, we need to place a number of additional restrictions on the formation of type instance declarations (c.f., Definition 5 (Relaxed Conditions) of [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html Type Checking with Open Type Functions]). Instance declarations have the general form<br />
<haskell><br />
type instance F t1 .. tn = t<br />
</haskell><br />
where we require that for every type family application <hask>(G s1 .. sm)</hask> in <hask>t</hask>, <br />
# <hask>s1 .. sm</hask> do not contain any type family constructors,<br />
# the total number of symbols (data type constructors and type variables) in <hask>s1 .. sm</hask> is strictly smaller than in <hask>t1 .. tn</hask>, and<br />
# for every type variable <hask>a</hask>, <hask>a</hask> occurs in <hask>s1 .. sm</hask> at most as often as in <hask>t1 .. tn</hask>.<br />
These restrictions are easily verified and ensure termination of type inference. However, they are not sufficient to guarantee completeness of type inference in the presence of, so called, ''loopy equalities'', such as <hask>a ~ [F a]</hask>, where a recursive occurrence of a type variable is underneath a family application and data constructor application - see the above mentioned paper for details. <br />
<br />
If the option <tt>-XUndecidableInstances</tt> is passed to the compiler, the above restrictions are not enforced and it is on the programmer to ensure termination of the normalisation of type families during type inference.<br />
<br />
=== Equality constraints ===<br />
<br />
Type context can include equality constraints of the form <hask>t1 ~ t2</hask>, which denote that the types <hask>t1</hask> and <hask>t2</hask> need to be the same. In the presence of type families, whether two types are equal cannot generally be decided locally. Hence, the contexts of function signatures may include equality constraints, as in the following example:<br />
<haskell><br />
sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2<br />
</haskell><br />
where we require that the element type of <hask>c1</hask> and <hask>c2</hask> are the same. In general, the types <hask>t1</hask> and <hask>t2</hask> of an equality constraint may be arbitrary monotypes; i.e., they may not contain any quantifiers, independent of whether higher-rank types are otherwise enabled.<br />
<br />
Equality constraints can also appear in class and instance contexts. The former enable a simple translation of programs using functional dependencies into programs using family synonyms instead. The general idea is to rewrite a class declaration of the form<br />
<haskell><br />
class C a b | a -> b<br />
</haskell><br />
to<br />
<haskell><br />
class (F a ~ b) => C a b where<br />
type F a<br />
</haskell><br />
That is, we represent every functional dependency (FD) <hask>a1 .. an -> b</hask> by an FD type family <hask>F a1 .. an</hask> and a superclass context equality <hask>F a1 .. an ~ b</hask>, essentially giving a name to the functional dependency. In class instances, we define the type instances of FD families in accordance with the class head. Method signatures are not affected by that process.<br />
<br />
NB: Equalities in superclass contexts are not fully implemented in the GHC 6.10 branch.<br />
<br />
== Frequently asked questions ==<br />
<br />
=== Injectivity, type inference, and ambiguity ===<br />
<br />
A common problem is this<br />
<haskell><br />
type family F a<br />
<br />
f :: F a -> F a<br />
f = undefined<br />
<br />
g :: F Int -> F Int<br />
g x = f x<br />
</haskell><br />
The compiler complains about the definition of <tt>g</tt> saying<br />
<haskell><br />
Couldn't match expected type `F Int' against inferred type `F a1'<br />
</haskell><br />
In type-checking <tt>g</tt>'s right hand side GHC discovers (by instantiating f's type with a fresh type variable) that it has type <tt>F a1 -> F a1</tt> for some as-yet-unknown type <tt>a1</tt>. Now it tries to make the inferred type match <tt>g</tt>'s type signature. Well, you say, just make <haskell>a1</haskell> equal to <tt>Int</tt> and you are done. True, but what if there were these instance<br />
<haskell><br />
type instance F Int = Bool<br />
type instance F Char = Bool<br />
</haskell><br />
Then making <tt>a1</tt> equal to <tt>Char</tt> would ''also'' make the two types equal. Because there is more than one choice, the program is rejected.<br />
<br />
The difficulty is that the type function <tt>F</tt> need not be ''injective''; it can map two distinct types to the same type. For an injective type constructor like <tt>Maybe</tt>, if we know that <tt>Maybe t1</tt> = <tt>Maybe t2</tt>, then we know that <tt>t1</tt> = <tt>t2</tt>. But not so for non-injective type functions.<br />
<br />
The problem starts with <tt>f</tt>. Its type is ''ambiguous''; even if I know the argument and result types for <tt>f</tt>, I cannot use that to find the type at which <tt>a</tt> should be instantiated. (So arguably, <tt>f</tt> should be rejected as having an ambiguous type, and probably will be in future.) The situation is well known in type classes: <br />
<haskell><br />
bad :: (Read a, Show a) => String -> String<br />
bad x = show (read x)<br />
</haskell><br />
At a call of <tt>bad</tt> one cannot tell at what type <tt>a</tt> should be instantiated.<br />
<br />
The only solution is to avoid ambiguous types. In the type signature of a function, <br />
* Ensure that every type variable occurs in the part after the "<tt>=></tt>"<br />
* Ensure that every type variable appears at least once outside a type function call. <br />
<br />
Even then ambiguity is possible. For example:<br />
<haskell><br />
f :: F a -> [a] <br />
f = undefined<br />
<br />
g :: F b -> Int<br />
g x = length (f x)<br />
</haskell><br />
Although <tt>f</tt>'s type is unambiguous, its result type is swallowed up by <tt>length</tt>, which now makes <tt>g</tt>'s type ambiguous.<br />
<br />
== References ==<br />
<br />
* [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html Associated Types with Class.] Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. In ''Proceedings of The 32nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'05)'', pages 1-13, ACM Press, 2005.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/CKP05.html Associated Type Synonyms.] Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. In ''Proceedings of The Tenth ACM SIGPLAN International Conference on Functional Programming'', ACM Press, pages 241-253, 2005.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/SCPD07.html System F with Type Equality Coercions.] Martin Sulzmann, Manuel M. T. Chakravarty, Simon Peyton Jones, and Kevin Donnelly. In ''Proceedings of The Third ACM SIGPLAN Workshop on Types in Language Design and Implementation'', ACM Press, 2007.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html Type Checking With Open Type Functions.] Tom Schrijvers, Simon Peyton-Jones, Manuel M. T. Chakravarty, Martin Sulzmann. In ''Proceedings of The 13th ACM SIGPLAN International Conference on Functional Programming'', ACM Press, pages 51-62, 2008.<br />
<br />
[[Category:Type-level programming]]<br />
[[Category:Language extension]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Functional_programming&diff=31843Functional programming2009-11-24T07:36:15Z<p>Nedervold: some rewording</p>
<hr />
<div>'''Functional programming''' is a style of programming which—unlike '''imperative programming'''—models computations as the evaluation of expressions. This article is meant to describe it briefly; however, the best way to understand functional programming is to learn the basics of one of the functional programming languages ([[Haskell in 5 steps|learn Haskell]]).<br />
<br />
You can find an old version of this page [[Functional programming/Old version|here]].<br />
<br />
==What is functional programming?==<br />
'''Functional programming''' means that programs are executed by evaluating '''expressions'''. This contrasts with '''imperative programming''' where programs are composed of '''statements''' which change global '''state''' when executed. Functional programming, on the other hand, avoids using state and mutable data.<br />
<br />
Functional programming requires that functions are '''first-class''', which means that they are treated like any other values and can be passed as arguments to other functions or be returned as a result of a function. Being first-class also means that it is possible to define and manipulate functions '''nested''' in code blocks. Special attention needs to be given to nested functions, called '''[[closure]]s''', that reference local variables from their scope. If such a function '''escapes''' their block after being returned from it, the '''local variables''' must be '''retained''' in memory, as they might be needed later when the function is called. Usually it is not possible to determine statically the moment of release, which means that an automatic [[memory management]] technique has to be used.<br />
<br />
==Functional vs imperative languages==<br />
<br />
Many programming languages support programming in both functional and imperative style but each language has '''syntax''' and facilities that are optimised only for one of these styles. Often, code written in one particular style is executed more efficiently by the implementation than if written in the other. In addition to that, coding conventions and libraries often force the programmer towards one of the styles. Therefore, programming languages are categorized into functional and imperative ones.<br />
<br />
The following table shows which languages support functional programming (by supporting closures) and for which the functional style is the dominant one.<br />
{| class="wikitable"<br />
|-<br />
! Language<br />
! Closures<br />
! Functional<br />
|-<br />
! C/C++<br />
| No || No<br />
|-<br />
! Pascal<br />
| No || No<br />
|-<br />
! Java<br />
| Yes || No<br />
|-<br />
! Modula-3<br />
| Yes || No<br />
|-<br />
! Python<br />
| Yes || No<br />
|-<br />
! Ruby<br />
| Yes || No<br />
|-<br />
! D (2.0)<br />
| Yes || No<br />
|-<br />
! Ocaml<br />
| Yes || Yes<br />
|-<br />
! Erlang<br />
| Yes || Yes<br />
|-<br />
! Haskell<br />
| Yes || Yes<br />
|}<br />
<br />
==Features of functional languages==<br />
===Higher-order functions===<br />
[[Higher order function|Higher-order function]]s ('''HOFs''') are functions that take other functions as their arguments. A basic example of a HOF is <hask>map</hask> which takes a function and a list as its arguments, applies the function to all elements of the list and returns the list of its results. For instance, we can write a function that subtracts 2 from all elements of a list without using loops or recursion:<br />
<haskell><br />
subtractTwoFromList l = map (\x -> x - 2) l<br />
</haskell><br />
We can generalize this function to subtract any given number:<br />
<haskell><br />
subtractFromList l y = map (\x -> x - y) l<br />
</haskell><br />
The function given to <hask>map</hask> then becomes a [[closure]] because <hask>\x -> x - y</hask> references a local variable <hask>y</hask> from outside its body.<br />
<br />
Higher-order functions are very useful for refactoring code and reduce the amount of repetition. For example, typically most ''for'' loops can be expressed using maps or [[fold]]s. Custom iteration schemes, such as parallel loops, can be easily expressed using HOFs.<br />
<br />
Higher-order functions are often used to implement '''[[Embedded domain specific language|domain-specific languages]]''' embedded in Haskell as '''combinator libraries'''.<br />
<br />
Higher-order functions can be usually simulated in object-oriented languages by functions that take ''function-objects'', also called ''functors'' (note that [[functor]] in Haskell is an entirely different concept). Variables from the scope of the call can be bound inside the function-object which acts as if it were a closure. This way of simulating HOFs is, however, very verbose and requires declaring a new class each time we want to use a HOF.<br />
<br />
===Purity===<br />
Some functional languages allow expressions to yield actions in addition to return values. These actions are called '''side effects''' to emphasize that the return value is the most important outcome of a function (as opposed to the case in imperative programming). Languages that prohibit side effects are called '''pure'''. Even though some functional languages are impure they often contain a '''pure subset''' that is also useful as a programming language. It is usually beneficial to write a significant part of a functional program in a purely functional fashion and keep the code involving state and I/O to the minimum as impure code is more prone to errors.<br />
<br />
====Immutable data====<br />
Purely functional programmes operate only on '''immutable''' data. This is possible because on each modification a new version of a data structure is created and the old one is preserved. Therefore, data structures are '''persistent''' as it is possible to refer also to old versions of them. If there are no more references to the old version the unreferred data can be collected by automatic [[memory management]], such as a garbage collector. Often, bigger data structures '''share''' their parts between versions and so do not consume as much memory as they would if all versions were stored separately.<br />
<br />
====Referential transparency====<br />
Pure computations yield the same value each time they are invoked. This property is called '''[[referential transparency]]''' and makes possible to conduct '''equational reasoning''' on the code. For instance if <hask>y = f x</hask> and <hask>g = h y y</hask> then we should be able to replace the definition of <hask>g</hask> with <hask>g = h (f x) (f x)</hask> and get the same result; only the efficiency might change.<br />
<br />
====Lazy evaluation====<br />
Since pure computations are referentially transparent they can be performed at any time and still yield the same result. This makes it possible to defer the computation of values until they are needed, that is, to compute them ''lazily''. '''[[Lazy evaluation]]''' avoids unnecessary computations and allows, for instance, to create '''lazy data structures''' that are built on the fly.<br />
<br />
====Purity and effects====<br />
Even though purely functional programming is very beneficial, the programmer might want to use features that are not available in pure programs, like efficient mutable arrays or convenient I/O. There are two approaches to this problem.<br />
<br />
=====Side effects in the language=====<br />
Some functional languages extend their purely functional core with side effects. The programmer must be careful not to use impure functions in places where only pure functions are expected.<br />
<br />
=====Side effects through monads=====<br />
Another way of introducing side effects to a pure language is to simulate them using [[monad]]s. While the language remains pure and referentially transparent, monads can provide implicit state by threading it inside them. The compiler does not even have to 'know' about the imperative features because the language itself remains pure, however usually the implementations do 'know' about them due to the efficiency reasons, for instance to provide <math>O(1)</math> mutable arrays.<br />
<br />
Allowing side effects only through monads and keeping the language pure makes it possible to have lazy evaluation that does not conflict with the effects of impure code. Even though the expressions are evaluated lazily, some parts of them are '''forced''' by monads to be evaluated in a specific order and the effects are properly '''sequenced'''.<br />
<br />
===Recursion===<br />
'''Recursion''' is heavily used in functional programming as it is the canonical and often the only way to '''iterate'''. Loops are naturally expressed using '''tail recursion'''.<br />
<br />
==Benefits of functional programming==<br />
Functional programming is known to provide better support for '''structured programming''' than imperative programming. To make a program structured it is necessary to develop '''abstractions''' and split it into '''components''' which interface each other with those abstractions. Functional languages aid this by making it easy to create clean and simple abstractions. It is easy, for instance, to '''abstract out''' a recurring piece of code by creating a higher-order function which will make the resulting code more '''declarative''' and comprehensible.<br />
<br />
Functional programs are often shorter and easier to understand than their imperative counterparts. Since various studies have shown that the average programmer's productivity in terms of lines of code is more or less the same for any programming language, this translates also to higher productivity.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Control-Engine&diff=29562Control-Engine2009-08-15T13:29:17Z<p>Nedervold: removed unneeded escaping of angle brackets within haskell tags</p>
<hr />
<div>== Introduction ==<br />
The control-engine package provides two threadpool implementations and helper functions allowing for serial and parallel operations before and after the main function in addition to managed state and the capability to inject tasks anywhere in the chain. Source code is available from hackage[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Control-Engine].<br />
<br />
== Thread Pools from the Control-Engine Package ==<br />
Control-Engine was recently released on hackage, providing a simple way to instantiate worker threads to split-up the processing of streaming data. Its was originally developed as a spin-off library from my DHT and I've since generalized it to cover numerous cases.<br />
<br />
== Trivial Thread Pools ==<br />
The trivial module Control.ThreadPool can cover static examples; here we will simply count the lines in various files (and hashing them would be just as easy). This example uses only the base packages and Control-Engine:<br />
<br />
<haskell><br />
import Control.ThreadPool (threadPoolIO)<br />
import System.IO (openFile, IOMode(..))<br />
import System.Environment (getArgs)<br />
import Control.Concurrent.Chan<br />
import Control.Monad (forM_)<br />
import qualified Data.ByteString.Lazy.Char8 as L<br />
<br />
main = do<br />
as <- getArgs<br />
</haskell><br />
<br />
As you can see below, we simply say how many threads we want in our thread pool and what action (or pure computation, using 'threadPool') we wish to perform. After that its just channels - send input in and read results out!<br />
<br />
<haskell><br />
(input,output) <- threadPoolIO nrCPU op<br />
mapM_ (writeChan input) as -- input stream<br />
forM_ [1..length as] (\_ -> readChan output >>= print)<br />
where<br />
nrCPU = 4<br />
op f = do<br />
h <- openFile f ReadMode<br />
c <- L.hGetContents h<br />
let !x = length . L.words $ c<br />
hClose h<br />
return (f,x)<br />
</haskell><br />
<br />
And while this does nothing to demonstrate paralellism, it does work:<br />
<br />
<haskell><br />
[tom@Mavlo Test]$ ghc -O2 parLines.hs --make -threaded -fforce-recomp<br />
[1 of 1] Compiling Main ( web.hs, web.o )<br />
Linking web ...<br />
[tom@Mavlo Test]$ find ~/dev/Pastry -name *lhs | xargs ./parLines +RTS -N4 -RTS<br />
("/home/tom/dev/Pastry/Network/Pastry/Module/Joiner.lhs",107)<br />
("/home/tom/dev/Pastry/Network/Pastry/Config.lhs",14)<br />
("/home/tom/dev/Pastry/Network/Pastry/Data/LeafSet.lhs",120)<br />
("/home/tom/dev/Pastry/Network/Pastry/Data/Router.lhs",87)<br />
("/home/tom/dev/Pastry/Network/Pastry/Data/RouteTable.lhs",75)<br />
("/home/tom/dev/Pastry/Network/Pastry/Data/Address.lhs",152)</blockquote><br />
</haskell><br />
<br />
== Control Engine Setup ==<br />
The thread pools are simple, but what if you need more flexibility or power? What happens if you want to have an up-to-date state shared amoung the threads, or there's a non-paralizable cheap computation you need to perform before the main operation? The answer is to use Control.Engine instead of Control.ThreadPool. The engine provides managed state, numerous hook location, and an abilty to inject information to mid-engine locations.<br />
<br />
http://tommd.wordpress.com/files/2009/03/controlengine.png<br />
<br />
=== Injectors ===<br />
The inject* calls can bypass the input hooks (injectPreMutator) or bypass everything besides the output hooks (injectPostMutator) - thus creating a 'result' that had no corrosponding 'job'.<br />
<br />
=== Hooks ===<br />
Hooks are capable of modifying or filtering jobs or results. All hooks are of type <em>state -&gt; a -&gt; IO (Maybe a)</em>; its important to note the type can not change and if a hook returns Nothing then the job or result stops there.<br />
<br />
Hooks can either be input, pre-mutate, post-mutate, or output. Input and output hooks are ran in series on all jobs or results respectively; this is intended for low computation tasks that shouldn't be done in parallel later. Pre and post mutate hooks happen on the (parallel) worker threads before and after the main task, called the mutator.<br />
<br />
=== Mutator ===<br />
The engine consists of N worker threads presumably with the bulk of the work involving running the mutator action on the available jobs. This is the only operation capable of transforming the jobs into the different (result) type.<br />
<br />
=== State Management ===<br />
Control.Engine was built with the idea that jobs and state reads were frequent while alterations to the state were rare. A design decision was made to use STM to resolve all contention on state alterations and have a manager watch the TVar for change then bundle those changes in a quicker to read fashion (MVar) for the input, output, and worker threads.<br />
<br />
The state provided to the hooks and mutator is always consistent but not guarenteed up-to-date. When modifications to the state occur a transactional variable is modified, which wakes the <em>stateManager</em>; in turn, the state manager updates the state MVar which is read by each thread before processing the next job. In the future IORefs might be used instead of the MVar - all contention is handled by the STM and the only writer for the MVar (future IORef) should be the State Manager.<br />
<br />
== Web Crawling ==<br />
Now lets figure out how to help users who need more flexibility using Control.Engine instead of Control.ThreadPool.<br />
<br />
MyCatVerbs, from #haskell, suggested a web crawler that uses URls as the job and the mutator (worker) can add all the links of the current page as new jobs while ignoring any URL that was already visited. Lets start!<br />
<br />
The imports aren't too surprising - tagsoup, concurrent, bloomfilter and Control-Engine are the packages I draw on.<br />
<br />
<haskell><br />
module Main where<br />
<br />
import Control.Concurrent (forkIO, threadDelay)<br />
import Control.Concurrent.Chan<br />
import Control.Monad (forever, when)<br />
import Control.Engine -- Control-Engine<br />
import Control.Exception as X<br />
import Data.BloomFilter -- bloomfilter<br />
import Data.BloomFilter.Hash -- bloomfilter<br />
import Data.BloomFilter.Easy -- bloomfilter<br />
import Data.IORef<br />
import System.Environment (getArgs)<br />
import Text.HTML.Download -- tagsoup<br />
import Text.HTML.TagSoup -- tagsoup<br />
<br />
type URL = String<br />
<br />
data Job = GetURL URL | ParseHTML URL String deriving (Eq, Ord, Show)<br />
<br />
main = do<br />
(nrCPU:url:_) <- getArgs<br />
</haskell><br />
<br />
The library tries to remain flexible which makes you do a little more work but don't let that scare you! It needs an IO action to get tasks and an IO action that delivers the results. Most people will probably just want a channel, but sockets or files would do just as well.<br />
<br />
<haskell><br />
input <- newChan<br />
output <- newChan<br />
</haskell><br />
<br />
Starting the engine is a one line affair. You provide the number of threads, input, output, a mutator function and initial state. In return you are provided with an 'Engine' with which you can modify the hooks and use the injection points.<br />
<br />
For this web crawler my 'state' is just a bloom filter of all visited URLs so I'll keep that in the one hook its needed and declare the engine-wide state as a null - <b>()</b>. For the chosen task the mutator needs a way to add more jobs (more URLs) so as pages are parsed any new URLs can be queued for future crawling; this is handled via partial application of mutator funciton.<br />
<br />
<haskell><br />
eng <- initEngine (read nrCPU) (readChan input) (writeChan output) (mutator (writeChan input)) ()<br />
</haskell><br />
<br />
As mentioned, I'll use a bloom filter to keep the web crawler from re-visiting the same site many times. This should happen exactly once for each URL and is fairly fast so I'll insert it as an 'Input Hook' which means a single thread will process all jobs before they get parsed out to the parallel thread pool.<br />
<br />
<haskell><br />
let initialBF = fromListB (cheapHashes nrHashes) nrBits []<br />
(nrBits, nrHashes) = suggestSizing 100000 (10 ** (-6))<br />
bf <- newIORef (initialBF,0)<br />
let bfHook = Hk (uniqueURL bf) 1 "Ensure URLs have not already been crawled"<br />
addInputHook eng bfHook<br />
</haskell><br />
<br />
Finishing up main, we print all results then provide an initial URL. Notice we run forever - there's no clean shutdown in this toy example.<br />
<br />
<haskell><br />
forkIO $ forever $ printResult output<br />
writeChan input (GetURL url)<br />
neverStop eng<br />
where<br />
neverStop eng = forever $ threadDelay maxBound<br />
</haskell><br />
<br />
And from here on we're just providing the worker routine that will run across all the threads and we'll define the input hook. <a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tagsoup">TagSoup</a> performs all the hard work of downloading the page and parsing HTML. Just pull out the &lt;a href="..."&gt; tags to add the new URLs as jobs before returning any results. In this example I decided to avoid any sort of error checking (ex: making sure this is an HTML document) and simply returning the number of words as a result.<br />
<br />
<haskell><br />
mutator :: (Job -> IO ()) -> st -> Job -> IO (Maybe (URL,Int))<br />
mutator addJob _ (GetURL url) = forkIO (do<br />
e <- X.try (openURL url) :: IO (Either X.SomeException String)<br />
case e of<br />
Right dat -> addJob (ParseHTML url dat)<br />
_ -> return () )<br />
>> return Nothing<br />
mutator addJob _ (ParseHTML url dat) = do<br />
let !urls = getURLs dat<br />
!len = length urls<br />
fixed = map (\u -> if take 4 u /= "http" then url ++ '/' : u else u) urls<br />
mapM_ (addJob . GetURL) fixed<br />
return $ Just (url,len)<br />
where<br />
getURLs :: String -> [URL]<br />
getURLs s = <br />
let tags = parseTags s<br />
in map snd (concatMap hrefs tags)<br />
hrefs :: Tag -> [(String,String)]<br />
hrefs (TagOpen "a" xs) = filter ( (== "href") . fst) xs<br />
hrefs _ = []<br />
<br />
printResult :: (Show result) => Chan result -> IO ()<br />
printResult c = readChan c >>= print<br />
</haskell><br />
<br />
Filtering out non-unique URLs is just the bloom filter in action.<br />
<br />
<haskell><br />
uniqueURL :: IORef (Bloom URL, Int) -> st -> Job -> IO (Maybe Job)<br />
uniqueURL _ _ j@(ParseHTML _ _) = return $ Just j<br />
uniqueURL bf _ j@(GetURL url) = do<br />
(b,i) <- readIORef bf<br />
if elemB url b<br />
then putStrLn ("Reject: " ++ url) >> return Nothing<br />
else do writeIORef bf (insertB url b, i + 1)<br />
when (i `rem` 100 == 0) (print i)<br />
return $ Just j<br />
</haskell><br />
<br />
== Performance ==<br />
No serious performance measurements have been made beyond extremely expensive (and trivially parallel) problems, so those don't count.<br />
<br />
<br />
[[Category:Libraries]]<br />
[[Category:Packages]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Colour&diff=29068Colour2009-07-11T20:05:21Z<p>Nedervold: punct, spelling</p>
<hr />
<div>[[Category:Libraries]]<br />
<br />
This page provides a short introduction to using the [http://hackage.haskell.org/package/colour colour package] on hackage.<br />
<br />
== The Colour data type ==<br />
<br />
The <hask>Colour a</hask> data type and its basic operations are found in the <hask>Data.Colour</hask> module. The type variable <hask>a</hask> is used to specify the numeric type used for the internal representation of the data. Typically one will use:<br />
<br />
<haskell><br />
Colour Double<br />
</haskell><br />
<br />
You may wish to make a type synonym for this type in your program if you will use it everywhere.<br />
<br />
You can always use <hask>colourConvert</hask> to change to a different internal representation type.<br />
<br />
== Creating colours ==<br />
<br />
A collections of colours given by name can be found in the <hask>Data.Colour.Names</hask> module. There is also a <hask>readColourName</hask> to convert a string with one of these names into a colour. Be aware that the colour <hask>tan</hask> will conflict with the Prelude function unless you hide the Prelude function or import the module qualified.<br />
<br />
Another way to make a colour is by specifying an RGB triple. These functions can be found in the <hask>Data.Colour.SRGB</hask> library. For example, if you have three <hask>Word8</hask>s named <hask>red</hask>, <hask>green</hask>, and <hask>blue</hask>, then <br />
<br />
<haskell><br />
sRGB24 red green blue<br />
</haskell><br />
<br />
will create the colour with those [http://en.wikipedia.org/wiki/SRGB sRGB] colour coordinates.<br />
<br />
If you have three <hask>Double</hask>s (or whatever you are using for your internal representation) named <hask>red</hask>, <hask>green</hask>, and <hask>blue</hask>, then <br />
<br />
<haskell><br />
sRGB red green blue<br />
</haskell><br />
<br />
will produce the colour with those colour coordinates. These <hask>Double</hask> should be in the range [0,1] otherwise the resulting colour would be out of gamut (a [http://en.wikipedia.org/wiki/Gamut colour gamut] is a collection of representable colours on a device, such as your monitor).<br />
<br />
Lastly, <hask>sRGB24read</hask> and <hask>sRGB24reads</hask> can create colour from string specifications of the form <hask>"#00aaff"</hask> or <hask>"00aaff"</hask>.<br />
<br />
== Manipulating Colours ==<br />
<br />
The colour operations are found in the <hask>Data.Colour</hask> module.<br />
The most common operation on colours is <hask>blend</hask>. For example, <br />
the function <br />
<br />
<haskell><br />
blend 0.25 red green<br />
</haskell><br />
<br />
will create a new colour that is 25% red, and 75% green. The weight parameter (the first parameter) should be between 0 and 1, otherwise an out-of-gamut colour could result.<br />
<br />
If you need to blend more than two colours, you can use multiple applications of <hask>blend</hask>, or you can use <hask>affineCombo</hask>. For example,<br />
<br />
<haskell><br />
affineCombo [(0.25,red),(0.5,green)] violet<br />
</haskell><br />
<br />
will create a new colour that is 25% red, 50% green, and 25% violet. Again the weights should all be non-negative and the sum of the weights should be no more than 1, otherwise an out-of-gamut colour could result.<br />
<br />
Colour intensity can be changed by using <hask>darken</hask>. For example,<br />
<br />
<haskell><br />
darken 0.4 turquoise<br />
</haskell><br />
<br />
will produce a turquoise that is only 40% of the intensity of normal turquoise.<br />
The weight parameter (the first parameter) should be between 0 and 1, otherwise an out-of-gamut colour could result. However if you know that the intensity is low enough, you may safely "darken" by values greater than 1 (which will actually lighten the colour).<br />
<br />
Lastly, colours are instance of a [[Monoid]] so colours can be "added" by using <hask>mappend</hask> (and <hask>mempty</hask> is a quick way to get black). However, like spotlights, adding colours makes more intense colours. Adding colours could take you out of gamut by making colours too intense. Unless you specifically know you want to be adding colours, you probably want to be using <hask>blend</hask> instead.<br />
<br />
== Getting colour coordinates out ==<br />
<br />
To retrieve the [http://en.wikipedia.org/wiki/SRGB sRGB] coordinates of a colour, use the functions found in the <hask>Data.Colour.SRGB</hask> module. To get coordinates as <hask>Double</hask>s (or whatever your internal representation is) use <hask>toSRGB</hask>. For example<br />
<br />
<haskell><br />
toSRGB chartreuse<br />
</haskell><br />
<br />
will produce a value of type <hask>RGB Double</hask>.<br />
<br />
=== RGB triples ===<br />
<br />
The type <hask>RGB</hask> is special type of (strict) triple used to store colour coordinates. The functions <hask>channelRed</hask>, <hask>channelGreen</hask>, and <hask>channelBlue</hask> can be used to access the three fields. The constructor <hask>RGB</hask> will create such a triple. For example,<br />
<br />
<haskell><br />
RGB 0.5 0.4 0.6<br />
</haskell><br />
<br />
You might find the functions<br />
<br />
<haskell><br />
curryRGB :: (RGB a -> b) -> a -> a -> a -> b<br />
uncurryRGB :: (a -> a -> a -> b) -> RGB a -> b<br />
</haskell><br />
<br />
useful when working with functions that operate on RGB triples. These functions can be found in <hask>Data.Colour.RGBSpace</hask>.<br />
<br />
=== Back to colour coordinates ===<br />
<br />
Recall that<br />
<br />
<haskell><br />
toSRGB chartreuse<br />
</haskell><br />
<br />
produces an <hask>RGB Double</hask>. The coordinates output by <hask>toSRGB</hask> will all be between 0 and 1 unless the colour is out of gamut.<br />
<br />
If you want to retrieve the colour coordinates as <hask>Word8</hask>s, use <hask>toSRGB24</hask><br />
<br />
<haskell><br />
toSRGB24 khaki<br />
</haskell><br />
<br />
will produce an <hask>RGB Word8</hask>. Out-of-gamut channels will be clamped to the range 0 to 255.<br />
<br />
Lastly, the functions <hask>sRGB24show</hask> and <hask>sRGB24shows</hask> will produce colour strings of the form <hask>"#00aaff"</hask>.<br />
<br />
== Transparent Colour ==<br />
<br />
Colours that are semi transparent are represented by the <hask>AlphaColour a</hask> type found in <hask>Data.Colour</hask>. Again the <hask>a</hask> type parameter represents the data type used for the internal representation and would typically be <hask>Double</hask>. You can use <hask>alphaColourConvert</hask> to change the internal representation type of a semi-transparent colour.<br />
<br />
Opaque <hask>AlphaColour</hask>s are created from <hask>Colour</hask>s using <hask>opaque</hask>. For example.<br />
<br />
<haskell><br />
opaque goldenrod<br />
</haskell><br />
<br />
creates an opaque goldenrod. Semi transparent colours can be made using <hask>withOpacity</hask><br />
<br />
<haskell><br />
moccasin `withOpacity` 0.7<br />
</haskell><br />
<br />
creates a colour that is 70% opaque and hence 30% transparent.<br />
<br />
The value <hask>transparent</hask> is 100% transparent and <hask>transparent == anyColour `withOpacity` 0</hask>.<br />
<br />
Like regular colours, semi-transparent colours can be blended using <hask>blend</hask> and <hask>affineCombo</hask>. The function <hask>darken</hask> will darken a semi-transparent colour without affecting its opacity.<br />
<br />
To make an existing semi-transparent colour more transparent use <hask>dissolve</hask>. For example,<br />
<br />
<haskell><br />
dissolve 0.6 ac<br />
</haskell><br />
<br />
will return a semi-transparent colour that is 60% of the opacity of <hask>ac</hask>.<br />
<br />
One should avoid dissolving with weights (the first parameter) greater than 1, as you may create invalid "super-opaque" colours. If you know the opacity is less than <hask>x</hask> then you can safely use weights no more than <hask>(recip x)</hask>. Negative weights will also produce invalid "super-transparent" colours.<br />
<br />
<haskell><br />
anyColour `withOpacity` opacity == disolve opacity (opaque anyColour)<br />
</haskell><br />
<br />
Lastly, the key operation on transparent colours is compositing. Given two semitransparent colours <hask>acTop</hask> and <hask>acBottom</hask><br />
<br />
<haskell><br />
acTop `over` acBottom<br />
</haskell><br />
<br />
will produce the semi-transparent colour resulting from acTop being composited over top of <hask>acBottom</hask>. The bottom layer, <hask>acBottom</hask> can be a non-transparent colour (of type <hask>Colour</hask>). In this case the result will also be a non-transparent colour. However, the top layer must be of semi-transparent type (although it could, of course, be opaque).<br />
<br />
Compositing is such important operation on semi-transparent colours, that it is the [[Monoid]] instance for <hask>AlphaColour a</hask>. The function <hask>mappend</hask> is <hask>over</hask>, and <hask>mempty</hask> is <hask>transparent</hask>.<br />
<br />
=== Getting semi-transparent coordinates ===<br />
<br />
The opacity of a semi-transparent colour can be retrieved by the <hask>alphaChannel</hask> function.<br />
<br />
The pure colour of a semi-transparent colour <hask>ac</hask> can be retrieved by first compositing the colour over black, then darkening by the reciprocal of the alpha channel.<br />
<br />
<haskell><br />
pureColour :: AlphaColour a -> Colour a<br />
pureColour ac | a > 0 = darken (recip a) (ac `over` mempty)<br />
| otherwise = error "transparent has no pure colour"<br />
where<br />
a = alphaChannel ac<br />
</haskell><br />
<br />
Note however, that transparent has no pure colour, and this case needs to be handled specially.<br />
<br />
This operation is not natively provided because it is an operation that should be avoided. It is only really useful for interfacing with libraries that require pure colour components. Ideally it would be these libraries that implement conversion to and from <hask>Colour</hask>. However, you may find it necessary to implement the conversion functions yourself, in which case you can use the above "trick" to write the conversion function.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Abbreviations&diff=27324Abbreviations2009-04-03T05:48:45Z<p>Nedervold: </p>
<hr />
<div>{{Stub}}<br />
<br />
== An overview of Haskell related abbreviations ==<br />
<br />
For GHC related abbreviations [[GHC/List of abbreviations]].<br />
Note: if there is an abbreviation you cannot find here, it might be the name of a package, so check the [http://hackage.haskell.org/packages/archive/pkg-list.html Hackage package list].<br />
<br />
{| <br />
| ABI<br />
| [http://en.wikipedia.org/wiki/Application_binary_interface Application Binary Interface]<br />
|- <br />
| ADP<br />
| [http://bibiserv.techfak.uni-bielefeld.de/adp/ Algebraic Dynamic Programming]<br />
|- <br />
| ADT <br />
| [[Abstract data type | Abstract Data Type]] / [[Algebraic data type | Algebraic Data Type]]<br />
|- <br />
| AFAIU<br />
| As Far As I Understand<br />
|- <br />
| AFRP<br />
| [Yampa | Arrows-based Functional Reactive Programming], also known as Yampa<br />
|- <br />
| AKA<br />
| Also Known As<br />
|- <br />
| ANN<br />
| Announcement<br />
|- <br />
| API<br />
| [http://en.wikipedia.org/wiki/Application_programming_interface Application Programmer Interface]<br />
|- <br />
| AT<br />
| [[Abstract data type | Abstract (Data) Type]] / [http://nattermorphisms.blogspot.com/2008/10/2-minute-intro-to-associated-types-type.html Associated (Data) Type] (see also [http://portal.acm.org/citation.cfm?id=1040306 Associated types with class])<br />
|- <br />
| BSD<br />
| [http://en.wikipedia.org/wiki/BSD_license Berkeley Software Distributions (license)]<br />
|- <br />
| Cabal<br />
| [[Cabal | Common Architecture for Building Applications and Libraries]]<br />
|- <br />
| CAF<br />
| [[Constant applicative form | Constant Applicative Form]]<br />
|- <br />
| CAML<br />
| A programming language<br />
|- <br />
| CPR<br />
| [http://research.microsoft.com/en-us/um/people/simonpj/Papers/cpr/index.htm Constructed Product Result] (analysis)<br />
|- <br />
| CPS<br />
| [[Continuation | Continuation-Passing Style]]<br />
|- <br />
| CUFP<br />
| [http://cufp.galois.com/ Commercial Users of Functional Programming] <br />
|- <br />
| DPH<br />
| [[Data Parallel Haskell]]<br />
|- <br />
| DSEL<br />
| [[Embedded domain specific language | Domain-Specific Embedded Language]]<br />
|- <br />
| DSL<br />
| [[Embedded domain specific language | Domain-Specific Language]]<br />
|- <br />
| EDSL<br />
| [[Embedded domain specific language | Embedded Domain-Specific Language]]<br />
|- <br />
| elt<br />
| Element (of a list/set/...)<br />
|- <br />
| FAQ<br />
| Frequently Asked Questions<br />
|- <br />
| FD <br />
| [[Functional dependencies | Functional Dependencies]]<br />
|- <br />
| FFI <br />
| [[Foreign Function Interface]]<br />
|- <br />
| FHM<br />
| [http://www.cs.nott.ac.uk/~ggg/ Functional Hybrid Modeling]<br />
|- <br />
| FRP<br />
| [[Functional Reactive Programming]]<br />
|- <br />
| FunDeps<br />
| [[Functional dependencies | Functional Dependencies]]<br />
|- <br />
| FTW<br />
| [http://en.wiktionary.org/wiki/FTW For The World / For The Win]<br />
|- <br />
| FWIW<br />
| For what it's worth<br />
|- <br />
| GHC<br />
| [http://haskell.org/ghc/ Glasgow Haskell Compiler]<br />
|-<br />
| GPL<br />
| [http://www.gnu.org/licenses/gpl.html GNU General Public License]<br />
|- <br />
| HOAS <br />
| [http://en.wikipedia.org/wiki/Higher-order_abstract_syntax Higher-Order Abstract Syntax] (using binding in the host language to represent binding in the embedded language)<br />
|- <br />
| HOF<br />
| [[Higher order function | Higher-Order Functions]]<br />
|- <br />
| HTH<br />
| Hope This Helps<br />
|- <br />
| HUGS <br />
| [[Hugs | Haskell User's Gofer System]]<br />
|- <br />
| I18n<br />
| Internationalization / Internationalisation (which shows why the abbreviation is useful)<br />
|- <br />
| IANAL<br />
| I Am Not A Lawyer<br />
|- <br />
| ICFP<br />
| [http://www.icfpconference.org/ International Conference on Functional Programming]<br />
|- <br />
| IIRC<br />
| If I Recall Correctly<br />
|- <br />
| IIUC<br />
| If I Understand Correctly<br />
|- <br />
| IMHO<br />
| In My Humble Opinion<br />
|- <br />
| IMO<br />
| In My Opinion<br />
|- <br />
| IRC<br />
| [[IRC channel | Internet Relay Chat]]<br />
|- <br />
| LGPL<br />
| [http://www.gnu.org/licenses/lgpl.html GNU Lesser General Public License]<br />
|- <br />
| LHS<br />
| Left-Hand Side (of a statement)<br />
|- <br />
| LLVM<br />
| [[LLVM | Low-Level Virtual Machine]]<br />
|- <br />
| ML<br />
| A programming language / Mailing list<br />
|- <br />
| MPTC<br />
| [[Multi-parameter type class | Multi-Parameter Type Class]]<br />
|- <br />
| MTL<br />
| [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/mtl Monad Template Library]<br />
|- <br />
| OCAML<br />
| A programming language<br />
|- <br />
| OP<br />
| Original Poster (who sent the first e-mail of the current thread)<br />
|- <br />
| OT<br />
| Off-Topic<br />
|- <br />
| POPL<br />
| [http://en.wikipedia.org/wiki/POPL Principles of Programming Languages, Symposium on]<br />
|- <br />
| RHS<br />
| Right-Hand Side (of a statement)<br />
|- <br />
| RWH<br />
| [http://www.realworldhaskell.org/ Real World Haskell], a book about Haskell<br />
|- <br />
| SML<br />
| A programming language<br />
|- <br />
| SQL<br />
| [http://en.wikipedia.org/wiki/SQL Structured Query Language]<br />
|- <br />
| STG machine<br />
| [http://research.microsoft.com/users/simonpj/papers/spineless-tagless-gmachine.ps.gz Spineless Tagless G-machine]<br />
|- <br />
| STM<br />
| [[Software transactional memory]]<br />
|- <br />
| TaPL<br />
| [http://www.cis.upenn.edu/~bcpierce/tapl/ Types and Programming Languages] (book)<br />
|- <br />
| TCM<br />
| [http://conal.net/blog/tag/type-class-morphism/ Type Class Morphism]<br />
|- <br />
| TCO<br />
| [http://en.wikipedia.org/wiki/Tail_call_optimization Tail-Call Optimisation]<br />
|- <br />
| TMR<br />
| [[The Monad.Reader]]<br />
|- <br />
| UTF8<br />
| [http://unicode.org/faq/utf_bom.html#UTF8 Unicode Transformation Format, byte-oriented]<br />
|- <br />
| WHNF<br />
| [http://encyclopedia2.thefreedictionary.com/Weak+Head+Normal+Form Weak Head Normal Form]<br />
|- <br />
| YAHT<br />
| [http://en.wikibooks.org/wiki/Haskell/YAHT Yet Another Haskell Tutorial]<br />
|- <br />
| YHC<br />
| [[Yhc | York Haskell Compiler]]<br />
|- <br />
| YMMV<br />
| [http://en.wiktionary.org/wiki/your_mileage_may_vary Your Milage May Vary]<br />
|- <br />
|}<br />
<br />
[[Category:Language]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Applications_and_libraries/Data_structures&diff=21120Applications and libraries/Data structures2008-05-29T17:57:47Z<p>Nedervold: fixed typos; smoothed some wording</p>
<hr />
<div>{{unknown copyright}}<br />
{{LibrariesPage}}<br />
<br />
==General libraries and tools for data structures==<br />
<br />
;[http://www.eecs.tufts.edu/~rdocki01/edison.html Edison]<br />
:This is the latest version of the Edison library of efficient data structures. There are also [http://www.haskell.org/ghc/docs/edison/ earlier version of Edison] by Chris Okasaki. It provides sequences, finite maps, priority queues, and sets/bags. ([http://www.eecs.usma.edu/Personnel/okasaki/pubs.html#hw00 overview paper]).<br />
<br />
;[[Library/New collections]]<br />
:This is a package of many useful collections types. Advantages include:<br />
:*It's easy to migrate from standard Lists/Sets/Maps to the new package. The package is an evolution (rather than a revolution) of the collections currently in the base package.<br />
:*Each collection type fits in a consistent framework (thanks to classes)<br />
:*An extensive QuickCheck test suite also serves as detailed specification for the collections.<br />
<br />
:This package includes and supercedes the following libraries:<br />
<br />
:;[http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/ Data.Tree.AVL]<br />
::An implementation of AVL trees and related utilities.<br />
<br />
:;[http://homepages.nildram.co.uk/~ahey/HLibs/Data.StringMap/ Data.StringMap]<br />
::A library providing maps from String keys to values, based on Tries.<br />
<br />
:This package includes the following libraries, but they are maintained separately:<br />
<br />
:;[http://sourceforge.net/projects/ranged-sets/ Ranged Sets]<br />
::A ranged set is a list of non-overlapping ranges. The ranges have upper and lower boundaries, and a boundary divides the base type into values above and below. No value can ever sit on a boundary. So you can have the set {2.0 < x <= 3.0, 5.3 < x < 6}<br />
<br />
;[http://www.cs.vu.nl/Strafunski/ Strafunski]<br />
:A bundle for generic programming. It provides programming support for generic traversal as useful in the implementation of program transformations.<br />
<br />
;[http://www.lochan.org/2005/keith-cl/libs/ Partial v0.1]<br />
:The Partial library provides a partial order class. It also provides routines for generating a Hasse diagram from a set and a partial order. Renderers are provided for the abstract Hasse diagram representation into LaTeX (via Xy-pic) and into dot, the format for AT&amp;T's Graphviz tools. Since no horizontal sorting is done, the Xy-pic output is rather poor at present; dot does a much better job with its layout optimisation algorithm.<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/diet/ Discrete Interval Encoding Trees]<br />
:The discrete interval encoding tree (DIET) is a structure for storing subsets of types having a total order and a predecessor and a successor function.<br />
<br />
;[http://www.cwi.nl/~ralf/HList/ HList]<br />
:A heterogeneous collection is a datatype that is capable of storing data of different types, while providing operations for look-up, update, iteration, and others. There are various kinds of heterogeneous collections, differing in representation, invariants, and access operations.<br />
<br />
;[http://www.csee.ogi.edu/~diatchki/monadLib monadLib]<br />
:Iavor Diatchki's library of monad transformers for Haskell. It enables the quick construction of monads --- abstract data types that capture common programming idioms, such as throwing and catching exceptions or continuations. In many programming languages such features are built into the language (if they're provided at all), but in Haskell they are user-programmable.<br />
<br />
;[http://wiki.di.uminho.pt/wiki/bin/view/Alcino/PointlessHaskell Pointless Haskell]<br />
:Pointless Haskell is library for [[pointfree|point-free]] programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions.<br />
<br />
;[http://www.informatik.uni-freiburg.de/~wehr/haskell/ rhaskell : Reactive Objects]<br />
:Stefan Wehr's reactive objects library. Reactive objects are a convenient abstraction for writing programs which have to interact with a concurrent environment. A reactive object has two characteristics: the abandonment of all blocking operations and the unification of the concepts state and process. The former allows a reactive object to accept input from multiple sources without imposing any ordering on the input events. The latter prevents race conditions because the state of an object is only manipulated from the process belonging to the object.<br />
<br />
;[http://repetae.net/john/recent/out/GenUtil.html GenUtil]<br />
:A collection of random useful utility functions written in pure Haskell 98. In general, it tries to conform to the naming scheme put forth in the Haskell prelude and fill in the obvious omissions, as well as providing useful routines in general.<br />
<br />
;[http://www.cs.uu.nl/~afie/pd09122004.zip PersistentDocument] ''The link is dead, somebody please either update it or remove it.''<br />
:The persistent document abstraction takes care of dealing with a document you want to open from and save to disk and that supports undo. This functionality can be used by editors of arbitrary documents and saves you a lot of quite subtle coding.<br />
<br />
;[[Zipper monad]]<br />
:A generic monad for navigating around arbitrary data structures<br />
<br />
==Graphs==<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/fgl/haskell/ FGL - A Functional Graph Library]<br />
:The functional graph library provides a collection of graph operations.<br />
<br />
;[http://wiki.di.uminho.pt/wiki/bin/view/PURe/PUReSoftware Data.Relation]<br />
:Part of the UMinho Haskell libraries, this library provides a representation and operations on relations. A special case of relations are graphs. The operations include graph chopping and slicing, strong connected component analysis, graphs metrics, and more.<br />
<br />
;[http://article.gmane.org/gmane.comp.lang.haskell.libraries/4739 Haskell Graph Automorphism Library]<br />
:Jean-Philippe Bernardy's implementation of Brendan McKay's algorithm for graph canonical labeling and automorphism group (Nauty).<br />
<br />
==IO==<br />
<br />
;[[Library/Streams | Streams]]<br />
:Streams is a feature-rich, flexible, extensible, backward-compatible and fast I/O library. It supports various stream types: files and legacy Handle type, string and memory buffers, pipes. There is also common functionality available for any stream: buffering, Char encoding, locking.<br />
<br />
;[[Binary IO]]<br />
<br />
==Mutable data==<br />
<br />
;[http://www.isi.edu/~hdaume/STPP/ The Haskell STate Preprocessor]<br />
:This is a short preprocessor for stateful Haskell programs. It aleviates the pain of performing single array lookup/write/update functions with some syntax to support it. It also supports hash table operations based on the HashTable implementation available from the author. Finally, it supports monadic if and monadic case constructions. It is lightweight in the sense that it performs no syntactic analysis and is essentially a character transformer.<br />
<br />
;[[Library/ArrayRef | Arrays & References Library]]<br />
:Featuring:<br />
* Unboxed references in IO and ST monads<br />
* Monad-independent interfaces to boxed and unboxed references<br />
* Syntax sugar to make using of mutable objects easier (=:, +=, -=,..)<br />
* Reimplemented Arrays library with the following improvements:<br />
* Unboxed arrays now can be used in polymorphic functions<br />
* The MArray class now supports arrays with dynamic bounds<br />
* Implementation of dynamic (resizable) arrays<br />
<br />
;[http://code.haskell.org/storablevector/ Data.StorableVector.ST]<br />
:StorableVector also support mutation in ST monad.<br />
<br />
See also [[Modern array libraries]]<br />
<br />
==Lists==<br />
<br />
;[http://code.google.com/p/slist/ SList] ''(broken link)''<br />
:Sized lists for Haskell<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/dlist.html dlist]<br />
:Difference lists (supporting O(1) append and snoc)<br />
<br />
==Strings==<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/fps.html Data.ByteString]<br />
:The FPS library provides mmapped and malloc'd packed strings (byte arrays held by a ForeignPtr), along with a list interface to these strings. It lets you do extremely fast I/O in Haskell; in some cases, even faster than typical C implementations, as well as conserving space.<br />
<br />
;[http://code.haskell.org/storablevector/ Data.StorableVector]<br />
:This is very much the same like Data.ByteString extended to any Storable element type. There is a data structure for monolithic blocks and chunky sequences. Mutable access is also possible in ST monad.<br />
<br />
;[http://software.complete.org/missingh/ MissingH]<br />
:MissingH is a library of pure-Haskell utility functions relating to strings, logging, and I/O.<br />
<br />
;[http://repetae.net/john/recent/out/HsLocale.html HsLocale]<br />
:A locale-aware replacement for the standard IO routines, and support for ''wide'' strings<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/icfp05/tests/unit-tests/VariableExpansion.hs VariableExpansion]<br />
:A library for variable expansion inside strings<br />
<br />
;[http://haskell-i18n.cvs.sourceforge.net/haskell-i18n/ i18n strings]<br />
:At sourceforge<br />
<br />
==Regular expressions==<br />
<br />
There are many libraries for regular expressions available. By default<br />
GHC comes with:<br />
<br />
;[http://darcs.haskell.org/packages/regex-base/ regex-base]<br />
:This defines the type classes for the new API<br />
<br />
;[http://darcs.haskell.org/packages/regex-compat/ regex-compat]<br />
:This defines the old Text.Regex.Posix API, using regex-posix<br />
<br />
;[http://darcs.haskell.org/packages/regex-posix/ regex-posix]<br />
:This is the interface to the old (and slow) posix backend (C's regex.h)<br />
<br />
All backends provide String and ByteString interfaces.<br />
<br />
Additional backend libraries are available for (hopefully) more efficient regular expression<br />
implementations:<br />
<br />
;[http://darcs.haskell.org/packages/regex-pcre/ regex-pcre]<br />
:PCRE-based regexes. This requires [http://www.pcre.org/ libpcre] (currently works against version 6.6.0 as of January 2007). This Haskell library and libpcre are both BSD. This is very fast but has left branch semantics instead of POSIX leftmost longest semantics.<br />
<br />
;[http://darcs.haskell.org/packages/regex-tre/ regex-tre]<br />
:TRE-based regexes. This requires [http://laurikari.net/tre/ libtre] (currently works against version 0.7.5 as of January 2007). Libtre aims to be POSIX compatible and is a much faster implementation that used by regex-posix. Note that libtre does have an [http://laurikari.net/pipermail/tre-general/2007-January/000083.html outstanding bug] in correctly interpreting some regular expressions. This Haskell package is BSD-3 licensed and libtre is LGPL.<br />
<br />
;[http://darcs.haskell.org/packages/regex-parsec/ regex-parsec]<br />
:Pure Haskell regexes implemented via parsec. The leftmost longest subexpression capture semantics of this library differ from the POSIX standard. This also has an option to prefer the left branch semantics that libpcre uses.<br />
<br />
;[http://darcs.haskell.org/packages/regex-dfa/ regex-dfa]<br />
:Pure Haskell DFA for regexes. This is licensed under LPGL (the above packages are all under BSD-3) due to derived code. This is faster than regex-parsec but does not return captured subexpressions. It also is being updated to handle repeated patterns that can match empty strings (the older version hangs, the new version rewrites the pattern internally).<br />
<br />
;There is a regex-tdfa packages in development (not released) that will be a pure Haskell and BSD-3 licensed implementation inspired by libtre. It aims to be a replacement for regex-posix.<br />
<br />
;Development versions (possible unstable or broken) of the above packages are also available under [http://darcs.haskell.org/packages/regex-unstable/ regex-unstable]. For support, please use the [[Mailing_lists | haskell-cafe]] mailing list.<br />
<br />
==Serialising data==<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/binary/Data-Binary.html Data.Binary] ([http://darcs.haskell.org/binary/ darcs repository])<br />
;A library for serialising binary values to and from lazy ByteStrings.<br />
<br />
;[http://www.n-heptane.com/nhlab/repos/NewBinary NewBinary]<br />
:A port of Malcolm Wallace's Binary library from NHC, offering facilities for heap compression and binary I/O. The de-facto standard for binary I/O in Haskell<br />
<br />
;[http://www.cs.helsinki.fi/u/ekarttun/SerTH/ SerTH]<br />
:SerTH is a binary serialization library for Haskell. It supports serializing cyclic datatypes in a fast binary format. SerTH uses template haskell for deriving the serializing interface for new datatypes.<br />
<br />
;[[Library/AltBinary | AltBinary]]<br />
: AltBinary is an exhaustive library that support binary I/O and serialization. It's part of [http://haskell.org/haskellwiki/Library/Streams Streams] library, so serialization is possible to any I/O source, from String to memory-mapped file. It's also backward compatible with [http://www.n-heptane.com/nhlab/repos/NewBinary NewBinary] library what makes translation of old code trivial. Very fast, very feature-rich, Hugs/GHC compatible, etc, etc...<br />
<br />
;[http://svn.openfoundry.org/pugs/third-party/HsSyck/ HsSyck]<br />
:YAML is a straightforward machine parsable data serialization format designed for human readability and interaction with dynamic languages. It is optimized for data serialization, configuration settings, log files, Internet messaging and filtering. Syck is an extension, written in C, for reading and writing YAML swiftly in popular scripting languages. It is part of core Ruby, and also has bindings for Perl 5, Python, Lua, Cocoa, and Perl 6. HsSyck provides Data.Yaml.Syck as an interface to YAML structures, using Data.ByteString for efficient textual data representation. Additionally, we provide a set of DrIFT rules to dump and load arbitrary Haskell data types in the YAML format.<br />
<br />
;[[GenericSerialize]]<br />
:GenericSerialize is a library which serializes data using the "Scrap Your Boilerplate" infrastructure. This means that while it cannot easily support data-structure-specific serialization, it can support many different data formats cheaply.<br />
<br />
==Compressing data==<br />
<br />
;[[Library/Compression | Compressions-2005]]<br />
:Features of the Compression-2005 Library ([http://freearc.narod.ru/ homepage])<br />
* easy and uniform access to most competitive free compression algorithms as of April'05: LZMA, PPMd and GRZip<br />
* all input/output performed via user-supplied functions (callbacks), so you can compress data in memory, files, pipes, sockets and anything else<br />
* all parameters of compression algorithm are defined with a single string, for example "lzma:8mb:fast:hc4:fb32". <br />
* Using this library, you can write a bzip-like utility in one line, with better compression results than bzip2 itself.<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/zlib Zlib]<br />
:Zlib bindings for ByteStrings. darcs get http://code.haskell.org/zlib/ ([http://hackage.haskell.org/cgi-bin/hackage-scripts/package/zlib docs])<br />
<br />
;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bzlib BZip2]<br />
:BZip2 bindings for ByteStrings. darcs get http://code.haskell.org/bzlib/ ([http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bzlib docs])<br />
<br />
==Benchmarking data structures==<br />
<br />
;[http://www.cs.york.ac.uk/fp/auburn/ Auburn]<br />
:Auburn is Graeme Moss's kit for benchmarking implementations of lazy data structures. Give it several implementations of an ADT (abstract data type) and it will tell you which one is best for your particular application.<br />
<br />
;[http://www.cse.unsw.edu.au/~dons/code/fps/tests/Bench.hs Bench]<br />
:Simple time and space benchmarking for various list-like data structures. Easily adapted to arbitrary structures<br />
<br />
==Generic traversals==<br />
<br />
;[http://eecs.oregonstate.edu/~erwig/reclib/ RecLib A Recursion and Traversal Library for Haskell]<br />
:The Recursion Library for Haskell provides a rich set of generic traversal strategies to facilitate the flexible specification of generic term traversals. The underlying mechanism is the Scrap Your Boilerplate (SYB) approach. Most of the strategies that are used to implement recursion operators are taken from Stratego.<br />
<br />
==Typesafe variants of <hask>IntSet</hask> and <hask>IntMap</hask> for enumerations==<br />
<br />
* ChrisKuklewicz wrote a bit of boilerplate to re-use IntSet and IntMap with any Enum type: [[EnumSet EnumMap]]<br />
* an efficient implementation of EnumSet for sets which fit into a machine word can be found in [http://www.eecs.tufts.edu/~rdocki01/docs/edison/Data-Edison-Coll-EnumSet.html Edison] (see above)<br />
<br />
==Hackage==<br />
<br />
* [http://hackage.haskell.org/packages/archive/pkg-list.html#cat:Data%20Structures Data structures on Hackage]<br />
* [http://hackage.haskell.org/packages/archive/pkg-list.html#cat:Data More data structures on Hackage]<br />
* [http://hackage.haskell.org/packages/archive/pkg-list.html#cat:Generics Generics on Hackage]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Dealing_with_binary_data&diff=18808Dealing with binary data2008-01-30T05:49:14Z<p>Nedervold: fixed typos</p>
<hr />
<div>== 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 charactors. 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 you 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.<br />
Instructions for installing Cabal packages are out of scope for this tutorial,<br />
but should be fairly easy to find.<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-0.2.2 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're 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 />
====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>&not;</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-0.2.2 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>Nedervoldhttps://wiki.haskell.org/index.php?title=Debugging&diff=16997Debugging2007-11-26T21:53:23Z<p>Nedervold: added question</p>
<hr />
<div>== Printf and friends ==<br />
The simplest approach is to use <tt>Debug.Trace.trace</tt>:<br />
<pre><br />
trace :: String -> a -> a<br />
</pre><br />
: "''When called, trace outputs the string in its first argument, before returning the second argument as its result.'"<br />
<br />
A common idiom to trace a function is:<br />
<pre><br />
myfun a b | trace ("myfun " ++ show a ++ " " ++ show b) False = undefined<br />
myfun a b = ...<br />
</pre><br />
The advantage is that disabling and enabling the trace takes only one line comment.<br />
<br />
You must keep in mind that due to lazy evaluation your traces will only print if the value they wrap is ever demanded.<br />
<br />
<br />
A more powerful<br />
alternative for this approach is [http://www.haskell.org/hood Hood]. Even if it hasn't been<br />
updated in some time, Hood works perfectly with the current ghc<br />
distribution. Even more, Hugs has it already integrated, see the [http://cvs.haskell.org/Hugs/pages/users_guide/observe.html manual page]. Add an <tt>import Observe</tt> and start inserting observations in your code.<br />
For instance:<br />
<pre><br />
import Hugs.Observe<br />
<br />
f' = observe "Informative name for f" f <br />
f x = if odd x then x*2 else 0<br />
</pre><br />
And then in hugs:<br />
<pre><br />
Main> map f' [1..5]<br />
[2,0,6,0,10]<br />
<br />
>>>>>>> Observations <<<<<<<br />
<br />
Informative name for f<br />
{ \ 5 -> 10<br />
, \ 4 -> 0<br />
, \ 3 -> 6<br />
, \ 2 -> 0<br />
, \ 1 -> 2<br />
}<br />
<br />
</pre><br />
<br />
outputs a report of all the invocations of f and their result.<br />
<br />
I have a handy bogus Hugs.Observe module with no-ops for the observations so that I don't need to remove them manually, expecting that the compiler will optimize them away. <br />
<br />
<br />
== The Safe Library ==<br />
<br />
There is a safe library of functions from the Prelude that can crash, see [http://www-users.cs.york.ac.uk/~ndm/safe/ the safe library]. If you get an error message such as "pattern match failure, head []", you can then use <tt>headNote "extra information"</tt> to get a more detailed error message for that particular call to <tt>head</tt>. The safe library also has functions that return default values and wrap their computation in <tt>Maybe</tt> as required.<br />
<br />
== Offline analysis of traces ==<br />
The most advanced debugging tools are based in offline analysis of traces. [http://www.haskell.org/hat Hat] is probably the most up-to-date tool for this, offering a comprehensive set of tools. [[User:NeilMitchell|Neil Mitchell]] has made available a Windows port of Hat at [http://www-users.cs.york.ac.uk/~ndm/projects/windows.php his site].<br />
<br />
The disadvantage of these tools is that they are not always compatible with the latest libraries, so you can put them to use only in some cases. <br />
<br />
''Some Hat user should complete this section''<br />
<br />
== Dynamic breakpoints in GHCi == <br />
Finally, the [[GHC/GHCi debugger| GHCi debugger]] project aims to bring dynamic<br />
breakpoints and intermediate values observation to GHCi in a near<br />
future. Right now the tool is only available from the site as a<br />
modified version of GHC, so unfortunately you will have to compile it<br />
yourself if you want to have it.<br />
<br />
This tool allows to set breakpoints in your code, directly from the GHCi command prompt. An example session:<br />
<pre><br />
*main:Main> :break add Main 2<br />
Breakpoint set at (2,15)<br />
*main:Main> qsort [10,9..1]<br />
Local bindings in scope:<br />
x :: a, xs :: [a], left :: [a], right :: [a]<br />
<br />
qsort2.hs:2:15-46> :sprint x<br />
x = _<br />
qsort2.hs:2:15-46> x<br />
This is an untyped, unevaluated computation. You can use seq to <br />
force its evaluation and then :print to recover its type<br />
qsort2.hs:2:15-46> seq x ()<br />
() <br />
qsort2.hs:2:15-46> :p x<br />
x - 10<br />
</pre><br />
<br />
Once a breakpoint is hit, you can explore the bindings in scope, as well as to evaluate any haskell expression, as you would do in a normal GHCi prompt. The <tt>':print'</tt> command can be very useful to explore the lazyness of your code.<br />
<br />
== Source-located errors ==<br />
<br />
[http://www.cse.unsw.edu.au/~dons/loch.html LocH] provides wrappers over<br />
<hask>assert</hask> for generating source-located exceptions and errors.<br />
<br />
Consider the use of a located <hask>fromJust</hask>:<br />
<br />
<haskell><br />
import Debug.Trace.Location<br />
import qualified Data.Map as M<br />
import Data.Maybe<br />
<br />
main = do print f<br />
<br />
f = let m = M.fromList<br />
[(1,"1")<br />
,(2,"2")<br />
,(3,"3")]<br />
s = M.lookup 4 m<br />
in fromJustSafe assert s<br />
<br />
fromJustSafe a s = check a (fromJust s)<br />
</haskell><br />
<br />
This will result in:<br />
<br />
<haskell><br />
$ ./a.out<br />
a.out: A.hs:12:20-25: Maybe.fromJust: Nothing<br />
</haskell><br />
<br />
This can be automated, using the 'loch' preprocessor, so a program<br />
failing with:<br />
<br />
<code><br />
$ ghc A.hs --make -no-recomp<br />
[1 of 1] Compiling Main ( A.hs, A.o )<br />
Linking A ...<br />
<br />
$ ./A<br />
A: Maybe.fromJust: Nothing<br />
</code><br />
<br />
Can be transformed to a src-located one by adding:<br />
<br />
<haskell><br />
import Debug.Trace.Location<br />
</haskell><br />
<br />
and then recompiling with the preprocessor on:<br />
<br />
<code><br />
$ ghc A.hs --make -pgmF loch -F -no-recomp<br />
[1 of 1] Compiling Main ( A.hs, A.o )<br />
Linking A ...<br />
<br />
$ ./A<br />
A: A.hs:14:14-19: Maybe.fromJust: Nothing<br />
</code><br />
<br />
== Other tricks ==<br />
<br />
* If you use GHC, you can get a stack trace in the console when your program fails with an error condition. See the [http://www.haskell.org/ghc/docs/latest/html/users_guide/runtime-control.html#rts-options-debugging manual page]<br />
<br />
=== Locating a failure in a library function ===<br />
<br />
The simplest way to provide locating in the source code a mismatch<br />
run-time error in the library functions:<br />
<haskell><br />
head, tail, fromJust<br />
</haskell><br />
<br />
and others is to avoid these functions and to use explicit matching instead.<br />
<br />
For example, consider:<br />
<br />
<haskell><br />
g x = h $ fromJust $ f x,<br />
</haskell><br />
<br />
ghc-6.6 often looses the reference to <hask>g</hask>, <hask>f</hask>,<br />
and <hask>h</hask> in its run-time error report, when <hask>f</hask><br />
returns <hask>Nothing</hask>.<br />
<br />
But for the program:<br />
<br />
<haskell><br />
g x = let Just y = f x in h y,<br />
</haskell><br />
<br />
GHC reports:<br />
<br />
<haskell><br />
Main: M1.hs:9:11-22:<br />
Irrefutable pattern failed for pattern Data.Maybe.Just y<br />
</haskell><br />
<br />
Indicating the source of the failure.<br />
<br />
=== Mysterious parse errors ===<br />
<br />
GHC provides `-ferror-spans`, which will give you the exactly position<br />
of the start and end of an offending statement.<br />
<br />
[[Category:Tools]]<br />
<br />
=== Infinite loops ===<br />
On glasgow-haskell-users on 21 Nov 2007, pepe made the following suggestion for detecting the cause infinite loops in GHCi. Assuming the offending function is named `loop`, and takes one argument:<br />
<br />
# enable the flag -fbreak-on-error (`:set -f-break-on-error` in GHCi)<br />
# run your expression with :trace (`:trace loop 'a'`)<br />
# hit Ctrl-C while your program is stuck in the loop to have the debugger break in the loop<br />
# use :history and :back to find out where the loop is located and why.<br />
<br />
''(For which versions? ghci >= 6.8?)''</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Parsers&diff=15173Parsers2007-08-20T06:05:38Z<p>Nedervold: fixed typos</p>
<hr />
<div>[[Category:Libraries]]<br />
Language/File format Parsers in Haskell<br />
<br />
This page is intended to serve as a collection of links to various readily-available parsers, implemented in Haskell.<br />
<br />
== ASN.1 ==<br />
[[Parsec]] parser for large subset of ASN.1 grammar (circa 98): http://adept.linux.kiev.ua/repos/asn1/<br />
<br />
== E-mail/SMTP ==<br />
[[Parsec]] parsers for grammars from RFC2821 and RFC2822 : http://cryp.to/hsemail/<br />
<br />
== Javascript ==<br />
[[Parsec]] parser for Javascript 1.5: [[Libraries_and_tools/HJS]]<br />
<br />
== JSON ==<br />
[[Parsec]] parser for JSON: http://www.tom.sfc.keio.ac.jp/~sakai/d/data/200604/JSON.hs<br />
<br />
Another [[Parsec]] parser for JSON: http://snippets.dzone.com/posts/show/3660<br />
<br />
== Other places to look ==<br />
Make sure you visited [[Applications_and_libraries/Compilers_and_interpreters]].<br />
<br />
Found a parser which I forgot to mention? Add link here.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Blow_your_mind&diff=15172Blow your mind2007-08-20T06:03:02Z<p>Nedervold: fixed typo</p>
<hr />
<div>Useful Idioms that will blow your mind (unless you already know them :)<br />
<br />
This collection is supposed to be comprised of short, useful, cool, magical examples, which should incite the reader's curiosity and (hopefully) lead him to a deeper understanding of advanced Haskell concepts. At a later time I might add explanations to the more obscure solutions. I've also started providing several alternatives to give more insight into the interrelations of solutions.<br />
<br />
More examples are always welcome, especially "obscure" monadic ones.<br />
<br />
<br />
== List/String operations ==<br />
<br />
<br />
<haskell><br />
-- split at whitespace<br />
-- "hello world" -> ["hello","world"]<br />
words<br />
<br />
unfoldr (\b -> fmap (const . (second $ drop 1) . break (==' ') $ b) . listToMaybe $ b)<br />
<br />
takeWhile (not . null) . evalState (repeatM $ modify (drop 1) >> State (break (== ' '))) . (' ' :)<br />
where repeatM = sequence . repeat<br />
<br />
fix (\f l -> if null l then [] else let (s,e) = break (==' ') l in s:f (drop 1 e))<br />
<br />
<br />
-- splitting in two (alternating)<br />
-- "1234567" -> ("1357", "246")<br />
-- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists<br />
foldr (\a ~(x,y) -> (a:y,x)) ([],[])<br />
<br />
(map snd *** map snd) . partition (even . fst) . zip [0..]<br />
<br />
transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
-- this one uses the solution to the next problem in a nice way :)<br />
<br />
toMaybe b x = if b then Just x else Nothing<br />
-- or generalize it:<br />
-- toMaybe = (toMonadPlus :: Bool -> a -> Maybe a)<br />
toMonadPlus b x = guard b >> return x<br />
<br />
-- splitting into lists of length N<br />
-- "1234567" -> ["12", "34", "56", "7"]<br />
unfoldr (\a -> toMaybe (null a) (splitAt 2 a))<br />
<br />
takeWhile (not . null) . unfoldr (Just . splitAt 2)<br />
<br />
<br />
-- sorting by a custom function<br />
-- length -> ["abc", "ab", "a"] -> ["a", "ab", "abc"]<br />
comparing f x y = compare (f x) (f y)<br />
sortBy (comparing length)<br />
<br />
map snd . sortBy (comparing fst) . map (length &&& id) <br />
-- the so called "Schwartzian Transform" for computationally more expensive <br />
-- functions.<br />
<br />
-- comparing adjacent elements<br />
rises xs = zipWith (<) xs (tail xs)<br />
<br />
-- lazy substring search<br />
-- "ell" -> "hello" -> True<br />
substr a b = any (a `isPrefixOf`) $ tails b<br />
<br />
-- multiple splitAt's:<br />
-- splitAts [2,5,0,3] [1..15] == [[1,2],[3,4,5,6,7],[],[8,9,10],[11,12,13,14,15]]<br />
splitAts = foldr (\n r -> splitAt n >>> second r >>> uncurry (:)) return<br />
</haskell><br />
<br />
== Mathematical sequences, etc ==<br />
<br />
<br />
<haskell><br />
-- factorial<br />
-- 6 -> 720<br />
product [1..6]<br />
<br />
foldl1 (*) [1..6]<br />
<br />
(!!6) $ scanl (*) 1 [1..]<br />
<br />
fix (\f n -> if n <= 0 then 1 else n * f (n-1))<br />
<br />
<br />
-- powers of two sequence<br />
iterate (*2) 1<br />
<br />
unfoldr (\z -> Just (z,2*z)) 1<br />
<br />
<br />
-- fibonacci sequence<br />
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)<br />
<br />
fibs = 0:1:zipWith (+) fibs (tail fibs)<br />
<br />
fib = 0:scanl (+) 1 fib<br />
<br />
<br />
-- pascal triangle<br />
pascal = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]<br />
<br />
<br />
-- prime numbers<br />
-- example of a memoising caf (??)<br />
primes = sieve [2..] where<br />
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]<br />
<br />
unfoldr sieve [2..] where <br />
sieve (p:x) = Just(p, [ n | n <- x, n `mod` p > 0 ])<br />
<br />
-- or if you want to use the Sieve of Eratosthenes..<br />
diff [] l = l<br />
diff l [] = l<br />
diff xl@(x:xs) yl@(y:ys) | x < y = x:diff xs yl<br />
| x > y = diff xl ys<br />
| otherwise = diff xs ys <br />
esieve [] = []<br />
esieve (p:ps) = p:esieve (diff ps (iterate (+p) p))<br />
eprimes = esieve [2..]<br />
<br />
-- enumerating the rationals (see [1])<br />
rats :: [Rational]<br />
rats = iterate next 1 where<br />
next x = recip (fromInteger n+1-y) where (n,y) = properFraction x<br />
<br />
-- another way<br />
rats2 = fix ((1:) . (>>= \x -> [1+x, 1/(1+x)])) :: [Rational]<br />
</haskell><br />
<br />
[1] [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#rationals Gibbons, Lest, Bird - Enumerating the Rationals]<br />
<br />
== Monad magic ==<br />
<br />
The list monad can be used for some amazing Prolog-ish search problems.<br />
<br />
<haskell><br />
-- all combinations of a list of lists.<br />
-- these solutions are all pretty much equivalent in that they run<br />
-- in the List Monad. the "sequence" solution has the advantage of<br />
-- scaling to N sublists.<br />
-- "12" -> "45" -> ["14", "15", "24", "25"]<br />
sequence ["12", "45"]<br />
<br />
[[x,y] | x <- "12", y <- "45"]<br />
<br />
do { x <- "12"; y <- "45"; return [x,y] }<br />
<br />
"12" >>= \a -> "45" >>= \b -> return [a,b]<br />
<br />
-- all combinations of letters<br />
(inits . repeat) ['a'..'z'] >>= sequence<br />
<br />
-- apply a list of functions to an argument<br />
-- even -> odd -> 4 -> [True,False]<br />
map ($4) [even,odd]<br />
<br />
sequence [even,odd] 4<br />
<br />
-- all subsequences of a sequence/ aka powerset.<br />
filterM (const [True, False])<br />
<br />
-- apply a function to two other function the same argument<br />
-- (lifting to the Function Monad (->))<br />
-- even 4 && odd 4 -> False<br />
liftM2 (&&) even odd 4<br />
<br />
liftM2 (>>) putStrLn return "hello"<br />
<br />
fix ((1:) . (>>= \x -> [x+1, 1/(x+1)])) :: [Rational]<br />
[1%1,2%1,1%2,3%1,1%3,3%2,2%3,4%1,1%4,4%3,3%4,5%2,2%5,5%3,3%5,5%1,1%5,5%4,4%5...<br />
<br />
-- forward function concatenation<br />
(*3) >>> (+1) $ 2<br />
<br />
foldl1 (flip (.)) [(+1),(*2)] 500<br />
<br />
<br />
-- perform functions in/on a monad, lifting<br />
fmap (+2) (Just 2)<br />
<br />
liftM2 (+) (Just 4) (Just 2)<br />
<br />
<br />
-- [still to categorize]<br />
(id >>= (+) >>= (+) >>= (+)) 3 -- (3+3)+(3+3) = 12<br />
<br />
double = join (+)<br />
<br />
(join . liftM2) (*) (+3) 5 -- 64<br />
<br />
mapAccumL (\acc n -> (acc+n,acc+n)) 0 [1..10] -- interesting for fac, fib, ...<br />
<br />
do f <- [not, not]; d <- [True, False]; return (f d) -- [False,True,False,True]<br />
<br />
do { Just x <- [Nothing, Just 5, Nothing, Just 6, Just 7, Nothing]; return x }<br />
</haskell><br />
<br />
== Other ==<br />
<br />
<br />
<haskell><br />
-- simulating lisp's cond<br />
case () of () | 1 > 2 -> True<br />
| 3 < 4 -> False<br />
| otherwise -> True<br />
<br />
<br />
-- match a constructor<br />
-- this is better than applying all the arguments, because this way the<br />
-- data type can be changed without touching the code (ideally).<br />
case a of Just{} -> True<br />
_ -> False<br />
<br />
<br />
{- <br />
TODO, IDEAS:<br />
more fun with monad, monadPlus (liftM, ap, guard, when)<br />
fun with arrows (second, first, &&&, ***)<br />
liftM, ap<br />
lazy search (searching as traversal of lazy structures)<br />
innovative data types (i.e. having fun with Maybe sequencing)<br />
<br />
LINKS:<br />
bananas, envelopes, ... (generic traversal)<br />
why functional fp matters (lazy search, ...)<br />
-}<br />
</haskell><br />
<br />
=== Polynomials ===<br />
In abstract algebra you learn that polynomials can be used the same way integers are used given the right assumptions about their coefficients and roots. Specifically, polynomials support addition, subtraction, multiplication and sometimes division. It also turns out that one way to think of polynomials is that they are just lists of numbers (their coefficients). <br />
<br />
instance Num a => Num [a] where -- (1)<br />
<br />
(f:fs) + (g:gs) = f+g : fs+gs -- (2)<br />
fs + [] = fs -- (3a)<br />
[] + gs = gs -- (3b)<br />
<br />
(f:fs) * (g:gs) = f*g : [f]*gs + fs*(g:gs) -- (4)<br />
_ * _ = [] -- (5)<br />
<br />
====Explanation====<br />
(1) puts lists into type class Num, the class to which operators + and * belong, provided the list elements are in class Num.<br />
<br />
Lists are ordered by increasing powers. Thus <tt>f:fs</tt> means <tt>f+x*fs</tt> in algebraic notation. (2) and (4) follow from these algebraic identities:<br />
<br />
(f+x*fs) + (g+x*gs) = f+g + x*(fs+gs)<br />
(f+x*fs) * (g+x*gs) = f*g + x*(f*gs + fs*(g+x*gs))<br />
<br />
(3) and (5) handle list ends.<br />
<br />
The bracketed <tt>[f]</tt> in (4) avoids mixed arithmetic, which Haskell doesn't support.<br />
<br />
====Comments====<br />
<br />
The methods are qualitatively different from ordinary array-based methods; there is no vestige of subscripting or counting of terms.<br />
<br />
The methods are suitable for on-line computation. Only<br />
<i>n</i> terms of each input must be seen before the <i>n</i>-th term<br />
of output is produced.<br />
<br />
Thus the methods work on infinite series as well as polynomials.<br />
<br />
Integer power comes for free. This example tests the cubing of (1+x):<br />
<br />
[1, 1]^3 == [1, 3, 3, 1]<br />
<br />
See also<br />
* [[Pointfree]]<br />
* [http://darcs.haskell.org/numericprelude/src/MathObj/Polynomial.hs NumericPrelude: Polynomials]<br />
* [[Add polynomials]]<br />
* Solve differential equations in terms of [http://www.haskell.org/pipermail/haskell-cafe/2004-May/006192.html power series].<br />
<br />
[[Category:Idioms]]<br />
[[Category:Mathematics]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Implementations&diff=13900Implementations2007-06-30T19:29:34Z<p>Nedervold: spelling; punctuation</p>
<hr />
<div>== '''GHC''' the [[Glasgow Haskell Compiler]] ==<br />
GHC is an optimising compiler for Haskell, providing many language extensions. GHC is the de facto standard compiler if you want fast code. GHC is written in Haskell (plus extensions), and its size and complexity mean that it is less portable than Hugs, it runs more slowly, and it needs more memory. However, the programs it produces run ''much'' faster.<br />
<br />
There is also an interactive environment, GHCi, which is like Hugs but supports interactive loading of compiled code. GHC provides profiling for time and space, and supports concurrent and (recently) parallel programming. It is available for most common platforms, including Windows, Mac OS X, and several Unix variants (Linux, *BSD, Solaris).<br />
<br />
== The Haskell Interpreter '''[http://haskell.org/hugs Hugs]''' ==<br />
This small, portable Haskell interpreter written in C runs on almost any machine. Hugs is best used as a Haskell program development system: it boasts extremely fast compilation, supports incremental compilation, and has the convenience of an interactive interpreter (within which one can move from module to module to test different portions of a program). However, being an interpreter, it does not nearly match the run-time performance of, for example, GHC, nhc98, or HBC. It is certainly the best system for newcomers to learn Haskell. Hugs 98 is conformant with Haskell 98. Available for all Unix platforms including Linux, DOS, Windows 3.x, and Win 32 (Windows 95, Win32s, NT) and Macintoshes. It has many libraries including Win32 libraries, a foreign interface mechanism to facilitate interoperability with C, and the Windows version has a graphical user interface called [[WinHugs]]. Explanations of some common Hugs error messages and their causes can be found on [http://www.cs.ukc.ac.uk/people/staff/sjt/craft2e/errors.html Simon Thompson's page].<br />
<br />
== [http://haskell.org/nhc98 nhc98] ==<br />
A small, easy to install, standards-compliant Haskell 98 compiler. It provides some advanced kinds of heap profiles not found in any other Haskell compiler. It produces medium-fast code, and compilation is itself quite fast. The compiler stresses the saving of space, that is, it produces small programs requiring comparatively little space at runtime (and it is itself much smaller than the other compilers). It is available for all Unix-like platforms (including Mac OS X, Cygwin/Windows, Linux, Solaris, *BSD, AIX, HP-UX, Ultrix, IRIX, etc.). It is written in Haskell 98, but can be quickly and easily bootstrapped from C sources.<br />
<br />
== '''Yhc''' the [[Yhc|York Haskell Compiler]] ==<br />
Yhc is a fork of [[nhc98]], with the goals of being simpler, more portable, more efficient and integrating [[Hat]] support.<br />
<br />
== [http://www.cs.chalmers.se/~augustss/hbc/hbc.html '''HBI''' and '''HBC'''], Chalmers' Haskell Interpreter and Compiler ==<br />
The Chalmers Haskell-B compiler 0.9999.5c implements Haskell 98, as well as some extensions. It is written by Lennart Augustsson, and based on the classic LML compiler by Augustsson and Johnsson. The interpreter can also load code compiled with HBC. There has been no official release for the last few years and the support level is pretty low, but the compiler exists and can be used. Unfortunately the web-pages and the documentation has not been updated the last few years! You can download an unofficial [http://haskell.org/hbc/hbc-2004-06-29.src.tar.gz snapshot of the sources] and the corresponding [http://haskell.org/hbc/hbc-2004-06-29.bin-i386-linux.tar.gz x86 Linux binaries] (based on [http://www.cs.chalmers.se/pub/users/hallgren/Alfa/Haskell/ snapshots] from Thomas Hallgren and Magnus Carlsson).<br />
<br />
== [http://www.cs.uu.nl/helium/ '''Helium'''] ==<br />
Helium is a functional programming language and a compiler designed especially for teaching Haskell. Quality of the error messages has been the main concern both in the choice of the language features and in the implementation of the compiler. The language is a subset of the Haskell language. The most notable difference with Haskell is the absence of overloading. The compiler keeps track of a lot of information to produce informative messages.<br />
<br />
== [http://repetae.net/computer/jhc/ '''Jhc'''] ==<br />
Jhc is an experimental compiler with a goal of testing new optimization methods and exploring the design space of Haskell implementations.<br />
<br />
== Yale Haskell ==<br />
[http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/syntax/haskell/0.html Yale Haskell 2.05], an early implementation of Haskell in Lisp. See an early [http://groups.google.com/group/comp.lang.functional/msg/5b929ac0223a6212?dmode=source&hl=en release announcement]<br />
<br />
[[Category:Implementations| ]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Applications_and_libraries/GUI_libraries&diff=13765Applications and libraries/GUI libraries2007-06-26T21:11:44Z<p>Nedervold: wxWindows -> wxWidgets</p>
<hr />
<div>[[Category:User interfaces]]<br />
{{unknown copyright}}<br />
{{LibrariesPage}}<br />
<br />
There is a large number of GUI libraries for Haskell. Unfortunately there is no standard one and all are more or less incomplete. In general, low-level veneers are going well, but they are low level. High-level abstractions are pretty experimental. There is a need for a supported medium-level GUI library.<br />
<br />
== High-level ==<br />
<br />
=== FG ===<br />
<br />
FG is an arrow-based high-level functional approach to composable GUIs, built on top of Gtk2Hs. It is inspired by Fruit but uses discrete events instead of continuous signals.<br />
<br />
See the [http://kevin.atkinson.dhs.org/fg/doc/FG.html FG homepage].<br />
<br />
=== FranTk ===<br />
<br />
FranTk is a library for building GUIs in Haskell. FranTk uses behaviours and events, concepts from Conal Elliot’s Functional Reactive Animation. FranTk provides good support for developing complex dynamic systems, and is built on top of Tcl/Tk. This makes it platform independent. FranTk was developed by [http://www.dcs.gla.ac.uk/~meurig/ Meurig Sage]. It runs on Unix and Windows.<br />
<br />
See the [http://haskell.org/FranTk FranTk homepage].<br />
<br />
=== Fruit ===<br />
<br />
Fruit is another high-level approach to GUIs in Haskell. It is based on the concepts of Functional Reactive Programming and arrows. There is also another implementation of this approach, called wxFruit (see below). Fruit is implemented on top of wxHaskell.<br />
<br />
See the [http://www.haskell.org/fruit/ Fruit homepage].<br />
<br />
=== Fudgets ===<br />
Fudgets is primarily a Graphical User Interface Toolkit for Haskell and the X Windows system. Fudgets also makes it easy to create client-server applications that communicate via the Internet. It runs on Unix but not on Windows.<br />
<br />
See the [http://www.cs.chalmers.se/ComputingScience/Research/Functional/Fudgets/ Fudgets homepage] and [http://www.cs.chalmers.se/ComputingScience/Research/Functional/Fudgets/springschool95-intro.html Programming with Fudgets] which is a short presentation of the Fudget Library and the ideas underlying it.<br />
<br />
=== Grapefruit ===<br />
<br />
Grapefruit is an arrow-based declarative library. Widgets, windows and control components communicate via signals and event streams. The use of signals and event streams is explicit in the interface to avoid certain inefficiencies. Internally, Grapefruit uses the event handling mechanisms of the underlying GUI toolkit.<br />
<br />
Currently, Grapefruit is build on top of Gtk2Hs but implementations based on other toolkits are planned for the future.<br />
<br />
See [[Grapefruit]].<br />
<br />
=== GuiTV ===<br />
<br />
GuiTV is a small library for GUI-style visualizing functional values. It can also be viewed as an approach to functional GUIs. It is implemented very simply by using [[Phooey]] in the [[TV]] framework.<br />
<br />
See [[GuiTV]].<br />
<br />
=== Phooey === <br />
<br />
Phooey is simple, functional, arrow-based library. Currently it is implemented atop [[wxHaskell]]. Phooey supports dynamic input bounds, flexible layout, and mutually-referential widgets.<br />
<br />
See [[Phooey]].<br />
<br />
=== wxFruit ===<br />
<br />
wxFruit is a GUI library based on the ideas of Fruit but built on top of wxHaskell.<br />
<br />
See the [http://zoo.cs.yale.edu/classes/cs490/03-04b/bartholomew.robinson/ wxFruit homepage].<br />
<br />
== Medium-level ==<br />
<br />
=== [[AutoForms]] ===<br />
<br />
[http://autoforms.sourceforge.net AutoForms] is a library to ease the creation of Graphical User Interfaces (GUI). It does this by using generic programming to construct GUI components.<br />
<br />
=== Functional Forms ===<br />
<br />
An addition to wxHaskell, Functional Forms is a combinator library/domain specific language which enables a very concise programming style for forms: dialogs which only show and edit a set of values. Forms are used in many applications as Options or Settings dialogs.<br />
<br />
See the [http://www.sandr.dds.nl/FunctionalForms Functional Forms homepage].<br />
<br />
=== Gtk2Hs ===<br />
<br />
Gtk2Hs is a GUI library for Haskell based on [http://www.gtk.org Gtk+]. Gtk+ is an extensive and mature multi-platform toolkit for creating graphical user interfaces. Gtk2Hs is actively developed, supporting the latest version of the Gtk+ 2.x series. It provides automatic memory management, Unicode support and also bindings for various Gnome modules. It runs on Windows, Linux, MacOS X, FreeBSD and Solaris.<br />
<br />
See the [http://haskell.org/gtk2hs/ Gtk2Hs homepage].<br />
<br />
=== HGL ===<br />
<br />
HGL is actually only a grapics library.<br />
<br />
See the [http://haskell.org/graphics/ HGL homepage].<br />
<br />
=== HTk ===<br />
<br />
Htk is a typed, portable encapsulation of Tcl/Tk into Haskell. Its distinctive features are the use of Haskell types and type classes for structuring the interface, an abstract notion of event for describing user interaction, and portability across Windows, Unix and Linux.<br />
<br />
See the [http://www.informatik.uni-bremen.de/htk HTk homepage].<br />
<br />
=== HToolkit ===<br />
<br />
HToolkit is a portable Haskell library for writing graphical user interfaces (GUI's). The library is built upon a low-level interface that will be implemented for each different target platform. The low-level library is called Port and is currently implemented for GTK and Windows. The middle-level library is named GIO (the Graphical IO library) and is built upon the low-level Port library.<br />
<br />
See the [http://htoolkit.sourceforge.net/ HToolkit homepage].<br />
<br />
=== Object I/O for Haskell ===<br />
<br />
This is a port of Clean Object I/O library for Haskell.<br />
<br />
See the [http://haskell.org/ObjectIO Object I/O for Haskell homepage].<br />
<br />
=== wxHaskell ===<br />
<br />
wxHaskell is a portable and native GUI library built on top of wxWidgets (formerly wxWindows)—a comprehensive C++ library that is portable across all major GUI platforms; including GTK, Windows, X11, and MacOS X. wxWidgets is a mature library (in development since 1992) that supports a wide range of widgets with the native look-and-feel, and it has a very active community.<br />
<br />
See [[wxHaskell]].<br />
<br />
== Low-level ==<br />
<br />
=== GLUT ===<br />
<br />
This is a binding to the OpenGL GLUT library.<br />
<br />
=== TclHaskell ===<br />
<br />
TclHaskell is a library of functions for writing platform independent, graphical user interfaces in Haskell. The library provides a convenient, abstract and high-level way to write window-oriented applications. It also provides a more low level interface to write primitive Tcl code where helpful. For Unix and Windows and maybe Macintosh.<br />
<br />
See the [http://www.dcs.gla.ac.uk/~meurig/TclHaskell/ TclHaskell homepage].<br />
<br />
=== Win32 ===<br />
<br />
A binding to parts of the Win32 API.<br />
<br />
=== X11 ===<br />
<br />
A binding to parts of the X11 libraries.<br />
<br />
== Uncategorized ==<br />
<br />
=== Curses.hsc ===<br />
<br />
Curses.hsc is a minimal binding to curses and ncurses. It is smaller than hscurses and has less features. It also provides fast packed string support.<br />
<br />
See the [http://www.cse.unsw.edu.au/~dons/code/hmp3/Curses.hsc Curses.hsc homepage].<br />
<br />
=== hscurses ===<br />
<br />
This is a Haskell binding to the NCurses library, a library of functions that manage an application’s display on character-cell terminals. hscurses also provides some basic widgets implemented on top of the ncurses binding, such as a text input widget and a table widget.<br />
<br />
See the [http://www.informatik.uni-freiburg.de/~wehr/haskell/ hscurses homepage].<br />
<br />
== Unsupported ==<br />
<br />
The following libraries seem to be no longer maintained. However, someone might pick up one of them or at least profit from some design ideas.<br />
<br />
=== Budgets ===<br />
<br />
Budgets is a library of Fudget-like combinators based on the Openlook widget library was developed by [http://www.reid-consulting-uk.ltd.uk/alastair/ Alastair Reid] and Satnam Singh. The code has suffered tremendous bit-rot (Does anyone have a copy of ghc-0.16?) but all the reusable ideas are described in the [http://www.reid-consulting-uk.ltd.uk/alastair/publications/gfpw93/ respective paper].<br />
<br />
See the [http://www.reid-consulting-uk.ltd.uk/alastair/publications/gfpw93/ Budgets homepage].<br />
<br />
=== Embracing Windows ===<br />
<br />
This is a framework for developing graphical user interfaces. It runs under Windows 95 using a modified version of Hugs 1.3.<br />
<br />
See the [http://citeseer.ist.psu.edu/taylor96embracing.html Embracing Windows paper].<br />
<br />
=== Gadgets ===<br />
<br />
Gadgets are lazy functional components for graphical user interfaces, developed by Rob Noble under the supervision of [http://www.cs.york.ac.uk/~colin/ Colin Runciman].<br />
<br />
See LNCS 982, pages 321-340.<br />
<br />
=== Gtk+HS ===<br />
<br />
Gtk+HS is a Haskell binding for GTK+. It provides a transcription of the original GTK+ API into Haskell. GTK+ is a modern, portable GUI library and forms the basis of the Gnome desktop project. The binding, while not complete, covers most of GTK+'s core functionality and is ready for use in applications that require a GUI of medium complexity. It was developed under Unix, but should also be usable with the Windows port of GTK+.<br />
<br />
See the [http://www.cse.unsw.edu.au/~chak/haskell/gtk/ Gtk+HS homepage].<br />
<br />
=== Haggis ===<br />
<br />
Haggis is a graphical user interface framework for Haskell, running under the X Window system. It is being developed using the Glasgow Haskell Compiler with its concurrent extensions to achieve more comfortable interaction with the outside world.<br />
<br />
See the [http://www.dcs.gla.ac.uk/fp/software/haggis/ Haggis homepage].<br />
<br />
=== iHaskell ===<br />
<br />
iHaskell is a functional wrapper on top of GTK+HS that provides convenience functions for frequently used programming patterns, and eliminates the need for explicit mutable variables.<br />
<br />
See the [http://www.cse.unsw.edu.au/~chak/haskell/gtk/#iHaskell iHaskell homepage].<br />
<br />
=== Pidgets ===<br />
<br />
Pidgets, developed by [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Scholz:Enno.html Enno Scholz], unifies pictures and widgets in a constraint-based framework for concurrent functional GUI programming.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Open_research_problems&diff=13124Open research problems2007-05-21T06:27:23Z<p>Nedervold: tweaked formatting</p>
<hr />
<div>[[Category:Research]]<br />
<br />
==Efficiency of lazy functional languages==<br />
This is a problem that came up during IRC discussions. We consider a purely functional language L. By "purely functional" we mean a language that has value semantics; that is, there is no function such that after evaluation of the function the value that was referred to by something else changed. (Also known as "No Side Effects"). A value is "changed" when it is not the case during an evaluation that when the old value and the new value would both be fully evaluated, there wouldn't be the same result. This should make sure that laziness is allowed in the purely functional language. <br />
<br />
The general problem is whether these purely functional languages can implement all algorithms that can be implemented in a language like C as efficiently in an amortized sense ignoring space-usage. <br />
<br />
===Specific problems===<br />
As for a specific problem: <br />
Implement <code>Data.STRef</code> and <code>Control.Monad.ST.runST</code> without using the built-in <code>ST</code>/<code>IO</code> monad. This needs to happen with operations that all run in O(1) amortized time.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Parametric_polymorphism&diff=13123Parametric polymorphism2007-05-21T06:20:24Z<p>Nedervold: fixed typo; added clarification</p>
<hr />
<div>Parametric polymorphism is when a function's type signature allows various arguments to take on arbitrary types, but the types must be ''related'' to each other in some way.<br />
<br />
For example, in Java one can write a function that accepts two arguments of any possible type. However, Haskell goes further by allowing a function to accept two arguments of any type so long as they are both ''the same'' type. For example<br />
<br />
As a specific (and slightly more complicated) example, the well-known <hask>map</hask> function has a parametrically polymorphic type<br />
<br />
<haskell><br />
map :: (a -> b) -> [a] -> [b]<br />
</haskell><br />
<br />
which means that the function will accept ''any'' type of list and ''any'' type of function, '''provided''' the types match up. (That is, the function's argument type and the list's element type match.) This makes <hask>map</hask> highly polymorphic, yet there is still no risk of a runtime type mismatch.</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Poor_man%27s_here_document&diff=12578Poor man's here document2007-04-20T05:20:07Z<p>Nedervold: added another implementation</p>
<hr />
<div>== Poor man's heredoc / here document ==<br />
<haskell><br />
main = do<br />
doc <- here "DATA" "Here.hs" [("variable","some"),("substitution","variables")]<br />
putStrLn doc<br />
html <- here "HTML" "Here.hs" [("code",doc)]<br />
putStrLn html<br />
<br />
here tag file env = do<br />
txt <- readFile file<br />
let (_,_:rest) = span (/="{- "++tag++" START") (lines txt)<br />
(doc,_) = span (/=" "++tag++" END -}") rest<br />
return $ unlines $ map subst doc<br />
where<br />
subst ('$':'(':cs) = case span (/=')') cs of <br />
(var,')':cs) -> maybe ("$("++var++")") id (lookup var env) ++ subst cs<br />
_ -> '$':'(':subst cs<br />
subst (c:cs) = c:subst cs<br />
subst "" = ""<br />
<br />
{- DATA START<br />
<br />
this is a poor man's here-document<br />
<br />
with quotes ", and escapes \, <br />
and line-breaks, and layout<br />
without escaping \" \\ \n,<br />
without concatenation.<br />
<br />
oh, and with $(variable) $(substitution), $(too).<br />
<br />
DATA END -}<br />
<br />
{- HTML START<br />
<br />
<html><br />
<head><title>very important page</title></head><br />
<body><br />
<verb><br />
$(code)<br />
</verb><br />
</body><br />
</html><br />
<br />
HTML END -}<br />
<br />
</haskell><br />
<br />
== Even poorer man's here-doc / here-document ==<br />
<br />
If you're just looking to define a multiline string constant, you can just say:<br />
<br />
<haskell><br />
str :: String<br />
str = unlines [<br />
"Here's a multiline string constant.",<br />
"\tIt's not as convenient as Perl's here-documents,",<br />
"\tbut it does the trick for me."<br />
]<br />
</haskell><br />
<br />
You can fake interpolation with:<br />
<haskell><br />
hereDocPraise :: String -> String<br />
hereDocPraise lang = unlines [<br />
"The language with the best here-document support",<br />
"in my opinion is " ++ lang ++ "."<br />
]<br />
</haskell><br />
<br />
Disadvantages to poorer man's here-docs:<br />
* You still need to escape special characters.<br />
* It ends with a newline whether you want one or not.<br />
<br />
----<br />
<br />
See Also<br />
* [[String Interpolation]]<br />
* [http://groups.google.de/group/fa.haskell/msg/bb29c1797fe19caf Poor Man's Heredoc, as originally posted by Claus Reinke to Haskell Cafe]<br />
* http://en.wikipedia.org/wiki/Here_document</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Tags&diff=11964Tags2007-03-14T16:31:06Z<p>Nedervold: added definition</p>
<hr />
<div>== Introduction ==<br />
<br />
"Tags" are a listing of code objects in a group of files, together with their precise location, often used by text editors to quickly jump around in a program. <tt>ctags</tt> (for C) was the first tag-generation program.<br />
<br />
There are currently a number of different ways to generate tags with<br />
Haskell.<br />
<br />
This page should be used to collect information on tag-generation for Haskell, including information on how to use tags with common editors and what benefits they can give you.<br />
<br />
== Haskell tag generators ==<br />
<br />
Chris Ryder and Simon Thompson give a tag generator's source in<br />
[http://www.cs.kent.ac.uk/pubs/2005/2266/content.pdf a paper]<br />
<br />
Norman Ramsey and Kathleen Fisher's partial hasktags implementation<br />
using the GHC API is [http://darcs.haskell.org/ghctags/ in darcs].<br />
There's also a [http://hackage.haskell.org/trac/ghc/ticket/946 GHC trac task] relating to it.<br />
<br />
<tt>echo ":ctags" | ghci -v0 Main.hs</tt><br />
<br />
<tt>echo ":etags" | ghci -v0 Main.hs</tt><br />
<br />
utils/hasktags from GHC.<br />
<br />
== Random other bits ==<br />
<br />
http://vim-taglist.sourceforge.net/<br />
<br />
<pre><br />
vim<br />
:help tags-file-format<br />
:help cursorhold-example<br />
</pre></div>Nedervoldhttps://wiki.haskell.org/index.php?title=Talk:Type_arithmetic&diff=11958Talk:Type arithmetic2007-03-14T04:26:36Z<p>Nedervold: </p>
<hr />
<div>== Why? ==<br />
<br />
This page seems to explain ''what'' but not ''why''. I don't know about anyone else, but when I read 'arithmetic at the type level', the very first thought that pops into my head is 'why in the name of God would you ''want'' to do such an insane thing?' [[User:MathematicalOrchid|MathematicalOrchid]] 11:53, 12 March 2007 (UTC)<br />
<br />
== This why? ==<br />
<br />
Following some discussions in #haskell, I understand this is related to that widespread Haskell obsession with attempting to "prove" things about programs (in spite of the fact that this is obviously impossible).<br />
<br />
If I'm understanding this right, the idea is to be able to construct a type that means not merely "a List containing Integers", but "a List containing at least 6 Integers". And the "arithmetic" part comes in when one wants to say something like<br />
<br />
: "This function takes a List containing at least X objects of type T and another List containing at least Y objects of type T, and returns a List containing at least X+Y objects of type T."<br />
<br />
In other words, the "arithmetic" part is calculating X+Y at compile-time. And any function that calls the one so-described must prove to the type system that it satisfies the constrains. And, once the constraints are statically verified, no further runtime checks are required.<br />
<br />
Is that roughly what this is all about? (And if so, can somebody add some statements to that effect to the content page?) [[User:MathematicalOrchid|MathematicalOrchid]] 20:07, 12 March 2007 (UTC)<br />
<br />
== One example ==<br />
<br />
I'm working on code where I need to handle a stack of objects of different types. I like the security of type-safety, so I use <hask>HList</hask> instead of creating a universal wrapper type, wrapping all the elements, and using a homogenous list. But to index into a heterogenous list, you have to use a type-level index. Then to be able to manipulate the indices, you need to be able to do type-level arithmetic.<br />
<br />
Not necessarily something you'd do every day, but when it's needed, it's needed. --[[User:Nedervold|Nedervold]] 04:26, 14 March 2007 (UTC)</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Programming_guidelines&diff=11478Programming guidelines2007-02-21T18:44:29Z<p>Nedervold: fixed typo</p>
<hr />
<div>Programming guidelines shall help to make the code of a project better<br />
readable and maintainable by the varying number of contributors.<br />
<br />
It takes some programming experience to develop something like a<br />
personal "coding style" and guidelines only serve as rough shape for<br />
code. Guidelines should be followed by all members working on the<br />
project even if they prefer (or are already used to) different<br />
guidelines.<br />
<br />
These guidelines have been originally set up for the hets-project<br />
[http://www.informatik.uni-bremen.de/cofi/hets/ hets-project] and are<br />
now put on the [http://haskell.org/haskellwiki/ HaskellWiki] gradually<br />
integrating parts of [http://haskell.org/hawiki the old hawiki]<br />
entries [http://haskell.org/haskellwiki/Things_to_avoid ThingsToAvoid] and<br />
[http://haskell.org/hawiki/HaskellStyle HaskellStyle] (hopefully not<br />
hurting someone's copyrights). The other related entry<br />
[http://haskell.org/hawiki/TipsAndTricks TipsAndTricks] treats more<br />
specific points that are left out here,<br />
<br />
Surely some style choices are a bit arbitrary (or "religious") and<br />
too restrictive with respect to language extensions. Nevertheless I hope<br />
to keep up these guidelines (at least as a basis) for our project<br />
in order to avoid maintaining diverging guidelines. Of course I want<br />
to supply - partly tool-dependent - reasons for certain decisions and<br />
also show alternatives by possibly bad examples. At the time of<br />
writing I use ghc-6.4.1, haddock-0.7 and (GNU-) emacs with the latest<br />
[http://www.haskell.org/haskell-mode/ haskell mode].<br />
<br />
The following quote and links are taken from<br />
[http://haskell.org/hawiki/HaskellStyle the old general comments]:<br />
<br />
We all have our own ideas about good Haskell style. There's More Than<br />
One Way To Do It. But some ways are better than others.<br />
<br />
Some (unfinished) comments from the GHC team about their internal coding<br />
standards can be found at<br />
http://www.cse.unsw.edu.au/~chak/haskell/ghc/comm/the-beast/coding-style.html<br />
<br />
Also http://research.microsoft.com/~simonpj/papers/haskell-retrospective/<br />
contains some brief comments on syntax and style,<br />
<br />
What now follows are descriptions of program documentation, file<br />
format, naming conventions and good programming practice (adapted form<br />
Matt's C/C++ Programming Guidelines and the Linux kernel coding<br />
style).<br />
<br />
<br />
=== Documentation ===<br />
<br />
<br />
Comments are to be written in application terms (i.e. user's point of<br />
view). Don't use technical terms - that's what the code is for!<br />
<br />
Comments should be written using correct spelling and grammar in complete<br />
sentences with punctation (in English only).<br />
<br />
"Generally, you want your comments to tell WHAT your code does, not HOW.<br />
Also, try to avoid putting comments inside a function body: if the<br />
function is so complex that you need to separately comment parts of it,<br />
you should probably" (... decompose it)<br />
<br />
Put a haddock comment on top of every exported function and data type!<br />
Make sure haddock accepts these comments.<br />
<br />
<br />
=== File Format ===<br />
<br />
<br />
All Haskell source files start with a haddock header of the form:<br />
<br />
<pre><br />
{- |<br />
Module : <File name, i.e. generated by \$Header\$><br />
Description : <Short text displayed on contents page><br />
Copyright : (c) <You> and <Your affiliation><br />
License : similar to LGPL, see LICENSE.txt<br />
<br />
Maintainer : maeder@tzi.de<br />
Stability : provisional<br />
Portability : portable<br />
<br />
<module description starting at first column><br />
-}<br />
</pre><br />
<br />
A possible compiler pragma (like {-# OPTIONS -cpp #-}) may precede<br />
this header. The following hierarchical module name must of course<br />
match the file name.<br />
<br />
Make sure that the description is changed to meet the module (if the<br />
header was copied from elsewhere). Insert your email address as maintainer.<br />
<br />
Try to write portable (Haskell98) code. If you (indirectly) import<br />
a module that uses i.e. multi-parameter type classes and functional<br />
dependencies the code becomes "non-portable (MPTC with FD)".<br />
<br />
The \$Header\$ entry is automatically expanded by cvs (and will wrap<br />
around). All other lines should not be longer than 80 (preferably 75)<br />
characters to avoid wrapped lines (for casual readers)!<br />
<br />
Expand all your tabs to spaces to avoid the danger of wrongly expanding<br />
them (or a different display of tabs versus eight spaces). Possibly put<br />
something like the following in your ~/.emacs file.<br />
<br />
(custom-set-variables '(indent-tabs-mode nil))<br />
<br />
The last character in your file should be a newline! Under solaris<br />
you'll get a warning if this is not the case and sometimes last lines<br />
without newlines are ignored (i.e. "#endif" without newline). Emacs<br />
usually asks for a final newline.<br />
<br />
The whole module should not be too long (about 400 lines)<br />
<br />
<br />
=== Naming Conventions ===<br />
<br />
<br />
In Haskell types start with capital and functions with lowercase<br />
letters, so only avoid infix identifiers! Defining symbolic infix<br />
identifiers should be left to library writers only.<br />
<br />
(The infix identifier "\\" at the end of a line causes cpp preprocessor<br />
problems.)<br />
<br />
Names (especially global ones) should be descriptive and if you need<br />
long names write them as mixed case words (aka camelCase). (but "tmp"<br />
is to be preferred over "thisVariableIsATemporaryCounter")<br />
<br />
Also in the standard libraries, function names with multiple words are<br />
written using the camelCase convention. Similarly, type, typeclass and<br />
constructor names are written using the StudlyCaps convention.<br />
<br />
Some parts of our code use underlines (without unnecessary uppercase<br />
letters) for long identifiers to better reflect names given with<br />
hyphens in the requirement documentation. Also such names should be<br />
transliterated to camlCase identifiers possibly adding a (consistent)<br />
suffix or prefix to avoid conflicts with keywords. However, instead of<br />
a recurring prefix or suffix you may consider to use qualified imports<br />
and names.<br />
<br />
<br />
=== Good Programming Practice ===<br />
<br />
<br />
"Functions should be short and sweet, and do just one thing. They should<br />
fit on one or two screenfuls of text (the ISO/ANSI screen size is 80x24,<br />
as we all know), and do one thing and do that well."<br />
<br />
Most haskell functions should be at most a few lines, only case<br />
expression over large data types (that should be avoided, too) may need<br />
corresponding space.<br />
<br />
The code should be succinct (though not obfuscated), readable and easy to<br />
maintain (after unforeseeable changes). Don't exploit exotic language<br />
features without good reason.<br />
<br />
It's not fixed how deep you indent (4 or 8 chars). You can break the<br />
line after "do", "let", "where", and "case .. of". Make sure that<br />
renamings don't destroy your layout. (If you get to far to the right,<br />
the code is unreadable anyway and needs to be decomposed.)<br />
<br />
Bad:<br />
case foo of Foo -> "Foo"<br />
Bar -> "Bar"<br />
Good:<br />
case <longer expression> of<br />
Foo -> "Foo"<br />
Bar -> "Bar"<br />
<br />
Avoid the notation with braces and semicolons since the layout rule<br />
forces you to properly align your alternatives.<br />
<br />
Respect compiler warnings. Supply type signatures, avoid shadowing and<br />
unused variables. Particularly avoid non-exhaustive and<br />
overlapping patterns. Missing unreachable cases can be filled in using<br />
"error" with a fixed string "<ModuleName>.<function>" to indicate the<br />
error position (in case the impossible should happen). Don't invest<br />
time to "show" the offending value, only do this temporarily when<br />
debugging the code.<br />
<br />
Don't leave unused or commented-out code in your files! Readers don't<br />
know what to think of it.<br />
<br />
<br />
==== Case expressions ====<br />
<br />
Prefer case expressions over pattern binding declarations with<br />
multiple equations.<br />
<br />
Not always nice:<br />
longFunctionName (Foo: _ : _) = e1<br />
longFunctionName (Bar: _) = e2<br />
<br />
Better:<br />
longFunctionName arg = case arg of<br />
Foo : _ : _ -> e1<br />
Bar : _ -> e2<br />
_ -> error "ProgrammingGuidelines.longFunctionName"<br />
<br />
In<br />
http://research.microsoft.com/~simonpj/papers/haskell-retrospective/<br />
the first example is said to be written in "declaration style". The<br />
equations look like written for a rewrite system (although their order<br />
matters of course).<br />
<br />
But this declarative style is only nice for toy examples and annoying<br />
if functions are renamed or if the number of arguments changes.<br />
<br />
The other extreme (according to SPJ) is "expression style":<br />
longFunctionName = \ arg -> ...<br />
<br />
We don't propose this style either. We propose to use as much pattern<br />
matching (including as-patterns) on a single left-hand-side as appropriate.<br />
<br />
However, the expression style with a lambda term may come in handy, when<br />
setting record fields of a function type. <br />
<br />
We avoid lambda expressions if this is easily possibly using the<br />
Prelude functions const, flip, curry, uncurry or section notation or<br />
plain partial application. We do not indroduce an auxiliary function only to<br />
avoid the lambda, though.<br />
<br />
<br />
==== Partial functions ====<br />
<br />
For partial functions do document their preconditions (if not obvious)<br />
and make sure that partial functions are only called when<br />
preconditions are obviously fulfilled (i.e. by a case statement or a<br />
previous test). Particularly the call of "head" should be used with<br />
care or (even better) be made obsolete by a case statement.<br />
<br />
Usually a case statement (and the import of isJust and fromJust from<br />
Data.[[Maybe]]) can be avoided by using the "maybe" function:<br />
<br />
maybe (error "<ModuleName>.<function>") id $ Map.lookup key map<br />
<br />
Generally we require you to be more explicit about failure<br />
cases. Surely a missing (or an irrefutable) pattern would precisely<br />
report the position of a runtime error, but these are not so obvious<br />
when reading the code.<br />
<br />
==== Let or where expressions ====<br />
<br />
Do avoid mixing and nesting "let" and "where". (I prefer the<br />
expression-stylistic "let".) Use auxiliary top-level functions that<br />
you do not export. Export lists also support the detection of unused<br />
functions.<br />
<br />
<br />
==== Code reuse ====<br />
<br />
If you notice that you're doing the same task again, try to generalize<br />
it in order to avoid duplicate code. It is frustrating to change the<br />
same error in several places.<br />
<br />
<br />
==== Application notation ====<br />
<br />
Many parentheses can be eliminated using the infix application operator "$"<br />
with lowest priority. Try at least to avoid unnecessary parentheses in<br />
standard infix expression.<br />
<br />
f x : g x ++ h x<br />
<br />
a == 1 && b == 1 || a == 0 && b == 0<br />
<br />
Rather than putting a large final argument in parentheses (with a<br />
distant closing one) consider using "$" instead.<br />
<br />
"f (g x)" becomes "f $ g x" and consecutive applications<br />
"f (g (h x))" can be written as "f $ g $ h x" or "f . g $ h x".<br />
<br />
A function definition like<br />
"f x = g $ h x" can be abbreviated to "f = g . h".<br />
<br />
Note that the final argument may even be an infix- or case expression:<br />
<br />
map id $ c : l<br />
<br />
filter (const True) . map id $ case l of ...<br />
<br />
However, be aware that $-terms cannot be composed further in infix<br />
expressions.<br />
<br />
Probably wrong:<br />
f $ x ++ g $ x<br />
<br />
But the scope of an expression is also limited by the layout rule, so<br />
it is usually save to use "$" on right hand sides.<br />
<br />
Ok:<br />
do f $ l<br />
++<br />
do g $ l<br />
<br />
Of course "$" can not be used in types. GHC has also some primitive<br />
functions involving the kind "#" that cannot be applied using "$".<br />
<br />
Last warning: always leave spaces around "$" (and other mixfix<br />
operators) since a clash with template haskell is possible.<br />
<br />
(Also write "\ t" instead of "\t" in lambda expressions)<br />
<br />
<br />
==== List Comprehensions ====<br />
<br />
Use these only when "short and sweet". Prefer map, filter, and foldr!<br />
<br />
Instead of:<br />
<br />
[toUpper c | c <- s]<br />
<br />
write:<br />
<br />
map toUpper s<br />
<br />
<br />
Consider:<br />
<br />
[toUpper c | s <- strings, c <- s]<br />
<br />
Here it takes some time for the reader to find out which value depends<br />
on what other value and it is not so clear how many times the interim<br />
values s and c are used. In contrast to that the following can't be clearer:<br />
<br />
map toUpper (concat strings)<br />
<br />
<br />
When using higher order functions you can switch easier to data<br />
structures different from list. Compare:<br />
<br />
map (1+) list<br />
<br />
and:<br />
<br />
Set.map (1+) set<br />
<br />
<br />
==== Types ====<br />
<br />
Prefer proper data types over type synonyms or tuples even if you have<br />
to do more constructing and unpacking. This will make it easier to<br />
supply class instances later on. Don't put class constraints on<br />
a data type, constraints belong only to the functions that manipulate<br />
the data.<br />
<br />
Using type synonyms consistently is difficult over a longer time,<br />
because this is not checked by the compiler. (The types shown by<br />
the compiler may be unpredictable: i.e. FilePath, String or [Char])<br />
<br />
Take care if your data type has many variants (unless it is an<br />
enumeration type.) Don't repeat common parts in every variant since<br />
this will cause code duplication.<br />
<br />
Bad (to handle arguments in sync):<br />
<br />
data Mode f p = Box f p | Diamond f p<br />
<br />
Good (to handle arguments only once):<br />
<br />
data BoxOrDiamond = Box | Diamond<br />
<br />
data Mode f p = Mode BoxOrDiamond f p<br />
<br />
<br />
Consider (bad):<br />
<br />
data Tuple a b = Tuple a b | Undefined<br />
<br />
versus (better):<br />
<br />
data Tuple a b = Tuple a b<br />
<br />
and using:<br />
<br />
Maybe (Tuple a b)<br />
<br />
(or another monad) whenever an undefined result needs to be propagated<br />
<br />
<br />
==== Records ====<br />
<br />
For (large) records avoid the use of the constructor directly and<br />
remember that the order and number of fields may change.<br />
<br />
Take care with (the rare case of) depend polymorphic fields:<br />
<br />
data Fields a = VariantWithTwo <br />
{ field1 :: a<br />
, field2 :: a }<br />
<br />
The type of a value v can not be changed by only setting field1:<br />
<br />
v { field1 = f }<br />
<br />
Better construct a new value:<br />
<br />
VariantWithTwo { field1 = f } -- leaving field2 undefined<br />
<br />
Or use a polymorphic element that is instantiated by updating:<br />
<br />
empty = VariantWithTwo { field1 = [], field2 = [] }<br />
<br />
empty { field1 = [f] }<br />
<br />
Several variants with identical fields may avoid some code duplication<br />
when selecting and updating, though possibly not in a few<br />
depended polymorphic cases.<br />
<br />
However, I doubt if the following is a really good alternative to the<br />
above data Mode with data BoxOrDiamond.<br />
<br />
<br />
data Mode f p =<br />
Box { formula :: f, positions :: p }<br />
| Diamond { formula :: f, positions :: p }<br />
<br />
<br />
==== IO ====<br />
<br />
Try to strictly separate IO, Monad and pure (without do) function<br />
programming (possibly via separate modules).<br />
<br />
Bad:<br />
x <- return y<br />
...<br />
<br />
Good:<br />
let x = y<br />
...<br />
<br />
<br />
Don't use Prelude.interact and make sure your program does not depend<br />
on the (not always obvious) order of evaluation. I.e. don't read and<br />
write to the same file:<br />
<br />
This will fail:<br />
<br />
do s <- readFile f<br />
writeFile f $ 'a' : s<br />
<br />
because of lazy IO! (Writing is starting before reading is finished.)<br />
<br />
<br />
==== Trace ====<br />
<br />
Tracing is for debugging purposes only and should not be used as<br />
feedback for the user. Clean code is not cluttered by trace calls.<br />
<br />
<br />
==== Imports ====<br />
<br />
Standard library modules like Char. List, Maybe, Monad, etc should be<br />
imported by their hierarchical module name, i.e. the base package (so<br />
that haddock finds them):<br />
<br />
import Data.List<br />
import Control.Monad<br />
import System.Environment<br />
<br />
The libraries for Set and Map are to be imported qualified:<br />
<br />
import qualified Data.Set as Set<br />
import qualified Data.Map as Map<br />
<br />
<br />
==== Glasgow extensions and Classes ====<br />
<br />
Stay away from extensions as long as possible. Also use classes with<br />
care because soon the desire for overlapping instances (like for lists<br />
and strings) may arise. Then you may want MPTC (multi-parameter type<br />
classes), functional dependencies (FD), undecidable and possibly incoherent<br />
instances and then you are "in the wild" (according to SPJ).<br />
<br />
=== Style in other languages ===<br />
<br />
* [http://www.cs.caltech.edu/~cs20/a/style.html OCaml style]<br />
<br />
=== Final remarks ===<br />
<br />
Despite guidelines, writing "correct code" (without formal proof<br />
support yet) still remains the major challenge. As motivation to<br />
follow these guidelines consider the points that are from the "C++<br />
Coding Standard", where I replaced "C++" with "Haskell".<br />
<br />
Good Points:<br />
<br />
* programmers can go into any code and figure out what's going on<br />
<br />
* new people can get up to speed quickly<br />
<br />
* people new to Haskell are spared the need to develop a personal style and defend it to the death<br />
<br />
* people new to Haskell are spared making the same mistakes over and over again<br />
<br />
* people make fewer mistakes in consistent environments<br />
<br />
* programmers have a common enemy :-)<br />
<br />
Bad Points:<br />
<br />
* the standard is usually stupid because it was made by someone who doesn't understand Haskell<br />
<br />
* the standard is usually stupid because it's not what I do<br />
<br />
* standards reduce creativity<br />
<br />
* standards are unnecessary as long as people are consistent<br />
<br />
* standards enforce too much structure<br />
<br />
* people ignore standards anyway<br />
<br />
<br />
<br />
[[Category:Style]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Haskell_Quiz&diff=11017Haskell Quiz2007-02-04T05:34:22Z<p>Nedervold: spelling</p>
<hr />
<div>A collection of solutions to the [http://www.rubyquiz.com Ruby quiz] puzzles in simple, elegant Haskell.<br />
<br />
As you solve the puzzles, please contribute your code, and create a page<br />
for the puzzle entries. When creating a new page for your source, be<br />
sure to categorise it as code, with a [ [ Category:Code ] ] tag.<br />
<br />
== The Puzzles ==<br />
<br />
1. [[Haskell Quiz/The Solitaire Cipher|The Solitaire Cipher]]<br />
<br />
2. [[Haskell Quiz/Secret Santas|Secret Santas]]<br />
<br />
7. [[Haskell Quiz/Countdown|Countdown]]<br />
<br />
15. [[Haskell Quiz/Animal Quiz|Animal Quiz]]<br />
<br />
19. [[Haskell Quiz/Yahtzee|Yahtzee]]<br />
<br />
20. [[Haskell Quiz/Phone Number Words|Phone Number Words]]<br />
<br />
22. [[Haskell Quiz/Roman Numerals|Roman Numerals]]<br />
<br />
25. [[Haskell Quiz/English Numerals|English Numerals]]<br />
<br />
27. [[Haskell Quiz/Knight's Travails|Knight's Travails]]<br />
<br />
31. [[Haskell Quiz/Amazing Mazes|Amazing Mazes]]<br />
<br />
33. [[Haskell Quiz/Tiling Turmoil|Tiling Turmoil]]<br />
<br />
39. [[Haskell Quiz/Sampling|Sampling]]<br />
<br />
43. [[Haskell Quiz/Sodoku Solver|Sodoku Solver]]<br />
<br />
54. [[Haskell Quiz/Index and Query|Text Index and Query]]<br />
<br />
57. [[Haskell Quiz/Weird Numbers|Weird Numbers]]<br />
<br />
60. [[Haskell Quiz/Numeric Maze|Numeric Maze]]<br />
<br />
63. [[Haskell Quiz/Grid Folding|Grid Folding]]<br />
<br />
65. [[Haskell Quiz/Splitting the Loot|Splitting the Loot]]<br />
<br />
70. [[Haskell Quiz/Constraint Processing|Constraint Processing]] <br />
<br />
76. [[Haskell Quiz/Text Munger|Text Munger]]<br />
<br />
77. [[Haskell Quiz/Cat2Rafb|cat2rafb]]<br />
<br />
84. [[Haskell Quiz/PP Pascal|PP Pascal]]<br />
<br />
92. [[Haskell Quiz/DayRange|DayRange]]<br />
<br />
93. [[Haskell Quiz/Happy Numbers|Happy Numbers]]<br />
<br />
97. [[Haskell Quiz/Posix Pangrams|Posix Pangrams]]<br />
<br />
98. [[Haskell Quiz/Astar|A*]]<br />
<br />
99. [[Haskell Quiz/Fuzzy Time|Fuzzy Time]]<br />
<br />
100. [[Haskell Quiz/Bytecode Compiler|Bytecode Compiler]]<br />
<br />
106. [[Haskell Quiz/Chess960|Chess960]]<br />
<br />
107. [[Haskell Quiz/Word Search|Word Search]]<br />
<br />
108. [[Haskell Quiz/Word Blender|Word Blender]]<br />
<br />
==Possibly fun ones not yet done in haskell==<br />
<br />
3. Geodesic Dome Faces http://www.rubyquiz.com/quiz3.html<br />
<br />
11. Learning Tic-Tac-Toe http://www.rubyquiz.com/quiz11.html<br />
<br />
37. Inference Engine http://www.rubyquiz.com/quiz37.html<br />
<br />
48. Math Captcha http://www.rubyquiz.com/quiz48.html<br />
<br />
49. Text Image http://www.rubyquiz.com/quiz50.html (Not sure how image loading will work)<br />
<br />
85. C-Style Ints http://www.rubyquiz.com/quiz85.html<br />
<br />
87. Negative Sleep http://www.rubyquiz.com/quiz87.html (As a Monad!!!)<br />
<br />
88. Chip-8 http://www.rubyquiz.com/quiz88.html<br />
<br />
Many weren't included because of either clumsy ASCII output, or requiring a dictionary. Perhaps a dictionary module could be created and those problems attacked in a unified fashion.<br />
<br />
[[Category:Code]]<br />
[[Category:Haskell Quiz|*]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Knight%27s_Travails&diff=11015Haskell Quiz/Knight's Travails2007-02-04T05:33:38Z<p>Nedervold: Haskell Quiz/Knight's Trevails moved to Haskell Quiz/Knight's Travails</p>
<hr />
<div>RubyQuiz #27: A program that calculates the shortest path between 2 squares on a chess board using only Knight moves (and with optional list of forbidden squares)<br />
<br />
==The Problem==<br />
<br />
* http://www.rubyquiz.com/quiz27.html<br />
<br />
==Solutions==<br />
<br />
* [[Haskell Quiz/Knight's Travails/Solution LukePlant|Luke Plant]]<br />
<br />
[[Category:Haskell Quiz|Knight's Travails]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Haskell_Quiz/Knight%27s_Trevails&diff=11016Haskell Quiz/Knight's Trevails2007-02-04T05:33:38Z<p>Nedervold: Haskell Quiz/Knight's Trevails moved to Haskell Quiz/Knight's Travails: misspelling of "travails"</p>
<hr />
<div>#redirect [[Haskell Quiz/Knight's Travails]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Category_theory&diff=10995Category theory2007-02-03T18:31:50Z<p>Nedervold: fixed typos, some rewording</p>
<hr />
<div>{{Foundations infobox}}<br />
'''Category theory''' can be helpful in understanding Haskell's type system. There exists a "Haskell category", of which the objects are Haskell types, and the morphisms from types <hask>a</hask> to <hask>b</hask> are Haskell functions of type <hask>a -> b</hask>. Various other Haskell structures can be used to make it a Cartesian closed category.<br />
<br />
__TOC__<br />
<br />
<br />
==Defintion of a category==<br />
<br />
<br />
A category <math>\mathcal{C}</math>consists of two collections:<br />
<br />
Ob<math>(\mathcal{C})</math>, the objects of <math>\mathcal{C}</math><br />
<br />
Ar<math>(\mathcal{C})</math>, the arrows of <math>\mathcal{C}</math><br />
(which are not the same as [[Arrow]]s defined in [[GHC]])<br />
<br />
Each arrow <math>f</math> in Ar<math>(\mathcal{C})</math> has a<br />
domain, dom <math>f</math>, and a codomain, cod <math>f</math>, each<br />
chosen from Ob<math>(\mathcal{C})</math>. The notation <math>f\colon<br />
A \to B</math> means <math>f</math> is an arrow with domain<br />
<math>A</math> and codomain <math>B</math>. Further, there is a<br />
function <math>\circ</math> called composition, such that <math>g<br />
\circ f</math> is defined only when the codomain of <math>f</math> is<br />
the domain of <math>g</math>, and in this case, <math>g \circ f</math><br />
has the domain of <math>f</math> and the codomain of <math>g</math>. <br />
<br />
In symbols, if <math>f\colon A \to B</math> and <math>g\colon B \to<br />
C</math>, then <math>g \circ f \colon A \to C</math>. <br />
<br />
Also, for each object <math>A</math>, there is an arrow<br />
<math>\mathrm{id}_A\colon A \to A</math>, (often simply denoted as<br />
<math>1</math> or <math>\mathrm{id}</math>, when there is no chance of<br />
confusion). <br />
<br />
===Axioms===<br />
The following axioms must hold for <math>\mathcal{C}</math> to be a category:<br />
<br />
#If <math>f\colon A \to B</math> then <math>f \circ \mathrm{id}_A = \mathrm{id}_B\circ f = f</math> (left and right identity) <br />
#If <math>f\colon A \to B</math> and <math>g \colon B \to C</math> and <math>h \colon C \to D</math>, then <math>h \circ (g \circ f) = (h<br />
\circ g) \circ f</math> (associativity) <br />
<br />
===Examples of categories===<br />
* Set, the category of sets and set functions.<br />
* Mon, the category of monoids and monoid morphisms.<br />
* Monoids are themselves one-object categories.<br />
* Grp, the category of groups and group morphisms.<br />
* Rng, the category of rings and ring morphisms.<br />
* Grph, the category of graphs and graph morphisms.<br />
* Top, the category of topological spaces and continuous maps.<br />
* Preord, the category of preorders and order preserving maps.<br />
* CPO, the category of complete partial orders and continuous functions.<br />
* Cat, the category of categories and functors.<br />
<br />
* the category of data types and functions on data structures<br />
* the category of functions and data flows (~ data flow diagram)<br />
* the category of stateful objects and dependencies (~ object diagram)<br />
* the category of values and value constructors<br />
* the category of states and messages (~ state diagram)<br />
<br />
===Further definitions===<br />
With examples in Haskell at:<br />
* [[Category theory/Functor]]<br />
* [[Category theory/Natural transformation]]<br />
* [[Category theory/Monads]]<br />
<br />
== Categorical programming ==<br />
<br />
Catamorphisms and related concepts, categorical approach to functional programming, categorical programming. Many materials cited here refer to category theory, so as an introduction to this discipline see the [[#See also]] section.<br />
* Erik Meijer, Maarten Fokkinga, Ross Paterson: [http://citeseer.ist.psu.edu/meijer91functional.html Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire]. See also related documents (in the CiteSeer page). Understanding the article does not require knowledge of category theory—the paper is self-contained with regard to understanding catamorphisms, anamorphisms and other related concepts.<br />
* Varmo Vene and Tarmo Uustalu: [http://citeseer.ist.psu.edu/vene98functional.html Functional Programming with Apomorphisms / Corecursion]<br />
* Varmo Vene: [http://www.cs.ut.ee/~varmo/papers/thesis.pdf Categorical Programming with Inductive and Coinductive Types]. The book gives Haskell examples to illustrate the deep categorical theory topic.<br />
* Tatsuya Hagino: [http://www.tom.sfc.keio.ac.jp/~hagino/thesis.pdf A Categorical Programming Language]<br />
* [http://pll.cpsc.ucalgary.ca/charity1/www/home.html Charity], a categorical programming language implementation.<br />
* [http://okmij.org/ftp/Haskell/categorical-maxn.lhs Deeply uncurried products, as categorists might like them] article mentions a conjecture: relatedness to [[Combinatory logic]]<br />
<br />
==See also==<br />
<br />
* Michael Barr and Charles Wells have a [http://www.math.upatras.gr/~cdrossos/Docs/B-W-LectureNotes.pdf paper] that presents category theory from a computer-science perspective, assuming no prior knowledge of categories.<br />
*Michael Barr and Charles Wells: [http://www.cwru.edu/artsci/math/wells/pub/ttt.html Toposes, Triples and Theories]. The online, freely available book is both an introductory and a detailed description of category theory. It also contains a category-theoretical description of the concept of ''monad'' (but calling it a ''triple'' instead of ''monad'').<br />
*[http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.html A Gentle Introduction to Category Theory - the calculational approach] written by [http://wwwhome.cs.utwente.nl/~fokkinga/index.html Maarten M Fokkinga].<br />
* Wikipedia has a good [http://en.wikipedia.org/List_of_category_theory_topics collection of category-theory articles], although, as is typical of Wikipedia articles, they are rather dense.<br />
<br />
[[Category:Theoretical foundations]]<br />
[[Category:Mathematics]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Alpha_conversion&diff=10993Alpha conversion2007-02-03T18:23:25Z<p>Nedervold: </p>
<hr />
<div>An ''alpha conversion'' (also written ''&alpha; conversion'') is a renaming of variables.<br />
<br />
{{Foundations infobox}}<br />
For example, suppose we have an expression such as<br />
<haskell><br />
\x y -> 2*x*x + y<br />
</haskell><br />
and we change this to<br />
<haskell><br />
\a b -> 2*a*a + b<br />
</haskell><br />
This is clearly the same function, even though it uses different variable names. This process of renaming variables is ''alpha conversion''.<br />
<br />
Note that alpha conversion is not as simple as it first seems. We must be careful to avoid ''name capture''. For example, if we rename <hask>x</hask> to <hask>y</hask> in <hask>\x -> x + y</hask> then we end up with <hask>\y -> y + y</hask>, which is not the same function!<br />
<br />
Some compilers include an alpha-conversion stage to rename all program variables such that variable names become unique. (This simplifies subsequent processing somewhat.)<br />
<br />
[[Category:Glossary]]<br />
<br />
Also see [[Lambda calculus]] and the [http://en.wikipedia.org/wiki/Lambda_calculus wikipedia lambda calculus article].</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Beta_reduction&diff=10992Beta reduction2007-02-03T18:22:16Z<p>Nedervold: </p>
<hr />
<div>A ''beta reduction'' (also written ''&beta; reduction'') is the process of calculating a result from the application of a function to an expression.<br />
<br />
{{Foundations infobox}}<br />
For example, suppose we apply the function<br />
<haskell><br />
(\x -> 2*x*x + y)<br />
</haskell><br />
to the value <hask>7</hask>. To calculate the result, we substitute <hask>7</hask> for every [[Free variable|free occurrence]] of <hask>x</hask>, and so the application of the function<br />
<haskell><br />
(\x -> 2*x*x + y)(7)<br />
</haskell><br />
is ''reduced'' to the result<br />
<haskell><br />
2*7*7 + y<br />
</haskell><br />
This is a ''beta reduction''.<br />
<br />
(Further reductions could be applied to reduce <hask>2*7*7</hask> to <hask>98</hask>. Although the lambdas are not explicit, they exist hidden in the definition of <hask>(*)</hask>.)<br />
<br />
Also see [[Lambda calculus]] and the [http://en.wikipedia.org/wiki/Lambda_calculus wikipedia lambda calculus article].<br />
<br />
[[Category:Glossary]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Lambda_abstraction&diff=10991Lambda abstraction2007-02-03T18:08:19Z<p>Nedervold: eta -> beta plus minor changes</p>
<hr />
<div>A ''lambda abstraction'' is another name for an [[anonymous function]]. It gets its name from the usual notation for writing it: for example, <math>\lambda x \to x^2</math>. (Another common but equivalent notation is: <math>\lambda x . \ x^2</math>.)<br />
<br />
In Haskell source code, the Greek letter lambda is replaced by a backslash character ('<hask>\</hask>') instead, since this is easier to type and requires only the basic 7-bit ASCII character set. Similarly, the arrow is replaced with the much more ugly (but strictly ASCII) character sequence '<hask>-></hask>'. So, for example, the lambda abstraction above would be written in Haskell as<br />
<br />
<haskell><br />
\ x -> x * x<br />
</haskell><br />
<br />
There is actually a whole mathematical theory devoted to expressing computation entirely using lambda abstractions: the [[lambda calculus]]. Most functional programming languages (including Haskell) are based upon some extension of this idea.<br />
<br />
When a lambda abstraction is applied to a value—for instance, <math>(\lambda x \to x^2 ) \ 7</math>—the result of the expression is determined by replacing every [[free variable|free occurrence]] of the parameter variable (in this case <math>x</math>) with the parameter value (in this case <math>7</math>). This is a [[Beta reduction|beta reduction]].</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Eta_conversion&diff=10874Eta conversion2007-01-30T03:40:44Z<p>Nedervold: </p>
<hr />
<div>An ''eta conversion'' (also written ''&eta;-conversion'') is adding or dropping of abstraction over a function. For example, the following two values are equivalent under &eta;-conversion: <haskell>\x -> abs x<br />
</haskell>and <haskell>abs</haskell><br />
<br />
Extensive use of &eta;-reduction can lead to [[Pointfree]] programming.<br />
<br />
[[Category:Glossary]]</div>Nedervoldhttps://wiki.haskell.org/index.php?title=Roman_numerals&diff=9629Roman numerals2006-12-20T17:52:00Z<p>Nedervold: code was running off page</p>
<hr />
<div>The system of '''Roman numerals''' is a numeral system originating in ancient Rome, and was adapted from Etruscan numerals. The system used in classical antiquity was slightly modified in the Middle Ages to produce the system we use today. It is based on certain letters which are given values as numerals.<br />
<br />
== Oneliner ==<br />
<br />
This is a nearly-completely points-freed expression which evaluates a given Roman numeral as a String to the corresponding Int. The folded function is not points-freed for ease of reading, and it would also need an `if' function which needs separate definition.<br />
<br />
<haskell><br />
import Data.Maybe (fromJust)<br />
<br />
romanToInt :: String -> Int<br />
romanToInt = fs<br />
. foldr (\p (t,s) -> if p >= s then (t+p,p) else (t-p,p)) (0,0)<br />
. map (fromJust . flip lookup (zip "IVXLCDM" [1,5,10,50,100,500,1000]))<br />
</haskell><br />
<br />
== Roman (type-)numerals ==<br />
<br />
The function `roman' here infers the value of the Roman numeral from the type of its first argument, which in turn is left unevaluated, and returns it as an Int.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
module Romans where<br />
<br />
class Roman t where<br />
roman :: t -> Int<br />
<br />
data O -- 0<br />
data I a -- 1<br />
data V a -- 5<br />
data X a -- 10<br />
data L a -- 50<br />
data C a -- 100<br />
data D a -- 500<br />
data M a -- 1000<br />
<br />
instance Roman O where roman _ = 0<br />
instance Roman (I O) where roman _ = 1<br />
instance Roman (V O) where roman _ = 5<br />
instance Roman (X O) where roman _ = 10<br />
<br />
instance Roman (I a) => Roman (I (I a)) where roman _ = roman (undefined :: (I a)) + 1<br />
instance Roman a => Roman (I (V a)) where roman _ = roman (undefined :: a) + 4<br />
instance Roman a => Roman (I (X a)) where roman _ = roman (undefined :: a) + 9<br />
<br />
instance Roman (I a) => Roman (V (I a)) where roman _ = roman (undefined :: (I a)) + 5<br />
instance Roman (V a) => Roman (V (V a)) where roman _ = roman (undefined :: (V a)) + 5<br />
<br />
instance Roman (I a) => Roman (X (I a)) where roman _ = roman (undefined :: (I a)) + 10<br />
instance Roman (V a) => Roman (X (V a)) where roman _ = roman (undefined :: (V a)) + 10<br />
instance Roman (X a) => Roman (X (X a)) where roman _ = roman (undefined :: (X a)) + 10<br />
instance Roman a => Roman (X (L a)) where roman _ = roman (undefined :: a) + 40<br />
instance Roman a => Roman (X (C a)) where roman _ = roman (undefined :: a) + 90<br />
instance Roman a => Roman (X (D a)) where roman _ = roman (undefined :: a) + 490<br />
<br />
instance Roman a => Roman (L a) where roman _ = roman (undefined :: a) + 50<br />
<br />
instance Roman (I a) => Roman (C (I a)) where roman _ = roman (undefined :: (I a)) + 100<br />
instance Roman (V a) => Roman (C (V a)) where roman _ = roman (undefined :: (V a)) + 100<br />
instance Roman (X a) => Roman (C (X a)) where roman _ = roman (undefined :: (X a)) + 100<br />
instance Roman (L a) => Roman (C (L a)) where roman _ = roman (undefined :: (L a)) + 100<br />
instance Roman (C a) => Roman (C (C a)) where roman _ = roman (undefined :: (C a)) + 100<br />
instance Roman a => Roman (C (D a)) where roman _ = roman (undefined :: a) + 400<br />
instance Roman a => Roman (C (M a)) where roman _ = roman (undefined :: a) + 900<br />
<br />
instance Roman a => Roman (D a) where roman _ = roman (undefined :: a) + 500<br />
<br />
instance Roman a => Roman (M a) where roman _ = roman (undefined :: a) + 1000<br />
<br />
-- Example type: XVI ~> X (V (I O)); MCMXCIX ~> M (C (M (X (C (I (X O))))))<br />
<br />
powersoftwo = [roman (undefined :: (I (I O))),<br />
roman (undefined :: (I (V O))),<br />
roman (undefined :: (V (I (I (I O))))),<br />
roman (undefined :: (X (V (I O)))),<br />
roman (undefined :: (X (X (X (I (I O)))))),<br />
roman (undefined :: (L (X (I (V O))))),<br />
roman (undefined :: (C (X (X (V (I (I (I O)))))))),<br />
roman (undefined :: (C (C (L (V (I O)))))),<br />
roman (undefined :: (D (X (I (I O))))),<br />
roman (undefined :: (M (X (X (I (V O)))))),<br />
roman (undefined :: (M (M (X (L (V (I (I (I O)))))))))]<br />
</haskell><br />
<br />
== With data constructors ==<br />
<br />
I think there is also some simpler solution using<br />
<haskell><br />
data RomanDigit a =<br />
O -- 0<br />
| I a -- 1<br />
| V a -- 5<br />
| X a -- 10<br />
| L a -- 50<br />
| C a -- 100<br />
| D a -- 500<br />
| M a -- 1000<br />
</haskell><br />
if not only an enumeration of digits which can be used in a regular list.<br />
<br />
<br />
[[Category:Idioms]]<br />
[[Category:Mathematics]]</div>Nedervold