https://wiki.haskell.org/api.php?action=feedcontributions&user=Blaisorblade&feedformat=atomHaskellWiki - User contributions [en]2024-03-19T12:11:34ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=MonadPlus_reform_proposal&diff=59878MonadPlus reform proposal2015-06-23T18:22:14Z<p>Blaisorblade: Question unbiased MonadPlus instance for Maybe</p>
<hr />
<div>The [[MonadPlus]] class is ambiguous: while all instances satisfy '''Monoid''' and '''Left Zero''', some such as <tt>[]</tt> satisfy '''Left Distribution''', while others such as <tt>Maybe</tt> and <tt>IO</tt> satisfy '''Left Catch'''.<br />
<br />
== Proposal ==<br />
<br />
It is proposed that MonadPlus be split like this:<br />
<br />
=== MonadZero ===<br />
<br />
<haskell><br />
class Monad m => MonadZero m where<br />
mzero :: m a<br />
</haskell><br />
<br />
satisfying '''Left Zero''':<br />
<br />
<haskell><br />
mzero >>= k = mzero<br />
</haskell><br />
<br />
=== MonadPlus ===<br />
<br />
<haskell><br />
class MonadZero m => MonadPlus m where<br />
mplus :: m a -> m a -> m a<br />
</haskell><br />
<br />
satisfying '''Monoid''' and '''Left Distribution''':<br />
<br />
<haskell><br />
mplus mzero b = b<br />
mplus a mzero = a<br />
mplus (mplus a b) c = mplus a (mplus b c)<br />
mplus a b >>= k = mplus (a >>= k) (b >>= k)<br />
</haskell><br />
<br />
=== MonadOr ===<br />
<br />
<haskell><br />
class MonadZero m => MonadOr m where<br />
morelse :: m a -> m a -> m a<br />
</haskell><br />
<br />
satisfying '''Monoid''' and '''Left Catch''':<br />
<br />
<haskell><br />
morelse mzero b = b<br />
morelse a mzero = a<br />
morelse (morelse a b) c = morelse a (morelse b c)<br />
morelse (return a) b = return a<br />
</haskell><br />
<br />
== Instances of both ==<br />
<br />
Some types could be made instances of both. For instance:<br />
<br />
<haskell><br />
instance MonadOr [] where<br />
morelse [] b = b<br />
morelse a b = a<br />
</haskell><br />
<br />
The left-biased implementation of mplus for the Maybe monad should be used as an implementation of morelse, but it is also possible to give an unbiased mplus for Maybe:<br />
<br />
<haskell><br />
instance MonadPlus Maybe where<br />
mplus (Just a) Nothing = Just a<br />
mplus Nothing (Just a) = Just a<br />
mplus _ _ = Nothing<br />
<br />
instance MonadOr Maybe where<br />
morelse (Just a) _ = Just a<br />
morelse _ b = b<br />
</haskell><br />
<br />
Question: But does this instance satisfy '''Left Distribution'''? If a = Just v1 and b = Just v2, '''Left Distribution''' implies that Nothing = mplus (k v1) (k v2), which isn't generally true — take for instance<br />
<haskell><br />
v1 = 0<br />
v2 = 1<br />
f 0 = Just 0<br />
f 1 = Nothing<br />
</haskell><br />
<br />
Am I missing something? -- Blaisorblade<br />
<br />
== Discussion ==<br />
Given that Control.Applicative(Alternative) now defines a class which seems innately bound to '''Left Catch''', at least in spirit, it seems to make sense to clean up MonadPlus such that all instances obey '''Left Distribution'''? --sclv<br />
<br />
I'd actually suggest almost the opposite, that MonadPlus be dispensed with and merged into Monad. The (controversial) fail method looks no different than an mzero, except the string argument; indeed, so far as I know <tt>fail s</tt> is just mzero for any MonadPlus. MonadPlus is also barely made use of; just guard and msum in the standard? To be concrete, I would make the following the default definitions (in Monad):<br />
<br />
<haskell><br />
mzero = fail "something"<br />
mplus a b = a<br />
</haskell><br />
<br />
These are thus somewhat trivial by default, but having msum=head and guard=assert (roughly; more like <tt>(`assert` return ())</tt>) for less-flexible monads doesn't seem actually wrong and could be useful fallbacks.<br />
<br />
I also question the claim that Maybe and IO should be thought of as "left catch". IO is not even in MonadPlus, and I don't see how it can be meaningfully in any way other than the above. Maybe does satisfy Left Catch, but it seems almost like that's only because it's such a simple monad (holding only one value). It is a useful observation that it fails Left Distribution, but that may only call for weaker Monad/Plus conditions.<br />
<br />
The MonadOr idea is a solid one, but it seems to be taking the monad in a different direction. So if there's a good match in Control.Applicative or Parsec, that might be the best place to develop that idea. -- Galen<br />
<br />
The default <hask>mplus</hask> doesn't satisfy <hask>mplus mzero b = b</hask>, so you lose Monoid which seems to be the only thing people actually agree on :) -- [[User:Benmachine|Benmachine]]<br />
<br />
[[Category:Proposals]] [[Category:Monad]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=GHC/Using_rules&diff=58185GHC/Using rules2014-05-23T10:33:50Z<p>Blaisorblade: Merge lines to prevent unintended line breaks in output (and fix typo)</p>
<hr />
<div>[[Category:GHC|Rules]]<br />
[[Category:Performance]]<br />
[[Category:Program transformation]]<br />
== Using rules in GHC ==<br />
<br />
GHC's rewrite rules (invoked by the RULES pragma) offer a powerful way to optimise your program. This page is a place for people who use rewrite rules to collect thoughts about how to use them.<br />
<br />
If you aren't already familiar with RULES, read this stuff first:<br />
* [http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html The relevant section of the GHC user manual]<br />
* [http://research.microsoft.com/%7Esimonpj/Papers/rules.htm Playing by the rules: rewriting as a practical optimisation technique in GHC]. This paper, from the 2001 Haskell workshop, describes the idea of rewrite rules.<br />
<br />
=== Advice about using rewrite rules ===<br />
<br />
* Remember to use the flag <tt>-fglasgow-exts</tt> and the optimisation flag <tt>-O</tt><br />
* Use the flag <tt>-ddump-simpl-stats</tt> to see how many rules actually fired.<br />
* For even more detail use <tt>-ddump-simpl-stats -ddump-simpl-iterations</tt> to see the core code at each iteration of the simplifer. Note that this produces '''lots''' of output so you'll want to direct the output to a file or pipe it to <tt>less</tt>. Looking at the output of this can help you figure out why rules are not firing when you expect them to do so.<br />
* Another tip for discovering why rules do not fire, is to use the flag <tt>-dverbose-core2core</tt>, which (amongst other things) produces the AST after every rule is fired. This can help you to examine whether one rule is creating an expression that thereby prevents another rule from firing, for example.<br />
* You need to be careful that your identifiers aren't inlined before your RULES have a chance to fire. Consider<br />
<haskell><br />
{-# INLINE nonFusable #-}<br />
{-# RULES "fusable/aux" forall x y.<br />
fusable x (aux y) = faux x y ; #-}<br />
nonFusable x y = fusable x (aux y)<br />
</haskell><br />
: You are possibly surprised when the rule for <hask>fusable</hask> does not fire. It may well be that <hask>fusable</hask> was inlined before rules were applied.<br />
: To control this we add an <hask>NOINLINE</hask> or an <hask>INLINE [1]</hask> pragma to identifiers we want to match in rules, to ensure they haven't disappeared by the time the rule matching comes around.<br />
<br />
To have rewrite rules fire in code interpreted in GHCi, you'll need<br />
to explicitly ask for -frewrite-rules in an options pragma at the<br />
start of your file.<br />
<br />
=== Structure of simplification process ===<br />
<br />
There are currently the simplifier phases "gentle", 2, 1, 0, each consisting of 4 iterations.<br />
Starting with GHC 6.10 you can alter these numbers with the command line options <code>-fsimplifier-phases</code> and <code>-fmax-simplifier-iterations</code>.<br />
However in each iteration rules are applied multiple times, until rules can no longer be applied.<br />
That rules can no longer be applied is due to the fact that the simplifier chooses some way from outer to inner or reverse.<br />
Actually it's always the same, but you should not rely on a particular order, mind you?<br />
The good effect is that arbitrary big expressions of the type <hask>map f0 . map f1 . ... . map fn</hask><br />
can be collapsed to a single <hask>map</hask> by the single rule <hask>map f (map g xs) = map (f . g) xs</hask>.<br />
The bad effect is that rules like <hask>f x y = f y x</hask> lead to an infinite loop.<br />
<br />
=== Example: <hask>map</hask> ===<br />
<br />
(This example code is taken from GHC's <tt>base/GHC/Base.lhs</tt> module.)<br />
<br />
map :: (a -> b) -> [a] -> [b]<br />
map _ [] = []<br />
map f (x:xs) = f x : map f xs<br />
<br />
mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst<br />
{-# INLINE [0] mapFB #-}<br />
mapFB c f x ys = c (f x) ys<br />
<br />
The rules for map work like this.<br />
<br />
Up to (but not including) phase 1, we use the <tt>"map"</tt> rule to<br />
rewrite all saturated applications of map with its build/fold<br />
form, hoping for fusion to happen.<br />
In phase 1 and 0, we switch off that rule, inline build, and<br />
switch on the <tt>"mapList"</tt> rule, which rewrites the foldr/mapFB<br />
thing back into plain map.<br />
<br />
It's important that these two rules aren't both active at once<br />
(along with build's unfolding) else we'd get an infinite loop<br />
in the rules. Hence the activation control below.<br />
<br />
The <tt>"mapFB"</tt> rule optimises compositions of map.<br />
<br />
This same pattern is followed by many other functions:<br />
e.g. <hask>append</hask>, <hask>filter</hask>, <hask>iterate</hask>, <hask>repeat</hask>, etc.<br />
<br />
{-# RULES<br />
"map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)<br />
"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f<br />
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)<br />
#-}<br />
<br />
== Questions ==<br />
<br />
=== Order of rule-matching ===<br />
<br />
For example, let's say we have two rules<br />
"f->g" forall x y . f x (h y) = g x y<br />
"h->g" forall x . h x = g 0 x<br />
and a fragment of the AST corresponding to<br />
f a (h b)<br />
<br />
Which rule will fire? "f->g" or "h->g"? (Each rule disables the other.)<br />
<br />
Answer: rules are matched against the AST for expressions basically<br />
''bottom-up'' rather than top-down. In this example, "h->g" is the rule<br />
that fires. But due to the nature of inlining and so on, there are<br />
absolutely no guarantees about this kind of behaviour. If you really<br />
need to control the order of matching, phase control is the only<br />
reliable mechanism.<br />
<br />
=== [[Confluent term rewriting system]] ===<br />
<br />
Since there is no guarantee on a particular order of rule application, except the control by phases,<br />
you should assert that the result is the same independent of the order of rule application.<br />
This property of a term rewriting system is called confluence.<br />
See for example:<br />
<haskell><br />
{-# RULES<br />
"project/project" forall x.<br />
project (project x) = project x ;<br />
<br />
"project/foo" forall x.<br />
project (foo x) = projectFoo x ;<br />
#-}<br />
<br />
f = project . project . foo<br />
</haskell><br />
For this set of rewriting rules it matters whether you apply "project/project" or "project/foo" first to the body of <hask>f</hask>.<br />
In the first case you can apply additionally "project/foo" yielding <hask>projectFoo x</hask>,<br />
whereas the second case leaves you with <hask>project (projectFoo x)</hask>.<br />
To make the system confluent you should add the rule<br />
<haskell><br />
project (projectFoo x) = projectFoo x<br />
</haskell><br />
You can complete a rule system this way by hand, although it'd be quite a nice thing to automate it in GHC.<br />
<br />
We assume that non-confluent rewriting systems are bad design,<br />
but it is not clear how to achieve confluence for any system.<br />
<br />
=== Pair rules ===<br />
<br />
It is often useful to provide two implementations of a function, and<br />
have rewrite rules pick which version to use depending on context. In<br />
both GHC's foldr/build fusion, and more extensively in Data.ByteString's<br />
stream fusion system, pair rules are used to allow the compiler to<br />
choose between two implementations of a function.<br />
<br />
Consider the rules:<br />
<br />
<haskell><br />
"FPS length -> fused" [~1]<br />
length = F.strConsumerBi F.lengthS<br />
<br />
"FPS length -> unfused" [1]<br />
F.strConsumerBi F.lengthS = length<br />
</haskell><br />
<br />
This rule pair tells the compiler to rewrite occurences of <hask>length</hask> to a stream-fusible form in early simplifications phases, hoping for fusion to happen. However, if by phase 1 (remember that phases count down from 4), the fusible form remains unfused, it is better to rewrite it back to the unfused-but-fast implementation of length. A similar trick is used for <hask>map</hask> in the base libraries.<br />
<br />
As we want to match <hask>length</hask> in the rules, we need to ensure that it isn't inlined too soon:<br />
<br />
<haskell><br />
length :: ByteString -> Int<br />
length (PS _ _ l) = assert (l >= 0) $ l<br />
{-# INLINE [1] length #-}<br />
</haskell><br />
<br />
and we need <hask>strConsumerBi</hask> to stick around for even longer:<br />
<br />
<haskell><br />
strConsumerBi :: (Stream -> a) -> (ByteString -> a)<br />
strConsumerBi f = f . readStrUp<br />
{-# INLINE [0] strConsumerBi #-}<br />
<br />
lengthS :: Stream -> Int <br />
lengthS ...<br />
{-# INLINE [0] lengthS #-}<br />
</haskell><br />
<br />
Pair rules thus provide a useful mechanism to allow a library to provide<br />
multiple implementations of a function, picking the best one to use<br />
based on context.<br />
<br />
=== Custom specialisation rules ===<br />
<br />
Another use for rules is to replace a particular use of a slow,<br />
polymorphic function with a custom monomorphic implementation.<br />
<br />
Consider:<br />
<haskell><br />
zipWith :: (Word8 -> Word8 -> a) -> ByteString -> ByteString -> [a]<br />
</haskell><br />
<br />
This is a bit slow, but useful. It's often used to zip ByteStrings into<br />
a new ByteString, that is:<br />
<haskell><br />
pack (zipWith f p q)<br />
</haskell><br />
<br />
We'd like to spot this, and throw away the intermediate [a] created. And<br />
also use a specialised implementation of:<br />
<haskell><br />
zipWith :: (Word8 -> Word8 -> Word8) -> ByteString -> ByteString -> ByteString<br />
</haskell><br />
<br />
We can use rules for this:<br />
<br />
<haskell><br />
"FPS specialise pack.zipWith" forall (f :: Word8 -> Word8 -> Word8) p q .<br />
pack (zipWith f p q) = zipWith' f p q<br />
</haskell><br />
<br />
This rule spots the specific use of zipWith we're looking for, and<br />
replaces it with a fast, specialised version.<br />
<br />
=== Rules and sections ===<br />
<br />
This is useful for higher order functions as well. As of ghc 6.6, the<br />
rule LHS syntax has been relaxed, allowing for sections and lambda<br />
abstractions to appear. Previously, only applications of the following<br />
form were valid:<br />
<br />
<haskell><br />
"FPS specialise break (x==)" forall x.<br />
break ((==) x) = breakByte x<br />
</haskell><br />
<br />
That is, replace occurences of: <hask>break (x==)</hask> with the optimised breakByte function.<br />
<br />
This code illustrates how higher order functions can be rewritten to optimised first order equivalents, for special cases like <hask>(==)</hask>. In the case of Data.ByteString, functions using <hask>(==)</hask> or <hask>(/=)</hask> are much faster when implemented with memchr(3), and we can use rules to do this, as long as it is possible to match sections. In ghc 6.6 we can now write:<br />
<br />
<haskell><br />
"FPS specialise break (==x)" forall x.<br />
break (==x) = breakByte x<br />
<br />
"FPS specialise break (x==)" forall x.<br />
break (x==) = breakByte x<br />
</haskell><br />
<br />
Some fragility remains in this rule though, as described below.<br />
<br />
=== Literals, dictionaries and sections ===<br />
<br />
Consider:<br />
<haskell><br />
break (== 10)<br />
</haskell><br />
<br />
Hopefully, this can be rewritten to a <hask>breakByte 10</hask> call, however, the combination of sections, literals and dictionaries for Eq makes this rather fragile.<br />
<br />
The rule for break ends up translated by GHC as;<br />
<br />
<haskell><br />
forall ($dEq :: base:GHC.Base.Eq base:GHC.Word.Word8) <br />
(x :: base:GHC.Word.Word8)<br />
<br />
break (base:GHC.Base.== @ base:GHC.Word.Word8 $dEq x) = <br />
breakByte x<br />
</haskell><br />
<br />
Notice the LHS: an application of the selector to a (suitably-typed) Eq<br />
dictionary. GHC does very little simplification on LHSs, because if it<br />
does too much, the LHS doesn't look like you thought it did. Here it<br />
might perhaps be better to simplify to GHC.Word.Word8.==, by selecting<br />
from the dictionary, but GHC does not do that.<br />
<br />
When this rules works, GHC generates exactly that pattern; we get<br />
<br />
<haskell><br />
eq = (==) deq<br />
main = ... break (\x. eq x y) ...<br />
</haskell><br />
<br />
GHC is anxious about substituting eq inside the lambda, but it does it<br />
because (==) is just a record selector, and hence is very cheap. <br />
<br />
But when we put a literal inline, we get an (Eq a) constraint and a (Num<br />
a) constraint (from the literal). Ultimately, 'a' turns out to be Int,<br />
by defaulting, but we don't know that yet. So GHC picks the Eq<br />
dictionary from the Num dictionary:<br />
<br />
<haskell><br />
eq = (==) ($p1 dnum)<br />
main = ... break (\x. eq x y) ...<br />
</haskell><br />
<br />
Now the 'eq' doesn't look quite so cheap, and it isn't inlined, so the<br />
rule does not fire. However, GHC 6.6 has been modified to believe that<br />
nested selection is also cheap, so that makes the rule fire.<br />
<br />
The underlying lesson is this: the only robust way to make rules fire is<br />
if the LHS is a normal form. Otherwise GHC may miss the fleeting moment<br />
at which (an instance of) the rule LHS appears in the program. The way<br />
you ensure this is with inline phases: don't inline LHS stuff until<br />
later, so that the LHS stuff appears in the program more than<br />
fleetingly.<br />
<br />
But in this case you have (==) on the LHS, and you have no phase control<br />
there. So it gets inlined right away, so the rule doesn't match any<br />
more. The only way the rule "works" is because GHC catches the pattern<br />
right away, before (==) is inlined. Not very robust.<br />
<br />
To make this robust, you'd have to say something like<br />
<br />
<haskell><br />
instance Eq Word 8 where<br />
(==) = eqWord8<br />
<br />
eqWord8 = ..<br />
{-# NOINLINE [1] eqWord8 #-}<br />
<br />
{-# RULES<br />
"FPS specialise break (x==)" forall x.<br />
break (x`eqWord8`) = breakByte x<br />
#-}<br />
</haskell><br />
<br />
=== Rules and method sharing ===<br />
<br />
GHC by default instantiates overloaded methods by partially applying the original overloaded identifier. This facilitates sharing of multiple method instances with one global definition. However, since a new function name is created during this process, rules matching the original names will not fire. Here is an example from <tt>Control.Arrow</tt>:<br />
<br />
<haskell><br />
class Arrow a where<br />
arr :: (b -> c) -> a b c<br />
first :: a b c -> a (b,d) (c,d)<br />
(>>>) :: a b c -> a c d -> a b d<br />
<br />
{-# RULES<br />
"compose/arr" forall f g . arr f >>> arr g = arr (f >>> g)<br />
"first/arr" forall f . first (arr f) = arr (first f)<br />
...<br />
-#}<br />
</haskell><br />
<br />
Consider an instance of an arrow and some code on which the rules above should fire:<br />
<br />
<haskell><br />
newtype SF a b = SF ([a] -> [b])<br />
<br />
instance Arrow SF where<br />
arr f = SF (map f)<br />
...<br />
<br />
foo :: SF (Int,Int) (Int,Int)<br />
foo = first (arr (+1)) >>> first (arr (+2) >>> arr (+3))<br />
</haskell><br />
<br />
GHC would generate intermediate code like:<br />
<br />
<haskell><br />
dsf :: Arrow SF<br />
dsf = ...<br />
<br />
first_1 = Control.Arrow.first SF dsf<br />
arr_1 = Control.Arrow.arr SF dsf<br />
<br />
foo = first_1 (arr_1 (+1)) ...etc...<br />
</haskell><br />
<br />
Due to the introduction of <tt>first_1</tt> and <tt>arr_1</tt>, the rules no longer match since the names have changed. <br />
<br />
The solution is to switch off sharing with the <tt>-fno-method-sharing</tt> flag.<br />
<br />
=== Coexistence of fusion frameworks ===<br />
<br />
I like to use my own fusion framework on an existing data structure because I want to experiment with it<br />
or because I have a specific application and I want to optimize the fusion framework for it.<br />
How can I disable the fusion rules shipped with that data structure - or at least defer them until the optimizer is finished with my rules?<br />
<br />
Answer:<br />
Second part of the question first:<br />
Asserting that your rules are used before the standard rules is not possible with [[GHC]] up to version 6.8.<br />
The current system is quite monolithic in this respect.<br />
It would be a nice application of a more sophisticated rule control system that allows any number of simplifier phases with explicit statements which phase shall be entered after which other phase.<br />
<br />
First part of the question: <br />
You may wrap the data structure in a <hask>newtype</hask> or, to be entirely safe, redefine the data structure.<br />
This means that several functions have to be lifted to the wrapped data type.<br />
This is tedious, but given that you make an application specific fusion framework,<br />
the set of basic functions will be different from that of the general data structure.<br />
You might have planned to make your data type distinct anyway, may it be for the <hask>Arbitrary</hask> class of [[QuickCheck]].<br />
Remember to attach a NOINLINE pragma to the wrapped functions,<br />
otherwise the compiler may unpack the wrappers and starts fusion on the underlying data structure.<br />
<br />
=== Interaction of INLINE and RULES ===<br />
<br />
Rules can be seen as alternative function definitions. They are somehow special because they do not allow pattern matching, but allow expressions in arguments using existing variable names in the left hand side. Since pattern matching can be moved into a <hask>case</hask>, fusion rules are actually the more flexible way to define functions. Alternative function definition means that the compiler has to decide which definition to use: The original function definition (by an explicit call or by [[inlining]]/[[unfolding]]) or one of the optimizer rules ("a rule fires").<br />
<br />
Now the critical question is: How do inlining and rule application interact?<br />
<br />
Inlining is always an option for the compiler, whether you use the INLINE pragma or not.<br />
The compiler measures some kind of size of the function and<br />
decides whether a function is small enough in order to be inlined.<br />
The INLINE pragma reduces this size virtually.<br />
But the inlining can still be omitted.<br />
In that sense RULES are applied more aggressively because they don't respect a size measurement of functions.<br />
<br />
It's interesting to note, that declaring a function as INLINE disables fusion for the inner of the function.<br />
E.g., you can expect that<br />
<haskell><br />
doubleMap f g = map f . map g<br />
</haskell><br />
is fused to<br />
<haskell><br />
doubleMap f g = map (f . g)<br />
</haskell><br />
However, if you add<br />
<haskell><br />
{-# INLINE doubleMap #-}<br />
</haskell><br />
then the function definition is not fused to <hask>map (f . g)</hask>.<br />
The compiler expects that the function will never called as is, and thus skips fusion.<br />
That is, you cannot control the application order of rules by enclosing expressions in function definitions,<br />
that shall be fused before fusion with outer parts.<br />
<br />
However, since the compiler may decide not to inline, the compiler may leave you with a call to the unoptimized <hask>doubleMap</hask>. You could prevent this e.g. by:<br />
<br />
<haskell><br />
{-# NOINLINE doubleMap #-}<br />
doubleMap f g = map f . map g -- will be fused<br />
<br />
{-# RULES<br />
"doubleMap" forall f g. doubleMap f g = map f . map g<br />
#-}<br />
</haskell><br />
<br />
This makes sure that the right hand side of <hask>doubleMap</hask> will be optimised for those cases when the rule doesn't fire, e.g. when <hask>doubleMap</hask> is applied to less than two arguments.<br />
<br />
=== Interaction of SPECIALISE and INLINE ===<br />
<br />
<hask>SPECIALISE</hask> pragmas are also some kind of rules, where calls to functions with a specific [[type class dictionary]] are replaced by calls to versions of a function which are instantiated to a specific type.<br />
If you want to use a function the inlined way, it might be a bad idea to add the <hask>SPECIALISE</hask> pragma, since this will replace a call to the function by a call to a specialised function instead of inlining it.<br />
<br />
== Future of rules in GHC ==<br />
<br />
GHC has much too rigid a notion of phases up to version 6.8.<br />
There are precisely 3, namely 2 then 1 then 0, and that does not give enough control.<br />
Really we should let you give arbitrary names to phases,<br />
express constraints (A must be before B), and run a constraint solver to map phase names to a linear ordering.<br />
The current system is horribly non-modular.<br />
(See Haskell-Cafe on [http://www.haskell.org/pipermail/haskell-cafe/2008-January/038198.html Properties of optimizer rule application?])</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Phantom_type&diff=41452Phantom type2011-08-06T14:05:04Z<p>Blaisorblade: /* Why not type synonyms */ Insulate comments into a specific section</p>
<hr />
<div>A '''phantom type''' is a parametrised type whose parameters do not all appear on the right-hand side of its definition, e.g. from <tt>Control.Applicative</tt>:<br />
<br />
<haskell><br />
newtype Const a b = Const { getConst :: a }<br />
</haskell><br />
<br />
Here <tt>Const</tt> is a phantom type, because the <tt>b</tt> parameter doesn't appear after the <tt>=</tt> sign.<br />
<br />
Phantom types are useful in a variety of contexts: in the standard <tt>Data.Fixed</tt> module they are used with type classes to encode the precision being used, with [[smart constructors]] or GADTs they can encode information about how and where a value can be used, or with more exotic extensions they can be used for [[Smart_constructors#Enforcing_the_constraint_statically|encoding bounds checks in the type system.]]<br />
<br />
Since the values of type parameters in a phantom type may be unused, they are often used in combination with [[empty type]]s.<br />
<br />
A phantom type might not be a type synonym, but must be a newtype or a data type. Actually, the compiler will accept a "phantom type synonym", but it's a very bad idea, as explained below.<br />
<br />
==Simple examples==<br />
<br />
A phantom type will have a declaration that looks something like this:<br />
<br />
<haskell><br />
data FormData a = FormData String<br />
</haskell><br />
<br />
This looks strange since at first it seems the type parameter is unused and could be anything, without affecting the value inside. Indeed, one can write:<br />
<br />
<haskell><br />
changeType :: FormData a -> FormData b<br />
changeType (FormData str) = FormData str<br />
</haskell><br />
<br />
to change it from any type to any other. However, if the constructor is not exported then users of the library that defined <hask>FormData</hask> can't define functions like the above, so the type parameter can only be set or changed by library functions. So we might do:<br />
<br />
<haskell><br />
data Validated<br />
data Unvalidated<br />
<br />
-- since we don't export the constructor itself,<br />
-- users with a String can only create Unvalidated values<br />
formData :: String -> FormData Unvalidated<br />
formData str = FormData str<br />
<br />
-- Nothing if the data doesn't validate<br />
validate :: FormData Unvalidated -> Maybe (FormData Validated)<br />
validate (FormData str) = ...<br />
<br />
-- can only be fed the result of a call to validate!<br />
useData :: FormData Validated -> IO ()<br />
useData (FormData str) = ...<br />
</haskell><br />
<br />
The beauty of this is that we can define functions that work on all kinds of <hask>FormData</hask>, but still can't turn unvalidated data into validated data:<br />
<br />
<haskell><br />
-- the library exports this<br />
liftStringFn :: (String -> String) -> FormData a -> FormData a<br />
liftStringFn fn (FormData str) = FormData (fn str)<br />
<br />
-- the validation state is the *same* in the return type and the argument<br />
dataToUpper :: FormData a -> FormData a<br />
dataToUpper = liftStringFn (map toUpper)<br />
</haskell><br />
<br />
With type classes, we can even choose different behaviours conditional on information that is nonexistent at runtime:<br />
<br />
<haskell><br />
class Sanitise a where<br />
sanitise :: FormData a -> FormData Validated<br />
<br />
-- do nothing to data that is already validated<br />
instance Sanitise Validated where<br />
sanitise = id<br />
<br />
-- sanitise untrusted data<br />
instance Sanitise Unvalidated where<br />
sanitise (FormData str) = FormData (filter isAlpha str)<br />
</haskell><br />
<br />
This technique is perfect for e.g. escaping user input to a web application. We can ensure with zero overhead that the data is escaped once and only once everywhere that it needs to be, or else we get a compile-time error.<br />
<br />
==The use of a type system to guarantee well-formedness.==<br />
<br />
We create a Parameterized type in which the parameter does not appear<br />
on the rhs (shameless cutting and pasting from Daan Leijen and Erik Meijer)<br />
<haskell><br />
data Expr a = Expr PrimExpr<br />
<br />
constant :: Show a => a -> Expr a<br />
(.+.) :: Expr Int -> Expr Int -> Expr Int<br />
(.==.) :: Eq a=> Expr a-> Expr a-> Expr Bool<br />
(.&&.) :: Expr Bool -> Expr Bool-> Expr Bool<br />
<br />
data PrimExpr<br />
= BinExpr BinOp PrimExpr PrimExpr<br />
| UnExpr UnOp PrimExpr<br />
| ConstExpr String<br />
<br />
data BinOp<br />
= OpEq | OpAnd | OpPlus | ...<br />
</haskell><br />
i.e. the datatype is such that we could get garbage such as<br />
<haskell><br />
BinExpr OpEq (ConstExpr "1") (ConstExpr "\"foo\"")<br />
</haskell><br />
but since we only expose the functions our attempts<br />
to create this expression via<br />
<haskell><br />
constant 1 .==. constant "foo"<br />
</haskell><br />
would fail to typecheck<br />
<br />
== Why not type synonyms ==<br />
Remember that type synonyms are expanded behind the scenes before typechecking.<br />
Suppose that in the above example you replace the declaration of Expr with <hask>type Expr a = PrimExpr</hask>. Then <hask>Expr Int</hask> and <hask>Expr String</hask> are both expanded to <hask>PrimExpr</hask> before being compared, and those types would be compatible, defeating the point of using a phantom type.<br />
<br />
== Comments ==<br />
I believe this technique is used when trying to interface<br />
with a language that would cause a runtime exception if the types<br />
were wrong but would have a go at running the expression first.<br />
(They use it in the context of SQL but I have also seen it in the<br />
context of FLI work.)<br />
<br />
-- ChrisAngus<br />
<br />
[http://www.brics.dk/RS/02/34/ A foundation for embedded languages] provides some formal background for embedding typed languages in Haskell, and also its references give a fairly comprehensive survey of uses of phantom types and related techniques.<br />
<br />
[[Category:Idioms]]<br />
[[Category:Glossary]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Phantom_type&diff=41451Phantom type2011-08-06T14:04:22Z<p>Blaisorblade: Explain that type synonyms shouldn't be used for phantom types</p>
<hr />
<div>A '''phantom type''' is a parametrised type whose parameters do not all appear on the right-hand side of its definition, e.g. from <tt>Control.Applicative</tt>:<br />
<br />
<haskell><br />
newtype Const a b = Const { getConst :: a }<br />
</haskell><br />
<br />
Here <tt>Const</tt> is a phantom type, because the <tt>b</tt> parameter doesn't appear after the <tt>=</tt> sign.<br />
<br />
Phantom types are useful in a variety of contexts: in the standard <tt>Data.Fixed</tt> module they are used with type classes to encode the precision being used, with [[smart constructors]] or GADTs they can encode information about how and where a value can be used, or with more exotic extensions they can be used for [[Smart_constructors#Enforcing_the_constraint_statically|encoding bounds checks in the type system.]]<br />
<br />
Since the values of type parameters in a phantom type may be unused, they are often used in combination with [[empty type]]s.<br />
<br />
A phantom type might not be a type synonym, but must be a newtype or a data type. Actually, the compiler will accept a "phantom type synonym", but it's a very bad idea, as explained below.<br />
<br />
==Simple examples==<br />
<br />
A phantom type will have a declaration that looks something like this:<br />
<br />
<haskell><br />
data FormData a = FormData String<br />
</haskell><br />
<br />
This looks strange since at first it seems the type parameter is unused and could be anything, without affecting the value inside. Indeed, one can write:<br />
<br />
<haskell><br />
changeType :: FormData a -> FormData b<br />
changeType (FormData str) = FormData str<br />
</haskell><br />
<br />
to change it from any type to any other. However, if the constructor is not exported then users of the library that defined <hask>FormData</hask> can't define functions like the above, so the type parameter can only be set or changed by library functions. So we might do:<br />
<br />
<haskell><br />
data Validated<br />
data Unvalidated<br />
<br />
-- since we don't export the constructor itself,<br />
-- users with a String can only create Unvalidated values<br />
formData :: String -> FormData Unvalidated<br />
formData str = FormData str<br />
<br />
-- Nothing if the data doesn't validate<br />
validate :: FormData Unvalidated -> Maybe (FormData Validated)<br />
validate (FormData str) = ...<br />
<br />
-- can only be fed the result of a call to validate!<br />
useData :: FormData Validated -> IO ()<br />
useData (FormData str) = ...<br />
</haskell><br />
<br />
The beauty of this is that we can define functions that work on all kinds of <hask>FormData</hask>, but still can't turn unvalidated data into validated data:<br />
<br />
<haskell><br />
-- the library exports this<br />
liftStringFn :: (String -> String) -> FormData a -> FormData a<br />
liftStringFn fn (FormData str) = FormData (fn str)<br />
<br />
-- the validation state is the *same* in the return type and the argument<br />
dataToUpper :: FormData a -> FormData a<br />
dataToUpper = liftStringFn (map toUpper)<br />
</haskell><br />
<br />
With type classes, we can even choose different behaviours conditional on information that is nonexistent at runtime:<br />
<br />
<haskell><br />
class Sanitise a where<br />
sanitise :: FormData a -> FormData Validated<br />
<br />
-- do nothing to data that is already validated<br />
instance Sanitise Validated where<br />
sanitise = id<br />
<br />
-- sanitise untrusted data<br />
instance Sanitise Unvalidated where<br />
sanitise (FormData str) = FormData (filter isAlpha str)<br />
</haskell><br />
<br />
This technique is perfect for e.g. escaping user input to a web application. We can ensure with zero overhead that the data is escaped once and only once everywhere that it needs to be, or else we get a compile-time error.<br />
<br />
==The use of a type system to guarantee well-formedness.==<br />
<br />
We create a Parameterized type in which the parameter does not appear<br />
on the rhs (shameless cutting and pasting from Daan Leijen and Erik Meijer)<br />
<haskell><br />
data Expr a = Expr PrimExpr<br />
<br />
constant :: Show a => a -> Expr a<br />
(.+.) :: Expr Int -> Expr Int -> Expr Int<br />
(.==.) :: Eq a=> Expr a-> Expr a-> Expr Bool<br />
(.&&.) :: Expr Bool -> Expr Bool-> Expr Bool<br />
<br />
data PrimExpr<br />
= BinExpr BinOp PrimExpr PrimExpr<br />
| UnExpr UnOp PrimExpr<br />
| ConstExpr String<br />
<br />
data BinOp<br />
= OpEq | OpAnd | OpPlus | ...<br />
</haskell><br />
i.e. the datatype is such that we could get garbage such as<br />
<haskell><br />
BinExpr OpEq (ConstExpr "1") (ConstExpr "\"foo\"")<br />
</haskell><br />
but since we only expose the functions our attempts<br />
to create this expression via<br />
<haskell><br />
constant 1 .==. constant "foo"<br />
</haskell><br />
would fail to typecheck<br />
<br />
== Why not type synonyms ==<br />
Remember that type synonyms are expanded behind the scenes before typechecking.<br />
Suppose that in the above example you replace the declaration of Expr with <hask>type Expr a = PrimExpr</hask>. Then <hask>Expr Int</hask> and <hask>Expr String</hask> are both expanded to <hask>PrimExpr</hask> before being compared, and those types would be compatible, defeating the point of using a phantom type.<br />
<br />
I believe this technique is used when trying to interface<br />
with a language that would cause a runtime exception if the types<br />
were wrong but would have a go at running the expression first.<br />
(They use it in the context of SQL but I have also seen it in the<br />
context of FLI work.)<br />
<br />
-- ChrisAngus<br />
<br />
[http://www.brics.dk/RS/02/34/ A foundation for embedded languages] provides some formal background for embedding typed languages in Haskell, and also its references give a fairly comprehensive survey of uses of phantom types and related techniques.<br />
<br />
[[Category:Idioms]]<br />
[[Category:Glossary]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Import_modules_properly&diff=41450Import modules properly2011-08-06T09:39:43Z<p>Blaisorblade: /* Clashing of module name abbreviations */ Reformat like introduction</p>
<hr />
<div>== Introduction ==<br />
<br />
Haskell has a lot of variants of [[Import|importing]] identifiers from other modules.<br />
However not all of them are as comfortable as they seem to be at the first glance.<br />
We recommend to focus on the following two forms of import:<br />
<haskell><br />
import qualified Very.Special.Module as VSM<br />
import Another.Important.Module (printf, (<|>), )<br />
</haskell><br />
instead of<br />
<haskell><br />
import Very.Special.Module<br />
import Another.Important.Module hiding (open, close, )<br />
</haskell><br />
<br />
There are three different kind of reasons for this.<br />
<br />
* '''Style:''' If you read <hask>printf</hask>, <hask><|></hask> or <hask>VSM.open</hask> in the program you can find out easily where the identifier comes from. In the second case you don't know if these identifiers are from <hask>Very.Special.Module</hask>, <hask>Another.Important.Module</hask> or even other modules. Mind you that grep won't help, because <hask>Very.Special.Module</hask> and <hask>Another.Important.Module</hask> might just re-export other modules. You might guess the origin of <hask>printf</hask> according to its name, but for the infix operator <hask><|></hask> you will certainly have no idea.<br />
* '''Compatibility:''' In the second case, if new identifiers are added to the imported modules they might clash with names of other modules. Thus updating imported modules may break your code. If you import a package A with version a.b.c.d that follows the [[Package versioning policy]] then within versions with the same a.b it is allowed to add identifiers. This means that if you import the suggested way, you can safely specify <code>A >= a.b.c && <a.b+1</code> in your [[Cabal]] file. Otherwise you have to chose the smaller range <code>A >= a.b.c && <a.b.c+1</code>. It may also be that <hask>Another.Important.Module.open</hask> was deprecated when you hid it, and with a module update removing that identifier, your import fails. That is, an identifier that you never needed but only annoyed you, annoys you again, when it was meant to not bother you any longer! The first variant of import does not suffer from these problems.<br />
* '''Correctness:''' I once found a bug in the StorableVector package by converting anonymous imports to explicit imports. I found out that the function <hask>Foreign.Ptr.plusPtr</hask> was imported, although functions from this module always have to calculate with unit "element" not "byte". That is, <hask>advancePtr</hask> must be used instead. Actually, the <hask>reverse</hask> function used <hask>plusPtr</hask> and this was wrong. A misbehaviour could only be observed for sub-vectors and elements with size greater than 1 byte. The test suite did miss that.<br />
<br />
== Exception from the rule ==<br />
<br />
Since the Prelude is intended to be fixed for the future, it should be safe to use the <hask>hiding</hask> clause when importing <hask>Prelude</hask>.<br />
Actually if you do not mention Prelude it will be imported anonymously.<br />
<br />
== Clashing of module name abbreviations ==<br />
<br />
In Haskell it is possible to use the same abbreviation for different modules:<br />
<haskell><br />
import qualified Data.List as List<br />
import qualified Data.List.Extra as List<br />
</haskell><br />
This is discouraged for the same reasons as above:<br />
<br />
* '''Style''': The identifier <hask>List.intercalate</hask> may refer to either <hask>Data.List</hask> or <hask>Data.List.Extra</hask>. The reader of that module has to check these modules in order to find it out.<br />
<br />
* '''Compatibility''': The function <hask>List.intercalate</hask> may be currently defined only in <hask>Data.List.Extra</hask>. However after many people found it useful, it is also added to <hask>Data.List</hask>. Then <hask>List.intercalate</hask> can no longer be resolved.<br />
<br />
== Counter-arguments to explicit import lists ==<br />
<br />
The issue of whether to use explicit import lists is not always clear-cut, however.<br />
Here are some reasons you might not want to do this:<br />
<br />
* Development is slower: almost every change is accompanied by an import list change, especially if you want to keep your code warning-clean.<br />
<br />
* When working on a project with multiple developers, explicit import lists can cause spurious conflicts, since two otherwise-unrelated changes to a file may both require changes to the same import list.<br />
<br />
For these reasons amongst others, the GHC project decided to drop the use of explicit import lists.<br />
We recommend using explicit import lists when importing from other packages,<br />
but not when importing modules within the same package.<br />
<br />
Qualified use of identifiers does not suffer from the above problems.<br />
<br />
== See also ==<br />
<br />
* [[Qualified names]]<br />
<br />
{{essay}}<br />
<br />
[[Category:Style]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Import_modules_properly&diff=41449Import modules properly2011-08-06T09:38:21Z<p>Blaisorblade: /* Introduction */ Remove extra linebreaks, reformat list of reasons, highlight their name</p>
<hr />
<div>== Introduction ==<br />
<br />
Haskell has a lot of variants of [[Import|importing]] identifiers from other modules.<br />
However not all of them are as comfortable as they seem to be at the first glance.<br />
We recommend to focus on the following two forms of import:<br />
<haskell><br />
import qualified Very.Special.Module as VSM<br />
import Another.Important.Module (printf, (<|>), )<br />
</haskell><br />
instead of<br />
<haskell><br />
import Very.Special.Module<br />
import Another.Important.Module hiding (open, close, )<br />
</haskell><br />
<br />
There are three different kind of reasons for this.<br />
<br />
* '''Style:''' If you read <hask>printf</hask>, <hask><|></hask> or <hask>VSM.open</hask> in the program you can find out easily where the identifier comes from. In the second case you don't know if these identifiers are from <hask>Very.Special.Module</hask>, <hask>Another.Important.Module</hask> or even other modules. Mind you that grep won't help, because <hask>Very.Special.Module</hask> and <hask>Another.Important.Module</hask> might just re-export other modules. You might guess the origin of <hask>printf</hask> according to its name, but for the infix operator <hask><|></hask> you will certainly have no idea.<br />
* '''Compatibility:''' In the second case, if new identifiers are added to the imported modules they might clash with names of other modules. Thus updating imported modules may break your code. If you import a package A with version a.b.c.d that follows the [[Package versioning policy]] then within versions with the same a.b it is allowed to add identifiers. This means that if you import the suggested way, you can safely specify <code>A >= a.b.c && <a.b+1</code> in your [[Cabal]] file. Otherwise you have to chose the smaller range <code>A >= a.b.c && <a.b.c+1</code>. It may also be that <hask>Another.Important.Module.open</hask> was deprecated when you hid it, and with a module update removing that identifier, your import fails. That is, an identifier that you never needed but only annoyed you, annoys you again, when it was meant to not bother you any longer! The first variant of import does not suffer from these problems.<br />
* '''Correctness:''' I once found a bug in the StorableVector package by converting anonymous imports to explicit imports. I found out that the function <hask>Foreign.Ptr.plusPtr</hask> was imported, although functions from this module always have to calculate with unit "element" not "byte". That is, <hask>advancePtr</hask> must be used instead. Actually, the <hask>reverse</hask> function used <hask>plusPtr</hask> and this was wrong. A misbehaviour could only be observed for sub-vectors and elements with size greater than 1 byte. The test suite did miss that.<br />
<br />
== Exception from the rule ==<br />
<br />
Since the Prelude is intended to be fixed for the future, it should be safe to use the <hask>hiding</hask> clause when importing <hask>Prelude</hask>.<br />
Actually if you do not mention Prelude it will be imported anonymously.<br />
<br />
== Clashing of module name abbreviations ==<br />
<br />
In Haskell it is possible to use the same abbreviation for different modules:<br />
<haskell><br />
import qualified Data.List as List<br />
import qualified Data.List.Extra as List<br />
</haskell><br />
This is discouraged for the same reasons as above:<br />
<br />
Stylistic reason:<br />
The identifier <hask>List.intercalate</hask> may refer to either <hask>Data.List</hask> or <hask>Data.List.Extra</hask>.<br />
The reader of that module has to check these modules in order to find it out.<br />
<br />
Compatibility reason:<br />
The function <hask>List.intercalate</hask> may be currently defined only in <hask>Data.List.Extra</hask>.<br />
However after many people found it useful, it is also added to <hask>Data.List</hask>.<br />
Then <hask>List.intercalate</hask> can no longer be resolved.<br />
<br />
== Counter-arguments to explicit import lists ==<br />
<br />
The issue of whether to use explicit import lists is not always clear-cut, however.<br />
Here are some reasons you might not want to do this:<br />
<br />
* Development is slower: almost every change is accompanied by an import list change, especially if you want to keep your code warning-clean.<br />
<br />
* When working on a project with multiple developers, explicit import lists can cause spurious conflicts, since two otherwise-unrelated changes to a file may both require changes to the same import list.<br />
<br />
For these reasons amongst others, the GHC project decided to drop the use of explicit import lists.<br />
We recommend using explicit import lists when importing from other packages,<br />
but not when importing modules within the same package.<br />
<br />
Qualified use of identifiers does not suffer from the above problems.<br />
<br />
== See also ==<br />
<br />
* [[Qualified names]]<br />
<br />
{{essay}}<br />
<br />
[[Category:Style]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Import_modules_properly&diff=41448Import modules properly2011-08-06T09:29:43Z<p>Blaisorblade: /* Introduction */ Remove extra line break missed before</p>
<hr />
<div>== Introduction ==<br />
<br />
Haskell has a lot of variants of [[Import|importing]] identifiers from other modules.<br />
However not all of them are as comfortable as they seem to be at the first glance.<br />
We recommend to focus on the following two forms of import:<br />
<haskell><br />
import qualified Very.Special.Module as VSM<br />
import Another.Important.Module (printf, (<|>), )<br />
</haskell><br />
instead of<br />
<haskell><br />
import Very.Special.Module<br />
import Another.Important.Module hiding (open, close, )<br />
</haskell><br />
<br />
Stylistic reason:<br />
If you read <hask>printf</hask>, <hask><|></hask> or <hask>VSM.open</hask> in the program you can find out easily where the identifier comes from.<br />
In the second case you don't know if these identifiers are from <hask>Very.Special.Module</hask>, <hask>Another.Important.Module</hask> or even other modules.<br />
Mind you that grep won't help, because <hask>Very.Special.Module</hask> and <hask>Another.Important.Module</hask> might just re-export other modules.<br />
You might guess the origin of <hask>printf</hask> according to its name,<br />
but for the infix operator <hask><|></hask> you will certainly have no idea.<br />
<br />
Compatibility reason:<br />
In the second case, if new identifiers are added to the imported modules they might clash with names of other modules.<br />
Thus updating imported modules may break your code.<br />
If you import a package A with version a.b.c.d that follows the [[Package versioning policy]] then within versions with the same a.b it is allowed to add identifiers.<br />
This means that if you import the suggested way, you can safely specify <code>A >= a.b.c && <a.b+1</code> in your [[Cabal]] file.<br />
Otherwise you have to chose the smaller range <code>A >= a.b.c && <a.b.c+1</code>.<br />
<br />
It may also be that <hask>Another.Important.Module.open</hask> was deprecated when you hid it, and with a module update removing that identifier, your import fails.<br />
That is, an identifier that you never needed but only annoyed you, annoys you again, when it was meant to not bother you any longer!<br />
The first variant of import does not suffer from these problems.<br />
<br />
Correctness reason:<br />
I once found a bug in the StorableVector package by converting anonymous imports to explicit imports.<br />
I found out that the function <hask>Foreign.Ptr.plusPtr</hask> was imported, although functions from this module always have to calculate with unit "element" not "byte".<br />
That is, <hask>advancePtr</hask> must be used instead.<br />
Actually, the <hask>reverse</hask> function used <hask>plusPtr</hask> and this was wrong.<br />
A misbehaviour could only be observed for sub-vectors and elements with size greater than 1 byte.<br />
The test suite did miss that.<br />
<br />
== Exception from the rule ==<br />
<br />
Since the Prelude is intended to be fixed for the future, it should be safe to use the <hask>hiding</hask> clause when importing <hask>Prelude</hask>.<br />
Actually if you do not mention Prelude it will be imported anonymously.<br />
<br />
== Clashing of module name abbreviations ==<br />
<br />
In Haskell it is possible to use the same abbreviation for different modules:<br />
<haskell><br />
import qualified Data.List as List<br />
import qualified Data.List.Extra as List<br />
</haskell><br />
This is discouraged for the same reasons as above:<br />
<br />
Stylistic reason:<br />
The identifier <hask>List.intercalate</hask> may refer to either <hask>Data.List</hask> or <hask>Data.List.Extra</hask>.<br />
The reader of that module has to check these modules in order to find it out.<br />
<br />
Compatibility reason:<br />
The function <hask>List.intercalate</hask> may be currently defined only in <hask>Data.List.Extra</hask>.<br />
However after many people found it useful, it is also added to <hask>Data.List</hask>.<br />
Then <hask>List.intercalate</hask> can no longer be resolved.<br />
<br />
== Counter-arguments to explicit import lists ==<br />
<br />
The issue of whether to use explicit import lists is not always clear-cut, however.<br />
Here are some reasons you might not want to do this:<br />
<br />
* Development is slower: almost every change is accompanied by an import list change, especially if you want to keep your code warning-clean.<br />
<br />
* When working on a project with multiple developers, explicit import lists can cause spurious conflicts, since two otherwise-unrelated changes to a file may both require changes to the same import list.<br />
<br />
For these reasons amongst others, the GHC project decided to drop the use of explicit import lists.<br />
We recommend using explicit import lists when importing from other packages,<br />
but not when importing modules within the same package.<br />
<br />
Qualified use of identifiers does not suffer from the above problems.<br />
<br />
== See also ==<br />
<br />
* [[Qualified names]]<br />
<br />
{{essay}}<br />
<br />
[[Category:Style]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Import_modules_properly&diff=41447Import modules properly2011-08-06T09:28:54Z<p>Blaisorblade: Remove spurious extra line breaks</p>
<hr />
<div>== Introduction ==<br />
<br />
Haskell has a lot of variants of [[Import|importing]] identifiers from other modules.<br />
However not all of them are as comfortable as they seem to be at the first glance.<br />
We recommend to focus on the following two forms of import:<br />
<haskell><br />
import qualified Very.Special.Module as VSM<br />
import Another.Important.Module (printf, (<|>), )<br />
</haskell><br />
instead of<br />
<haskell><br />
import Very.Special.Module<br />
import Another.Important.Module hiding (open, close, )<br />
</haskell><br />
<br />
Stylistic reason:<br />
If you read <hask>printf</hask>, <hask><|></hask> or <hask>VSM.open</hask> in the program you can find out easily where the identifier comes from.<br />
In the second case you don't know if these identifiers are from <hask>Very.Special.Module</hask>, <hask>Another.Important.Module</hask> or even other modules.<br />
Mind you that grep won't help, because <hask>Very.Special.Module</hask> and <hask>Another.Important.Module</hask> might just re-export other modules.<br />
You might guess the origin of <hask>printf</hask> according to its name,<br />
but for the infix operator <hask><|></hask> you will certainly have no idea.<br />
<br />
Compatibility reason:<br />
In the second case, if new identifiers are added to the imported modules they might clash with names of other modules.<br />
Thus updating imported modules may break your code.<br />
If you import a package A with version a.b.c.d that follows the [[Package versioning policy]] then within versions with the same a.b it is allowed to add identifiers.<br />
This means that if you import the suggested way, you can safely specify <code>A >= a.b.c && <a.b+1</code> in your [[Cabal]] file.<br />
Otherwise you have to chose the smaller range <code>A >= a.b.c && <a.b.c+1</code>.<br />
<br />
It may also be that <hask>Another.Important.Module.open</hask> was deprecated when you hid it, and with a module update removing that identifier, your import fails.<br />
That is, an identifier that you never needed but only annoyed you, annoys you again, when it was meant to not bother you any longer!<br />
The first variant of import does not suffer from these problems.<br />
<br />
Correctness reason:<br />
I once found a bug in the StorableVector package by converting anonymous imports to explicit imports.<br />
I found out that the function <hask>Foreign.Ptr.plusPtr</hask> was imported,<br />
although functions from this module always have to calculate with unit "element" not "byte".<br />
That is, <hask>advancePtr</hask> must be used instead.<br />
Actually, the <hask>reverse</hask> function used <hask>plusPtr</hask> and this was wrong.<br />
A misbehaviour could only be observed for sub-vectors and elements with size greater than 1 byte.<br />
The test suite did miss that.<br />
<br />
== Exception from the rule ==<br />
<br />
Since the Prelude is intended to be fixed for the future, it should be safe to use the <hask>hiding</hask> clause when importing <hask>Prelude</hask>.<br />
Actually if you do not mention Prelude it will be imported anonymously.<br />
<br />
== Clashing of module name abbreviations ==<br />
<br />
In Haskell it is possible to use the same abbreviation for different modules:<br />
<haskell><br />
import qualified Data.List as List<br />
import qualified Data.List.Extra as List<br />
</haskell><br />
This is discouraged for the same reasons as above:<br />
<br />
Stylistic reason:<br />
The identifier <hask>List.intercalate</hask> may refer to either <hask>Data.List</hask> or <hask>Data.List.Extra</hask>.<br />
The reader of that module has to check these modules in order to find it out.<br />
<br />
Compatibility reason:<br />
The function <hask>List.intercalate</hask> may be currently defined only in <hask>Data.List.Extra</hask>.<br />
However after many people found it useful, it is also added to <hask>Data.List</hask>.<br />
Then <hask>List.intercalate</hask> can no longer be resolved.<br />
<br />
== Counter-arguments to explicit import lists ==<br />
<br />
The issue of whether to use explicit import lists is not always clear-cut, however.<br />
Here are some reasons you might not want to do this:<br />
<br />
* Development is slower: almost every change is accompanied by an import list change, especially if you want to keep your code warning-clean.<br />
<br />
* When working on a project with multiple developers, explicit import lists can cause spurious conflicts, since two otherwise-unrelated changes to a file may both require changes to the same import list.<br />
<br />
For these reasons amongst others, the GHC project decided to drop the use of explicit import lists.<br />
We recommend using explicit import lists when importing from other packages,<br />
but not when importing modules within the same package.<br />
<br />
Qualified use of identifiers does not suffer from the above problems.<br />
<br />
== See also ==<br />
<br />
* [[Qualified names]]<br />
<br />
{{essay}}<br />
<br />
[[Category:Style]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Pointfree&diff=40393Pointfree2011-06-05T14:44:55Z<p>Blaisorblade: Jos -> José</p>
<hr />
<div>__TOC__<br />
<br />
'''Pointfree Style'''<br />
<br />
It is very common for functional programmers to write functions as a<br />
composition of other functions, never mentioning the actual arguments<br />
they will be applied to. For example, compare:<br />
<br />
<haskell><br />
sum = foldr (+) 0<br />
</haskell><br />
<br />
with:<br />
<br />
<haskell><br />
sum' xs = foldr (+) 0 xs<br />
</haskell><br />
<br />
These functions perform the same operation, however, the former is more compact, and is considered cleaner. This is closely related to function pipelines (and to [http://www.vex.net/~trebla/weblog/pointfree.html unix shell scripting]): it is clearer to write <hask>let fn = f . g . h</hask> than to write <hask>let fn x = f (g (h x))</hask>.<br />
<br />
This style is particularly useful when deriving efficient programs by<br />
calculation and, in general, constitutes good discipline. It helps the writer<br />
(and reader) think about composing functions (high level), rather than<br />
shuffling data (low level).<br />
<br />
It is a common experience when rewriting expressions in pointfree style<br />
to derive more compact, clearer versions of the code -- explicit points<br />
often obscure the underlying algorithm.<br />
<br />
Point-free map fusion:<br />
<br />
<haskell><br />
foldr f e . map g == foldr (f . g) e<br />
</haskell><br />
<br />
versus pointful map fusion:<br />
<br />
<haskell><br />
foldr f e . map g == foldr f' e<br />
where f' a b = f (g a) b<br />
</haskell><br />
<br />
Some more examples:<br />
<br />
<haskell><br />
-- point-wise, and point-free member<br />
mem, mem' :: Eq a => a -> [a] -> Bool<br />
<br />
mem x lst = any (== x) lst<br />
mem' = any . (==)<br />
</haskell><br />
<br />
== But pointfree has more points! ==<br />
<br />
A common misconception is that the 'points' of pointfree style are the <hask>(.)</hask> operator (function composition, as an ASCII symbol), which uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values. In the declaration<br />
<haskell><br />
f x = x + 1<br />
</haskell><br />
we define the function <hask>f</hask> in terms of its action on an arbitrary point <hask>x</hask>. Contrast this with the points-free version:<br />
<haskell><br />
f = (+ 1)<br />
</haskell><br />
where there is no mention of the value on which the function is acting.<br />
<br />
== Background ==<br />
<br />
To find out more about this style, search for Squiggol and the Bird-Meertens Formalism, a style of functional programming by calculation that was developed by [http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications.html Richard Bird], [http://www.kestrel.edu/home/people/meertens/ Lambert Meertens], and others at Oxford University. [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/ Jeremy Gibbons] has also written a number of papers about the topic, which are cited below.<br />
<br />
== Tool support ==<br />
<br />
Thomas Yaeger has<br />
[http://www.cse.unsw.edu.au/~dons/code/lambdabot/Plugins/Pl/ written] a <br />
[http://haskell.org/haskellwiki/Lambdabot Lambdabot] <br />
plugin to automatically convert a large subset of Haskell expressions to<br />
pointfree form. This tool has made it easier to use the more abstract<br />
pointfree encodings (as it saves some mental gymnastics on the part of<br />
the programmer). You can experiment with this in the [[IRC channel|Haskell IRC channel]]. A stand-alone command-line version is available at [http://hackage.haskell.org/package/pointfree HackageDB] (package pointfree).<br />
<br />
The @pl (point-less) plugin is rather infamous for using the <hask>(->) a</hask> [[Monad|monad]] to obtain concise code. It also makes use of [[Arrow|Arrows]]. It also sometimes produces (amusing) code blow ups with the<br />
<hask>(.)</hask> operator. <br />
<br />
Recently, @unpl has been written, which (attempts) to unscramble @pl-ified code. It also has a [http://hackage.haskell.org/package/pointful stand-alone command-line version] (package pointful).<br />
<br />
A transcript:<br />
<br />
<haskell><br />
> pl \x y -> x y<br />
id<br />
<br />
> unpl id<br />
(\ a -> a)<br />
<br />
> pl \x y -> x + 1<br />
const . (1 +)<br />
<br />
> unpl const . (1 +)<br />
(\ e _ -> 1 + e)<br />
<br />
> pl \v1 v2 -> sum (zipWith (*) v1 v2)<br />
(sum .) . zipWith (*)<br />
<br />
> unpl (sum .) . zipWith (*)<br />
(\ d g -> sum (zipWith (*) d g))<br />
<br />
> pl \x y z -> f (g x y z)<br />
((f .) .) . g<br />
<br />
> unpl ((f .) .) . g<br />
(\ e j m -> f (g e j m))<br />
<br />
> pl \x y z -> f (g x y) z<br />
(f .) . g<br />
<br />
> unpl (f .) . g<br />
(\ d i -> f (g d i))<br />
<br />
> pl \x y z -> f z (g x y)<br />
(flip f .) . g<br />
<br />
> unpl (flip f .) . g<br />
(\ i l c -> f c (g i l))<br />
<br />
> pl \(a,b) -> (b,a)<br />
uncurry (flip (,))<br />
<br />
> pl f a b = b a<br />
f = flip id<br />
<br />
> pl \ x -> x * x<br />
join (*)<br />
<br />
> pl \a b -> a:b:[]<br />
(. return) . (:)<br />
<br />
> pl \x -> x+x+x<br />
(+) =<< join (+)<br />
<br />
> pl \a b -> Nothing<br />
const (const Nothing)<br />
<br />
> pl \(a,b) -> (f a, g b)<br />
f *** g<br />
<br />
> pl \f g h x -> f x `h` g x<br />
flip . (ap .) . flip (.)<br />
<br />
> pl \x y -> x . f . y<br />
(. (f .)) . (.)<br />
<br />
> pl \f xs -> xs >>= return . f<br />
fmap<br />
<br />
> pl \h f g x -> f x `h` g x<br />
liftM2<br />
<br />
> pl \f a b c d -> f b c d a<br />
flip . ((flip . (flip .)) .)<br />
<br />
> pl \a (b,c) -> a c b<br />
(`ap` snd) . (. fst) . flip<br />
<br />
> pl \x y -> compare (f x) (f y)<br />
((. f) . compare .)<br />
</haskell><br />
<br />
For many many more examples, google for the results of '@pl' in the [[IRC_channel|#haskell]] logs. (Or join #haskell on FreeNode and try it yourself!) It can, of course, get out of hand:<br />
<br />
<haskell><br />
> pl \(a,b) -> a:b:[]<br />
uncurry ((. return) . (:))<br />
<br />
> pl \a b c -> a*b+2+c<br />
((+) .) . flip flip 2 . ((+) .) . (*)<br />
<br />
> pl \f (a,b) -> (f a, f b)<br />
(`ap` snd) . (. fst) . (flip =<< (((.) . (,)) .))<br />
<br />
> pl \f g (a,b) -> (f a, g b)<br />
flip flip snd . (ap .) . flip flip fst . ((.) .) . flip . (((.) . (,)) .)<br />
<br />
> unpl flip flip snd . (ap .) . flip flip fst . ((.) .) . flip . (((.) . (,)) .)<br />
(\ aa f -><br />
(\ p w -> ((,)) (aa (fst p)) (f w)) >>=<br />
\ ao -> snd >>= \ an -> return (ao an))<br />
</haskell><br />
<br />
== Combinator discoveries ==<br />
<br />
Some fun combinators have been found via @pl. Here we list some of the best:<br />
<br />
=== The owl ===<br />
<br />
<haskell><br />
((.)$(.))<br />
</haskell><br />
<br />
The owl has type <hask>(a -> b -> c) -> a -> (a1 -> b) -> a1 -> c</hask>, and in pointful style can be written as <hask> f a b c d = a b (c d)</hask>.<br />
<br />
Example <br />
<haskell><br />
> ((.)$(.)) (==) 1 (1+) 0<br />
True<br />
</haskell><br />
<br />
=== Dot ===<br />
<br />
<haskell><br />
dot = ((.).(.))<br />
<br />
dot :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c<br />
</haskell><br />
<br />
Example:<br />
<br />
<haskell><br />
sequence `dot` replicate == <br />
(sequence .) . replicate ==<br />
replicateM<br />
<br />
(=<<) == join `dot` fmap<br />
</haskell><br />
<br />
=== Swing ===<br />
<br />
-- Note: @pl had nothing to do with the invention of this combinator. I constructed it by hand after noticing a common pattern. -- Cale<br />
<br />
<haskell><br />
swing :: (((a -> b) -> b) -> c -> d) -> c -> a -> d<br />
swing = flip . (. flip id)<br />
swing f = flip (f . runCont . return)<br />
swing f c a = f ($ a) c<br />
</haskell><br />
<br />
Some examples of use:<br />
<br />
<haskell><br />
swing map :: forall a b. [a -> b] -> a -> [b]<br />
swing any :: forall a. [a -> Bool] -> a -> Bool<br />
swing foldr :: forall a b. b -> a -> [a -> b -> b] -> b<br />
swing zipWith :: forall a b c. [a -> b -> c] -> a -> [b] -> [c]<br />
swing find :: forall a. [a -> Bool] -> a -> Maybe (a -> Bool)<br />
-- applies each of the predicates to the given value, returning the first predicate which succeeds, if any<br />
swing partition :: forall a. [a -> Bool] -> a -> ([a -> Bool], [a -> Bool])<br />
</haskell><br />
<br />
=== Squish ===<br />
<br />
<haskell><br />
f >>= a . b . c =<< g<br />
</haskell><br />
<br />
Example:<br />
<br />
<haskell><br />
(readFile y >>=) . ((a . b) .) . c =<< readFile x<br />
</haskell><br />
<br />
[[/Combine|An actually useful example]], numbering lines of a file.<br />
<br />
== Problems with pointfree ==<br />
<br />
Point-free style can (clearly) lead to [[Obfuscation]] when used unwisely.<br />
As higher-order functions are chained together, it can become harder to<br />
mentally infer the types of expressions. The mental cues to an<br />
expression's type (explicit function arguments, and the number of<br />
arguments) go missing.<br />
<br />
Point-free style often times leads to code which is difficult to modify. A function written in a pointfree style may have to be radically changed to make minor changes in functionality. This is because the function becomes more complicated than a composition of lambdas and other functions, and compositions must be changed to application for a pointful function.<br />
<br />
Perhaps these are why pointfree style is sometimes (often?) referred to as<br />
''pointless style''.<br />
<br />
== References ==<br />
<br />
One early reference is<br />
<br />
* Backus, J. 1978. "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs," Communications of the Association for Computing Machinery 21:613-641.<br />
<br />
which appears to be available (as a scan) at http://www.stanford.edu/class/cs242/readings/backus.pdf<br />
<br />
A paper specifically about point-free style: <br />
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#radix<br />
<br />
This style underlies a lot of expert Haskeller's intuitions. A rather infamous paper (for all the cute symbols) is Erik Meijer et. al's:<br />
<br />
* Functional Programming with Bananas, Lenses, and Barbed Wire, http://wwwhome.cs.utwente.nl/~fokkinga/mmf91m.ps.<br />
<br />
[http://en.wikipedia.org/wiki/Squiggol Squiggol], and the Bird-Meertens Formalism:<br />
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#squiggolintro.<br />
* A Calculus of Functions for Program Derivation, R.S. Bird, in Res Topics in Fnl Prog, D. Turner ed, A-W 1990.<br />
* The Squiggolist, ed Johan Jeuring, published irregularly by CWI Amsterdam.<br />
<br />
[http://wiki.di.uminho.pt/twiki/bin/view/Personal/Alcino/PointlessHaskell Pointless Haskell] is a library for point-free programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions. [http://wiki.di.uminho.pt/wiki/pub/Ze/Bic/report.pdf Haskell Manipulation] by Jose Miguel Paiva Proenca discusses this tool based approach to re-factoring.<br />
<br />
This project is written by [http://www.di.uminho.pt/~mac/ Manuel Alcino Cunha], see his homepage for more related materials on the topic.<br />
An extended verson of his paper ''Point-free Programming with Hylomorphisms'' can be found [http://web.comlab.ox.ac.uk/oucl/research/pdt/ap/dgp/workshop2004/cunha.pdf here].<br />
<br />
== Other areas ==<br />
<br />
[[Combinatory logic]] and also [[Recursive function theory]] can be said in some sense pointfree.<br />
<br />
Are there pointfree approaches to [[relational algebra]]?<br />
See [http://www.di.uminho.pt/~jno/ps/_.pdf First Steps in Pointfree Functional Dependency Theory] written by José Nuno Oliveira. A concise and deep approach. See also [http://www.di.uminho.pt/~jno/html/ the author's homepage] and also [http://www.di.uminho.pt/~jno/html/jnopub.html his many other papers] -- many materials related to this topic can be found there.<br />
<br />
[[Category:Idioms]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=GHC/Type_families&diff=36491GHC/Type families2010-08-14T19:35:14Z<p>Blaisorblade: Minor clarifications to TillmannRendel's changes</p>
<hr />
<div>[[Category:GHC|Indexed types]]<br />
<br />
Indexed type families, or '''type families''' for short, are a Haskell extension supporting ad-hoc overloading of data types. Type families are parametric types that can be assigned specialized representations based on the type parameters they are instantiated with. They are the data type analogue of [[Type class|type classes]]: families are used to define overloaded ''data'' in the same way that classes are used to define overloaded ''functions''. Type families are useful for generic programming, for creating highly parameterised library interfaces, and for creating interfaces with enhanced static information, much like dependent types.<br />
<br />
Type families come in two flavors: ''data families'' and ''type synonym families''. Data families are the indexed form of data and newtype definitions. Type synonym families are the indexed form of type synonyms. Each of these flavors can be defined in a standalone manner or ''associated'' with a type class. Standalone definitions are more general, while associated types can more clearly express how a type is used and lead to better error messages.<br />
<br />
== What are type families? ==<br />
<br />
The concept of a type family comes from type theory. An indexed type family in type theory is a partial function at the type level. Applying the function to parameters (called ''type indices'') yields a type. Type families permit a program to compute what data constructors it will operate on, rather than having them fixed statically (as with simple type systems) or treated as opaque unknowns (as with parametrically polymorphic types).<br />
<br />
Type families are to vanilla data types what type class methods are to regular functions. Vanilla polymorphic data types and functions have a single definition, which is used at all type instances. Classes and type families, on the other hand, have an interface definition and any number of instance definitions. A type family's interface definition declares its [[kind]] and its arity, or the number of type indices it takes. Instance definitions define the type family over some part of the domain.<br />
<br />
As a simple example of how type families differ from ordinary parametric data types, consider a strict list type. We can represent a list of <hask>Char</hask> in the usual way, with cons cells. We can do the same thing to represent a list of <hask>()</hask>, but since a strict <hask>()</hask> value carries no useful information, it would be more efficient to just store the length of the list. This can't be done with an ordinary parametric data type, because the data constructors used to represent the list would depend on the list's type parameter: if it's <hask>Char</hask> then the list consists of cons cells; if it's <hask>()</hask>, then the list consists of a single integer. We basically want to select between two different data types based on a type parameter. Using type families, this list type could be declared as follows:<br />
<br />
<haskell><br />
-- Declare a list-like data family<br />
data family XList a<br />
<br />
-- Declare a list-like instance for Char<br />
data instance XList Char = XCons !Char !(XList Char) | XNil<br />
<br />
-- Declare a number-like instance for ()<br />
data instance XList () = XListUnit !Int<br />
</haskell><br />
<br />
The right-hand sides of the two <code>data instance</code> declarations are exactly ordinary data definitions. However, they define two instances of the same parametric data type, <hask>XList Char</hask> and <hask>XList ()</hask>, whereas ordinary data declarations define completely unrelated types. A recent [[Simonpj/Talk:FunWithTypeFuns|tutorial paper]] has more in-depth examples of programming with type families. <br />
<br />
GADTs bear some similarity to type families, in the sense that they allow a parametric type's constructors to depend on the type's parameters. However, all GADT constructors must be defined in one place, whereas type families can be extended. Functional dependences are similar to type families, and many type classes that use functional dependences can be equivalently expressed with type families. Type families provide a more functional style of type-level programming than the relational style of functional dependences.<br />
<br />
== What do I need to use type families? ==<br />
<br />
Type families are a GHC extension enabled with the <code>-XTypeFamilies</code> flag or the <code>{-# LANGUAGE TypeFamilies #-}</code> pragma. The first stable release of GHC that properly supports type families is 6.10.1. (The 6.8 release included an early partial implementation, 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-families.html#data-family-declarations ''kind signature''] (here <hask>* -> *</hask>) for the associated data type <hask>GMap k</hask> - analogous 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.IntMap</hask>, thusly:<br />
<haskell><br />
instance GMapKey Int where<br />
data GMap Int v = GMapInt (Data.IntMap.IntMap v)<br />
empty = GMapInt Data.IntMap.empty<br />
lookup k (GMapInt m) = Data.IntMap.lookup k m<br />
insert k v (GMapInt m) = GMapInt (Data.IntMap.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 <tt>f</tt>'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 <tt>a1</tt> equal to <tt>Int</tt> and you are done. True, but what if there were these instances<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 />
Or, to put it another way, knowing that <tt>F t1</tt>=<tt>F t2</tt> does ''not'' imply that <tt>t1</tt> = <tt>t2</tt>.<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 />
The above ambiguity is caused by <tt>F</tt> being a type family, so it is possibly non-injective. However, data families create new types, so they are always injective and the following code works:<br />
<br />
<haskell>data 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</haskell><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>Blaisorbladehttps://wiki.haskell.org/index.php?title=Infix_operator&diff=18147Infix operator2008-01-06T13:34:42Z<p>Blaisorblade: Correct a claim: backticks work even for functions with more than two arguments</p>
<hr />
<div>[[Category:Syntax]] [[Category:Glossary]]<br />
== Overview ==<br />
<br />
Functions in Haskell are usually called using prefix notation, or the function name followed by its arguments. However, some functions, like +, are called with infix notation, or putting the function name between its two arguments.<br />
<br />
== Using infix functions with prefix notation ==<br />
<br />
Putting parenthesis around an infix operator converts it into a prefix function:<br />
<br />
Prelude> (+) 1 2<br />
3<br />
Prelude> (*) 3 4<br />
12<br />
<br />
== Using prefix functions with infix notation ==<br />
<br />
Putting ` marks around a prefix function allows us to use it like an infix function:<br />
<br />
Prelude> let concatPrint x y = putStrLn $ (++) x y<br />
Prelude> concatPrint "a" "b"<br />
ab<br />
Prelude> "a" `concatPrint` "b"<br />
ab<br />
<br />
Note that you can only normally do this with a function that takes two arguments. Actually, for a function taking more than two arguments, you can do it but it's not nearly as nice (note the need for extra parentheses):<br />
<br />
Prelude> foldl (+) 0 [1..5]<br />
15<br />
Prelude> ((+) `foldl` 0) [1..5]<br />
15<br />
<br />
== See also ==<br />
<br />
* [[section of an infix operator]]<br />
* [[use of infix operators]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Learn_Haskell_in_10_minutes&diff=18146Learn Haskell in 10 minutes2008-01-06T13:28:04Z<p>Blaisorblade: Typo fix: actully -> actually</p>
<hr />
<div>== Overview ==<br />
<br />
Haskell is a functional (that is, everything is done with function calls), statically, implicitly typed ([[type]]s are checked by the compiler, but you don't have to declare them), lazy (nothing is done until it needs to be) language. Its closest popular relative is probably the ML family of languages (which are not, however, lazy languages).<br />
<br />
The most common Haskell compiler is [[GHC]]. You can download GHC from http://www.haskell.org/ghc/download_ghc_661.html . GHC binaries are available for [[GNU/Linux]], [[BSD | FreeBSD]], [[Mac OS X |MacOS]], [[Windows]], and [[Solaris]]. Once you've installed [[GHC]], you get two programs you're interested in right now: <tt>ghc</tt>, and <tt>[[GHC/GHCi | ghci]]</tt>. The first compiles Haskell libraries or applications to binary code. The second is an interpreter that lets you write Haskell code and get feedback right away.<br />
<br />
== Simple expressions ==<br />
<br />
You can type most math expressions directly into <tt>ghci</tt> and get an answer. <tt>Prelude></tt> is the default GHCi prompt.<br />
<br />
Prelude> <hask>3 * 5</hask><br />
15<br />
Prelude> <hask>4 ^ 2 - 1</hask><br />
15<br />
Prelude> <hask>(1 - 5)^(3 * 2 - 4)</hask><br />
16<br />
<br />
Strings are in "double quotes." You can concatenate them with <hask>++</hask>.<br />
<br />
Prelude> <hask>"Hello"</hask><br />
"Hello"<br />
Prelude> <hask>"Hello" ++ ", Haskell"</hask><br />
"Hello, Haskell"<br />
<br />
Calling [[function]]s is done by putting the arguments directly after the function. There are no parentheses as part of the function call:<br />
<br />
Prelude> <hask>succ 5</hask><br />
6<br />
Prelude> <hask>truncate 6.59</hask><br />
6<br />
Prelude> <hask>round 6.59</hask><br />
7<br />
Prelude> <hask>sqrt 2</hask><br />
1.4142135623730951<br />
Prelude> <hask>not (5 < 3)</hask><br />
True<br />
Prelude> <hask>gcd 21 14</hask><br />
7<br />
<br />
== The console ==<br />
<br />
[[Introduction to IO |I/O actions]] can be used to read from and write to the console. Some common ones include:<br />
<br />
Prelude> <hask>putStrLn "Hello, Haskell"</hask><br />
Hello, Haskell<br />
Prelude> <hask>putStr "No newline"</hask><br />
No newlinePrelude> <hask>print (5 + 4)</hask><br />
9<br />
Prelude> <hask>print (1 < 2)</hask><br />
True<br />
<br />
The <hask>putStr</hask> and <hask>putStrLn</hask> functions output strings to the terminal. The <hask>print</hask> function outputs any type of value. (If you <hask>print</hask> a string, it will have quotes around it.)<br />
<br />
If you need multiple I/O actions in one expression, you can use a <hask>do</hask> block. Actions are separated by semicolons.<br />
<br />
Prelude> <hask>do { putStr "2 + 2 = " ; print (2 + 2) }</hask><br />
2 + 2 = 4<br />
Prelude> <hask>do { putStrLn "ABCDE" ; putStrLn "12345" }</hask><br />
ABCDE<br />
12345<br />
<br />
Reading can be done with <hask>getLine</hask> (which gives back a <hask>String</hask>) or <hask>readLn</hask> (which gives back whatever type of value you want). The <hask> <- </hask> symbol is used to assign a name to the result of an I/O action.<br />
<br />
Prelude> <hask>do { n <- readLn ; print (n^2) }</hask><br />
4<br />
16<br />
<br />
(The 4 was input. The 16 was a result.)<br />
<br />
There is actually another way to write <hask>do</hask> blocks. If you leave off the braces and semicolons, then indentation becomes significant. This doesn't work so well in <tt>ghci</tt>, but try putting the file in a source file (say, <tt>Test.hs</tt>) and build it.<br />
<br />
<haskell><br />
main = do putStrLn "What is 2 + 2?"<br />
x <- readLn<br />
if x == 4<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
You can build with <tt>ghc --make Test.hs</tt>, and the result will be called <tt>Test</tt>. (On [[Windows]], <tt>Test.exe</tt>) You get an <hask>if</hask> expression as a bonus.<br />
<br />
The first non-space character after <hask>do</hask> is special. In this case, it's the <tt>p</tt> from <hask>putStrLn</hask>. Every line that starts in the same column as that <hask>p</hask> is another statement in the <hask>do</hask> block. If you indent more, it's part of the previous statement. If you indent less, it ends the <hask>do</hask> block. This is called "layout", and Haskell uses it to avoid making you put in statement terminators and braces all the time. (The <hask>then</hask> and <hask>else</hask> phrases have to be indented for this reason: if they started in the same column, they'd be separate statements, which is wrong.)<br />
<br />
(Note: Do '''not''' indent with tabs if you're using layout. It technically still works if your tabs are 8 spaces, but it's a bad idea. Also, don't use proportional fonts -- which apparently some people do, even when programming!)<br />
<br />
== Simple types ==<br />
<br />
So far, not a single [[type]] declaration has been mentioned. That's because Haskell does type inference. You generally don't have to declare types unless you want to. If you do want to declare types, you use <hask>::</hask> to do it.<br />
<br />
Prelude> <hask>5 :: Int</hask><br />
5<br />
Prelude> <hask>5 :: Double</hask><br />
5.0<br />
<br />
[[Type]]s (and type [[class]]es, discussed later) always start with upper-case letters in Haskell. Variables always start with lower-case letters. This is a rule of the language, not a [[Studly capitals|naming convention]].<br />
<br />
You can also ask <tt>ghci</tt> what type it has chosen for something. This is useful because you don't generally have to declare your types.<br />
<br />
Prelude> :t <hask>True</hask><br />
<hask>True :: Bool</hask><br />
Prelude> :t <hask>'X'</hask><br />
<hask>'X' :: Char</hask><br />
Prelude> :t <hask>"Hello, Haskell"</hask><br />
<hask>"Hello, Haskell" :: [Char]</hask><br />
<br />
(In case you noticed, <hask>[Char]</hask> is another way of saying <hask>String</hask>. See the [[#Structured data|section on lists]] later.)<br />
<br />
Things get more interesting for numbers.<br />
<br />
Prelude> :t <hask>42</hask><br />
<hask>42 :: (Num t) => t</hask><br />
Prelude> :t <hask>42.0</hask><br />
<hask>42.0 :: (Fractional t) => t</hask><br />
Prelude> :t <hask>gcd 15 20</hask><br />
<hask>gcd 15 20 :: (Integral t) => t</hask><br />
<br />
These types use "type classes." They mean:<br />
<br />
* <hask>42</hask> can be used as any numeric type. (This is why I was able to declare <hask>5</hask> as either an <hask>Int</hask> or a <hask>Double</hask> earlier.)<br />
* <hask>42.0</hask> can be any fractional type, but not an integral type.<br />
* <hask>gcd 15 20</hask> (which is a function call, incidentally) can be any integral type, but not a fractional type.<br />
<br />
There are five numeric types in the Haskell "prelude" (the part of the library you get without having to import anything):<br />
<br />
* <hask>Int</hask> is an integer with at least 30 bits of precision.<br />
* <hask>Integer</hask> is an integer with unlimited precision.<br />
* <hask>Float</hask> is a single precision floating point number.<br />
* <hask>Double</hask> is a double precision floating point number.<br />
* <hask>Rational</hask> is a fraction type, with no rounding error.<br />
<br />
All five are '''instances''' of the <hask>Num</hask> type class. The first two are '''instances''' of <hask>Integral</hask>, and the last three are '''instances''' of <hask>Fractional</hask>.<br />
<br />
Putting it all together,<br />
<br />
Prelude> <hask>gcd 42 35 :: Int</hask><br />
7<br />
Prelude> <hask>gcd 42 35 :: Double</hask><br />
<br />
<interactive>:1:0:<br />
No instance for (Integral Double)<br />
<br />
The final type worth mentioning here is <hask>()</hask>, pronounced "unit." It only has one value, also written as <hask>()</hask> and pronounced "unit."<br />
<br />
Prelude> <hask>()</hask><br />
<hask>()</hask><br />
Prelude> :t <hask>()</hask><br />
<hask>() :: ()</hask><br />
<br />
You can think of this as similar to the <tt>void</tt> keyword in C family languages. You can return <hask>()</hask> from an I/O action if you don't want to return anything.<br />
<br />
== Structured data ==<br />
<br />
Basic data types can be easily combined in two ways: lists, which go in [square brackets], and tuples, which go in (parentheses).<br />
<br />
Lists are used to hold multiple values of the same type.<br />
<br />
Prelude> <hask>[1, 2, 3]</hask><br />
[1,2,3]<br />
Prelude> <hask>[1 .. 5]</hask><br />
[1,2,3,4,5]<br />
Prelude> <hask>[1, 3 .. 10]</hask><br />
[1,3,5,7,9]<br />
Prelude> <hask>[True, False, True]</hask><br />
[True,False,True]<br />
<br />
Strings are just lists of characters.<br />
<br />
Prelude> <hask>['H', 'e', 'l', 'l', 'o']</hask><br />
"Hello"<br />
<br />
The <hask>:</hask> operator appends an item to the beginning of a list. (It is Haskell's version of the <tt>cons</tt> function in the Lisp family of languages.)<br />
<br />
Prelude> <hask>'C' : ['H', 'e', 'l', 'l', 'o']</hask><br />
"CHello"<br />
<br />
Tuples hold a fixed number of values, which can have different types.<br />
<br />
Prelude> <hask>(1, True)</hask><br />
(1,True)<br />
Prelude> <hask>zip [1 .. 5] ['a' .. 'e']</hask><br />
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]<br />
<br />
The last example used <hask>zip</hask>, a library function that turns two lists into a list of tuples.<br />
<br />
The types are probably what you'd expect.<br />
<br />
Prelude> :t <hask>['a' .. 'c']</hask><br />
<hask>['a' .. 'c'] :: [Char]</hask><br />
Prelude> :t <hask>[('x', True), ('y', False)]</hask><br />
<hask>[('x', True), ('y', False)] :: [(Char, Bool)]</hask><br />
<br />
Lists are used a lot in Haskell. There are several functions that do nice things with them.<br />
<br />
Prelude> <hask>[1 .. 5]</hask><br />
<hask>[1,2,3,4,5]</hask><br />
Prelude> <hask>map (+ 2) [1 .. 5]</hask><br />
<hask>[3,4,5,6,7]</hask><br />
Prelude> <hask>filter (> 2) [1 .. 5]</hask><br />
<hask>[3,4,5]</hask><br />
<br />
There are two nice functions on ordered pairs (tuples of two elements):<br />
<br />
Prelude> <hask>fst (1, 2)</hask><br />
<hask>1</hask><br />
Prelude> <hask>snd (1, 2)</hask><br />
<hask>2</hask><br />
Prelude> <hask>map fst [(1, 2), (3, 4), (5, 6)]</hask><br />
<hask>[1,3,5]</hask><br />
<br />
Also see [[how to work on lists]]<br />
<br />
== [[Function]] definitions ==<br />
<br />
We wrote a definition of an [[Introduction to Haskell IO/Actions |IO action]] earlier, called <hask>main</hask>:<br />
<br />
<haskell><br />
main = do putStrLn "What is 2 + 2?"<br />
x <- readLn<br />
if x == 4<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
Now, let's supplement it by actually writing a ''[[function]]'' definition and call it <hask>factorial</hask>. I'm also adding a module header, which is good form.<br />
<br />
<haskell><br />
module Main where<br />
<br />
factorial n = if n == 0 then 1 else n * factorial (n - 1)<br />
<br />
main = do putStrLn "What is 5! ?"<br />
x <- readLn<br />
if x == factorial 5<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
Build again with <tt>ghc --make Test.hs</tt>. And,<br />
<br />
$ ./Test<br />
What is 5! ?<br />
120<br />
You're right!<br />
<br />
There's a function. Just like the built-in functions, it can be called as <hask>factorial 5</hask> without needing parentheses.<br />
<br />
Now ask <tt>ghci</tt> for the [[type]].<br />
<br />
$ ghci Test.hs<br />
<< GHCi banner >><br />
Ok, modules loaded: Main.<br />
Prelude Main> :t <hask>factorial</hask><br />
<hask>factorial :: (Num a) => a -> a</hask><br />
<br />
Function types are written with the argument type, then <hask> -> </hask>, then the result type. (This also has the type class <hask>Num</hask>.)<br />
<br />
Factorial can be simplified by writing it with case analysis.<br />
<br />
<haskell><br />
factorial 0 = 1<br />
factorial n = n * factorial (n - 1)<br />
</haskell><br />
<br />
== Convenient syntax ==<br />
<br />
A couple extra pieces of [[:Category:Syntax |syntax]] are helpful.<br />
<br />
<haskell><br />
secsToWeeks secs = let perMinute = 60<br />
perHour = 60 * perMinute<br />
perDay = 24 * perHour<br />
perWeek = 7 * perday<br />
in secs * perWeek<br />
</haskell><br />
<br />
The <hask>let</hask> expression defines temporary names. (This is using layout again. You could use {braces}, and separate the names with semicolons, if you prefer.)<br />
<br />
<haskell><br />
classify age = case age of 0 -> "newborn"<br />
1 -> "infant"<br />
2 -> "toddler"<br />
_ -> "senior citizen"<br />
</haskell><br />
<br />
The <hask>case</hask> expression does a multi-way branch. The special label <hask>_</hask> means "anything else".<br />
<br />
== Using libraries ==<br />
<br />
Everything used so far in this tutorial is part of the [[Prelude]], which is the set of Haskell functions that are always there in any program.<br />
<br />
The best road from here to becoming a very productive Haskell programmer (aside from practice!) is becoming familiar with other [[Applications and libraries | libraries]] that do the things you need. Documentation on the standard libraries is at [http://haskell.org/ghc/docs/latest/html/libraries/ http://haskell.org/ghc/docs/latest/html/libraries/]. There are modules there with:<br />
<br />
* [[Applications and libraries/Data structures |Useful data structures]]<br />
* [[Applications and libraries/Concurrency and parallelism |Concurrent and parallel programming]]<br />
* [[Applications and libraries/GUI libraries | Graphics and GUI libraries]]<br />
* [[Applications and libraries/Network | Networking, POSIX, and other system-level stuff]]<br />
* Two test frameworks, QuickCheck and HUnit<br />
* Regular expressions and predictive parsers<br />
* More...<br />
<br />
<haskell><br />
module Main where<br />
<br />
import qualified Data.Map as M<br />
<br />
errorsPerLine = M.fromList<br />
[ ("Chris", 472), ("Don", 100), ("Simon", -5) ]<br />
<br />
main = do putStrLn "Who are you?"<br />
name <- getLine<br />
case M.lookup name errorsPerLine of<br />
Nothing -> putStrLn "I don't know you"<br />
Just n -> do putStr "Errors per line: "<br />
print n<br />
</haskell><br />
<br />
The <hask>import</hask> says to use code from <hask>Data.Map</hask> and that it will be prefixed by <hask>M</hask>. (That's necessary because some of the functions have the same names as functions from the prelude. Most libraries don't need the <hask>as</hask> part.)<br />
<br />
If you want something that's not in the standard library, try looking at http://hackage.haskell.org/packages/hackage.html or this wiki's [[applications and libraries]] page. This is a collection of many different libraries written by a lot of people for Haskell. Once you've got a library, extract it and switch into that directory and do this:<br />
<br />
runhaskell Setup configure<br />
runhaskell Setup build<br />
runhaskell Setup install<br />
<br />
On a UNIX system, you may need to be root for that last part.<br />
<br />
== Topics that don't fit in 10 minute limit ==<br />
<br />
* [[:Category:Language | Advanced data types]]<br />
** Arithmetic lists<br />
** [[List comprehension]]s<br />
** [[Type#Type and newtype | Type synonyms]]<br />
** [[Type|data vs newtype]] (and [[Newtype|here]])<br />
** [[Class |Type classes and instances]]<br />
* [[:Category:Syntax |Advanced syntax]]<br />
** [[Operator]]s<br />
** [[Infix operator |(+) and `foo`]]<br />
** [[Fixity declaration]]s<br />
* Advanced functions<br />
** [[Currying]]<br />
** [[Lambda abstraction]]s<br />
** [[Section of an infix operator |Sections]]<br />
* [[:Category:Monad |Monads]]<br />
* [[Tutorials/Programming Haskell/String IO |File I/O]]<br />
** Reading files<br />
** Writing Files<br />
<br />
[[Category:Tutorials]]<br />
Languages: [[Learn Haskell in 10 minutes|en]] [[Cn/十分钟学会 Haskell|zh/cn]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=Learn_Haskell_in_10_minutes&diff=18145Learn Haskell in 10 minutes2008-01-06T13:24:21Z<p>Blaisorblade: Mention the important difference between Haskell and *ML, i.e. that ML is not lazy</p>
<hr />
<div>== Overview ==<br />
<br />
Haskell is a functional (that is, everything is done with function calls), statically, implicitly typed ([[type]]s are checked by the compiler, but you don't have to declare them), lazy (nothing is done until it needs to be) language. Its closest popular relative is probably the ML family of languages (which are not, however, lazy languages).<br />
<br />
The most common Haskell compiler is [[GHC]]. You can download GHC from http://www.haskell.org/ghc/download_ghc_661.html . GHC binaries are available for [[GNU/Linux]], [[BSD | FreeBSD]], [[Mac OS X |MacOS]], [[Windows]], and [[Solaris]]. Once you've installed [[GHC]], you get two programs you're interested in right now: <tt>ghc</tt>, and <tt>[[GHC/GHCi | ghci]]</tt>. The first compiles Haskell libraries or applications to binary code. The second is an interpreter that lets you write Haskell code and get feedback right away.<br />
<br />
== Simple expressions ==<br />
<br />
You can type most math expressions directly into <tt>ghci</tt> and get an answer. <tt>Prelude></tt> is the default GHCi prompt.<br />
<br />
Prelude> <hask>3 * 5</hask><br />
15<br />
Prelude> <hask>4 ^ 2 - 1</hask><br />
15<br />
Prelude> <hask>(1 - 5)^(3 * 2 - 4)</hask><br />
16<br />
<br />
Strings are in "double quotes." You can concatenate them with <hask>++</hask>.<br />
<br />
Prelude> <hask>"Hello"</hask><br />
"Hello"<br />
Prelude> <hask>"Hello" ++ ", Haskell"</hask><br />
"Hello, Haskell"<br />
<br />
Calling [[function]]s is done by putting the arguments directly after the function. There are no parentheses as part of the function call:<br />
<br />
Prelude> <hask>succ 5</hask><br />
6<br />
Prelude> <hask>truncate 6.59</hask><br />
6<br />
Prelude> <hask>round 6.59</hask><br />
7<br />
Prelude> <hask>sqrt 2</hask><br />
1.4142135623730951<br />
Prelude> <hask>not (5 < 3)</hask><br />
True<br />
Prelude> <hask>gcd 21 14</hask><br />
7<br />
<br />
== The console ==<br />
<br />
[[Introduction to IO |I/O actions]] can be used to read from and write to the console. Some common ones include:<br />
<br />
Prelude> <hask>putStrLn "Hello, Haskell"</hask><br />
Hello, Haskell<br />
Prelude> <hask>putStr "No newline"</hask><br />
No newlinePrelude> <hask>print (5 + 4)</hask><br />
9<br />
Prelude> <hask>print (1 < 2)</hask><br />
True<br />
<br />
The <hask>putStr</hask> and <hask>putStrLn</hask> functions output strings to the terminal. The <hask>print</hask> function outputs any type of value. (If you <hask>print</hask> a string, it will have quotes around it.)<br />
<br />
If you need multiple I/O actions in one expression, you can use a <hask>do</hask> block. Actions are separated by semicolons.<br />
<br />
Prelude> <hask>do { putStr "2 + 2 = " ; print (2 + 2) }</hask><br />
2 + 2 = 4<br />
Prelude> <hask>do { putStrLn "ABCDE" ; putStrLn "12345" }</hask><br />
ABCDE<br />
12345<br />
<br />
Reading can be done with <hask>getLine</hask> (which gives back a <hask>String</hask>) or <hask>readLn</hask> (which gives back whatever type of value you want). The <hask> <- </hask> symbol is used to assign a name to the result of an I/O action.<br />
<br />
Prelude> <hask>do { n <- readLn ; print (n^2) }</hask><br />
4<br />
16<br />
<br />
(The 4 was input. The 16 was a result.)<br />
<br />
There is actually another way to write <hask>do</hask> blocks. If you leave off the braces and semicolons, then indentation becomes significant. This doesn't work so well in <tt>ghci</tt>, but try putting the file in a source file (say, <tt>Test.hs</tt>) and build it.<br />
<br />
<haskell><br />
main = do putStrLn "What is 2 + 2?"<br />
x <- readLn<br />
if x == 4<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
You can build with <tt>ghc --make Test.hs</tt>, and the result will be called <tt>Test</tt>. (On [[Windows]], <tt>Test.exe</tt>) You get an <hask>if</hask> expression as a bonus.<br />
<br />
The first non-space character after <hask>do</hask> is special. In this case, it's the <tt>p</tt> from <hask>putStrLn</hask>. Every line that starts in the same column as that <hask>p</hask> is another statement in the <hask>do</hask> block. If you indent more, it's part of the previous statement. If you indent less, it ends the <hask>do</hask> block. This is called "layout", and Haskell uses it to avoid making you put in statement terminators and braces all the time. (The <hask>then</hask> and <hask>else</hask> phrases have to be indented for this reason: if they started in the same column, they'd be separate statements, which is wrong.)<br />
<br />
(Note: Do '''not''' indent with tabs if you're using layout. It technically still works if your tabs are 8 spaces, but it's a bad idea. Also, don't use proportional fonts -- which apparently some people do, even when programming!)<br />
<br />
== Simple types ==<br />
<br />
So far, not a single [[type]] declaration has been mentioned. That's because Haskell does type inference. You generally don't have to declare types unless you want to. If you do want to declare types, you use <hask>::</hask> to do it.<br />
<br />
Prelude> <hask>5 :: Int</hask><br />
5<br />
Prelude> <hask>5 :: Double</hask><br />
5.0<br />
<br />
[[Type]]s (and type [[class]]es, discussed later) always start with upper-case letters in Haskell. Variables always start with lower-case letters. This is a rule of the language, not a [[Studly capitals|naming convention]].<br />
<br />
You can also ask <tt>ghci</tt> what type it has chosen for something. This is useful because you don't generally have to declare your types.<br />
<br />
Prelude> :t <hask>True</hask><br />
<hask>True :: Bool</hask><br />
Prelude> :t <hask>'X'</hask><br />
<hask>'X' :: Char</hask><br />
Prelude> :t <hask>"Hello, Haskell"</hask><br />
<hask>"Hello, Haskell" :: [Char]</hask><br />
<br />
(In case you noticed, <hask>[Char]</hask> is another way of saying <hask>String</hask>. See the [[#Structured data|section on lists]] later.)<br />
<br />
Things get more interesting for numbers.<br />
<br />
Prelude> :t <hask>42</hask><br />
<hask>42 :: (Num t) => t</hask><br />
Prelude> :t <hask>42.0</hask><br />
<hask>42.0 :: (Fractional t) => t</hask><br />
Prelude> :t <hask>gcd 15 20</hask><br />
<hask>gcd 15 20 :: (Integral t) => t</hask><br />
<br />
These types use "type classes." They mean:<br />
<br />
* <hask>42</hask> can be used as any numeric type. (This is why I was able to declare <hask>5</hask> as either an <hask>Int</hask> or a <hask>Double</hask> earlier.)<br />
* <hask>42.0</hask> can be any fractional type, but not an integral type.<br />
* <hask>gcd 15 20</hask> (which is a function call, incidentally) can be any integral type, but not a fractional type.<br />
<br />
There are five numeric types in the Haskell "prelude" (the part of the library you get without having to import anything):<br />
<br />
* <hask>Int</hask> is an integer with at least 30 bits of precision.<br />
* <hask>Integer</hask> is an integer with unlimited precision.<br />
* <hask>Float</hask> is a single precision floating point number.<br />
* <hask>Double</hask> is a double precision floating point number.<br />
* <hask>Rational</hask> is a fraction type, with no rounding error.<br />
<br />
All five are '''instances''' of the <hask>Num</hask> type class. The first two are '''instances''' of <hask>Integral</hask>, and the last three are '''instances''' of <hask>Fractional</hask>.<br />
<br />
Putting it all together,<br />
<br />
Prelude> <hask>gcd 42 35 :: Int</hask><br />
7<br />
Prelude> <hask>gcd 42 35 :: Double</hask><br />
<br />
<interactive>:1:0:<br />
No instance for (Integral Double)<br />
<br />
The final type worth mentioning here is <hask>()</hask>, pronounced "unit." It only has one value, also written as <hask>()</hask> and pronounced "unit."<br />
<br />
Prelude> <hask>()</hask><br />
<hask>()</hask><br />
Prelude> :t <hask>()</hask><br />
<hask>() :: ()</hask><br />
<br />
You can think of this as similar to the <tt>void</tt> keyword in C family languages. You can return <hask>()</hask> from an I/O action if you don't want to return anything.<br />
<br />
== Structured data ==<br />
<br />
Basic data types can be easily combined in two ways: lists, which go in [square brackets], and tuples, which go in (parentheses).<br />
<br />
Lists are used to hold multiple values of the same type.<br />
<br />
Prelude> <hask>[1, 2, 3]</hask><br />
[1,2,3]<br />
Prelude> <hask>[1 .. 5]</hask><br />
[1,2,3,4,5]<br />
Prelude> <hask>[1, 3 .. 10]</hask><br />
[1,3,5,7,9]<br />
Prelude> <hask>[True, False, True]</hask><br />
[True,False,True]<br />
<br />
Strings are just lists of characters.<br />
<br />
Prelude> <hask>['H', 'e', 'l', 'l', 'o']</hask><br />
"Hello"<br />
<br />
The <hask>:</hask> operator appends an item to the beginning of a list. (It is Haskell's version of the <tt>cons</tt> function in the Lisp family of languages.)<br />
<br />
Prelude> <hask>'C' : ['H', 'e', 'l', 'l', 'o']</hask><br />
"CHello"<br />
<br />
Tuples hold a fixed number of values, which can have different types.<br />
<br />
Prelude> <hask>(1, True)</hask><br />
(1,True)<br />
Prelude> <hask>zip [1 .. 5] ['a' .. 'e']</hask><br />
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]<br />
<br />
The last example used <hask>zip</hask>, a library function that turns two lists into a list of tuples.<br />
<br />
The types are probably what you'd expect.<br />
<br />
Prelude> :t <hask>['a' .. 'c']</hask><br />
<hask>['a' .. 'c'] :: [Char]</hask><br />
Prelude> :t <hask>[('x', True), ('y', False)]</hask><br />
<hask>[('x', True), ('y', False)] :: [(Char, Bool)]</hask><br />
<br />
Lists are used a lot in Haskell. There are several functions that do nice things with them.<br />
<br />
Prelude> <hask>[1 .. 5]</hask><br />
<hask>[1,2,3,4,5]</hask><br />
Prelude> <hask>map (+ 2) [1 .. 5]</hask><br />
<hask>[3,4,5,6,7]</hask><br />
Prelude> <hask>filter (> 2) [1 .. 5]</hask><br />
<hask>[3,4,5]</hask><br />
<br />
There are two nice functions on ordered pairs (tuples of two elements):<br />
<br />
Prelude> <hask>fst (1, 2)</hask><br />
<hask>1</hask><br />
Prelude> <hask>snd (1, 2)</hask><br />
<hask>2</hask><br />
Prelude> <hask>map fst [(1, 2), (3, 4), (5, 6)]</hask><br />
<hask>[1,3,5]</hask><br />
<br />
Also see [[how to work on lists]]<br />
<br />
== [[Function]] definitions ==<br />
<br />
We wrote a definition of an [[Introduction to Haskell IO/Actions |IO action]] earlier, called <hask>main</hask>:<br />
<br />
<haskell><br />
main = do putStrLn "What is 2 + 2?"<br />
x <- readLn<br />
if x == 4<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
Now, let's supplement it by actully writing a ''[[function]]'' definition and call it <hask>factorial</hask>. I'm also adding a module header, which is good form.<br />
<br />
<haskell><br />
module Main where<br />
<br />
factorial n = if n == 0 then 1 else n * factorial (n - 1)<br />
<br />
main = do putStrLn "What is 5! ?"<br />
x <- readLn<br />
if x == factorial 5<br />
then putStrLn "You're right!"<br />
else putStrLn "You're wrong!"<br />
</haskell><br />
<br />
Build again with <tt>ghc --make Test.hs</tt>. And,<br />
<br />
$ ./Test<br />
What is 5! ?<br />
120<br />
You're right!<br />
<br />
There's a function. Just like the built-in functions, it can be called as <hask>factorial 5</hask> without needing parentheses.<br />
<br />
Now ask <tt>ghci</tt> for the [[type]].<br />
<br />
$ ghci Test.hs<br />
<< GHCi banner >><br />
Ok, modules loaded: Main.<br />
Prelude Main> :t <hask>factorial</hask><br />
<hask>factorial :: (Num a) => a -> a</hask><br />
<br />
Function types are written with the argument type, then <hask> -> </hask>, then the result type. (This also has the type class <hask>Num</hask>.)<br />
<br />
Factorial can be simplified by writing it with case analysis.<br />
<br />
<haskell><br />
factorial 0 = 1<br />
factorial n = n * factorial (n - 1)<br />
</haskell><br />
<br />
== Convenient syntax ==<br />
<br />
A couple extra pieces of [[:Category:Syntax |syntax]] are helpful.<br />
<br />
<haskell><br />
secsToWeeks secs = let perMinute = 60<br />
perHour = 60 * perMinute<br />
perDay = 24 * perHour<br />
perWeek = 7 * perday<br />
in secs * perWeek<br />
</haskell><br />
<br />
The <hask>let</hask> expression defines temporary names. (This is using layout again. You could use {braces}, and separate the names with semicolons, if you prefer.)<br />
<br />
<haskell><br />
classify age = case age of 0 -> "newborn"<br />
1 -> "infant"<br />
2 -> "toddler"<br />
_ -> "senior citizen"<br />
</haskell><br />
<br />
The <hask>case</hask> expression does a multi-way branch. The special label <hask>_</hask> means "anything else".<br />
<br />
== Using libraries ==<br />
<br />
Everything used so far in this tutorial is part of the [[Prelude]], which is the set of Haskell functions that are always there in any program.<br />
<br />
The best road from here to becoming a very productive Haskell programmer (aside from practice!) is becoming familiar with other [[Applications and libraries | libraries]] that do the things you need. Documentation on the standard libraries is at [http://haskell.org/ghc/docs/latest/html/libraries/ http://haskell.org/ghc/docs/latest/html/libraries/]. There are modules there with:<br />
<br />
* [[Applications and libraries/Data structures |Useful data structures]]<br />
* [[Applications and libraries/Concurrency and parallelism |Concurrent and parallel programming]]<br />
* [[Applications and libraries/GUI libraries | Graphics and GUI libraries]]<br />
* [[Applications and libraries/Network | Networking, POSIX, and other system-level stuff]]<br />
* Two test frameworks, QuickCheck and HUnit<br />
* Regular expressions and predictive parsers<br />
* More...<br />
<br />
<haskell><br />
module Main where<br />
<br />
import qualified Data.Map as M<br />
<br />
errorsPerLine = M.fromList<br />
[ ("Chris", 472), ("Don", 100), ("Simon", -5) ]<br />
<br />
main = do putStrLn "Who are you?"<br />
name <- getLine<br />
case M.lookup name errorsPerLine of<br />
Nothing -> putStrLn "I don't know you"<br />
Just n -> do putStr "Errors per line: "<br />
print n<br />
</haskell><br />
<br />
The <hask>import</hask> says to use code from <hask>Data.Map</hask> and that it will be prefixed by <hask>M</hask>. (That's necessary because some of the functions have the same names as functions from the prelude. Most libraries don't need the <hask>as</hask> part.)<br />
<br />
If you want something that's not in the standard library, try looking at http://hackage.haskell.org/packages/hackage.html or this wiki's [[applications and libraries]] page. This is a collection of many different libraries written by a lot of people for Haskell. Once you've got a library, extract it and switch into that directory and do this:<br />
<br />
runhaskell Setup configure<br />
runhaskell Setup build<br />
runhaskell Setup install<br />
<br />
On a UNIX system, you may need to be root for that last part.<br />
<br />
== Topics that don't fit in 10 minute limit ==<br />
<br />
* [[:Category:Language | Advanced data types]]<br />
** Arithmetic lists<br />
** [[List comprehension]]s<br />
** [[Type#Type and newtype | Type synonyms]]<br />
** [[Type|data vs newtype]] (and [[Newtype|here]])<br />
** [[Class |Type classes and instances]]<br />
* [[:Category:Syntax |Advanced syntax]]<br />
** [[Operator]]s<br />
** [[Infix operator |(+) and `foo`]]<br />
** [[Fixity declaration]]s<br />
* Advanced functions<br />
** [[Currying]]<br />
** [[Lambda abstraction]]s<br />
** [[Section of an infix operator |Sections]]<br />
* [[:Category:Monad |Monads]]<br />
* [[Tutorials/Programming Haskell/String IO |File I/O]]<br />
** Reading files<br />
** Writing Files<br />
<br />
[[Category:Tutorials]]<br />
Languages: [[Learn Haskell in 10 minutes|en]] [[Cn/十分钟学会 Haskell|zh/cn]]</div>Blaisorbladehttps://wiki.haskell.org/index.php?title=How_to_read_Haskell&diff=18144How to read Haskell2008-01-06T13:20:48Z<p>Blaisorblade: Clearify "'" with a description (it can be hard to read in some fonts) + a spelling fix -> "arbitrary"</p>
<hr />
<div>== Introduction ==<br />
<br />
This tutorial is aimed at the non-Haskeller who probably doesn't care too much about trying to write code, but wants to understand it.<br />
Our adopted format is a collection of tips and tricks broken down by category. It probably isn't very important what order you read it in, but it might be good to start with the general advice. Please feel encouraged to make any complaints about Haskell on the discussion page! It will help us to improve this tutorial.<br />
<br />
Note: you should also consider having a look at [http://www.haskell.org/~pairwise/intro/intro.html Haskell for C Programmers]. It might be a good way to get over the culture shock.<br />
<br />
----<br />
<br />
== General advice ==<br />
<br />
=== Tip: it's just very very concise ===<br />
<br />
One thing that can make Haskell hard to read is that Haskell code is extremely succinct. One tiny little piece of code can say a lot, so many times, when you are faced with something you don't understand, the best thing you can do is to think about it for some time. It will usually make sense after a while. The good news is that because of this succinctness, Haskell functions tend to be very small, which means that when you're trying to understand a difficult piece of Haskell, you normally do not have to look very far. It's just two sides of the same coin:<br />
* bad news: high density == spending more time per line of code<br />
* good news: succinctness == fewer lines of code to spend time on<br />
<br />
Spending on this time to get one tiny line of code may be frustrating, but it's well worth the effort, because the fact that a very small code is hard to understand probably means that it's very abstract, and the fact that it is abstract probably means that it's going to be used in many places. So understanding that one tiny line code, as painful as it may have been initially, can pay off in a big way.<br />
<br />
=== Trick: use the haddock ===<br />
<br />
When reading a long piece of Haskell code, one which is broken up into many modules, you should consider keeping a browser window open with the auto-generated API documentation on the side (if any).<br />
<br />
----<br />
<br />
== What does this function do? ==<br />
<br />
=== Trick: use type signatures ===<br />
<br />
When you see stuff like this<br />
<haskell><br />
map :: (a -> b) -> [a] -> [b]<br />
</haskell><br />
...don't fight it! These are type signatures and they are an incredibly useful way of getting a rough idea what a function is supposed to do.<br />
<br />
For example, the function above takes any function of type <code>(a -> b)</code> and yields a function that takes a list of <code>a</code>'s and produces a list of <code>b</code>'s. So, if <code>sqrt</code> takes a number and returns the square root of that number, <code>map sqrt</code> takes a ''list'' of numbers and returns a ''list'' of their square roots.<br />
<br />
As another example,<br />
<haskell><br />
swap :: (a,b) -> (b,a)<br />
</haskell><br />
This takes a tuple of <code>(a,b)</code> and gives back a tuple of type <code>(b,a)</code>.<br />
<br />
Here are some more things you might see in Haskell type signatures:<br />
<br />
<haskell><br />
fn :: (b -> c) -> Foo -- fn is higher order; it takes a function from b -> c as input<br />
fn :: x -> IO Int -- fn is an input/output action that returns an Int<br />
fn :: x -> [y] -- fn returns a list of ys<br />
fn :: x -> (y,z) -- fn returns a tuple of (y,z)<br />
fn :: x -- fn is just a value <br />
</haskell><br />
<br />
=== Tip: Haskellers love pattern matching ===<br />
<br />
<haskell><br />
head [x] = x<br />
</haskell><br />
This says that if 'head' is followed by a list containing only 1 item, label that item as 'x', and then return 'x'. Another example might be<br />
<haskell><br />
fst (x,y) = x<br />
<br />
snd (x,y) = y<br />
</haskell><br />
These functions fetch the '''f'''ir'''st''' and '''s'''eco'''nd''' items in a tuple, respectively. It should be fairly obvious how they work.<br />
<br />
:''elaborate''<br />
<br />
=== Tip: a function may be defined in more than one piece ===<br />
<br />
Remember math class, where functions would be defined like abs(x) = x if x >= 0 or -x otherwise? It's a bit like that in Haskell too. Sometimes, rather than writing one big if-then-else, Haskellers find it more convenient to define a function separately for each case, such as...<br />
<haskell><br />
abs x | x >= 0 = x<br />
abs x = -x<br />
</haskell><br />
<br />
What gets confusing is when you look at a definition like this...<br />
<haskell><br />
foo x | blah = <br />
some enormous long thing<br />
<br />
foo x =<br />
some other enormously long thing<br />
</haskell><br />
<br />
Especially looking at the bottom bit, it's hard to remember that <code>foo</code> might have a <em>another</em> definition lurking around. Luckily, you never have to look very far, either immediately above or immediately below the other definition.<br />
<br />
(Note: some programmers will perhaps write something like <code>foo x | otherwise = ...</code>. The <code>otherwise</code> is redundant (and equal to <code>True</code>), but useful as reminder that this isn't the entire definition of <code>foo</code>)<br />
<br />
=== Tip: pattern matching and guards can be mixed and matched ===<br />
<br />
:''elaborate''<br />
<br />
<haskell><br />
combine ((f,a,b,r):(f',a',b',r'):ss)<br />
| f == f' = combine ((f,a.+a',b.+b',r+r'):ss)<br />
combine ((f,a,b,r):ss) = (f,a,b,r) : combine ss<br />
combine [] = []<br />
</haskell><br />
<br />
----<br />
<br />
== What the heck is xyz? ==<br />
<br />
One problem you might face when reading Haskell code is figuring out some cryptic entity like <code>xyz</code> is.<br />
<br />
=== Tip: the smaller the name, the smaller the scope ===<br />
<br />
Do you hate the way Haskell code is littered with short, meaningless name like <code>x</code> and <code>xs</code>? When Haskell programmers use names like that, it's often for good reason.<br />
<br />
First, typically, the short, "meaningless" names are contained within a very small space. Consider this typical (and inefficient!) implementation of a prime number generator:<br />
<haskell><br />
primes :: [Integer]<br />
primes = sieve [2..]<br />
where<br />
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]<br />
</haskell><br />
<br />
The where block contains a function with strange variables like <code>x</code> and <code>xs</code> and <code>p</code>. In a more verbose language this could be difficult to read simply because it's difficult to actually find the definitions of small variables in long blocks of code. In C, for example, these would usually be defined at the top of a function which could have dozens (if not hundreds) of lines of code. Thus you might want to see <code>p</code> named as <code>known_prime</code> and <code>xs</code> named as <code>candidate_primes</code> or the like.<br />
<br />
In this code, however, there is no such need for it. <code>p</code> is (implicitly) defined in the same line of code that uses it. <code>xs</code>, too, is defined there, as is <code>x</code>. Further all three variables use a popular naming convention which appends 's' to the names of lists (or equivalents) and uses single letters for singular values. The only unusual part is the selection of the pattern <code>(p:xs)</code> in the arguments over the more common <code>(x:xs)</code>. Here the programmer is signalling (subtly) that this list head is somehow different from a normal list. Quick inspection demonstrates that <code>p</code> is guaranteed to be a prime number.<br />
<br />
The reason coding can be expressed this way in Haskell without undue confusion is because of its extreme conciseness. The habits you've had to learn to manage more verbose languages simply don't apply anymore. It takes some getting used to, but it becomes a joy one you reach that point.<br />
<br />
This, however, is not the main reason for such "meaningless" names. The real reason for such names is even deeper. The Haskell language allows for unparallelled levels of abstraction through functional composition and higher-order functions. Where in most imperative languages a "function" (or, more often, a procedure masquerading as a function) is a pretty low-level entity with very specific, tangible functionality, Haskell functions can be extremely abstract. Consider this canonical implementation of <code>foldl</code> from the Prelude:<br />
<haskell><br />
foldl :: (a -> b -> a) -> a -> [b] -> a<br />
foldl f z [] = z<br />
foldl f z (x:xs) = foldl f (f z x) xs<br />
</haskell><br />
<br />
This function is a highly-abstract one. It is, in fact, an abstraction of iterating over a list and computing an aggregate result. What kind of list? Pretty much any kind. What kind of computation? Anything you'd care to name. What kind of result? Anything that matches the type of the priming value. What "meaningful" names can you apply to the variables here? Should it look something like this (elided and formed to fit a reasonable screen)?:<br />
<haskell><br />
foldl binary_operation priming_value (list_head:list_body) = <br />
foldl <br />
binary_operation <br />
(binary_operation priming_value list_head)<br />
list_body<br />
</haskell><br />
<br />
Knowing a few simple conventions of Haskell variable naming (functions progress, typically, as f, g, etc. for example) makes the first, terse version far more readable as an abstract definition than does the second, verbose version&mdash;once you get used to it.<br />
<br />
=== Tip: types, functions and values ===<br />
<br />
Type variables in Haskell are typically named starting at <code>a</code>, <code>b</code>, etc. They are sometimes (but not often) decorated with numbers like <code>a1</code> or <code>b3</code>.<br />
<br />
Functions used as higher-order arguments are typically named starting at <code>f</code>, <code>g</code>, etc. They will sometimes be decorated with numbers like type variables and will also be decorated with the <code>'</code> character like <code>g'</code>. You would read this latter example as "Jee-prime" and it is typically a function that is in some way related to <code>g</code> used as a helper or the like. Occasionally functions may be given names that are not on this continuum as an aide memoir, for example a function parameter used internally as a predicate may be given the name <code>p</code>.<br />
<br />
Arguments to functions, or variables used exclusively inside short functions, are often given names starting at <code>x</code>, <code>y</code>, etc., again occasionally decorated by numbers. Other single-letter variable names may be chosen if they can act as a mnemonic for their role such as using a variable named <code>p</code> for a value known to be prime.<br />
<br />
Note that these are guidelines and not rules. ''Any'' of them can and will be ignored, modified and/or abused in ''any'' given piece of Haskell code. (A quick look at the Standard Prelude as provided in the Haskell 98 Report should be convincing enough for this.)<br />
<br />
=== Tip: the -s and m- habits ===<br />
<br />
There is a variable name habit that sometimes comes with short names. Typically, if you have a thing you want to name <code>x</code>, you'll sometimes want to name lists of these <code>xs</code>. As in the plural of <code>x</code>. So if you see a name like <code>as</code> or <code>bs</code> or <code>foos</code>, it's often good to mentally read that as "aeyes" (the plural of a), "bees" (the plural of b), and "foohs" (the plural of foo). It might seem obvious to some, but it took me a while to stop asking myself in situations like this, "<code>as</code>? What the heck is aey-ess?"<br />
<br />
Similarly, another habit you might see is people who begin variable names with m-. This is probably less common, but if you see a lot of m-, it might be because of the Maybe type. Sometimes we have <code>foo</code> of type <code>Whatever</code>, and <code>mfoo</code> of type <code>Maybe Whatever</code>. Relax, this isn't [http://en.wikipedia.org/wiki/Hungarian_notation Hungarian notation]. It's not something that's used systematically, or rigidly in any way.<br />
<br />
Both of these conventions are just helpful when you have both variants floating around in the same place, that is, when you have both Whatever and [Whatever] (that would be list of whatever), <code>x</code> and <code>xs</code> is a good way to indicate that they are both the same thing, except one comes in a list. Likewise, when you have both Whatever and Maybe Whatever in the same function, <code>x</code> and <code>mx</code> are too.<br />
<br />
Finally, library functions are sometimes suffixed with "l", "r", "_", "M" or "'" (a single quote). What do these mean?<br />
<haskell><br />
mapM -- the 'map' function lifted into a monad. An 'M' suffix implies that the function is a<br />
-- monadic version of an equivalent pure function <br />
mapM_ -- the '_' suffix indicates that the result of this computation is discarded, and () is<br />
-- returned (by analogy with the _ pattern).<br />
foldl -- a fold that traverses its structure left to right<br />
foldr -- a fold that traverses its structure right to left<br />
foldl' -- a fold that is strict in its accumulator, "'" is used to indicate a strict variant of<br />
-- a function<br />
</haskell><br />
<br />
=== Tip: order mostly doesn't matter ===<br />
<br />
It doesn't matter what order functions are defined in. This:<br />
<haskell><br />
foo x y z = ...<br />
<br />
bar a b = ... foo b ...<br />
</haskell><br />
is exactly equivilent to this:<br />
<haskell><br />
bar a b = ... foo b ...<br />
<br />
foo x y z = ...<br />
</haskell><br />
Functions further up can call functions that are defined lower down, and vice versa. Functions can be written in any order at all. It doesn't matter.<br />
<br />
:* ''scope in a nutshell''<br />
<br />
=== Tip: order does matter for pieces of functions ===<br />
<br />
Very important: whilst the order that you define individual functions does not matter, what does matter is the order that you define its individual pieces.<br />
<br />
For example, these two versions of abs do NOT mean the same thing!<br />
<br />
<haskell><br />
-- the right order<br />
abs x | x >= 0 = x<br />
abs x = -x<br />
<br />
-- the wrong order<br />
abs2 x = -x<br />
abs2 x | x >= 0 = x<br />
</haskell><br />
<br />
=== Trick: use grep ===<br />
<br />
(This might seem really obvious, but it's sometimes easy to forget)<br />
<br />
Or use the search feature of your favourite text editor. It's probably defined right there before your eyes, and if it's true to Haskell style, the definition is probably so small you blew right through it. In vi, for example, you could do <code>/= *xyz</code> which searches for =, an arbitrary number of spaces, and then xyz.<br />
<br />
Barring that, <code>xyz</code> might be defined in some different module in the code you downloaded. You can look for telltale signs like<br />
<haskell><br />
import Manamana (xyz)<br />
</haskell><br />
<br />
But note that sometimes programmers get lazy, and they don't specify that <code>xyz</code> should be imported. They just let rip with<br />
<haskell><br />
import Manamana<br />
</haskell><br />
<br />
So solution number 3 would be do something like<br />
<code><br />
grep xyz *.lhs *.hs<br />
</code><br />
(Note that literate programs sometimes use non-literate code, so search in both lhs AND hs)<br />
<br />
A fourth idea, if you can't find something, is to look it up in [http://haskell.org/hoogle/ Hoogle]<br />
<br />
A fifth idea, for Hugs/WinHugs users, is to use the ":find" command, ":find xyz" will open up your text editor with the appropriate module, jumped to the correct place. GHCi users can use ":i xyz" to get the place "xyz" is defined. (It won't open an editor, though.)<br />
<br />
[[Category:Tutorials]]</div>Blaisorblade