https://wiki.haskell.org/api.php?action=feedcontributions&user=William&feedformat=atomHaskellWiki - User contributions [en]2024-03-28T22:41:42ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=Syntactic_sugar/Cons&diff=39409Syntactic sugar/Cons2011-04-08T19:54:09Z<p>William: /* Syntactic heroin */</p>
<hr />
<div>This page is dedicated to arguments against syntactic sugar. The request for extended syntactic sugar is present everywhere and the reasons for syntactic sugar are obvious, but there are also serious objections to them. The objections listed here may help to decide when to do without syntactic sugar and which special notations should better be dropped in future versions of Haskell.<br />
<br />
<br />
== General ==<br />
<br />
Haskell's basic syntax consists of function definition and function application.<br />
Though in some cases function application is hard to read<br />
and digs into details that are not essential for the situation they describe.<br />
For this purpose special syntaxes<br />
like <hask>do</hask> syntax, guards, list notation, list comprehension, infix notation<br />
were introduced<br />
for some frequent programming tasks<br />
to allow a more pleasant look.<br />
<br />
Many people seem to like Haskell only because of its syntactic sugar.<br />
But adding syntactic sugar to a language is not a big achievement.<br />
Python, Perl, C++ have lots of syntactic sugar, but I wouldn't prefer them to Haskell.<br />
Why?<br />
Because they lack the transparency of data dependency of functional programming languages,<br />
they lack static but easy to use polymorphism,<br />
they lack lazy evaluation,<br />
they lack reliable modularisation.<br />
It's not amazing that Haskell provides a lot of syntactic sugar.<br />
It's amazing that every syntactic sugar has pure functional explanations.<br />
That proves the power of the functional concept.<br />
<br />
<br />
=== Syntactic heroin ===<br />
<br />
Compiler writers can only lose if they give way<br />
to the insistence of users requesting more syntactic sugar.<br />
Every user has his own preferred applications,<br />
everyone has his taste<br />
and everyone wants his special application and his taste to be respected in future language revisions.<br />
Who is authorised to decide which application is general and which is too special?<br />
Is it more important to have many syntactic alternatives<br />
such that all people can write with their individual styles<br />
or is it more important that code of several authors have homogenous appearance<br />
such that it can be read by all people?<br />
<br />
You can bet if new syntactic sugar arises<br />
many users will rush at it and forget about the analytic expression<br />
the special notation shall replace.<br />
To argue against that is like trying to take the most beloved toy from children.<br />
<br />
Every special notation leads to the question if it can be extended and generalised.<br />
Guards are extended to [[pattern guard]]s and<br />
[[list comprehension]] is generalised to [[parallel list comprehension]]<br />
in current versions of Haskell compilers.<br />
Infix notation for alphanumeric functions is already possible in Haskell98<br />
but "lacks" the possibility to add arguments like in <hask>x `rel c` y</hask>.<br />
The last is not implemented, but was already requested.<br />
A solution using only Haskell98 infix operators is already<br />
[http://www.haskell.org/pipermail/haskell-cafe/2002-July/003215.html invented].<br />
Further on, the more general [http://www.dcs.gla.ac.uk/mail-www/haskell/msg02005.html MixFix] notation was already proposed,<br />
not to forget the silent lifting of map data structures to<br />
[http://www.haskell.org/pipermail/haskell/2002-October/010629.html functions],<br />
[http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html postfix operators],<br />
[[section of an infix operator|sections]] of<br />
[http://www.haskell.org/pipermail/haskell-cafe/2006-July/016683.html tuples], like <hask>(?,x,?)</hask>,<br />
[http://www.haskell.org/pipermail/haskell-cafe/2007-September/031544.html symbolic prefix operators].<br />
What comes next?<br />
<br />
Rodney Bates called the phenomena not only "syntactic sugar" but "[http://portal.acm.org/citation.cfm?id=1071738 syntactic heroin]".<br />
:(See also http://www.cs.wichita.edu/~rodney/languages/Modula-Ada-comparison.txt)<br />
People start with a small dosis of syntactic sugar,<br />
they quickly want more, because the initial dose isn't enough for ecstasy any longer.<br />
If one drug no longer helps then stronger ones are requested.<br />
It is so much tempting because the users requesting syntactic sugar<br />
are not responsible for implementing it and<br />
for avoiding inferences with other language features.<br />
<br />
=== Parse errors ===<br />
<br />
Compiler users have contradictory wishes.<br />
On the one hand they want more syntactic sugar,<br />
on the other hand they want better parser error messages.<br />
They don't realize that one is quite the opposite of the other.<br />
<br />
E.g. when a parser reads an opening bracket<br />
it doesn't know whether it is the start of a list comprehension expression<br />
like <hask>[f x | x <- xs]</hask><br />
or the start of a list of comma separated expressions<br />
like <hask>[f x, f y, g z]</hask>.<br />
Thus if you accidentally mix bars and commas<br />
the parser don't know if you wanted to write a list comprehension or a comma separated list.<br />
So it can't tell you precisely what you made wrong.<br />
<br />
Type error messages of GHC have already reached a complexity<br />
which can't be processed by many Haskell newbies.<br />
It is the price to be paid for a type system<br />
which tries to cope with as few as possible type hints.<br />
<br />
Let's consider another example from the view of a compiler.<br />
Internally it transforms the source code<br />
<haskell><br />
(+1)<br />
</haskell><br />
to<br />
<haskell><br />
flip (+) 1<br />
</haskell><br />
then it compiles it like regular functional code.<br />
Though what happens if it encounters an error?<br />
If it reports the error like<br />
<code><br />
type error in<br />
flip (+) 1<br />
</code><br />
(as Hugs November 2002)<br />
you wouldn't understand it,<br />
because you typed <hask>(+1)</hask> but not <hask>flip (+) 1</hask>.<br />
A compiler which handles this properly<br />
must support syntactic sugar at the same level like regular syntax<br />
which is obviously more complicated.<br />
<br />
<br />
=== Sugar adds complexity ===<br />
<br />
Syntactic sugar are usually special grammatical constructions.<br />
They can interfere badly with other constructions:<br />
<br />
* http://hackage.haskell.org/cgi-bin/haskell-prime/trac.cgi/wiki/FixityResolution<br />
<br />
<br />
But syntactic sugar does not only touch the compilers.<br />
Many other tools like those for<br />
syntax highlighting (emacs, nedit),<br />
source code markup (lhs2TeX),<br />
source code formatting (Language.Haskell.Pretty),<br />
source code transform (e.g. symbolic differentation),<br />
program proofs,<br />
debugging,<br />
dependency analysis,<br />
documentation extraction (haddock)<br />
are affected.<br />
<br />
Each tool becomes more complicated by more syntactic sugar.<br />
<br />
<br />
=== Flexibility ===<br />
<br />
The use of functions and functions of functions (i.e. higher order functions)<br />
allows for very flexible usage of program units.<br />
This is also true for the function notation,<br />
but it is not true for some syntactic sugar.<br />
<br />
E.g. <hask>map</hask> can be used with partial application<br />
which is not possible for list comprehension syntax.<br />
Thus <hask>map toLower</hask> can be generalised to lists of strings simply by lifting <hask>map toLower</hask> with <hask>map</hask>, again, leading to <hask>map (map toLower)</hask>.<br />
In contrast to that <hask>\s -> [toLower c | c <- s]</hask><br />
has to be turned into <hask>\ss -> [[toLower c | c <- s] | s <- ss]</hask><br />
or <hask>\ss -> map (\s -> [toLower c | c <- s]) ss</hask>.<br />
<br />
A function can get more arguments as the development goes on.<br />
If you are used to write <hask>x `rel` y</hask> then you have to switch to <hask>rel c x y</hask><br />
after you added a new parameter to <hask>rel</hask>.<br />
The extended infix notation <hask>x `rel c` y</hask> is (currently?) not allowed,<br />
probably because then also nested infixes like in <hask>x `a `superRel` b` y</hask> must be handled.<br />
The prefix notation <hask>rel x y</hask> tends to need less rewriting.<br />
<br />
Guards need to be rewritten to <hask>if</hask>s or to [[Case]] statements<br />
when the result of a function needs post-processing.<br />
Say we have the functions<br />
<haskell><br />
isLeapYear :: Int -> Bool<br />
isLeapYear year = mod year 4 == 0 && (mod year 100 /= 0 || mod year 400 == 0)<br />
<br />
leapYearText :: Int -> String<br />
leapYearText year<br />
| isLeapYear year = "A leap year"<br />
| otherwise = "Not a leap year"<br />
</haskell><br />
where <hask>leapYearText</hask> shall be extended to other languages<br />
using the fictitious function <hask>translate</hask>.<br />
If you stick to guards you will possibly rewrite it to the clumsy<br />
<haskell><br />
leapYearText :: Language -> Int -> String<br />
leapYearText lang year =<br />
translate lang (case () of ()<br />
| isLeapYear year -> "A leap year"<br />
| otherwise -> "Not a leap year")<br />
</haskell><br />
But what about<br />
<haskell><br />
leapYearText :: Language -> Int -> String<br />
leapYearText lang year =<br />
translate lang (if (isLeapYear year)<br />
then "A leap year"<br />
else "Not a leap year")<br />
</haskell><br />
So if you find that simpler why not using <hask>if</hask> also in the original definition?<br />
<haskell><br />
leapYearText :: Int -> String<br />
leapYearText year =<br />
if (isLeapYear year)<br />
then "A leap year"<br />
else "Not a leap year"<br />
</haskell><br />
<br />
<br />
<br />
== Examples ==<br />
<br />
The following section consider several notations and their specific problems.<br />
<br />
=== Infix notation ===<br />
<br />
==== Precedences ====<br />
<br />
Infix notation is problematic for both human readers<br />
and source code formatters.<br />
The reader doesn't know the precedences of custom infix operators,<br />
he has to read the modules which the operators are imported from.<br />
This is even more difficult because infix operators<br />
are usually imported unqualified,<br />
that is you don't know from which module an operator is imported.<br />
The same problem arises for source code formatters.<br />
You certainly prefer the formatting<br />
<haskell><br />
a +<br />
b * c<br />
</haskell><br />
to<br />
<haskell><br />
a + b *<br />
c<br />
</haskell><br />
because the first formatting reflects the high precedence of <hask>*</hask>.<br />
A source code formatter can format this properly<br />
only if it has access to the imported modules.<br />
This is certainly uncommon for a plain source code formatter.<br />
<br />
The problem also occurs if you use an infix operator, that you did forget to import.<br />
E.g. GHC-6.4.1 may say then<br />
<code><br />
Main.hs:52:6:<br />
precedence parsing error<br />
cannot mix `($)' [infixl 9] and `(.)' [infixr 9] in the same infix expression<br />
<br />
Main.hs:52:13: Not in scope: `$'<br />
</code><br />
Actually, only the second error is relevant.<br />
<br />
<br />
It has been noticed by many people,<br />
that the integer numbered precedences are not enough for describing the relations of all the infix operators.<br />
http://www.haskell.org/pipermail/haskell-cafe/2005-February/009260.html<br />
Fractional and negative fixities were already proposed:<br />
http://www.haskell.org/pipermail/haskell-cafe/2006-November/019293.html<br />
Indeed, rules like "multiplication and division precede addition and subtraction" would be more natural.<br />
However, the <hask>Show</hask> class would no longer be so simple.<br />
<br />
<br />
==== "Infixisation" ====<br />
<br />
You can't pass an argument to a function written in infix notation.<br />
<hask>x `rel c` y</hask> or <hask>x `lift rel` y</hask> is not allowed.<br />
<br />
Some library functions are designed for a "reversed" order of arguments,<br />
this means that you will most oftenly leave out the first argument on partial application<br />
rather than the second one.<br />
E.g. the functions <hask>div</hask> and <hask>mod</hask> have parameters in the order of common mathematical notation.<br />
But you will more oftenly use <hask>flip div x</hask> than <hask>div x</hask> and<br />
<hask>flip mod x</hask> more often than <hask>mod x</hask>.<br />
This is because the library designer expect that the user will prefer the infix style,<br />
writing <hask>x `div` y</hask> and thus <hask>`div` y</hask>.<br />
<br />
For functions which are not bound to a traditional notation<br />
one should avoid this order!<br />
A bad example in this respect is the module <hask>Data.Bits</hask> in the version that comes with GHC-6.2.<br />
Many of the functions of this module alter some bits in a machine word,<br />
thus they can be considered as update functions and their type signature should end with <hask>a -> a</hask>.<br />
Then you could easily combine several operations by<br />
<haskell><br />
shiftL 2 . clearBit 7 . setBit 4 . setBit 1<br />
</haskell><br />
instead of<br />
<haskell><br />
flip shiftL 2 . flip clearBit 7 . flip setBit 4 . flip setBit 1<br />
</haskell><br />
or<br />
<haskell><br />
(`shiftL` 2) . (`clearBit` 7) . (`setBit` 4) . (`setBit` 1)<br />
</haskell><br />
.<br />
<br />
<br />
=== Lists ===<br />
<br />
==== Special notation for the list type ====<br />
<br />
The type of a list over type <hask>a</hask> is named <hask>[a]</hask> rather than <hask>List a</hask>.<br />
This is confusing, since <hask>[a]</hask> looks like the notation of a single element list.<br />
For beginners it becomes even more complicated to distinguish between the type and the value of a list.<br />
Some people try to do some kind of [[list comprehension]] by enclosing expressions in brackets<br />
just like it is done for the list type.<br />
See [[Singleton list confusion]].<br />
<br />
I don't see the advantage of <hask>[a]</hask> and would like to see <hask>List a</hask> in [[Haskell two]].<br />
<br />
<br />
==== Comma separated list elements ====<br />
<br />
We are used to the [[list notation]] <hask>[0,1,2,3]</hask>.<br />
I think many Haskell users are not aware that it is a special notation.<br />
They don't know that it is a replacement for <hask>(0:1:2:3:[])</hask>,<br />
and because of that they also can't derive<br />
that a function for constructing single element list can be written as <hask>(:[])</hask>.<br />
<br />
The comma separated list notation <hask>[0,1,2,3]</hask> is very common, but is it sensible?<br />
There are two reasons against:<br />
<br />
* The theoretical reason: The intuitive list notation using comma separation requires one comma less than the number of elements, an empty list would need -1 commas, which can't be written, obviously.<br />
* The practical reason: The colon is like a terminator. Each list element is followed by the colon, thus it is easier to reorder the elements of a list in an editor. If you have written <hask>(1:2:3:[])</hask> you can simply cut some elements and the subsequent ':' and then you can insert them whereever you want.<br />
<br />
<br />
Although the list type has so many special support by the Haskell 98 language,<br />
there is no need for some syntactic support.<br />
The definition<br />
<br />
data List a = End | (:) a (List a)<br />
<br />
is regular Haskell98 code.<br />
The colon should have precedence below <hask>($)</hask>.<br />
Then a list type can be <hask>List Int</hask> and<br />
a list value can be <hask>1 : 2 : 3 : End</hask>.<br />
<br />
Again, this proves the power of the basic features of Haskell98.<br />
<br />
<br />
==== Parallel list comprehension ====<br />
<br />
Parallel list comprehension can be replaced by using <hask>zip</hask> in many (all?) cases.<br />
<br />
<br />
== (n+k) patterns ==<br />
<br />
Therer are some notational ambiguities concerning (n+k) patterns.<br />
<br />
See [http://www.dcs.gla.ac.uk/mail-www/haskell/msg01131.html Why I hate n+k]<br />
<br />
<br />
== If-Then-Else ==<br />
<br />
The construction <hask>if</hask>-<hask>then</hask>-<hask>else</hask> can be considered as syntactic sugar for a function <hask>if</hask> of type <hask>Bool -> a -> a -> a</hask> as presented on [[Case]].<br />
The definition as plain function had the advantages that it can be used with <hask>foldr</hask> and <hask>zipWith3</hask> and<br />
that <hask>then</hask> and <hask>else</hask> became regular identifiers.<br />
Some people prefer the explicit <hask>then</hask> and <hask>else</hask> for readability reasons.<br />
A generalisation of this syntactic exception was already proposed as "[http://www.dcs.gla.ac.uk/mail-www/haskell/msg02005.html MixFix]" notation.<br />
But it's worth to turn round the question:<br />
What is so special about <hask>if</hask> that it need a special syntax?<br />
<br />
<br />
== Conclusion ==<br />
<br />
* Guards can be dropped completely. <hask>if</hask> should be turned into a regular function. <hask>case expr of</hask> could be turned into a function, i.e. <hask>case 0 -> 'a'; 1 -> 'b';</hask> could an expression of type <hask>Int -> Char</hask>. It should be complemented by <hask>select</hask> function like that in [[Case]].<br />
* Infix notation is good for nested application, because <hask>(0:1:2:[])</hask> reflects the represented structure better than <hask>((:) 0 ((:) 1 ((:) 2 [])))</hask>.<br />
* Infix usage of functions with alphanumeric names is often just a matter of habit, just for the sake of fanciness, such as <hask>toLower `map` s</hask> which doesn't add anything to readability. If this feature is kept it should remain restricted to function names. It should not be extended to partially applied functions.<br />
* List comprehension should be used rarely, parallel list comprehension should be dropped completely.<br />
* <hask>do</hask> notation is good for representing imperative and stateful program structures.<br />
* <hask>(n+k)</hask> patterns simulate a number representation which is not used internally and thus it must be emulated with much effort. It should be dropped. Numeric patterns such as <hask>0</hask> involve conversions like <hask>fromInteger</hask> and real comparisons (<hask>Eq</hask> class!) for matching. It should be thought about dropping them, too.<br />
<br />
[[Category:Syntax]]<br />
[[Category:Style]]</div>Williamhttps://wiki.haskell.org/index.php?title=Syntactic_sugar/Cons&diff=39408Syntactic sugar/Cons2011-04-08T19:53:47Z<p>William: /* Syntactic heroin */</p>
<hr />
<div>This page is dedicated to arguments against syntactic sugar. The request for extended syntactic sugar is present everywhere and the reasons for syntactic sugar are obvious, but there are also serious objections to them. The objections listed here may help to decide when to do without syntactic sugar and which special notations should better be dropped in future versions of Haskell.<br />
<br />
<br />
== General ==<br />
<br />
Haskell's basic syntax consists of function definition and function application.<br />
Though in some cases function application is hard to read<br />
and digs into details that are not essential for the situation they describe.<br />
For this purpose special syntaxes<br />
like <hask>do</hask> syntax, guards, list notation, list comprehension, infix notation<br />
were introduced<br />
for some frequent programming tasks<br />
to allow a more pleasant look.<br />
<br />
Many people seem to like Haskell only because of its syntactic sugar.<br />
But adding syntactic sugar to a language is not a big achievement.<br />
Python, Perl, C++ have lots of syntactic sugar, but I wouldn't prefer them to Haskell.<br />
Why?<br />
Because they lack the transparency of data dependency of functional programming languages,<br />
they lack static but easy to use polymorphism,<br />
they lack lazy evaluation,<br />
they lack reliable modularisation.<br />
It's not amazing that Haskell provides a lot of syntactic sugar.<br />
It's amazing that every syntactic sugar has pure functional explanations.<br />
That proves the power of the functional concept.<br />
<br />
<br />
=== Syntactic heroin ===<br />
<br />
Compiler writers can only lose if they give way<br />
to the insistence of users requesting more syntactic sugar.<br />
Every user has his own preferred applications,<br />
everyone has his taste<br />
and everyone wants his special application and his taste to be respected in future language revisions.<br />
Who is authorised to decide which application is general and which is too special?<br />
Is it more important to have many syntactic alternatives<br />
such that all people can write with their individual styles<br />
or is it more important that code of several authors have homogenous appearance<br />
such that it can be read by all people?<br />
<br />
You can bet if new syntactic sugar arises<br />
many users will rush at it and forget about the analytic expression<br />
the special notation shall replace.<br />
To argue against that is like trying to take the most beloved toy from children.<br />
<br />
Every special notation leads to the question if it can be extended and generalised.<br />
Guards are extended to [[pattern guard]]s and<br />
[[list comprehension]] is generalised to [[parallel list comprehension]]<br />
in current versions of Haskell compilers.<br />
Infix notation for alphanumeric functions is already possible in Haskell98<br />
but "lacks" the possibility to add arguments like in <hask>x `rel c` y</hask>.<br />
The last is not implemented, but was already requested.<br />
A solution using only Haskell98 infix operators is already<br />
[http://www.haskell.org/pipermail/haskell-cafe/2002-July/003215.html invented].<br />
Further on, the more general [http://www.dcs.gla.ac.uk/mail-www/haskell/msg02005.html MixFix] notation was already proposed,<br />
not to forget the silent lifting of map data structures to<br />
[http://www.haskell.org/pipermail/haskell/2002-October/010629.html functions],<br />
[http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html postfix operators],<br />
[[section of an infix operator|sections]] of<br />
[http://www.haskell.org/pipermail/haskell-cafe/2006-July/016683.html tuples], like <hask>(?,x,?)</hask>,<br />
[http://www.haskell.org/pipermail/haskell-cafe/2007-September/031544.html symbolic prefix operators].<br />
What comes next?<br />
<br />
Rodney Bates called the phenomena not only "syntactic sugar" but "[http://portal.acm.org/citation.cfm?id=1071738 syntactic heroin]".<br />
:(See also http://www.cs.wichita.edu/~rodney/languages/Modula-Ada-comparison.txt)<br />
People start with a small dosis of syntactic sugar,<br />
they quickly want more, because the initial dose is isn't enough for ecstasy any longer.<br />
If one drug no longer helps then stronger ones are requested.<br />
It is so much tempting because the users requesting syntactic sugar<br />
are not responsible for implementing it and<br />
for avoiding inferences with other language features.<br />
<br />
=== Parse errors ===<br />
<br />
Compiler users have contradictory wishes.<br />
On the one hand they want more syntactic sugar,<br />
on the other hand they want better parser error messages.<br />
They don't realize that one is quite the opposite of the other.<br />
<br />
E.g. when a parser reads an opening bracket<br />
it doesn't know whether it is the start of a list comprehension expression<br />
like <hask>[f x | x <- xs]</hask><br />
or the start of a list of comma separated expressions<br />
like <hask>[f x, f y, g z]</hask>.<br />
Thus if you accidentally mix bars and commas<br />
the parser don't know if you wanted to write a list comprehension or a comma separated list.<br />
So it can't tell you precisely what you made wrong.<br />
<br />
Type error messages of GHC have already reached a complexity<br />
which can't be processed by many Haskell newbies.<br />
It is the price to be paid for a type system<br />
which tries to cope with as few as possible type hints.<br />
<br />
Let's consider another example from the view of a compiler.<br />
Internally it transforms the source code<br />
<haskell><br />
(+1)<br />
</haskell><br />
to<br />
<haskell><br />
flip (+) 1<br />
</haskell><br />
then it compiles it like regular functional code.<br />
Though what happens if it encounters an error?<br />
If it reports the error like<br />
<code><br />
type error in<br />
flip (+) 1<br />
</code><br />
(as Hugs November 2002)<br />
you wouldn't understand it,<br />
because you typed <hask>(+1)</hask> but not <hask>flip (+) 1</hask>.<br />
A compiler which handles this properly<br />
must support syntactic sugar at the same level like regular syntax<br />
which is obviously more complicated.<br />
<br />
<br />
=== Sugar adds complexity ===<br />
<br />
Syntactic sugar are usually special grammatical constructions.<br />
They can interfere badly with other constructions:<br />
<br />
* http://hackage.haskell.org/cgi-bin/haskell-prime/trac.cgi/wiki/FixityResolution<br />
<br />
<br />
But syntactic sugar does not only touch the compilers.<br />
Many other tools like those for<br />
syntax highlighting (emacs, nedit),<br />
source code markup (lhs2TeX),<br />
source code formatting (Language.Haskell.Pretty),<br />
source code transform (e.g. symbolic differentation),<br />
program proofs,<br />
debugging,<br />
dependency analysis,<br />
documentation extraction (haddock)<br />
are affected.<br />
<br />
Each tool becomes more complicated by more syntactic sugar.<br />
<br />
<br />
=== Flexibility ===<br />
<br />
The use of functions and functions of functions (i.e. higher order functions)<br />
allows for very flexible usage of program units.<br />
This is also true for the function notation,<br />
but it is not true for some syntactic sugar.<br />
<br />
E.g. <hask>map</hask> can be used with partial application<br />
which is not possible for list comprehension syntax.<br />
Thus <hask>map toLower</hask> can be generalised to lists of strings simply by lifting <hask>map toLower</hask> with <hask>map</hask>, again, leading to <hask>map (map toLower)</hask>.<br />
In contrast to that <hask>\s -> [toLower c | c <- s]</hask><br />
has to be turned into <hask>\ss -> [[toLower c | c <- s] | s <- ss]</hask><br />
or <hask>\ss -> map (\s -> [toLower c | c <- s]) ss</hask>.<br />
<br />
A function can get more arguments as the development goes on.<br />
If you are used to write <hask>x `rel` y</hask> then you have to switch to <hask>rel c x y</hask><br />
after you added a new parameter to <hask>rel</hask>.<br />
The extended infix notation <hask>x `rel c` y</hask> is (currently?) not allowed,<br />
probably because then also nested infixes like in <hask>x `a `superRel` b` y</hask> must be handled.<br />
The prefix notation <hask>rel x y</hask> tends to need less rewriting.<br />
<br />
Guards need to be rewritten to <hask>if</hask>s or to [[Case]] statements<br />
when the result of a function needs post-processing.<br />
Say we have the functions<br />
<haskell><br />
isLeapYear :: Int -> Bool<br />
isLeapYear year = mod year 4 == 0 && (mod year 100 /= 0 || mod year 400 == 0)<br />
<br />
leapYearText :: Int -> String<br />
leapYearText year<br />
| isLeapYear year = "A leap year"<br />
| otherwise = "Not a leap year"<br />
</haskell><br />
where <hask>leapYearText</hask> shall be extended to other languages<br />
using the fictitious function <hask>translate</hask>.<br />
If you stick to guards you will possibly rewrite it to the clumsy<br />
<haskell><br />
leapYearText :: Language -> Int -> String<br />
leapYearText lang year =<br />
translate lang (case () of ()<br />
| isLeapYear year -> "A leap year"<br />
| otherwise -> "Not a leap year")<br />
</haskell><br />
But what about<br />
<haskell><br />
leapYearText :: Language -> Int -> String<br />
leapYearText lang year =<br />
translate lang (if (isLeapYear year)<br />
then "A leap year"<br />
else "Not a leap year")<br />
</haskell><br />
So if you find that simpler why not using <hask>if</hask> also in the original definition?<br />
<haskell><br />
leapYearText :: Int -> String<br />
leapYearText year =<br />
if (isLeapYear year)<br />
then "A leap year"<br />
else "Not a leap year"<br />
</haskell><br />
<br />
<br />
<br />
== Examples ==<br />
<br />
The following section consider several notations and their specific problems.<br />
<br />
=== Infix notation ===<br />
<br />
==== Precedences ====<br />
<br />
Infix notation is problematic for both human readers<br />
and source code formatters.<br />
The reader doesn't know the precedences of custom infix operators,<br />
he has to read the modules which the operators are imported from.<br />
This is even more difficult because infix operators<br />
are usually imported unqualified,<br />
that is you don't know from which module an operator is imported.<br />
The same problem arises for source code formatters.<br />
You certainly prefer the formatting<br />
<haskell><br />
a +<br />
b * c<br />
</haskell><br />
to<br />
<haskell><br />
a + b *<br />
c<br />
</haskell><br />
because the first formatting reflects the high precedence of <hask>*</hask>.<br />
A source code formatter can format this properly<br />
only if it has access to the imported modules.<br />
This is certainly uncommon for a plain source code formatter.<br />
<br />
The problem also occurs if you use an infix operator, that you did forget to import.<br />
E.g. GHC-6.4.1 may say then<br />
<code><br />
Main.hs:52:6:<br />
precedence parsing error<br />
cannot mix `($)' [infixl 9] and `(.)' [infixr 9] in the same infix expression<br />
<br />
Main.hs:52:13: Not in scope: `$'<br />
</code><br />
Actually, only the second error is relevant.<br />
<br />
<br />
It has been noticed by many people,<br />
that the integer numbered precedences are not enough for describing the relations of all the infix operators.<br />
http://www.haskell.org/pipermail/haskell-cafe/2005-February/009260.html<br />
Fractional and negative fixities were already proposed:<br />
http://www.haskell.org/pipermail/haskell-cafe/2006-November/019293.html<br />
Indeed, rules like "multiplication and division precede addition and subtraction" would be more natural.<br />
However, the <hask>Show</hask> class would no longer be so simple.<br />
<br />
<br />
==== "Infixisation" ====<br />
<br />
You can't pass an argument to a function written in infix notation.<br />
<hask>x `rel c` y</hask> or <hask>x `lift rel` y</hask> is not allowed.<br />
<br />
Some library functions are designed for a "reversed" order of arguments,<br />
this means that you will most oftenly leave out the first argument on partial application<br />
rather than the second one.<br />
E.g. the functions <hask>div</hask> and <hask>mod</hask> have parameters in the order of common mathematical notation.<br />
But you will more oftenly use <hask>flip div x</hask> than <hask>div x</hask> and<br />
<hask>flip mod x</hask> more often than <hask>mod x</hask>.<br />
This is because the library designer expect that the user will prefer the infix style,<br />
writing <hask>x `div` y</hask> and thus <hask>`div` y</hask>.<br />
<br />
For functions which are not bound to a traditional notation<br />
one should avoid this order!<br />
A bad example in this respect is the module <hask>Data.Bits</hask> in the version that comes with GHC-6.2.<br />
Many of the functions of this module alter some bits in a machine word,<br />
thus they can be considered as update functions and their type signature should end with <hask>a -> a</hask>.<br />
Then you could easily combine several operations by<br />
<haskell><br />
shiftL 2 . clearBit 7 . setBit 4 . setBit 1<br />
</haskell><br />
instead of<br />
<haskell><br />
flip shiftL 2 . flip clearBit 7 . flip setBit 4 . flip setBit 1<br />
</haskell><br />
or<br />
<haskell><br />
(`shiftL` 2) . (`clearBit` 7) . (`setBit` 4) . (`setBit` 1)<br />
</haskell><br />
.<br />
<br />
<br />
=== Lists ===<br />
<br />
==== Special notation for the list type ====<br />
<br />
The type of a list over type <hask>a</hask> is named <hask>[a]</hask> rather than <hask>List a</hask>.<br />
This is confusing, since <hask>[a]</hask> looks like the notation of a single element list.<br />
For beginners it becomes even more complicated to distinguish between the type and the value of a list.<br />
Some people try to do some kind of [[list comprehension]] by enclosing expressions in brackets<br />
just like it is done for the list type.<br />
See [[Singleton list confusion]].<br />
<br />
I don't see the advantage of <hask>[a]</hask> and would like to see <hask>List a</hask> in [[Haskell two]].<br />
<br />
<br />
==== Comma separated list elements ====<br />
<br />
We are used to the [[list notation]] <hask>[0,1,2,3]</hask>.<br />
I think many Haskell users are not aware that it is a special notation.<br />
They don't know that it is a replacement for <hask>(0:1:2:3:[])</hask>,<br />
and because of that they also can't derive<br />
that a function for constructing single element list can be written as <hask>(:[])</hask>.<br />
<br />
The comma separated list notation <hask>[0,1,2,3]</hask> is very common, but is it sensible?<br />
There are two reasons against:<br />
<br />
* The theoretical reason: The intuitive list notation using comma separation requires one comma less than the number of elements, an empty list would need -1 commas, which can't be written, obviously.<br />
* The practical reason: The colon is like a terminator. Each list element is followed by the colon, thus it is easier to reorder the elements of a list in an editor. If you have written <hask>(1:2:3:[])</hask> you can simply cut some elements and the subsequent ':' and then you can insert them whereever you want.<br />
<br />
<br />
Although the list type has so many special support by the Haskell 98 language,<br />
there is no need for some syntactic support.<br />
The definition<br />
<br />
data List a = End | (:) a (List a)<br />
<br />
is regular Haskell98 code.<br />
The colon should have precedence below <hask>($)</hask>.<br />
Then a list type can be <hask>List Int</hask> and<br />
a list value can be <hask>1 : 2 : 3 : End</hask>.<br />
<br />
Again, this proves the power of the basic features of Haskell98.<br />
<br />
<br />
==== Parallel list comprehension ====<br />
<br />
Parallel list comprehension can be replaced by using <hask>zip</hask> in many (all?) cases.<br />
<br />
<br />
== (n+k) patterns ==<br />
<br />
Therer are some notational ambiguities concerning (n+k) patterns.<br />
<br />
See [http://www.dcs.gla.ac.uk/mail-www/haskell/msg01131.html Why I hate n+k]<br />
<br />
<br />
== If-Then-Else ==<br />
<br />
The construction <hask>if</hask>-<hask>then</hask>-<hask>else</hask> can be considered as syntactic sugar for a function <hask>if</hask> of type <hask>Bool -> a -> a -> a</hask> as presented on [[Case]].<br />
The definition as plain function had the advantages that it can be used with <hask>foldr</hask> and <hask>zipWith3</hask> and<br />
that <hask>then</hask> and <hask>else</hask> became regular identifiers.<br />
Some people prefer the explicit <hask>then</hask> and <hask>else</hask> for readability reasons.<br />
A generalisation of this syntactic exception was already proposed as "[http://www.dcs.gla.ac.uk/mail-www/haskell/msg02005.html MixFix]" notation.<br />
But it's worth to turn round the question:<br />
What is so special about <hask>if</hask> that it need a special syntax?<br />
<br />
<br />
== Conclusion ==<br />
<br />
* Guards can be dropped completely. <hask>if</hask> should be turned into a regular function. <hask>case expr of</hask> could be turned into a function, i.e. <hask>case 0 -> 'a'; 1 -> 'b';</hask> could an expression of type <hask>Int -> Char</hask>. It should be complemented by <hask>select</hask> function like that in [[Case]].<br />
* Infix notation is good for nested application, because <hask>(0:1:2:[])</hask> reflects the represented structure better than <hask>((:) 0 ((:) 1 ((:) 2 [])))</hask>.<br />
* Infix usage of functions with alphanumeric names is often just a matter of habit, just for the sake of fanciness, such as <hask>toLower `map` s</hask> which doesn't add anything to readability. If this feature is kept it should remain restricted to function names. It should not be extended to partially applied functions.<br />
* List comprehension should be used rarely, parallel list comprehension should be dropped completely.<br />
* <hask>do</hask> notation is good for representing imperative and stateful program structures.<br />
* <hask>(n+k)</hask> patterns simulate a number representation which is not used internally and thus it must be emulated with much effort. It should be dropped. Numeric patterns such as <hask>0</hask> involve conversions like <hask>fromInteger</hask> and real comparisons (<hask>Eq</hask> class!) for matching. It should be thought about dropping them, too.<br />
<br />
[[Category:Syntax]]<br />
[[Category:Style]]</div>Williamhttps://wiki.haskell.org/index.php?title=Learn_Haskell_in_10_minutes&diff=39309Learn Haskell in 10 minutes2011-04-02T20:17:29Z<p>William: /* The console */</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.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 newline<br />
Prelude> <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]] [[10分で学ぶHaskell|ja]]</div>Williamhttps://wiki.haskell.org/index.php?title=Euler_problems/31_to_40&diff=39285Euler problems/31 to 402011-03-31T12:49:19Z<p>William: /* Problem 38 */</p>
<hr />
<div>== [http://projecteuler.net/index.php?section=problems&id=31 Problem 31] ==<br />
Investigating combinations of English currency denominations.<br />
<br />
Solution:<br />
<br />
This is the naive doubly recursive solution. Speed would be greatly improved by use of [[memoization]], dynamic programming, or the closed form.<br />
<haskell><br />
problem_31 = ways [1,2,5,10,20,50,100,200] !!200<br />
where ways [] = 1 : repeat 0<br />
ways (coin:coins) =n <br />
where n = zipWith (+) (ways coins) (replicate coin 0 ++ n)<br />
</haskell><br />
<br />
A beautiful solution, making usage of laziness and recursion to implement a dynamic programming scheme, blazingly fast despite actually generating the combinations and not only counting them :<br />
<haskell><br />
coins = [1,2,5,10,20,50,100,200]<br />
<br />
combinations = foldl (\without p -><br />
let (poor,rich) = splitAt p without<br />
with = poor ++ zipWith (++) (map (map (p:)) with)<br />
rich<br />
in with<br />
) ([[]] : repeat [])<br />
<br />
problem_31 = length $ combinations coins !! 200<br />
</haskell><br />
<br />
The above may be ''a beautiful solution'', but I couldn't understand it without major mental gymnastics. I would like to offer the following, which I hope will be easier to follow for ordinary ''mentats'' -- HenryLaxen 2008-02-22<br />
<haskell><br />
coins = [1,2,5,10,20,50,100,200]<br />
<br />
withcoins 1 x = [[x]]<br />
withcoins n x = concatMap addCoin [0 .. x `div` coins!!(n-1)]<br />
where addCoin k = map (++[k]) (withcoins (n-1) (x - k*coins!!(n-1)) )<br />
<br />
problem_31 = length $ withcoins (length coins) 200 <br />
</haskell><br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=32 Problem 32] ==<br />
Find the sum of all numbers that can be written as pandigital products.<br />
<br />
Solution:<br />
<haskell><br />
import Control.Monad<br />
<br />
combs 0 xs = [([],xs)]<br />
combs n xs = [(y:ys,rest) | y <- xs, (ys,rest) <- combs (n-1) (delete y xs)]<br />
<br />
l2n :: (Integral a) => [a] -> a<br />
l2n = foldl' (\a b -> 10*a+b) 0<br />
<br />
swap (a,b) = (b,a)<br />
<br />
explode :: (Integral a) => a -> [a]<br />
explode = unfoldr (\a -> if a==0 then Nothing else Just . swap $ quotRem a 10)<br />
<br />
pandigiticals =<br />
nub $ do (beg,end) <- combs 5 [1..9]<br />
n <- [1,2]<br />
let (a,b) = splitAt n beg<br />
res = l2n a * l2n b<br />
guard $ sort (explode res) == end<br />
return res<br />
<br />
problem_32 = sum pandigiticals<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=33 Problem 33] ==<br />
Discover all the fractions with an unorthodox cancelling method.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Ratio<br />
problem_33 = denominator . product $ rs<br />
{-<br />
xy/yz = x/z<br />
(10x + y)/(10y+z) = x/z<br />
9xz + yz = 10xy<br />
-}<br />
rs = [(10*x+y)%(10*y+z) | x <- t, <br />
y <- t, <br />
z <- t,<br />
x /= y ,<br />
(9*x*z) + (y*z) == (10*x*y)]<br />
where t = [1..9]<br />
</haskell><br />
<br />
That is okay, but why not let the computer do the ''thinking'' for you? Isn't this a little more directly expressive of the problem? -- HenryLaxen 2008-02-34<br />
<haskell><br />
import Data.Ratio<br />
problem_33 = denominator $ product <br />
[ a%c | a<-[1..9], b<-[1..9], c<-[1..9],<br />
isCurious a b c, a /= b && a/= c]<br />
where isCurious a b c = ((10*a+b)%(10*b+c)) == (a%c)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=34 Problem 34] ==<br />
Find the sum of all numbers which are equal to the sum of the factorial of their digits.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Char<br />
problem_34 = sum [ x | x <- [3..100000], x == facsum x ]<br />
where facsum = sum . map (product . enumFromTo 1 . digitToInt) . show<br />
<br />
</haskell><br />
<br />
Another way:<br />
<br />
<haskell><br />
import Data.Array<br />
import Data.List<br />
<br />
{-<br />
<br />
The key comes in realizing that N*9! < 10^N when N >= 9, so we<br />
only have to check up to 9 digit integers. The other key is<br />
that addition is commutative, so we only need to generate<br />
combinations (with duplicates) of the sums of the various<br />
factorials. These sums are the only potential "curious" sums.<br />
<br />
-}<br />
<br />
fac n = a!n<br />
where a = listArray (0,9) (1:(scanl1 (*) [1..9]))<br />
<br />
-- subsets of size k, including duplicates<br />
combinationsOf 0 _ = [[]]<br />
combinationsOf _ [] = []<br />
combinationsOf k (x:xs) = map (x:) <br />
(combinationsOf (k-1) (x:xs)) ++ combinationsOf k xs<br />
<br />
intToList n = reverse $ unfoldr <br />
(\x -> if x == 0 then Nothing else Just (x `mod` 10, x `div` 10)) n<br />
<br />
isCurious (n,l) = sort (intToList n) == l<br />
<br />
-- Turn a list into the sum of the factorials of the digits<br />
factorialSum l = sum $ map fac l<br />
<br />
possiblyCurious = map (\z -> (factorialSum z,z)) <br />
curious n = filter isCurious $ possiblyCurious $ combinationsOf n [0..9]<br />
problem_34 = sum $ (fst . unzip) $ concatMap curious [2..9]<br />
</haskell><br />
(The wiki formatting is messing up the unzip"&gt;unzip line above, it is correct in the version I typed in. It should of course just be fst . unzip)<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=35 Problem 35] ==<br />
How many circular primes are there below one million?<br />
<br />
Solution:<br />
<haskell><br />
import Data.List (tails, (\\))<br />
<br />
primes :: [Integer]<br />
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]<br />
<br />
primeFactors :: Integer -> [Integer]<br />
primeFactors n = factor n primes<br />
where<br />
factor _ [] = []<br />
factor m (p:ps) | p*p > m = [m]<br />
| m `mod` p == 0 = p : factor (m `div` p) (p:ps)<br />
| otherwise = factor m ps<br />
<br />
isPrime :: Integer -> Bool<br />
isPrime 1 = False<br />
isPrime n = case (primeFactors n) of<br />
(_:_:_) -> False<br />
_ -> True<br />
<br />
permutations :: Integer -> [Integer]<br />
permutations n = take l $ map (read . take l) $ tails $ take (2*l -1) $ cycle s<br />
where<br />
s = show n<br />
l = length s<br />
<br />
circular_primes :: [Integer] -> [Integer]<br />
circular_primes [] = []<br />
circular_primes (x:xs)<br />
| all isPrime p = x : circular_primes xs<br />
| otherwise = circular_primes xs<br />
where<br />
p = permutations x<br />
<br />
problem_35 :: Int<br />
problem_35 = length $ circular_primes $ takeWhile (<1000000) primes<br />
</haskell><br />
<br />
Using isPrime from above, and observing that one that can greatly reduce the search space because no circular prime can contain an even number, nor a 5, since eventually such a digit will be at the end of the number, and<br />
hence composite, we get: (HenryLaxen 2008-02-27)<br />
<br />
<haskell><br />
import Control.Monad (replicateM)<br />
<br />
canBeCircularPrimeList = [1,3,7,9]<br />
<br />
listToInt n = foldl (\x y -> 10*x+y) 0 n<br />
rot n l = y ++ x where (x,y) = splitAt n l<br />
allrots l = map (\x -> rot x l) [0..(length l)-1]<br />
isCircular l = all (isPrime . listToInt) $ allrots l<br />
circular 1 = [[2],[3],[5],[7]] -- a slightly special case<br />
circular n = filter isCircular $ replicateM n canBeCircularPrimeList<br />
<br />
problem_35 = length $ concatMap circular [1..6]<br />
</haskell><br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=36 Problem 36] ==<br />
Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.<br />
<br />
Solution:<br />
<haskell><br />
import Numeric<br />
import Data.Char<br />
<br />
showBin = flip (showIntAtBase 2 intToDigit) ""<br />
<br />
isPalindrome x = x == reverse x<br />
<br />
problem_36 = sum [x | x <- [1,3..1000000], isPalindrome (show x), isPalindrome (showBin x)]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=37 Problem 37] ==<br />
Find the sum of all eleven primes that are both truncatable from left to right and right to left.<br />
<br />
Solution:<br />
<haskell><br />
import Data.List (tails, inits, nub)<br />
<br />
primes :: [Integer]<br />
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]<br />
<br />
primeFactors :: Integer -> [Integer]<br />
primeFactors n = factor n primes<br />
where<br />
factor _ [] = []<br />
factor m (p:ps) | p*p > m = [m]<br />
| m `mod` p == 0 = p : factor (m `div` p) (p:ps)<br />
| otherwise = factor m ps<br />
<br />
isPrime :: Integer -> Bool<br />
isPrime 1 = False<br />
isPrime n = case (primeFactors n) of<br />
(_:_:_) -> False<br />
_ -> True<br />
<br />
truncs :: Integer -> [Integer]<br />
truncs n = nub . map read $ (take l . tail . tails) s ++ (take l . tail . inits) s<br />
where<br />
l = length s - 1<br />
s = show n<br />
<br />
problem_37 = sum $ take 11 [x | x <- dropWhile (<=9) primes, all isPrime (truncs x)]<br />
</haskell><br />
<br />
Or, more cleanly:<br />
<br />
<haskell><br />
import Data.Numbers.Primes (primes, isPrime)<br />
<br />
test' :: Int -> Int -> (Int -> Int -> Int) -> Bool<br />
test' n d f<br />
| d > n = True<br />
| otherwise = isPrime (f n d) && test' n (10*d) f<br />
<br />
test :: Int -> Bool<br />
test n = test' n 10 (mod) && test' n 10 (div)<br />
<br />
problem_37 = sum $ take 11 $ filter test $ filter (>7) primes<br />
</haskell><br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=38 Problem 38] ==<br />
What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, ... ?<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
<br />
mult n i vs <br />
| length (concat vs) >= 9 = concat vs<br />
| otherwise = mult n (i+1) (vs ++ [show (n * i)])<br />
<br />
problem_38 :: Int<br />
problem_38 = maximum . map read . filter ((['1'..'9'] ==) . sort) <br />
$ [mult n 1 [] | n <- [2..9999]]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=39 Problem 39] ==<br />
If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?<br />
<br />
Solution:<br />
We use the well known formula to generate primitive Pythagorean triples. All we need are the perimeters, and they have to be scaled to produce all triples in the problem space.<br />
<haskell><br />
problem_39 = head $ perims !! indexMax<br />
where perims = group<br />
$ sort [n*p | p <- pTriples, n <- [1..1000 `div` p]]<br />
counts = map length perims<br />
Just indexMax = elemIndex (maximum counts) $ counts<br />
pTriples = [p |<br />
n <- [1..floor (sqrt 1000)],<br />
m <- [n+1..floor (sqrt 1000)],<br />
even n || even m,<br />
gcd n m == 1,<br />
let a = m^2 - n^2,<br />
let b = 2*m*n,<br />
let c = m^2 + n^2,<br />
let p = a + b + c,<br />
p < 1000]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=40 Problem 40] ==<br />
Finding the nth digit of the fractional part of the irrational number.<br />
<br />
Solution:<br />
<haskell><br />
problem_40 = (d 1)*(d 10)*(d 100)*(d 1000)*(d 10000)*(d 100000)*(d 1000000)<br />
where n = concat [show n | n <- [1..]]<br />
d j = Data.Char.digitToInt (n !! (j-1))<br />
</haskell></div>Williamhttps://wiki.haskell.org/index.php?title=Euler_problems/31_to_40&diff=39284Euler problems/31 to 402011-03-31T12:28:17Z<p>William: /* Problem 38 */</p>
<hr />
<div>== [http://projecteuler.net/index.php?section=problems&id=31 Problem 31] ==<br />
Investigating combinations of English currency denominations.<br />
<br />
Solution:<br />
<br />
This is the naive doubly recursive solution. Speed would be greatly improved by use of [[memoization]], dynamic programming, or the closed form.<br />
<haskell><br />
problem_31 = ways [1,2,5,10,20,50,100,200] !!200<br />
where ways [] = 1 : repeat 0<br />
ways (coin:coins) =n <br />
where n = zipWith (+) (ways coins) (replicate coin 0 ++ n)<br />
</haskell><br />
<br />
A beautiful solution, making usage of laziness and recursion to implement a dynamic programming scheme, blazingly fast despite actually generating the combinations and not only counting them :<br />
<haskell><br />
coins = [1,2,5,10,20,50,100,200]<br />
<br />
combinations = foldl (\without p -><br />
let (poor,rich) = splitAt p without<br />
with = poor ++ zipWith (++) (map (map (p:)) with)<br />
rich<br />
in with<br />
) ([[]] : repeat [])<br />
<br />
problem_31 = length $ combinations coins !! 200<br />
</haskell><br />
<br />
The above may be ''a beautiful solution'', but I couldn't understand it without major mental gymnastics. I would like to offer the following, which I hope will be easier to follow for ordinary ''mentats'' -- HenryLaxen 2008-02-22<br />
<haskell><br />
coins = [1,2,5,10,20,50,100,200]<br />
<br />
withcoins 1 x = [[x]]<br />
withcoins n x = concatMap addCoin [0 .. x `div` coins!!(n-1)]<br />
where addCoin k = map (++[k]) (withcoins (n-1) (x - k*coins!!(n-1)) )<br />
<br />
problem_31 = length $ withcoins (length coins) 200 <br />
</haskell><br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=32 Problem 32] ==<br />
Find the sum of all numbers that can be written as pandigital products.<br />
<br />
Solution:<br />
<haskell><br />
import Control.Monad<br />
<br />
combs 0 xs = [([],xs)]<br />
combs n xs = [(y:ys,rest) | y <- xs, (ys,rest) <- combs (n-1) (delete y xs)]<br />
<br />
l2n :: (Integral a) => [a] -> a<br />
l2n = foldl' (\a b -> 10*a+b) 0<br />
<br />
swap (a,b) = (b,a)<br />
<br />
explode :: (Integral a) => a -> [a]<br />
explode = unfoldr (\a -> if a==0 then Nothing else Just . swap $ quotRem a 10)<br />
<br />
pandigiticals =<br />
nub $ do (beg,end) <- combs 5 [1..9]<br />
n <- [1,2]<br />
let (a,b) = splitAt n beg<br />
res = l2n a * l2n b<br />
guard $ sort (explode res) == end<br />
return res<br />
<br />
problem_32 = sum pandigiticals<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=33 Problem 33] ==<br />
Discover all the fractions with an unorthodox cancelling method.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Ratio<br />
problem_33 = denominator . product $ rs<br />
{-<br />
xy/yz = x/z<br />
(10x + y)/(10y+z) = x/z<br />
9xz + yz = 10xy<br />
-}<br />
rs = [(10*x+y)%(10*y+z) | x <- t, <br />
y <- t, <br />
z <- t,<br />
x /= y ,<br />
(9*x*z) + (y*z) == (10*x*y)]<br />
where t = [1..9]<br />
</haskell><br />
<br />
That is okay, but why not let the computer do the ''thinking'' for you? Isn't this a little more directly expressive of the problem? -- HenryLaxen 2008-02-34<br />
<haskell><br />
import Data.Ratio<br />
problem_33 = denominator $ product <br />
[ a%c | a<-[1..9], b<-[1..9], c<-[1..9],<br />
isCurious a b c, a /= b && a/= c]<br />
where isCurious a b c = ((10*a+b)%(10*b+c)) == (a%c)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=34 Problem 34] ==<br />
Find the sum of all numbers which are equal to the sum of the factorial of their digits.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Char<br />
problem_34 = sum [ x | x <- [3..100000], x == facsum x ]<br />
where facsum = sum . map (product . enumFromTo 1 . digitToInt) . show<br />
<br />
</haskell><br />
<br />
Another way:<br />
<br />
<haskell><br />
import Data.Array<br />
import Data.List<br />
<br />
{-<br />
<br />
The key comes in realizing that N*9! < 10^N when N >= 9, so we<br />
only have to check up to 9 digit integers. The other key is<br />
that addition is commutative, so we only need to generate<br />
combinations (with duplicates) of the sums of the various<br />
factorials. These sums are the only potential "curious" sums.<br />
<br />
-}<br />
<br />
fac n = a!n<br />
where a = listArray (0,9) (1:(scanl1 (*) [1..9]))<br />
<br />
-- subsets of size k, including duplicates<br />
combinationsOf 0 _ = [[]]<br />
combinationsOf _ [] = []<br />
combinationsOf k (x:xs) = map (x:) <br />
(combinationsOf (k-1) (x:xs)) ++ combinationsOf k xs<br />
<br />
intToList n = reverse $ unfoldr <br />
(\x -> if x == 0 then Nothing else Just (x `mod` 10, x `div` 10)) n<br />
<br />
isCurious (n,l) = sort (intToList n) == l<br />
<br />
-- Turn a list into the sum of the factorials of the digits<br />
factorialSum l = sum $ map fac l<br />
<br />
possiblyCurious = map (\z -> (factorialSum z,z)) <br />
curious n = filter isCurious $ possiblyCurious $ combinationsOf n [0..9]<br />
problem_34 = sum $ (fst . unzip) $ concatMap curious [2..9]<br />
</haskell><br />
(The wiki formatting is messing up the unzip"&gt;unzip line above, it is correct in the version I typed in. It should of course just be fst . unzip)<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=35 Problem 35] ==<br />
How many circular primes are there below one million?<br />
<br />
Solution:<br />
<haskell><br />
import Data.List (tails, (\\))<br />
<br />
primes :: [Integer]<br />
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]<br />
<br />
primeFactors :: Integer -> [Integer]<br />
primeFactors n = factor n primes<br />
where<br />
factor _ [] = []<br />
factor m (p:ps) | p*p > m = [m]<br />
| m `mod` p == 0 = p : factor (m `div` p) (p:ps)<br />
| otherwise = factor m ps<br />
<br />
isPrime :: Integer -> Bool<br />
isPrime 1 = False<br />
isPrime n = case (primeFactors n) of<br />
(_:_:_) -> False<br />
_ -> True<br />
<br />
permutations :: Integer -> [Integer]<br />
permutations n = take l $ map (read . take l) $ tails $ take (2*l -1) $ cycle s<br />
where<br />
s = show n<br />
l = length s<br />
<br />
circular_primes :: [Integer] -> [Integer]<br />
circular_primes [] = []<br />
circular_primes (x:xs)<br />
| all isPrime p = x : circular_primes xs<br />
| otherwise = circular_primes xs<br />
where<br />
p = permutations x<br />
<br />
problem_35 :: Int<br />
problem_35 = length $ circular_primes $ takeWhile (<1000000) primes<br />
</haskell><br />
<br />
Using isPrime from above, and observing that one that can greatly reduce the search space because no circular prime can contain an even number, nor a 5, since eventually such a digit will be at the end of the number, and<br />
hence composite, we get: (HenryLaxen 2008-02-27)<br />
<br />
<haskell><br />
import Control.Monad (replicateM)<br />
<br />
canBeCircularPrimeList = [1,3,7,9]<br />
<br />
listToInt n = foldl (\x y -> 10*x+y) 0 n<br />
rot n l = y ++ x where (x,y) = splitAt n l<br />
allrots l = map (\x -> rot x l) [0..(length l)-1]<br />
isCircular l = all (isPrime . listToInt) $ allrots l<br />
circular 1 = [[2],[3],[5],[7]] -- a slightly special case<br />
circular n = filter isCircular $ replicateM n canBeCircularPrimeList<br />
<br />
problem_35 = length $ concatMap circular [1..6]<br />
</haskell><br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=36 Problem 36] ==<br />
Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.<br />
<br />
Solution:<br />
<haskell><br />
import Numeric<br />
import Data.Char<br />
<br />
showBin = flip (showIntAtBase 2 intToDigit) ""<br />
<br />
isPalindrome x = x == reverse x<br />
<br />
problem_36 = sum [x | x <- [1,3..1000000], isPalindrome (show x), isPalindrome (showBin x)]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=37 Problem 37] ==<br />
Find the sum of all eleven primes that are both truncatable from left to right and right to left.<br />
<br />
Solution:<br />
<haskell><br />
import Data.List (tails, inits, nub)<br />
<br />
primes :: [Integer]<br />
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]<br />
<br />
primeFactors :: Integer -> [Integer]<br />
primeFactors n = factor n primes<br />
where<br />
factor _ [] = []<br />
factor m (p:ps) | p*p > m = [m]<br />
| m `mod` p == 0 = p : factor (m `div` p) (p:ps)<br />
| otherwise = factor m ps<br />
<br />
isPrime :: Integer -> Bool<br />
isPrime 1 = False<br />
isPrime n = case (primeFactors n) of<br />
(_:_:_) -> False<br />
_ -> True<br />
<br />
truncs :: Integer -> [Integer]<br />
truncs n = nub . map read $ (take l . tail . tails) s ++ (take l . tail . inits) s<br />
where<br />
l = length s - 1<br />
s = show n<br />
<br />
problem_37 = sum $ take 11 [x | x <- dropWhile (<=9) primes, all isPrime (truncs x)]<br />
</haskell><br />
<br />
Or, more cleanly:<br />
<br />
<haskell><br />
import Data.Numbers.Primes (primes, isPrime)<br />
<br />
test' :: Int -> Int -> (Int -> Int -> Int) -> Bool<br />
test' n d f<br />
| d > n = True<br />
| otherwise = isPrime (f n d) && test' n (10*d) f<br />
<br />
test :: Int -> Bool<br />
test n = test' n 10 (mod) && test' n 10 (div)<br />
<br />
problem_37 = sum $ take 11 $ filter test $ filter (>7) primes<br />
</haskell><br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=38 Problem 38] ==<br />
What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, ... ?<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
<br />
mult n i vs <br />
| length (concat vs) >= 9 = concat vs<br />
| otherwise = mult n (i+1) (vs ++ [show (n * i)])<br />
<br />
problem_38 = maximum . map read . filter ((['1'..'9'] ==) . sort) <br />
$ [mult n 1 [] | n <- [2..9999]]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=39 Problem 39] ==<br />
If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?<br />
<br />
Solution:<br />
We use the well known formula to generate primitive Pythagorean triples. All we need are the perimeters, and they have to be scaled to produce all triples in the problem space.<br />
<haskell><br />
problem_39 = head $ perims !! indexMax<br />
where perims = group<br />
$ sort [n*p | p <- pTriples, n <- [1..1000 `div` p]]<br />
counts = map length perims<br />
Just indexMax = elemIndex (maximum counts) $ counts<br />
pTriples = [p |<br />
n <- [1..floor (sqrt 1000)],<br />
m <- [n+1..floor (sqrt 1000)],<br />
even n || even m,<br />
gcd n m == 1,<br />
let a = m^2 - n^2,<br />
let b = 2*m*n,<br />
let c = m^2 + n^2,<br />
let p = a + b + c,<br />
p < 1000]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=40 Problem 40] ==<br />
Finding the nth digit of the fractional part of the irrational number.<br />
<br />
Solution:<br />
<haskell><br />
problem_40 = (d 1)*(d 10)*(d 100)*(d 1000)*(d 10000)*(d 100000)*(d 1000000)<br />
where n = concat [show n | n <- [1..]]<br />
d j = Data.Char.digitToInt (n !! (j-1))<br />
</haskell></div>William