https://wiki.haskell.org/api.php?action=feedcontributions&user=Daniel.is.fischer&feedformat=atomHaskellWiki - User contributions [en]2021-09-28T16:56:38ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Prime_numbers&diff=42488Prime numbers2011-10-20T12:37:30Z<p>Daniel.is.fischer: </p>
<hr />
<div>In mathematics, a ''prime number'' (or a ''prime'') is a natural number which has exactly two distinct natural number divisors: 1 and itself. The smallest prime is thus 2.<br />
<br />
Any natural number is representable as a product of powers of its prime factors, and so a prime has no prime divisors other than itself. That means that starting with 2, ''for each'' newly found ''prime'' we can ''eliminate'' from the rest of the numbers ''all such numbers'' that have this prime as their divisor, giving us the ''next available'' number as next prime. This is known as ''sieving'' the natural numbers, so that in the end what we are left with are just primes. <br />
<br />
To eliminate a prime's multiples from the result we can either '''a.''' plainly test each new candidate number for divisibility by that prime with a direct test, giving rise to a kind of ''"trial division"'' algorithm; or '''b.''' we can find out multiples of a prime ''<code>p</code>'' by ''counting up'' from it by ''<code>p</code>'' numbers at a time, resulting in a variant of a ''"genuine sieve"'' as it was reportedly originally conceived by Eratosthenes in ancient Greece. <br />
<br />
Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an efficient ''list''-based code we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results one by one.<br />
<br />
== Prime Number Resources ==<br />
<br />
* At Wikipedia:<br />
**[http://en.wikipedia.org/wiki/Prime_numbers Prime Numbers]<br />
**[http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Sieve of Eratosthenes]<br />
<br />
* HackageDB packages:<br />
** [http://hackage.haskell.org/package/arithmoi arithmoi]: Various basic number theoretic functions; efficient array-based sieves, Montgomery curve factorisation ...<br />
** [http://hackage.haskell.org/package/Numbers Numbers]: An assortment of number theoretic functions.<br />
** [http://hackage.haskell.org/package/NumberSieves NumberSieves]: Number Theoretic Sieves: primes, factorization, and Euler's Totient.<br />
** [http://hackage.haskell.org/package/primes primes]: Efficient, purely functional generation of prime numbers.<br />
<br />
* Papers:<br />
** O'Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004.<br />
<br />
== Sieve of Eratosthenes ==<br />
Sieve of Eratosthenes is ''genuinely'' represented by <br />
<haskell><br />
-- genuine yet wasteful sieve of Eratosthenes<br />
primesTo m = 2 : eratos [3,5..m] where<br />
eratos [] = []<br />
eratos (p:xs) = p : eratos (xs `minus` [p,p+2*p..m])<br />
-- eulers (p:xs) = p : eulers (xs `minus` map (p*)(p:xs))<br />
-- turner (p:xs) = p : turner [x | x<-xs, rem x p /= 0]<br />
</haskell><br />
<br />
This should be regarded more like a ''specification'', not a code. It is extremely slow, running at empirical time complexities worse than quadratic in number of primes produced. But it has the core defining features of S. of E. as '''''a.''''' being bounded, i.e. having a top limit value, and '''''b.''''' finding out the multiples of a prime by counting up from it. Yes, this is exactly how Eratosthenes defined it ([http://www.archive.org/stream/nicomachigerasen00nicouoft#page/29/mode/1up Nicomachus, ''Introduction to Arithmetic'', I, pp. 13, 31]).<br />
<br />
The canonical list-difference <code>minus</code> and duplicates-removing list-union <code>union</code> functions dealing with ordered increasing lists - infinite as well as finite - are simple enough to define (using <code>compare</code> has an effect of comparing the values only once, unlike when using (<) etc):<br />
<haskell><br />
-- ordered lists, difference and union<br />
minus (x:xs) (y:ys) = case (compare x y) of <br />
LT -> x : minus xs (y:ys)<br />
EQ -> minus xs ys <br />
GT -> minus (x:xs) ys<br />
minus xs _ = xs<br />
union (x:xs) (y:ys) = case (compare x y) of <br />
LT -> x : union xs (y:ys)<br />
EQ -> x : union xs ys <br />
GT -> y : union (x:xs) ys<br />
union xs ys = xs ++ ys<br />
</haskell><br />
<br />
(the name ''merge'' ought to be reserved for duplicates-preserving merging as used by ''mergesort'' - that's why we use ''union'' here, following Leon P.Smith's [http://hackage.haskell.org/packages/archive/data-ordlist/0.4.4/doc/html/Data-List-Ordered.html Data.List.Ordered] package).<br />
<br />
=== Analysis ===<br />
<br />
So what does it do, this sieve code? For each found prime it removes its ''odd'' multiples from further consideration. It finds them by counting up in steps of ''2p''. There are thus '''<math>O(m/p)</math>''' multiples for each prime, and '''<math>O(m \log\log(m))</math>''' multiples total, with duplicates, by virtues of ''prime harmonic series'', where <math>\sum_{p_i<m}{1/p_i} = O(\log\log(m))</math>.<br />
<br />
If each multiple is dealt with in '''<math>O(1)</math>''' time, this will translate into '''<math>O(m \log \log(m))</math>''' RAM machine operations (since we consider addition as an atomic operation). Indeed, mutable random-access arrays allow for that. Melissa O'Neill's article's stated goal was to show that so does efficient Priority Queue implementation in Haskell as well. But lists in Haskell are sequential, ''not'' random-access, and complexity of <code>minus(a,b)</code> is about '''<math>O(|a \cup b|)</math>''', i.e. here it is '''<math>O(|a|)</math>''' which is '''<math>O(m/\log(p))</math>''' according to the remark about the '''Φ'''-function in Melissa O'Neill's article. <br />
<br />
It looks like <math>\sum_{i=1}^{k}{1/log(p_i)} = O(k/\log(k))</math>. Since the number of primes below ''m'' is '''<math>n = \pi(m) = O(m/\log(m))</math>''' by the ''prime number theorem'' (where <math>\pi(m)</math> is a prime counting function), there will be ''k = n'' multiples-removing steps in the algorithm; it means total complexity of '''<math>O(m k/\log(k)) = O(m^2/(\log(m))^2)</math>''', or '''<math>O(n^2)</math>''' in ''n'' primes produced - much much worse than the optimal '''<math>O(n \log(n) \log\log(n))</math>'''.<br />
<br />
=== From Squares ===<br />
<br />
But we can start each step at the prime's ''square'', as its smaller multiples will be already processed on previous steps. This means we can ''stop early'', when the prime's square reaches the top value ''m'', and thus cut the total number of steps to around '''<math>k = \pi(\sqrt{m}) = O(2\sqrt{m}/\log(m))</math>'''. This does not in fact change the complexity of random-access code, but for lists it makes it '''<math>O(m^{1.5}/(\log m)^2)</math>''', or '''<math>O(n^{1.5}/\sqrt{\log n})</math>''' in ''n'' primes produced, showing an ''enormous'' speedup in practice: <br />
<haskell><br />
primesToQ m = 2 : sieve [3,5..m] where<br />
sieve [] = []<br />
sieve (p:xs) = p : sieve (xs `minus` [p*p,p*p+2*p..m])<br />
</haskell><br />
<br />
Its empirical complexity is about <math>O(n^{1.45})</math>. This simple optimization of starting from a prime's square has dramatic effect here because our formulation is ''bounded'', in accordance with the original algorithm. This has the desired effect of ''stopping early'' and thus ''preventing'' the creation of all the ''extraneous'' multiples streams which start ''beyond'' the upper bound anyway, turning the unacceptably slow initial ''specification'' into a ''code'' yet-far-from-optimal and slow, but acceptably so, striking a good balance between clarity, succinctness and efficiency.<br />
<br />
=== Guarded ===<br />
This ought to be ''explicated'' (improving on clarity though not on time complexity) as in the following, for which it is indeed a minor optimization whether to ''start'' from ''p'' or ''p*p'' - but ''only after'' we've went to the necessary trouble of explicitly ''stopping'' as soon as possible:<br />
<haskell><br />
primesToG m = 2 : sieve [3,5..m] where<br />
sieve (p:xs) <br />
| p*p > m = p : xs<br />
| True = p : sieve (xs `minus` [p*p,p*p+2*p..m])<br />
</haskell><br />
It is now clear that it can't be made unbounded just by abolishing the upper bound ''m'', because the guard can not be simply omitted without changing the complexity back for the worst.<br />
<br />
=== Accumulating Array ===<br />
<br />
So while <code>minus(a,b)</code> takes <math>O(|b|)</math> operations for random-access imperative arrays and about <math>O(|a|)</math> operations for lists here, using Haskell's immutable array for ''a'' one ''could'' expect the array update time to be indeed <math>O(|b|)</math> but it looks like it's not so:<br />
<haskell><br />
primesToA m = sieve 3 $ array (3,m) [(i,odd i) | i<-[3..m]] <br />
where<br />
sieve p a <br />
| p*p>m = 2 : [i | (i,True) <- assocs a]<br />
| a!p = sieve (p+2) $ a//[(i,False) | i <- [p*p,p*p+2*p..m]]<br />
| True = sieve (p+2) a<br />
</haskell><br />
<br />
It's much slower than the above, though it ''should'' be running at optimal complexity on implementations which are able to properly use the destructive update here, for an array being passed along as an accumulating parameter, it seems. <br />
<br />
How this implementation deficiency is to be overcome? One way is to use explicitly mutable monadic arrays (''see below''), but we can also think about it a little bit more on the functional side of things.<br />
<br />
=== Postponed ===<br />
Going back to ''guarded'' Eratosthenes, first we notice that though it works with minimal number of prime multiples streams, it still starts working with each a bit prematurely. Fixing this with explicit synchronization won't change complexity but will speed it up some more:<br />
<haskell><br />
primesPE () = 2 : primes'<br />
where <br />
primes' = sieve [3,5..] primes' 9<br />
sieve (p:xs) ps@ ~(_:t) q<br />
| p < q = p : sieve xs ps q<br />
| True = sieve (xs `minus` [q,q+2*p..]) t (head t^2)<br />
</haskell><br />
Since the removal of a prime's multiples here starts at the right moment, and not just from the right place, the code could '''''now''''' finally be made unbounded. Because no multiples-removal process is started ''prematurely'', there are no ''extraneous'' multiples streams, which were the reason for the extreme wastefulness and thus inefficiency of the original formulation.<br />
<br />
=== Segmented ===<br />
With work done segment-wise between the successive squares of primes it becomes <br />
<br />
<haskell><br />
primesSE () = 2 : primes'<br />
where<br />
primes' = 3 : sieve primes' 5 9 []<br />
sieve (p:ps) x q fs = <br />
foldr (flip minus) [x,x+2..q-2] <br />
[[y+s,y+2*s..q] | (s,y) <- fs]<br />
++ sieve ps (q+2) (head ps^2)<br />
((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])<br />
</haskell> <br />
<br />
This "marks" the odd composites in a given range by generating them - just as a person performing the original sieve of Eratosthenes would do, counting ''one by one'' the multiples of the relevant primes. These composites are independently generated so some will be generated multiple times. Rearranging the chain of subtractions into a subtraction of merged streams ''(see below)'' and using [http://ideone.com/pfREP tree-like folding] further speeds up the code and improves its asymptotic behavior. <br />
<br />
The advantage in working with spans explicitly is that this code is easily amendable to using arrays for the composites marking and removal on each ''finite'' span; and memory usage can be kept in check by using fixed sized segments.<br />
<br />
=== Linear merging ===<br />
But segmentation doesn't add anything substantially, and each multiples stream starts at its prime's square anyway. What does the Postponed code do, operationally? For each prime's square passed over, it builds up a nested linear ''left-deepening'' structure, '''''(...((xs-a)-b)-...)''''', where '''''xs''''' is the original odds-producing ''[3,5..]'' list, so that each odd it produces must go through <code>`minus`</code> nodes on its way up - and those odd numbers that eventually emerge on top are prime. Thinking a bit about it, wouldn't another, ''right-deepening'' structure, '''''(xs-(a+(b+...)))''''', be better? This idea is due to Richard Bird (in the code presented in Melissa O'Neill's article).<br />
<br />
Here, ''xs'' would stay near the top, and ''more frequently'' odds-producing streams of multiples of ''smaller'' primes would be above those of the ''bigger'' primes, that produce ''less frequently'' their candidates which have to pass through ''more'' <code>`union`</code> nodes on their way up. Plus, no explicit synchronization is necessary anymore because the produced multiples of a prime start at its square anyway - just some care has to be taken to avoid a runaway access to the infinitely-defined structure (specifically, if each <code>(+)</code> operation passes along unconditionally its left child's head value ''before'' polling the right child's head value, then we are safe).<br />
<br />
Here's the code, faster yet but still with about same time complexity of <math>O(n^{1.4})</math>:<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -O2 -fno-cse #-}<br />
primesLME () = 2 : ([3,5..] `minus` <br />
join [[p*p,p*p+2*p..] | p <- primes']) <br />
where<br />
primes' = 3 : ([5,7..] `minus` <br />
join [[p*p,p*p+2*p..] | p <- primes']) <br />
join ((x:xs):t) = x : union xs (join t)<br />
</haskell><br />
<br />
The double primes feed is introduced here to prevent unneeded memoization and thus prevent memory leak, as per Melissa O'Neill's code, and is dependent on no expression sharing being performed by a compiler.<br />
<br />
=== Tree merging ===<br />
Moreover, it can be changed into a '''''tree''''' structure. This idea is due to Dave Bayer on haskell-cafe mailing list (though in more complex formulation, its radical simplification due to Will Ness):<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -O2 -fno-cse #-}<br />
primesTME () = 2 : ([3,5..] `minus` <br />
join [[p*p,p*p+2*p..] | p <- primes']) <br />
where<br />
primes' = 3 : ([5,7..] `minus` <br />
join [[p*p,p*p+2*p..] | p <- primes']) <br />
join ((x:xs):t) = x : union xs (join (pairs t))<br />
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t <br />
</haskell><br />
<br />
It is [http://ideone.com/p0e81 very fast], running at speeds and empirical complexities comparable with the code from Melissa O'Neill's article (about <math>O(n^{1.2})</math> in number of primes ''n'' produced).<br />
<br />
For esthetic purposes the above can be [http://ideone.com/qpnqe rewritten as follows], using explicated [[Fold#Tree-like_folds|infinite tree-like folding]]:<br />
<br />
<haskell><br />
primes = 2 : g (fix g)<br />
where<br />
g xs = 3 : gaps 5 (foldi (\(x:xs) ys -> x:union xs ys) []<br />
[[x*x, x*x+2*x..] | x <- xs])<br />
<br />
fix g = xs where xs = g xs <br />
<br />
gaps k s@(x:xs) | k<x = k:gaps (k+2) s -- equivalent to<br />
| True = gaps (k+2) xs -- [k,k+2..]`minus`s, k<=x<br />
</haskell><br />
<br />
=== Tree merging with Wheel ===<br />
Wheel factorization optimization can be further applied, and another tree structure can be used which is better adjusted for the primes multiples production (effecting about 5%-10% at the top of a total '''''2.5x speedup''''' w.r.t. the above tree merging on odds only - though complexity stays the same):<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -O2 -fno-cse #-}<br />
primesTMWE () = 2:3:5:7: gaps 11 wheel (join $ roll 11 wheel primes')<br />
where<br />
primes' = 11: gaps 13 (tail wheel) (join $ roll 11 wheel primes')<br />
join ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs) <br />
`union` join (pairs t) <br />
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t<br />
gaps k ws@(w:t) cs@(c:u) | k==c = gaps (k+w) t u <br />
| True = k : gaps (k+w) t cs <br />
roll k ws@(w:t) ps@(p:u) | k==p = scanl (\c d->c+p*d) (p*p) ws <br />
: roll (k+w) t u <br />
| True = roll (k+w) t ps <br />
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:<br />
4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel<br />
</haskell><br />
<br />
====Above Limit====<br />
Another task is to produce primes above a given number (not having to find out their ordinal numbers).<br />
<haskell><br />
{-# OPTIONS_GHC -O2 -fno-cse #-}<br />
primesFromTMWE a0 = (if a0 <= 2 then [2] else []) <br />
++ (gaps a wh' $ compositesFrom a)<br />
where<br />
(a,wh') = rollFrom (snap (max 3 a0) 3 2)<br />
(h,p':t) = span (< z) primes' -- p < z => p*p<=a<br />
z = ceiling $ sqrt $ fromIntegral a + 1 -- p'>=z => p'*p'>a<br />
<br />
compositesFrom a = <br />
foldi union' [] (foldi union [] [multsOf p a | p <- h++[p']]<br />
: [multsOf p (p*p) | p <- t])<br />
primes' = gaps 11 wheel (foldi union' []<br />
[multsOf p (p*p) | p <- primes'']) <br />
primes'' = 11: gaps 13 (tail wheel) (foldi union' []<br />
[multsOf p (p*p) | p <- primes''])<br />
union' (x:xs) ys = x : union xs ys<br />
multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- (p*)<$><br />
where -- scanl (+) x wh<br />
(x,wh) = rollFrom (snap from p (2*p) `div` p)<br />
<br />
gaps k ws@(w:t) cs@(c:u) | k==c = gaps (k+w) t u <br />
| True = k : gaps (k+w) t cs <br />
snap v origin step = if r==0 then v else v+(step-r)<br />
where r = mod (v-origin) step <br />
wheelNums = scanl (+) 0 wheel<br />
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:<br />
4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel<br />
rollFrom n = go wheelNums wheel <br />
where m = (n-11) `mod` 210 <br />
go (x:xs) ws@(w:ws') | x < m = go xs ws'<br />
| True = (n+x-m, ws) -- (x >= m)<br />
</haskell><br />
<br />
This uses the [[Fold#Tree-like_folds|infinite-tree folding]] <code>foldi</code> with plain <code>union</code> where heads are unordered, and back with <code>union'</code> above that. A certain preprocessing delay makes it worthwhile when producing more than just a few primes.<br />
<br />
== Turner's sieve - Trial division ==<br />
<br />
David Turner's original 1975 formulation ''(SASL Language Manual, 1975)'' replaces non-standard ''`minus`'' in the sieve of Eratosthenes by stock list comprehension with ''rem'' filtering, turning it into a kind of trial division algorithm:<br />
<br />
<haskell><br />
-- unbounded sieve, premature filters<br />
primesT () = 2 : sieve [3,5..] where<br />
sieve (p:xs) = p : sieve [x | x<-xs, rem x p /= 0]<br />
-- filter ((/=0).(`rem`p)) xs<br />
</haskell><br />
<br />
This creates an immense number of superfluous implicit filters in extremely premature fashion. To be admitted as prime, ''each number'' will be ''tested for divisibility'' here by all its preceding primes potentially, while just those not greater than its square root would suffice. To find e.g. the '''1001'''st prime (<code>7927</code>), '''1000''' filters are used, when in fact just the first '''24''' are needed (up to <code>89</code>'s filter only). Operational overhead is enormous here.<br />
<br />
=== Guarded Filters ===<br />
When we force ourselves away from the ''Quest for a Mythical One-Liner'' it really ought to be written ''at least'' as bounded and guarded variety (if not abandoned right away in favor of algorithmically superior sieve of Eratosthenes), yet again achieving the ''miraculous'' complexity improvement from above quadratic to about <math>O(n^{1.45})</math> empirically (in ''n'' primes produced):<br />
<br />
<haskell><br />
primesToGT m = 2 : sieve [3,5..m] where<br />
sieve (p:xs) <br />
| p*p > m = p : xs<br />
| True = p : sieve [x | x<-xs, rem x p /= 0]<br />
-- filter ((/=0).(`rem`p)) xs<br />
</haskell><br />
<br />
=== Postponed Filters ===<br />
or ''better yet'' as unbounded, postponed variety:<br />
<haskell><br />
primesPT () = 2 : primes'<br />
where <br />
primes' = sieve [3,5..] primes' 9<br />
sieve (p:xs) ps@ ~(_:t) q<br />
| p < q = p : sieve xs ps q<br />
| True = sieve [x | x<-xs, rem x p /= 0] t (head t^2)<br />
-- filter ((/=0).(`rem`p)) xs<br />
</haskell><br />
creating here as well the linear nested filters structure at run-time, ''(...(([3,5..] |> filterBy 3) |> filterBy 5)...)'' (with <code>|></code> defined as <code>x |> f = f x</code>), each filter started at its proper moment.<br />
<br />
=== Optimal trial divison ===<br />
<br />
The above is equivalent to the traditional formulation of trial division,<br />
<haskell><br />
isPrime primes n = foldr (\p r -> p*p > n || (rem n p /= 0 && r))<br />
True primes<br />
primes = 2 : filter (isPrime primes) [3..]<br />
</haskell><br />
except that this one is rechecking for each candidate which primes to use, which will be the same prefix of the primes list being built, for all the candidate numbers in the ever increasing spans between the successive primes squares.<br />
<br />
=== Segmented Generate and Test ===<br />
This ''primes prefix's length'' can be explicitly maintained, achieving a certain further speedup (though not in complexity which stays the same) by turning a list of filters into one filter by an explicit list of primes:<br />
<haskell><br />
primesST () = 2 : primes' <br />
where<br />
primes' = 3 : sieve 0 5 9 (tail primes')<br />
sieve k x q ps = let fs = take k primes' in<br />
[n | n <- [x,x+2..q-2], and [rem n f/=0 | f <- fs]]<br />
-- filter (\n-> all ((/=0).(rem n)) fs) [x,x+2..q-2]<br />
++ sieve (k+1) (q+2) (head ps^2) (tail ps)<br />
</haskell><br />
This seems to eliminate most recalculations, explicitly filtering composites out from batches of odds between the consecutive squares of primes. <br />
<br />
All these variants of course being variations of trial division &ndash; finding out primes by direct divisibility testing of every odd number by all primes below its square root potentially (instead of just by its factors, which is what ''direct generation of multiples'' is doing, essentially) &ndash; are thus of principally worse complexities than that of Sieve of Eratosthenes; but one far worse than another yet ''easily'' fixable from a wasteful monstrosity to almost acceptable performance (at least for the first few hundred thousand primes, when compiled) just by following the proper definition of the sieve as being bounded, simply with guarded formulation, instead of "heading for the hills" of using brittle implementations of complex data structures with unclear performance guarantees.<br />
<br />
==== Generate and Test Above Limit ====<br />
<br />
The following will start the segmented Turner sieve at the right place, using any primes list it's supplied with (e.g. [[Prime_numbers#Tree_merging_with_Wheel | TMWE]] etc.), demand computing it up to the square root of any prime it'll produce:<br />
<br />
<haskell><br />
primesSTFrom primes m <br />
| m>2 = sieve (length h-1) (m`div`2*2-1) (head ps^2) (tail ps)<br />
where <br />
(h,ps) = span (<= (floor.sqrt $ fromIntegral m+1)) primes<br />
sieve k x q ps = let fs = take k $ tail primes in<br />
[n | n <- [x+2,x+4..q-2], and [rem n f /= 0 | f <- fs]]<br />
++ sieve (k+1) q (head ps^2) (tail ps)<br />
</haskell><br />
<br />
This is usually faster than testing candidate numbers for divisibility [[#Optimal trial division|one by one]] which has to re-fetch anew the needed prime factors to test by, for each candidate. Faster is the [[99_questions/Solutions/39#Solution_4.|offset sieve of Eratosthenes on odds]], and yet faster the above one, [[Prime_numbers#Above_limit| w/ wheel optimization]].<br />
<br />
=== Conclusions ===<br />
So it really pays off to analyse the code properly instead of just labeling it ''"naive"''. BTW were this divisibility testing ''somehow turned'' into an '''O(1)''' operation, e.g. by some kind of massive parallelization, the overall complexity would drop to '''O(n)'''. It's the sequentiality of testing that's the culprit. Though of course the proper multiples-removing S. of E. is a better candidate for parallelization.<br />
<br />
Did Eratosthenes himself achieve the optimal complexity? It rather seems doubtful, as he probably counted boxes in the table by 1 to go from one number to the next, as in '''3''',''5'',''7'','''9''',''11'',''13'','''15''', ... for he had no access even to Hindu numerals, using Greek alphabet for writing down numbers instead. Was he performing a ''genuine'' sieve of Eratosthenes then? Should ''faithfulness'' of an algorithm's implementation be judged by its ''performance''? We'll leave that as an open question. <br />
<br />
So the initial Turner code is just a ''one-liner'' that ought to have been regarded as ''specification'' only, in the first place, not a code to be executed as such. The reason it was taught that way is probably so that it could provoke this discussion among the students. ''To regard it as plain executable code is what's been naive all along''.<br />
<br />
== Euler's Sieve ==<br />
=== Unbounded Euler's sieve ===<br />
With each found prime Euler's sieve removes all its multiples ''in advance'' so that at each step the list to process is guaranteed to have ''no multiples'' of any of the preceding primes in it (consists only of numbers ''coprime'' with all the preceding primes) and thus starts with the next prime:<br />
<br />
<haskell><br />
primesEU () = 2 : euler [3,5..] where<br />
euler (p:xs) = p : euler (xs `minus` map (p*) (p:xs))<br />
</haskell><br />
<br />
This code is extremely inefficient, running above <math>O({n^{2}})</math> complexity (and worsening rapidly), and should be regarded a ''specification'' only. Its memory usage is very high, with space complexity just below <math>O({n^{2}})</math>, in ''n'' primes produced.<br />
<br />
=== Wheeled list representation ===<br />
<br />
The situation can be somewhat improved using a different list representation, for generating lists not from a last element and an increment, but rather a last span and an increment, which entails a set of helpful equivalences:<br />
<haskell><br />
<br />
{- fromElt (x,i) = x : fromElt (x + i,i)<br />
=== iterate (+ i) x<br />
[n..] === fromElt (n,1) <br />
=== fromSpan ([n],1) <br />
[n,n+2..] === fromElt (n,2) <br />
=== fromSpan ([n,n+2],4) -}<br />
<br />
fromSpan (xs,i) = xs ++ fromSpan (map (+ i) xs,i)<br />
<br />
{- === concat $ iterate (map (+ i)) xs<br />
fromSpan (p:xt,i) === p : fromSpan (xt ++ [p + i], i) <br />
fromSpan (xs,i) `minus` fromSpan (ys,i) <br />
=== fromSpan (xs `minus` ys, i) <br />
map (p*) (fromSpan (xs,i)) <br />
=== fromSpan (map (p*) xs, p*i)<br />
fromSpan (xs,i) === forall (p > 0).<br />
fromSpan (concat $ take p $ iterate (map (+ i)) xs, p*i) -}<br />
<br />
spanSpecs = iterate eulerStep ([2],1)<br />
eulerStep (xs@(p:_), i) = <br />
( (tail . concat . take p . iterate (map (+ i))) xs<br />
`minus` map (p*) xs, p*i )<br />
<br />
{- > mapM_ print $ take 4 spanSpecs <br />
([2],1)<br />
([3],2)<br />
([5,7],6)<br />
([7,11,13,17,19,23,29,31],30) -}<br />
</haskell><br />
<br />
Generating a list from a span specification is like rolling a ''[[#Prime_Wheels|wheel]]'' as its pattern gets repeated over and over again. For each span specification <code>w@((p:_),_)</code> produced by <code>eulerStep</code>, the numbers in <code>(fromSpan w)</code> up to <math>{p^2}</math> are all primes too, so that<br />
<br />
<haskell><br />
eulerPrimesTo m = if m > 1 then go ([2],1) else []<br />
where<br />
go w@((p:_), _) <br />
| m < p*p = takeWhile (<= m) (fromSpan w)<br />
| True = p : go (eulerStep w)<br />
</haskell><br />
<br />
This runs at about <math>O(n^{1.5..1.8})</math> complexity, for <code>n</code> primes produced, and also suffers from a severe space leak problem (IOW its memory usage is also very high).<br />
<br />
== Using Immutable Arrays ==<br />
<br />
=== Generating Segments of Primes ===<br />
<br />
The removal of multiples on each segment of odds can be done by actually marking them in an array instead of manipulating the ordered lists, and can be further sped up more than twice by working with odds only, represented as their offsets in segment arrays:<br />
<br />
<haskell><br />
primesSA () = 2: 3: sieve (tail primes) 3 []<br />
where <br />
sieve (p:ps) x fs = [i*2 + x | (i,e) <- assocs a, e] <br />
++ sieve ps (p*p) fs'<br />
where<br />
q = (p*p-x)`div`2 <br />
fs' = (p,0) : [(s, rem (y-q) s) | (s,y) <- fs]<br />
a = accumArray (\ b c -> False) True (1,q-1)<br />
[(i,()) | (s,y) <- fs, i <- [y+s,y+s+s..q]] <br />
</haskell><br />
<br />
Apparently, arrays are ''fast''. The above is the fastest code of all presented so far. When run on ''[http://ideone.com/willness/primes Ideone.com]'' it is somewhat faster than [[#Tree Merging With Wheel|Tree Merging With Wheel]] in producing first few million primes, but is very much unacceptable in its memory consumption which grows faster than O(<math>{n}</math>), quickly getting into tens and hundreds of MBs.<br />
<br />
=== Calculating Primes Upto a Given Value ===<br />
<br />
<haskell><br />
primesToNA n = 2: [i | i <- [3,5..n], ar ! i]<br />
where<br />
ar = f 5 $ accumArray (\ a b -> False) True (3,n) <br />
[(i,()) | i <- [9,15..n]]<br />
f p a | q > n = a<br />
| True = if null x then a' else f (head x) a'<br />
where q = p*p<br />
a'= a // [(i,False) | i <- [q,q+2*p..n]]<br />
x = [i | i <- [p+2,p+4..n], a' ! i]<br />
</haskell><br />
<br />
=== Calculating Primes in a Given Range ===<br />
<br />
<haskell><br />
primesFromToA a b = (if a<3 then [2] else []) <br />
++ [i | i <- [o,o+2..b], ar ! i]<br />
where <br />
o = max (if even a then a+1 else a) 3<br />
r = floor.sqrt.fromInteger $ b+1<br />
ar = accumArray (\a b-> False) True (o,b) <br />
[(i,()) | p <- [3,5..r]<br />
, let q = p*p <br />
s = 2*p <br />
(n,x) = quotRem (o - q) s <br />
q' = if o <= q then q<br />
else q + (n + signum x)*s<br />
, i <- [q',q'+s..b] ]<br />
</haskell><br />
<br />
Although using odds instead of primes, the array generation is so fast that it is very much feasible and even preferable for quick generation of some short spans of relatively big primes.<br />
<br />
== Using Mutable Arrays ==<br />
<br />
Using mutable arrays is the fastest but not the most memory efficient way to calculate prime numbers in Haskell.<br />
<br />
=== Using ST Array ===<br />
<br />
This method implements the Sieve of Eratosthenes, similar to how you might do it<br />
in C, modified to work on odds only. It is fast, but about linear in memory consumption, allocating one (though apparently bit-packed) array for the whole sequence produced.<br />
<br />
<haskell><br />
import Control.Monad<br />
import Control.Monad.ST<br />
import Data.Array.ST<br />
import Data.Array.Unboxed<br />
<br />
primesToNA :: Int -> UArray Int Bool<br />
primesToNA n = runSTUArray sieve where<br />
sieve = do<br />
let m = (n-1)`div`2<br />
a <- newArray (1,m) True :: ST s (STUArray s Int Bool)<br />
let sr = floor . (sqrt::Double->Double) $ fromIntegral n+1<br />
forM_ [1..sr`div`2] $ \i -> do<br />
let ii = 2*i*(i+1) -- == ((2*i+1)^2-1)`div`2<br />
si <- readArray a i<br />
when si $<br />
forM_ [ii,ii+i+i+1..m] $ \j -> writeArray a j False<br />
return a<br />
<br />
primesToN :: Int -> [Int]<br />
primesToN n = 2:[i*2+1 | (i,True) <- assocs . primesToNA $n]<br />
</haskell><br />
<br />
Its empirical time complexity is improving with ''n'' (number of primes produced) from '''<math>O(n^{1.25})</math>''' through '''<math>O(n^{1.20})</math>''' towards '''<math>O(n^{1.16})</math>'''. The reference [http://ideone.com/FaPOB C++ vector-based implementation] exhibits this improvement in empirical time complexity too, from '''<math>O(n^{1.5})</math>''' gradually towards '''<math>O(n^{1.12})</math>''', where tested ''(which might be interpreted as evidence towards the expected [http://en.wikipedia.org/wiki/Computation_time#Linearithmic.2Fquasilinear_time quasilinearithmic] '''<math>O(n \log(n)\log(\log n))</math>''' time complexity)''.<br />
<br />
=== Bitwise prime sieve with Template Haskell ===<br />
<br />
Count the number of prime below a given 'n'. Shows fast bitwise arrays,<br />
and an example of [[Template Haskell]] to defeat your enemies.<br />
<br />
<haskell><br />
{-# OPTIONS -O2 -optc-O -XBangPatterns #-}<br />
module Primes (nthPrime) where<br />
<br />
import Control.Monad.ST<br />
import Data.Array.ST<br />
import Data.Array.Base<br />
import System<br />
import Control.Monad<br />
import Data.Bits<br />
<br />
nthPrime :: Int -> Int<br />
nthPrime n = runST (sieve n)<br />
<br />
sieve n = do<br />
a <- newArray (3,n) True :: ST s (STUArray s Int Bool)<br />
let cutoff = truncate (sqrt $ fromIntegral n) + 1<br />
go a n cutoff 3 1<br />
<br />
go !a !m cutoff !n !c<br />
| n >= m = return c<br />
| otherwise = do<br />
e <- unsafeRead a n<br />
if e then<br />
if n < cutoff then<br />
let loop !j<br />
| j < m = do<br />
x <- unsafeRead a j<br />
when x $ unsafeWrite a j False<br />
loop (j+n)<br />
| otherwise = go a m cutoff (n+2) (c+1)<br />
in loop ( if n < 46340 then n * n else n `shiftL` 1)<br />
else go a m cutoff (n+2) (c+1)<br />
else go a m cutoff (n+2) c<br />
</haskell><br />
<br />
And place in a module:<br />
<br />
<haskell><br />
{-# OPTIONS -fth #-}<br />
import Primes<br />
<br />
main = print $( let x = nthPrime 10000000 in [| x |] )<br />
</haskell><br />
<br />
Run as:<br />
<br />
<haskell><br />
$ ghc --make -o primes Main.hs<br />
$ time ./primes<br />
664579<br />
./primes 0.00s user 0.01s system 228% cpu 0.003 total<br />
</haskell><br />
<br />
== Implicit Heap ==<br />
<br />
See [[Prime_numbers_miscellaneous#Implicit_Heap | Implicit Heap]].<br />
<br />
== Prime Wheels ==<br />
<br />
See [[Prime_numbers_miscellaneous#Prime_Wheels | Prime Wheels]].<br />
<br />
== Using IntSet for a traditional sieve ==<br />
<br />
See [[Prime_numbers_miscellaneous#Using_IntSet_for_a_traditional_sieve | Using IntSet for a traditional sieve]].<br />
<br />
== Testing Primality ==<br />
<br />
See [[Testing_primality | Testing primality]]:<br />
<br />
* [[Testing_primality#Primality_Test_and_Integer_Factorization | Primality Test and Integer Factorization ]]<br />
* [[Testing_primality#Miller-Rabin_Primality_Test | Miller-Rabin Primality Test]]<br />
<br />
== External links ==<br />
* http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip<br />
: A collection of prime generators; the file "ONeillPrimes.hs" contains one of the fastest pure-Haskell prime generators; code by Melissa O'Neill. <br />
: WARNING: Don't use the priority queue from that file for your projects: it's broken and works for primes only by a lucky chance.<br />
<br />
* [http://ideone.com/willness/primes test entries] for (some of) the above code variants.<br />
<br />
* Speed/memory [http://ideone.com/p0e81 comparison table] for sieve of Eratosthenes variants.<br />
<br />
[[Category:Code]]<br />
[[Category:Mathematics]]</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Haskell.org_committee&diff=36728Haskell.org committee2010-09-09T13:19:53Z<p>Daniel.is.fischer: Fix typo (thing -> think)</p>
<hr />
<div>== Responsibilities ==<br />
<br />
The ''haskell.org committee'' represents the Open Source Haskell community. Its responsibilities include:<br />
<br />
* setting the policy on what the haskell.org domain name, and its subdomains, may be used for<br />
* setting the policy on what the servers owned by haskell.org may be used for<br />
* determining how haskell.org funds are spent<br />
<br />
== Current members ==<br />
<br />
The first haskell.org committee has not yet been selected.<br />
<br />
== Operation ==<br />
<br />
The committee consists of 7 members, with the members electing one of their number to be chair each year. Members are expected to serve a 3 year term, and terms are staggered so that 2 or 3 members step down each year.<br />
<br />
When a member steps down, either because they have reached the end of their term or because other circumstances require them to step down early, open self-nominations will be sought from the community via the haskell@ mailing list. Previous committee members, including those who have just stepped down, will also be eligible for nomination. The committee will then select a replacement from amongst those nominated.<br />
<br />
The committee replacement process is intentionally currently very light. As we get more experience, we may wish to change it, e.g. by having a larger subset of "the community" vote on nominations.<br />
<br />
If any member of the community wishes to raise any issue with the committee, they may contact it by e-mailing [an address yet to be set up]<br />
<br />
It is expected the committee will discuss any matters brought to it amongst themselves, and if they think appropriate, with the wider community, to try to reach consensus. Ultimately, the committee will make decisions by more than half of the membership voting for a particular outcome. These rules of operation may also be changed in the same way.<br />
<br />
Each year, the committee will post a statement of the haskell.org assets, and the transactions for that year. Some details may be omitted, e.g. for confidentiality of donors.</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=TypeDirectedNameResolution&diff=31640TypeDirectedNameResolution2009-11-18T05:08:10Z<p>Daniel.is.fischer: </p>
<hr />
<div>= Type directed name resolution =<br />
<br />
This publicly editable page is a place to summarise comments on the Haskell Prime proposal for Type Directed Name Resolution (TDNR).<br />
<br />
* The [http://hackage.haskell.org/trac/haskell-prime/wiki/TypeDirectedNameResolution TDNR proposal]<br />
<br />
= Straw poll =<br />
<br />
It's hard to gauge how much people like proposals like this, so let's try the experiment of collecting votes here:<br />
<br />
Names of people who would positively like to see TDNR happen (say briefly why)<br />
* Simon PJ (I wrote the proposal)<br />
* Daniel Fischer (I think it would be an improvement to the language. I have not much missed it yet, so I don't feel strongly about it, though.)<br />
* Levi Greenspan (The current module-scoped record selectors represent a major burden when defining many records with similar selectors, for example the "channel" property in Bayeux protocol messages. See [http://www.haskell.org/pipermail/haskell-cafe/2009-May/061879.html "How to implement this? ..."] for details. Currently only type classes can be used as a workaround but only with lots of boilerplate code consisting of instance definitions. TDNR would be of great help.)<br />
<br />
Names of people who think that on balance it's a bad idea<br />
* Ganesh Sittampalam (see http://thread.gmane.org/gmane.comp.lang.haskell.cafe/61723 ; I think that having constraints you can't quantify over is a bad idea. However if that is fixable I'd be generally in favour.)<br />
* Malcolm Wallace. (I see the attraction of the idea, but find the use of '.' highly confusing. If there are spaces around the dot, it is normal functional composition, if no spaces, then it is almost like composition in the opposite direction. Also, there seem to be lots of special cases based on what is easier to implement - the design does not seem sufficiently orthogonal and clear-cut. There is a new form of lightweight overloading hiding here, but it is struggling to fight its way out of a tangle of syntactic issues.)<br />
* Luke Palmer. (I don't like the idea that I could break someone's code that doesn't have anything to do with mine by changing one of my types -- that is, if they are using an overloaded function with the same name as mine. Also I echo Ganesh's concern)<br />
<br />
= Other comments =<br />
<br />
* A lot of people have commented that using <hask>.</hask> for this as well as composition and qualification is going to start getting confusing. One alternative suggestion was <hask>-></hask> but this would conflict with case branches and lambda syntax. Similar things like <hask>~></hask> or <hask>--></hask> could work too, but look a little uglier.<br />
<br />
However, I think a little ugly is preferable to confusing or conflicting with syntax. I ''think'' using '.' won't be too confusing (we all separate the composition operator from the functions by a space anyway, don't we?), so I'd go with that. But rather than letting it die over '.'-ambiguity, I'd choose a different notation (would <hask>a#f</hask> be an option?).[[User:Daniel.is.fischer|Daniel.is.fischer]] 21:06, 17 November 2009 (UTC)<br />
<br />
No, I often use composition now without surrounding spaces.</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=GHC/Type_families&diff=31629GHC/Type families2009-11-17T21:47:46Z<p>Daniel.is.fischer: Fixed a few typos</p>
<hr />
<div>[[Category:GHC|Indexed types]]<br />
<br />
== What are type families? ==<br />
<br />
Indexed type families, or type families for short, are type constructors that represent ''sets of types.'' Set members are denoted by supplying the type family constructor with type parameters, which are called ''type indices''. The difference between vanilla parametrised type constructors and family constructors is much like between parametrically polymorphic functions and (ad-hoc polymorphic) methods of type classes. Parametric polymorphic functions behave the same at all type instances, whereas class methods can change their behaviour in dependence on the class type parameters. Similarly, vanilla type constructors imply the same data representation for all type instances, but family constructors can have varying representation types for varying type indices.<br />
<br />
Indexed type families come in two flavours: ''data families'' and ''type synonym families''. They are the indexed family variants of algebraic data types and type synonyms, respectively. The instances of data families can be data types and newtypes.<br />
<br />
== Type families in GHC ==<br />
<br />
Indexed type families are a new GHC extension to facilitate type-level programming. Type families are a generalisation of [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html associated data types] and [http://www.cse.unsw.edu.au/~chak/papers/CKP05.html associated type synonyms], and are described in a [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html recent ICFP paper]. They essentially provide type-indexed data types and named functions on types, which are useful for generic programming and highly parameterised library interfaces as well as interfaces with enhanced static information, much like dependent types. They might also be regarded as an alternative to functional dependencies, but provide a more functional style of type-level programming than the relational style of functional dependencies.<br />
<br />
== What do I need to use type families? ==<br />
<br />
The first stable release of GHC that properly supports type families is 6.10.1. (An early partial implementation was part of the 6.8 release, but its use is deprecated.) Please [http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status=reopened&group=priority&type=bug&order=id&desc=1 report bugs] via the GHC bug tracker, ideally accompanied by a small example program that demonstrates the problem. Use the [mailto:glasgow-haskell-users@haskell.org GHC mailing list] for questions or for a discussion of this language extension and its description on this wiki page.<br />
<br />
== An associated data type example ==<br />
<br />
As an example, consider Ralf Hinze's [http://www.informatik.uni-bonn.de/~ralf/publications.html#J4 generalised tries], a form of generic finite maps. <br />
<br />
=== The class declaration ===<br />
<br />
We define a type class whose instances are the types that we can use as keys in our generic maps:<br />
<haskell><br />
class GMapKey k where<br />
data GMap k :: * -> *<br />
empty :: GMap k v<br />
lookup :: k -> GMap k v -> Maybe v<br />
insert :: k -> v -> GMap k v -> GMap k v<br />
</haskell><br />
The interesting part is the ''associated data family'' declaration of the class. It gives a [http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html#sec-kinding ''kind signature''] (here <hask>* -> *</hask>) for the associated data type <hask>GMap k</hask> - analog to how methods receive a type signature in a class declaration.<br />
<br />
What it is important to notice is that the first parameter of the associated type <hask>GMap</hask> coincides with the class parameter of <hask>GMapKey</hask>. This indicates that also in all instances of the class, the instances of the associated data type need to have their first argument match up with the instance type. In general, the type arguments of an associated type can be a subset of the class parameters (in a multi-parameter type class) and they can appear in any order, possibly in an order other than in the class head. The latter can be useful if the associated data type is partially applied in some contexts.<br />
<br />
The second important point is that as <hask>GMap k</hask> has kind <hask>* -> *</hask> and <hask>k</hask> (implicitly) has kind <hask>*</hask>, the type constructor <hask>GMap</hask> (without an argument) has kind <hask>* -> * -> *</hask>. Consequently, we see that <hask>GMap</hask> is applied to two arguments in the signatures of the methods <hask>empty</hask>, <hask>lookup</hask>, and <hask>insert</hask>.<br />
<br />
=== An Int instance ===<br />
<br />
To use Ints as keys into generic maps, we declare an instance that simply uses <hask>Data.Map</hask>, thusly:<br />
<haskell><br />
instance GMapKey Int where<br />
data GMap Int v = GMapInt (Data.Map.Map Int v)<br />
empty = GMapInt Data.Map.empty<br />
lookup k (GMapInt m) = Data.Map.lookup k m<br />
insert k v (GMapInt m) = GMapInt (Data.Map.insert k v m)<br />
</haskell><br />
The <hask>Int</hask> instance of the associated data type <hask>GMap</hask> needs to have both of its parameters, but as only the first one corresponds to a class parameter, the second needs to be a type variable (here <hask>v</hask>). As mentioned before, any associated type parameter that corresponds to a class parameter must be identical to the class parameter in each instance. The right hand side of the associated data declaration is like that of any other data type.<br />
<br />
NB: At the moment, GADT syntax is not allowed for associated data types (or other indexed types). This is not a fundamental limitation, but just a shortcoming of the current implementation, which we expect to lift in the future.<br />
<br />
As an exercise, implement an instance for <hask>Char</hask> that maps back to the <hask>Int</hask> instance using the conversion functions <hask>Char.ord</hask> and <hask>Char.chr</hask>.<br />
<br />
=== A unit instance ===<br />
<br />
Generic definitions, apart from elementary types, typically cover units, products, and sums. We start here with the unit instance for <hask>GMap</hask>:<br />
<haskell><br />
instance GMapKey () where<br />
data GMap () v = GMapUnit (Maybe v)<br />
empty = GMapUnit Nothing<br />
lookup () (GMapUnit v) = v<br />
insert () v (GMapUnit _) = GMapUnit $ Just v<br />
</haskell><br />
For unit, the map is just a <hask>Maybe</hask> value.<br />
<br />
=== Product and sum instances ===<br />
<br />
Next, let us define the instances for pairs and sums (i.e., <hask>Either</hask>):<br />
<haskell><br />
instance (GMapKey a, GMapKey b) => GMapKey (a, b) where<br />
data GMap (a, b) v = GMapPair (GMap a (GMap b v))<br />
empty = GMapPair empty<br />
lookup (a, b) (GMapPair gm) = lookup a gm >>= lookup b <br />
insert (a, b) v (GMapPair gm) = GMapPair $ case lookup a gm of<br />
Nothing -> insert a (insert b v empty) gm<br />
Just gm2 -> insert a (insert b v gm2 ) gm<br />
<br />
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where<br />
data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
empty = GMapEither empty empty<br />
lookup (Left a) (GMapEither gm1 _gm2) = lookup a gm1<br />
lookup (Right b) (GMapEither _gm1 gm2 ) = lookup b gm2<br />
insert (Left a) v (GMapEither gm1 gm2) = GMapEither (insert a v gm1) gm2<br />
insert (Right b) v (GMapEither gm1 gm2) = GMapEither gm1 (insert b v gm2)<br />
</haskell><br />
If you find this code algorithmically surprising, I'd suggest to have a look at [http://www.informatik.uni-bonn.de/~ralf/publications.html#J4 Ralf Hinze's paper]. The only novelty concerning associated types, in these two instances, is that the instances have a context <hask>(GMapKey a, GMapKey b)</hask>. Consequently, the right hand sides of the associated type declarations can use <hask>GMap</hask> recursively at the key types <hask>a</hask> and <hask>b</hask> - not unlike the method definitions use the class methods recursively at the types for which the class is given in the instance context.<br />
<br />
=== Using a generic map ===<br />
<br />
Finally, some code building and querying a generic map:<br />
<haskell><br />
myGMap :: GMap (Int, Either Char ()) String<br />
myGMap = insert (5, Left 'c') "(5, Left 'c')" $<br />
insert (4, Right ()) "(4, Right ())" $<br />
insert (5, Right ()) "This is the one!" $<br />
insert (5, Right ()) "This is the two!" $<br />
insert (6, Right ()) "(6, Right ())" $<br />
insert (5, Left 'a') "(5, Left 'a')" $<br />
empty<br />
main = putStrLn $ maybe "Couldn't find key!" id $ lookup (5, Right ()) myGMap<br />
</haskell><br />
<br />
=== Download the code ===<br />
<br />
If you want to play with this example without copying it off the wiki, just download the [http://darcs.haskell.org/testsuite/tests/ghc-regress/indexed-types/should_run/GMapAssoc.hs source code for <hask>GMap</hask>] from GHC's test suite.<br />
<br />
== Detailed definition of data families ==<br />
<br />
Data families appear in two flavours: (1) they can be defined on the toplevel or (2) they can appear inside type classes (in which case they are known as associated types). The former is the more general variant, as it lacks the requirement for the type-indices to coincide with the class parameters. However, the latter can lead to more clearly structured code and compiler warnings if some type instances were - possibly accidentally - omitted. In the following, we always discuss the general toplevel form first and then cover the additional constraints placed on associated types.<br />
<br />
=== Family declarations ===<br />
<br />
Indexed data families are introduced by a signature, such as <br />
<haskell><br />
data family GMap k :: * -> *<br />
</haskell><br />
The special <hask>family</hask> distinguishes family from standard data declarations. The result kind annotation is optional and, as usual, defaults to <hask>*</hask> if omitted. An example is<br />
<haskell><br />
data family Array e<br />
</haskell><br />
Named arguments can also be given explicit kind signatures if needed. Just as with [http://www.haskell.org/ghc/docs/latest/html/users_guide/gadt.html GADT declarations] named arguments are entirely optional, so that we can declare <hask>Array</hask> alternatively with<br />
<haskell><br />
data family Array :: * -> *<br />
</haskell><br />
<br />
==== Associated family declarations ====<br />
<br />
When a data family is declared as part of a type class, we drop the <hask>family</hask> keyword. The <hask>GMap</hask> declaration takes the following form<br />
<haskell><br />
class GMapKey k where<br />
data GMap k :: * -> *<br />
...<br />
</haskell><br />
In contrast to toplevel declarations, named arguments must be used for all type parameters that are to be used as type-indices. Moreover, the argument names must be class parameters. Each class parameter may only be used at most once per associated type, but some may be omitted and they may be in an order other than in the class head. In other words: '''the named type parameters of the data declaration must be a permutation of a subset of the class variables'''. <br />
<br />
Example is admissible:<br />
<haskell><br />
class C a b c where { data T c a :: * } -- OK<br />
class C a b c where { data T a a :: * } -- Bad: repeated variable<br />
class D a where { data T a x :: * } -- Bad: x is not a class variable<br />
class D a where { data T a :: * -> * } -- OK<br />
</haskell><br />
<br />
=== Instance declarations ===<br />
<br />
Instance declarations of data and newtype families are very similar to standard data and newtype declarations. The only two differences are that the keyword <hask>data</hask> or <hask>newtype</hask> is followed by <hask>instance</hask> and that some or all of the type arguments can be non-variable types, but may not contain forall types or type synonym families. However, data families are generally allowed in type parameters, and type synonyms are allowed as long as they are fully applied and expand to a type that is itself admissible - exactly as this is required for occurrences of type synonyms in class instance parameters. For example, the <hask>Either</hask> instance for <hask>GMap</hask> is<br />
<haskell><br />
data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)<br />
</haskell><br />
In this example, the declaration has only one variant. In general, it can be any number.<br />
<br />
Data and newtype instance declarations are only legit when an appropriate family declaration is in scope - just like class instances require the class declaration to be visible. Moreover, each instance declaration has to conform to the kind determined by its family declaration. This implies that the number of parameters of an instance declaration matches the arity determined by the kind of the family. Although all data families are declared with the <hask>data</hask> keyword, instances can be either <hask>data</hask> or <hask>newtype</hask>s, or a mix of both.<br />
<br />
Even if type families are defined as toplevel declarations, functions that perform different computations for different family instances still need to be defined as methods of type classes. In particular, the following is not possible:<br />
<haskell><br />
data family T a<br />
data instance T Int = A<br />
data instance T Char = B<br />
nonsense :: T a -> Int<br />
nonsense A = 1 -- WRONG: These two equations together...<br />
nonsense B = 2 -- ...will produce a type error.<br />
</haskell><br />
Given the functionality provided by GADTs (Generalised Algebraic Data Types), it might seem as if a definition, such as the above, should be feasible. However, type families - in contrast to GADTs - are ''open''; i.e., new instances can always be added, possibly in other modules. Supporting pattern matching across different data instances would require a form of extensible case construct.<br />
<br />
==== Associated type instances ====<br />
<br />
When an associated family instance is declared within a type class instance, we drop the <hask>instance</hask> keyword in the family instance. So, the <hask>Either</hask> instance for <hask>GMap</hask> becomes:<br />
<haskell><br />
instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where<br />
data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v<br />
...<br />
</haskell><br />
The most important point about associated family instances is that the type indices corresponding to class parameters must be identical to the type given in the instance head; here this is the first argument of <hask>GMap</hask>, namely <hask>Either a b</hask>, which coincides with the only class parameter. Any parameters to the family constructor that do not correspond to class parameters, need to be variables in every instance; here this is the variable <hask>v</hask>.<br />
<br />
Instances for an associated family can only appear as part of instance declarations of the class in which the family was declared - just as with the equations of the methods of a class. Also in correspondence to how methods are handled, declarations of associated types can be omitted in class instances. If an associated family instance is omitted, the corresponding instance type is not inhabited; i.e., only diverging expressions, such as <hask>undefined</hask>, can assume the type.<br />
<br />
==== Scoping of class parameters ====<br />
<br />
In the case of multi-parameter type classes, the visibility of class parameters in the right-hand side of associated family instances depends ''solely'' on the parameters of the data family. As an example, consider the simple class declaration<br />
<haskell><br />
class C a b where<br />
data T a<br />
</haskell><br />
Only one of the two class parameters is a parameter to the data family. Hence, the following instance declaration is invalid:<br />
<haskell><br />
instance C [c] d where<br />
data T [c] = MkT (c, d) -- WRONG!! 'd' is not in scope<br />
</haskell><br />
Here, the right-hand side of the data instance mentions the type variable <hask>d</hask> that does not occur in its left-hand side. We cannot admit such data instances as they would compromise type safety.<br />
<br />
==== Type class instances of family instances ====<br />
<br />
Type class instances of instances of data families can be defined as usual, and in particular data instance declarations can have <hask>deriving</hask> clauses. For example, we can write<br />
<haskell><br />
data GMap () v = GMapUnit (Maybe v)<br />
deriving Show<br />
</haskell><br />
which implicitly defines an instance of the form<br />
<haskell><br />
instance Show v => Show (GMap () v) where ...<br />
</haskell><br />
<br />
Note that class instances are always for particular ''instances'' of a data family and never for an entire family as a whole. This is for essentially the same reasons that we cannot define a toplevel function that performs pattern matching on the data constructors of ''different'' instances of a single type family. It would require a form of extensible case construct.<br />
<br />
==== Overlap ====<br />
<br />
The instance declarations of a data family used in a single program may not overlap at all, independent of whether they are associated or not. In contrast to type class instances, this is not only a matter of consistency, but one of type safety.<br />
<br />
=== Import and export ===<br />
<br />
The association of data constructors with type families is more dynamic than that is the case with standard data and newtype declarations. In the standard case, the notation <hask>T(..)</hask> in an import or export list denotes the type constructor and all the data constructors introduced in its declaration. However, a family declaration never introduces any data constructors; instead, data constructors are introduced by family instances. As a result, which data constructors are associated with a type family depends on the currently visible instance declarations for that family. Consequently, an import or export item of the form <hask>T(..)</hask> denotes the family constructor and all currently visible data constructors - in the case of an export item, these may be either imported or defined in the current module. The treatment of import and export items that explicitly list data constructors, such as <hask>GMap(GMapEither)</hask>, is analogous.<br />
<br />
==== Associated families ====<br />
<br />
As expected, an import or export item of the form <hask>C(..)</hask> denotes all of the class' methods and associated types. However, when associated types are explicitly listed as subitems of a class, we need some new syntax, as uppercase identifiers as subitems are usually data constructors, not type constructors. To clarify that we denote types here, each associated type name needs to be prefixed by the keyword <hask>type</hask>. So for example, when explicitly listing the components of the <hask>GMapKey</hask> class, we write <hask>GMapKey(type GMap, empty, lookup, insert)</hask>.<br />
<br />
==== Examples ====<br />
<br />
Assuming our running <hask>GMapKey</hask> class example, let us look at some export lists and their meaning:<br />
<br />
* <hask>module GMap (GMapKey) where...</hask>: Exports just the class name.<br />
* <hask>module GMap (GMapKey(..)) where...</hask>: Exports the class, the associated type <hask>GMap</hask> and the member functions <hask>empty</hask>, <hask>lookup</hask>, and <hask>insert</hask>. None of the data constructors is exported.<br />
* <hask>module GMap (GMapKey(..), GMap(..)) where...</hask>: As before, but also exports all the data constructors <hask>GMapInt</hask>, <hask>GMapChar</hask>, <hask>GMapUnit</hask>, <hask>GMapPair</hask>, and <hask>GMapEither</hask>.<br />
* <hask>module GMap (GMapKey(empty, lookup, insert), GMap(..)) where...</hask>: As before.<br />
* <hask>module GMap (GMapKey, empty, lookup, insert, GMap(..)) where...</hask>: As before.<br />
<br />
Finally, you can write <hask>GMapKey(type GMap)</hask> to denote both the class <hask>GMapKey</hask> as well as its associated type <hask>GMap</hask>. However, you cannot write <hask>GMapKey(type GMap(..))</hask> &mdash; i.e., sub-component specifications cannot be nested. To specify <hask>GMap</hask>'s data constructors, you have to list it separately.<br />
<br />
==== Instances ====<br />
<br />
Family instances are implicitly exported, just like class instances. However, this applies only to the heads of instances, not to the data constructors an instance defines.<br />
<br />
== An associated type synonym example ==<br />
<br />
Type synonym families are an alternative to functional dependencies, which makes functional dependency examples well suited to introduce type synonym families. In fact, type families are a more functional way to express the same as functional dependencies (despite the name!), as they replace the relational notation of functional dependencies by an expression-oriented notation; i.e., functions on types are really represented by functions and not relations.<br />
<br />
=== The <hask>class</hask> declaration ===<br />
<br />
Here's an example from Mark Jones' seminal paper on functional dependencies:<br />
<haskell><br />
class Collects e ce | ce -> e where<br />
empty :: ce<br />
insert :: e -> ce -> ce<br />
member :: e -> ce -> Bool<br />
toList :: ce -> [e]<br />
</haskell><br />
<br />
With associated type synonyms we can write this as<br />
<haskell><br />
class Collects ce where<br />
type Elem ce<br />
empty :: ce<br />
insert :: Elem ce -> ce -> ce<br />
member :: Elem ce -> ce -> Bool<br />
toList :: ce -> [Elem ce]<br />
</haskell><br />
Instead of the multi-parameter type class, we use a single parameter class, and the parameter <hask>e</hask><br />
turned into an associated type synonym <hask>Elem ce</hask>.<br />
<br />
=== An <hask>instance</hask>===<br />
<br />
Instances change correspondingly. An instance of the two-parameter class<br />
<haskell><br />
instance Eq e => Collects e [e] where<br />
empty = []<br />
insert e l = (e:l)<br />
member e [] = False<br />
member e (x:xs) <br />
| e == x = True<br />
| otherwise = member e xs<br />
toList l = l<br />
</haskell><br />
becomes an instance of a single-parameter class, where the dependent type parameter turns into an associated type instance declaration:<br />
<haskell><br />
instance Eq e => Collects [e] where<br />
type Elem [e] = e<br />
empty = []<br />
insert e l = (e:l)<br />
member e [] = False<br />
member e (x:xs) <br />
| e == x = True<br />
| otherwise = member e xs<br />
toList l = l<br />
</haskell><br />
<br />
=== Using generic collections ===<br />
<br />
With Functional Dependencies the code would be:<br />
<haskell><br />
sumCollects :: (Collects e c1, Collects e c2) => c1 -> c2 -> c2<br />
sumCollects c1 c2 = foldr insert c2 (toList c1)<br />
</haskell><br />
<br />
In contrast, with associated type synonyms, we get:<br />
<haskell><br />
sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2<br />
sumCollects c1 c2 = foldr insert c2 (toList c1)<br />
</haskell><br />
<br />
== Detailed definition of type synonym families ==<br />
<br />
Type families appear in two flavours: (1) they can be defined on the toplevel or (2) they can appear inside type classes (in which case they are known as associated type synonyms). The former is the more general variant, as it lacks the requirement for the type-indices to coincide with the class parameters. However, the latter can lead to more clearly structured code and compiler warnings if some type instances were - possibly accidentally - omitted. In the following, we always discuss the general toplevel form first and then cover the additional constraints placed on associated types.<br />
<br />
=== Family declarations ===<br />
<br />
Indexed type families are introduced by a signature, such as <br />
<haskell><br />
type family Elem c :: *<br />
</haskell><br />
The special <hask>family</hask> distinguishes family from standard type declarations. The result kind annotation is optional and, as usual, defaults to <hask>*</hask> if omitted. An example is<br />
<haskell><br />
type family Elem c<br />
</haskell><br />
Parameters can also be given explicit kind signatures if needed. We call the number of parameters in a type family declaration, the family's arity, and all applications of a type family must be fully saturated w.r.t. to that arity. This requirement is unlike ordinary type synonyms and it implies that the kind of a type family is not sufficient to determine a family's arity, and hence in general, also insufficient to determine whether a type family application is well formed. As an example, consider the following declaration:<br />
<haskell><br />
type family F a b :: * -> * -- F's arity is 2, <br />
-- although it's overall kind is * -> * -> * -> *<br />
</haskell><br />
Given this declaration the following are examples of well-formed and malformed types:<br />
<haskell><br />
F Char [Int] -- OK! Kind: * -> *<br />
F Char [Int] Bool -- OK! Kind: *<br />
F IO Bool -- WRONG: kind mismatch in the first argument<br />
F Bool -- WRONG: unsaturated application<br />
</haskell><br />
<br />
==== Associated family declarations ====<br />
<br />
When a type family is declared as part of a type class, we drop the <hask>family</hask> special. The <hask>Elem</hask> declaration takes the following form<br />
<haskell><br />
class Collects ce where<br />
type Elem ce :: *<br />
...<br />
</haskell><br />
Exactly as in the case of an associated data declaration, '''the named type parameters must be a permutation of a subset of the class parameters'''. Examples<br />
<haskell><br />
class C a b c where { type T c a :: * } -- OK<br />
class D a where { type T a x :: * } -- No: x is not a class parameter<br />
class D a where { type T a :: * -> * } -- OK<br />
</haskell><br />
<br />
=== Instance declarations ===<br />
<br />
Instance declarations of type families are very similar to standard type synonym declarations. The only two differences are that the keyword <hask>type</hask> is followed by <hask>instance</hask> and that some or all of the type arguments can be non-variable types, but may not contain forall types or type synonym families. However, data families are generally allowed, and type synonyms are allowed as long as they are fully applied and expand to a type that is admissible - these are the exact same requirements as for data instances. For example, the <hask>[e]</hask> instance for <hask>Elem</hask> is<br />
<haskell><br />
type instance Elem [e] = e<br />
</haskell><br />
<br />
A type family instance declaration must satisfy the following rules:<br />
* An appropriate family declaration is in scope - just like class instances require the class declaration to be visible. <br />
* The instance declaration conforms to the kind determined by its family declaration<br />
* The number of type parameters in an instance declaration matches the number of type parameters in the family declaration.<br />
* The right-hand side of a type instance must be a monotype (i.e., it may not include foralls) and after the expansion of all saturated vanilla type synonyms, no synonyms, except family synonyms may remain.<br />
<br />
Here are some examples of admissible and illegal type instances:<br />
<haskell><br />
type family F a :: *<br />
type instance F [Int] = Int -- OK!<br />
type instance F String = Char -- OK!<br />
type instance F (F a) = a -- WRONG: type parameter mentions a type family<br />
type instance F (forall a. (a, b)) = b -- WRONG: a forall type appears in a type parameter<br />
type instance F Float = forall a.a -- WRONG: right-hand side may not be a forall type<br />
<br />
type family G a b :: * -> *<br />
type instance G Int = (,) -- WRONG: must be two type parameters<br />
type instance G Int Char Float = Double -- WRONG: must be two type parameters<br />
</haskell><br />
<br />
==== Associated type instances ====<br />
<br />
When an associated family instance is declared within a type class instance, we drop the <hask>instance</hask> keyword in the family instance. So, the <hask>[e]</hask> instance for <hask>Elem</hask> becomes:<br />
<haskell><br />
instance (Eq (Elem [e])) => Collects ([e]) where<br />
type Elem [e] = e<br />
...<br />
</haskell><br />
The most important point about associated family instances is that the type indexes corresponding to class parameters must be identical to the type given in the instance head; here this is <hask>[e]</hask>, which coincides with the only class parameter.<br />
<br />
Instances for an associated family can only appear as part of instance declarations of the class in which the family was declared - just as with the equations of the methods of a class. Also in correspondence to how methods are handled, declarations of associated types can be omitted in class instances. If an associated family instance is omitted, the corresponding instance type is not inhabited; i.e., only diverging expressions, such as <hask>undefined</hask>, can assume the type.<br />
<br />
==== Overlap ====<br />
<br />
The instance declarations of a type family used in a single program may only overlap if the right-hand sides of the overlapping instances coincide for the overlapping types. More formally, two instance declarations overlap if there is a substitution that makes the left-hand sides of the instances syntactically the same. Whenever that is the case, the right-hand sides of the instances must also be syntactically equal under the same substitution. This condition is independent of whether the type family is associated or not, and it is not only a matter of consistency, but one of type safety.<br />
<br />
Here are two examples to illustrate the condition under which overlap is permitted.<br />
<haskell><br />
type instance F (a, Int) = [a]<br />
type instance F (Int, b) = [b] -- overlap permitted<br />
<br />
type instance G (a, Int) = [a]<br />
type instance G (Char, a) = [a] -- ILLEGAL overlap, as [Char] /= [Int]<br />
</haskell><br />
<br />
==== Decidability ====<br />
<br />
In order to guarantee that type inference in the presence of type families is decidable, we need to place a number of additional restrictions on the formation of type instance declarations (c.f., Definition 5 (Relaxed Conditions) of [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html Type Checking with Open Type Functions]). Instance declarations have the general form<br />
<haskell><br />
type instance F t1 .. tn = t<br />
</haskell><br />
where we require that for every type family application <hask>(G s1 .. sm)</hask> in <hask>t</hask>, <br />
# <hask>s1 .. sm</hask> do not contain any type family constructors,<br />
# the total number of symbols (data type constructors and type variables) in <hask>s1 .. sm</hask> is strictly smaller than in <hask>t1 .. tn</hask>, and<br />
# for every type variable <hask>a</hask>, <hask>a</hask> occurs in <hask>s1 .. sm</hask> at most as often as in <hask>t1 .. tn</hask>.<br />
These restrictions are easily verified and ensure termination of type inference. However, they are not sufficient to guarantee completeness of type inference in the presence of, so called, ''loopy equalities'', such as <hask>a ~ [F a]</hask>, where a recursive occurrence of a type variable is underneath a family application and data constructor application - see the above mentioned paper for details. <br />
<br />
If the option <tt>-XUndecidableInstances</tt> is passed to the compiler, the above restrictions are not enforced and it is on the programmer to ensure termination of the normalisation of type families during type inference.<br />
<br />
=== Equality constraints ===<br />
<br />
Type context can include equality constraints of the form <hask>t1 ~ t2</hask>, which denote that the types <hask>t1</hask> and <hask>t2</hask> need to be the same. In the presence of type families, whether two types are equal cannot generally be decided locally. Hence, the contexts of function signatures may include equality constraints, as in the following example:<br />
<haskell><br />
sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2<br />
</haskell><br />
where we require that the element type of <hask>c1</hask> and <hask>c2</hask> are the same. In general, the types <hask>t1</hask> and <hask>t2</hask> of an equality constraint may be arbitrary monotypes; i.e., they may not contain any quantifiers, independent of whether higher-rank types are otherwise enabled.<br />
<br />
Equality constraints can also appear in class and instance contexts. The former enable a simple translation of programs using functional dependencies into programs using family synonyms instead. The general idea is to rewrite a class declaration of the form<br />
<haskell><br />
class C a b | a -> b<br />
</haskell><br />
to<br />
<haskell><br />
class (F a ~ b) => C a b where<br />
type F a<br />
</haskell><br />
That is, we represent every functional dependency (FD) <hask>a1 .. an -> b</hask> by an FD type family <hask>F a1 .. an</hask> and a superclass context equality <hask>F a1 .. an ~ b</hask>, essentially giving a name to the functional dependency. In class instances, we define the type instances of FD families in accordance with the class head. Method signatures are not affected by that process.<br />
<br />
NB: Equalities in superclass contexts are not fully implemented in the GHC 6.10 branch.<br />
<br />
== Frequently asked questions ==<br />
<br />
=== Injectivity, type inference, and ambiguity ===<br />
<br />
A common problem is this<br />
<haskell><br />
type family F a<br />
<br />
f :: F a -> F a<br />
f = undefined<br />
<br />
g :: F Int -> F Int<br />
g x = f x<br />
</haskell><br />
The compiler complains about the definition of <tt>g</tt> saying<br />
<haskell><br />
Couldn't match expected type `F Int' against inferred type `F a1'<br />
</haskell><br />
In type-checking <tt>g</tt>'s right hand side GHC discovers (by instantiating f's type with a fresh type variable) that it has type <tt>F a1 -> F a1</tt> for some as-yet-unknown type <tt>a1</tt>. Now it tries to make the inferred type match <tt>g</tt>'s type signature. Well, you say, just make <haskell>a1</haskell> equal to <tt>Int</tt> and you are done. True, but what if there were these instance<br />
<haskell><br />
type instance F Int = Bool<br />
type instance F Char = Bool<br />
</haskell><br />
Then making <tt>a1</tt> equal to <tt>Char</tt> would ''also'' make the two types equal. Because there is more than one choice, the program is rejected.<br />
<br />
The difficulty is that the type function <tt>F</tt> need not be ''injective''; it can map two distinct types to the same type. For an injective type constructor like <tt>Maybe</tt>, if we know that <tt>Maybe t1</tt> = <tt>Maybe t2</tt>, then we know that <tt>t1</tt> = <tt>t2</tt>. But not so for non-injective type functions.<br />
<br />
The problem starts with <tt>f</tt>. Its type is ''ambiguous''; even if I know the argument and result types for <tt>f</tt>, I cannot use that to find the type at which <tt>a</tt> should be instantiated. (So arguably, <tt>f</tt> should be rejected as having an ambiguous type, and probably will be in future.) The situation is well known in type classes: <br />
<haskell><br />
bad :: (Read a, Show a) => String -> String<br />
bad x = show (read x)<br />
</haskell><br />
At a call of <tt>bad</tt> one cannot tell at what type <tt>a</tt> should be instantiated.<br />
<br />
The only solution is to avoid ambiguous types. In the type signature of a function, <br />
* Ensure that every type variable occurs in the part after the "<tt>=></tt>"<br />
* Ensure that every type variable appears at least once outside a type function call. <br />
<br />
Even then ambiguity is possible. For example:<br />
<haskell><br />
f :: F a -> [a] <br />
f = undefined<br />
<br />
g :: F b -> Int<br />
g x = length (f x)<br />
</haskell><br />
Although <tt>f</tt>'s type is unambiguous, its result type is swallowed up by <tt>length</tt>, which now makes <tt>g</tt>'s type ambiguous.<br />
<br />
== References ==<br />
<br />
* [http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html Associated Types with Class.] Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. In ''Proceedings of The 32nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'05)'', pages 1-13, ACM Press, 2005.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/CKP05.html Associated Type Synonyms.] Manuel M. T. Chakravarty, Gabriele Keller, and Simon Peyton Jones. In ''Proceedings of The Tenth ACM SIGPLAN International Conference on Functional Programming'', ACM Press, pages 241-253, 2005.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/SCPD07.html System F with Type Equality Coercions.] Martin Sulzmann, Manuel M. T. Chakravarty, Simon Peyton Jones, and Kevin Donnelly. In ''Proceedings of The Third ACM SIGPLAN Workshop on Types in Language Design and Implementation'', ACM Press, 2007.<br />
* [http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html Type Checking With Open Type Functions.] Tom Schrijvers, Simon Peyton-Jones, Manuel M. T. Chakravarty, Martin Sulzmann. In ''Proceedings of The 13th ACM SIGPLAN International Conference on Functional Programming'', ACM Press, pages 51-62, 2008.<br />
<br />
[[Category:Type-level programming]]<br />
[[Category:Language extension]]</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=TypeDirectedNameResolution&diff=31628TypeDirectedNameResolution2009-11-17T21:06:00Z<p>Daniel.is.fischer: </p>
<hr />
<div>= Type directed name resolution =<br />
<br />
This publicly editable page is a place to summarise comments on the Haskell Prime proposal for Type Directed Name Resolution (TDNR).<br />
<br />
* The [http://hackage.haskell.org/trac/haskell-prime/wiki/TypeDirectedNameResolution TDNR proposal]<br />
<br />
= Straw poll =<br />
<br />
It's hard to gauge how much people like proposals like this, so let's try the experiment of collecting votes here:<br />
<br />
Names of people who would positively like to see TDNR happen (say briefly why)<br />
* Simon PJ (I wrote the proposal)<br />
* Daniel Fischer (I think it would be an improvement to the language. I have not much missed it yet, so I don't feel strongly about it, though.)<br />
<br />
Names of people who think that on balance it's a bad idea<br />
* '''fill in here'''<br />
<br />
= Other comments =<br />
<br />
* A lot of people have commented that using <hask>.</hask> for this as well as composition and qualification is going to start getting confusing. One alternative suggestion was <hask>-></hask> but this would conflict with case branches and lambda syntax. Similar things like <hask>~></hask> or <hask>--></hask> could work too, but look a little uglier.<br />
<br />
However, I think a little ugly is preferable to confusing or conflicting with syntax. I ''think'' using '.' won't be too confusing (we all separate the composition operator from the functions by a space anyway, don't we?), so I'd go with that. But rater than letting it die over '.'-ambiguity, I'd choose a different notation (would <hask>a#f</hask> be an option?).[[User:Daniel.is.fischer|Daniel.is.fischer]] 21:06, 17 November 2009 (UTC)</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Questions_and_answers&diff=30326Questions and answers2009-09-28T23:57:31Z<p>Daniel.is.fischer: Add beginners list to first answer</p>
<hr />
<div>Feel free to ask your questions here. Please sign your question using four tildes (<nowiki>~~~~</nowiki>). Questions and answers will be organised as they are added, and linked from here. We don't have much here yet, but [http://www.haskell.org/hawiki/HaskellNewbie the Haskell Newbie page] on the old wiki has quite a few questions and answers you can look through.<br />
<br />
[[Category:Community]]<br />
[[Category:FAQ]]<br />
<br />
== Questions and answers ==<br />
<br />
;Q. What are the best place to ask beginner questions?<br />
:A. The [http://www.haskell.org/pipermail/beginners/ beginners] mailing list, the [http://haskell.org/pipermail/haskell-cafe/ haskell-cafe] mailing list, or the [http://haskell.org/haskellwiki/IRC_channel #haskell irc channel].<br />
<br />
;Q. Symbols are valid in Haskell function names. What are the rules for which characters can be used?<br />
:A. Refer to the [[Language and library specification]] under [http://haskell.org/onlinereport/lexemes.html#ids "Identifiers and Operators"]. Variable identifiers start with a lowercase letter, constructor identifiers with an uppercase letter and both can contain underscores, single quotes, letters and digits. Operators are formed from one or more of '<hask>!#$%&*+./<=>?@\^|-~</hask>'. Constructors can be operator names, so long as they start with a '<hask>:</hask>' (e.g., <hask>:+</hask> for <hask>Data.Complex</hask>). Lacking fixity declarations, the default [http://haskell.org/onlinereport/decls.html#sect4.4.2 fixity] is left associative and most tightly binding (9).<br />
<br />
;Q. Are fixity declarations required for functions defined with symbol names?<br />
:A. No.<br />
<br />
;Q. GHC does a wide variety of optimisations. How can I view the optimisaitons that are performed?<br />
:A. Keep around the [http://www.haskell.org/ghc/docs/latest/html/users_guide/separate-compilation.html#keeping-intermediates intermediate compiler outputs] using --keep-tmp-files or -ddump-simpl.<br />
<br />
;Q. Can I use multiple CPUs with a Haskell program?<br />
:A. Yes, GHC 6.6 supports symmetric multicore processing. see [[GHC/Concurrency#Multiprocessor GHC]]<br />
<br />
;Q. I just wrote this really cool program! Who can I show it to?<br />
<br />
;Q. I just wrote this interesting program that someone else might find useful. Where can I put it?<br />
:A. Provided you are ok with the [[HaskellWiki:Copyrights | simple permissive license]], you can put it here on the wiki. To do that, you must first [[Special:Userlogin |create a login]]. Once that is done, start a page for your project. (People often add a link to their projects from their wiki home page.) Before starting the page, check out the [[HaskellWiki:Guidelines | guidelines for pages]]. If you need it, there is also [[Help:Editing | help on editing wiki pages]]. Finally, don't forget to categorize your new page.<br />
<br />
;Q. I have a simple function; it behaves like <hask>map</hask>, but also threads state through the computation. Is there a standard library function that does the same thing?<br />
:A. Yes. <hask>mapAccumL</hask>. You could also use a state monad.<br />
<br />
== Uncategorised questions ==<br />
<br />
* Which is faster? <hask>putStr (xs ++ ys ++ xs)</hask> or <hask>putStr xs; putStr ys; putStr zs</hask>? How much of a difference does it make? [[User:MathematicalOrchid|MathematicalOrchid]] 11:47, 22 January 2007 (UTC)<br />
** hmm, <hask>(++)</hask> is a very slow operation which is O(n) in the length of the first string. for short strings the difference should be small, for very long string you'll see a big difference. concrete timing depends on putStr... --[[User:JohannesAhlmann|Johannes Ahlmann]] 12:29, 22 January 2007 (UTC)<br />
*** <hask>(++)</hask> is right-associative when there's several, resulting in the fastest possible performance. (I understand this is why the <hask>Show</hask> class is so damn weird...) Even so, I wonder if it's more efficient to join strings or use real I/O... [[User:MathematicalOrchid|MathematicalOrchid]] 13:23, 22 January 2007 (UTC)<br />
<br />
* I want to write a program that renders bitmap graphics. Is there ''any'' way to get this onto the video screen in Haskell? Is there any way to get the data saved to disk in some sane file format? [[User:MathematicalOrchid|MathematicalOrchid]] 11:47, 22 January 2007 (UTC)<br />
** have a look at [[Libraries and tools/GUI libraries]]. i'd have a look at [http://haskell.org/graphics/ HGL], [http://haskell.org/HOpenGL/ HOpenGL] and/or [http://haskell.org/gtk2hs/ gtk2hs]. of these, at least gtk2hs has some image handling routines. for pure image format libraries there's unfortunately a little less :(<br />
*** This is where it starts to get messy... I already tried using HGL from within Hugs. (Drawing 'pixels' that are really small squares.) However, once it's drawn enough pixels, I get a Dr Watson error and Hugs ungracefully terminates. (Actually, the latest version of Hugs seems to do this a lot.) So I went to compile it with GHC - and it seems GHC doesn't come with that library at all. And the page you linked says that HGL is 'currently broken on Win32'. Hmm... OK, I'm confused now. Then there's HOpenGL. (Is that the same thing as Graphics.Rendering.OpenGL, or is it seperate?) It's nice to know you can have hardware 3D acceleration if you want it, but maybe a tad overkill for just writing a bitmap to the display. Also, IIRC, doesn't OpenGL require you to open a window in a platform-specific way first? And then there's gtk2hs. I don't know if you can run Gtk on Win32... but that one looks like it might be worth investigating. [[User:MathematicalOrchid|MathematicalOrchid]] 15:52, 22 January 2007 (UTC)<br />
*** Ah-hah! It seems that burried away in gtk2hs is a fair of functions to load and save PNG images. That will do nicely... if I can figure out how to use it. :-) [[User:MathematicalOrchid|MathematicalOrchid]] 16:08, 22 January 2007 (UTC)<br />
**** I spoke too soon... I was looking at the cairo part. Apparently the main Gtk2hs part supports JPEG and others too. And it provides functions which look like you can plot pixels with them. Now, if I can figure out how to install this stuff... [[User:MathematicalOrchid|MathematicalOrchid]] 22:10, 22 January 2007 (UTC)</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Hoogle/Packages&diff=26685Hoogle/Packages2009-02-26T13:39:56Z<p>Daniel.is.fischer: </p>
<hr />
<div>This page is meant to get possible ideas for answers to the following questions:<br />
<br />
The three problems are:<br />
<br />
1) What packages should Hoogle search by default? All of hackage? The base libraries? Only the packages a user has installed? Only packages that make it in to the Haskell Platform?<br />
<br />
2) What groups of packages should Hoogle have available? Each package individually? All packages which compile on Windows? All packages by a certain author? All packages whose minor version number is even?<br />
<br />
3) What UI should Hoogle show? Should there be checkboxes for each os's package? Should there be a checkbox for each compiler/version? Should there be no UI but some documentation?<br />
<br />
And the trade offs are:<br />
<br />
1) The packages have to be divided under sensible and clear lines - I don't want to (and shouldn't) arbitrate divisions like "good" or "popular".<br />
<br />
2) The more packages you search, the less relevant the results will be.<br />
<br />
3) The fewer packages you search, the more chance that you miss something.<br />
<br />
4) The more UI that is added the more confusing things get.<br />
<br />
5) My development time for Hoogle derives Bounded, Finite and increasingly also derives Small.<br />
<br />
Thoughts and suggestions welcome. Please write all thoughts on this page, don't remove other peoples thoughts, and do try and edit them to form a consensus if possible. Signed comments are preferred, unlike the rest of the Haskell wiki this is intended to be a debate where people own comments, rather than a polished document.<br />
<br />
----<br />
<br />
My personal opinions are very much in flux, but my current views are: 1) the base libraries are a minimum, all of hackage is a maximum, I can't decide at all. 2) Lots of groupings seem good, the more the merrier. 3) UI is precious, should be minimal - OS/compiler/version at the most. --[[User:NeilMitchell|Neil Mitchell]] 20:51, 22 February 2009 (UTC)<br />
<br />
As expressed on -cafe, I support a default of all of the [[Haskell Platform]] being searched with a +hackage flag for all of hackage. To divide up the platforms I would be happy with +windows, +[li|u]nix, +osx being used to enable display of platform specific results. --[[User:Tom|Thomas DuBuisson]]<br />
<br />
:I second Thomas - not searching anything on Hackage is a bit too limited, I think, but we don't want to search all of Hackage since there's no guarantee it'll be usable by the searcher or even installable. Then a tri-partite platform division makes sense. (Mac libraries can differ much more from Unix/Linux than Linux packages would differ from *BSD.) --[[User:Gwern|Gwern]] 18:41, 25 February 2009 (UTC)<br />
<br />
I think that the best default for searchable set is "everything that we can stuff it into". However, default way of ordering items should be based on "relevance" to the topic: base and other standard packages comes first, then Haskell Platform ones, then the rest of the crew. If the user want more specyfic results, provide him "Advanced Search" page very like the Google's one, with switches to turn things on and off. This should deal with avoiding UI cluttering. Last but not least, the following flags could be helpful for quick search specyfications: windows, linux, osx, hackage, package:NameOfPackage, with ability to turn on and off. -- [[User:Krzysztof Skrzętnicki|Christopher Skrzętnicki]]<br />
<br />
I support a default search space of [[Haskell Platform]], too. And the +hackage flag plus the +myOS flags (as checkboxes on the UI?). If time permits it, flags for including or excluding specific packages would be nice. [[User:Daniel.is.fischer|Daniel.is.fischer]] 13:39, 26 February 2009 (UTC)</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Foldr_Foldl_Foldl%27&diff=25580Foldr Foldl Foldl'2009-01-08T19:28:00Z<p>Daniel.is.fischer: Added an example</p>
<hr />
<div>To ''foldr'', ''foldl'' or ''foldl''' that's the question! This article demonstrates the differences between these different folds by a simple example.<br />
<br />
If you want you can copy/paste this article into your [http://haskell.org/haskellwiki/Haskell_mode_for_Emacs favorite editor] and run it.<br />
<br />
We are going to define our own folds so we hide the ones from the Prelude:<br />
<br />
<haskell>> import Prelude hiding (foldr, foldl)</haskell><br />
<br />
Say we want to calculate the sum of a very big list:<br />
<br />
<haskell>> veryBigList = [1..1000000]</haskell><br />
<br />
Lets start with the following:<br />
<br />
<haskell><br />
> foldr f z [] = z<br />
> foldr f z (x:xs) = x `f` foldr f z xs<br />
<br />
> sum1 = foldr (+) 0<br />
<br />
> try1 = sum1 veryBigList<br />
</haskell><br />
<br />
If we evaluate ''try1'' we get:<br />
<br />
<tt><nowiki>*** Exception: stack overflow</nowiki></tt><br />
<br />
Too bad... So what happened:<br />
<haskell><br />
try1 --><br />
foldr (+) 0 [1..1000000] --><br />
1 + (foldr (+) 0 [2..1000000]) --><br />
1 + (2 + (foldr (+) 0 [3..1000000])) --><br />
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) --><br />
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) --><br />
-- ...<br />
-- ... My stack overflows when there's a chain of around 500000 (+)'s !!!<br />
-- ... But the following would happen if you got a large enough stack:<br />
-- ...<br />
1 + (2 + (3 + (4 + (... + (999999 + (foldr (+) 0 [1000000]))...)))) --><br />
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + ((foldr (+) 0 []))))...)))) --><br />
<br />
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...)))) --><br />
1 + (2 + (3 + (4 + (... + (999999 + 1000000)...)))) --><br />
1 + (2 + (3 + (4 + (... + 1999999 ...)))) --><br />
<br />
1 + (2 + (3 + (4 + 500000499990))) --><br />
1 + (2 + (3 + 500000499994)) --><br />
1 + (2 + 500000499997) --><br />
1 + 500000499999 --><br />
500000500000<br />
</haskell><br />
<br />
The problem, as you can see, is that a large chain of (+)'s is<br />
created which eventually won't fit in your stack anymore. This will<br />
then trigger a stack overflow exception.<br />
<br />
For a nice interactive animation of the above behaviour see: http://foldr.com<br />
<br />
Lets think about how to solve it... <br />
<br />
One problem with the chain of (+)'s is that we can't make it<br />
smaller (reduce it) until at the very last moment when it's already<br />
too late.<br />
<br />
The reason we can't reduce it, is that the chain doesn't contain an<br />
expression which can be reduced (a so called "redex" for '''red'''ucible<br />
'''ex'''pression.) If it did we could reduce that expression before going<br />
to the next element.<br />
<br />
Well, we can introduce a redex by forming the chain in another way. If<br />
instead of the chain <tt>1 + (2 + (3 + (...)))</tt> we could form the chain<br />
<tt>(((0 + 1) + 2) + 3) + ...</tt> then there would always be a redex.<br />
<br />
We can form the latter chain by using a function called ''foldl'':<br />
<br />
<haskell><br />
> foldl f z [] = z<br />
> foldl f z (x:xs) = foldl f (z `f` x) xs<br />
<br />
> sum2 = foldl (+) 0<br />
<br />
> try2 = sum2 veryBigList<br />
</haskell><br />
<br />
Lets evaluate ''try2'':<br />
<br />
<tt><nowiki>*** Exception: stack overflow</nowiki></tt><br />
<br />
Good Lord! Again a stack overflow! Lets see what happens:<br />
<br />
<haskell><br />
try2 --><br />
foldl (+) 0 [1..1000000] --><br />
foldl (+) (0 + 1) [2..1000000] --><br />
foldl (+) ((0 + 1) + 2) [3..1000000] --><br />
foldl (+) (((0 + 1) + 2) + 3) [4..1000000] --><br />
foldl (+) ((((0 + 1) + 2) + 3) + 4) [5..1000000] --><br />
-- ...<br />
-- ... My stack overflows when there's a chain of around 500000 (+)'s !!!<br />
-- ... But the following would happen if you got a large enough stack:<br />
-- ...<br />
foldl (+) ((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) [1000000] --><br />
foldl (+) (((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) + 1000000) [] --><br />
<br />
((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) + 1000000 --><br />
(((((1 + 2) + 3) + 4) + ...) + 999999) + 1000000 --><br />
((((3 + 3) + 4) + ...) + 999999) + 1000000 --><br />
(((6 + 4) + ...) + 999999) + 1000000 --><br />
((10 + ...) + 999999) + 1000000 --><br />
<br />
(499998500001 + 999999) + 1000000 --><br />
499999500000 + 1000000<br />
500000500000 --><br />
</haskell><br />
<br />
For a nice interactive animation of the above behaviour see: http://foldl.com (actually this animation is not quite the same :-( )<br />
<br />
Well, you clearly see that the redexen <tt>0 + 1</tt>, <tt>(0 + 1) + 2</tt>,<br />
etc. are created. So why doesn't the chain reduce sooner than<br />
before?<br />
<br />
The answer is that GHC uses a lazy reduction strategy. This means<br />
that GHC only reduces an expression when its value is actually<br />
needed. <br />
<br />
The reduction strategy works by reducing the outer-left-most redex<br />
first. In this case it are the outer <tt>foldl (+) ... [1..10000]</tt><br />
redexen which are repeatedly reduced. <br />
So the inner <tt>(((0 + 1) + 2) + 3) + 4</tt> redexen only get reduced when<br />
the foldl is completely gone.<br />
<br />
We somehow have to tell the system that the inner redex should be<br />
reduced before the outer. Fortunately this is possible with the<br />
''seq'' function:<br />
<br />
<haskell>seq :: a -> b -> b</haskell><br />
<br />
''seq'' is a primitive system function that when applied to ''x'' and<br />
''y'' will first reduce ''x'', then reduce ''y'' and return the result of<br />
the latter. The idea is that ''y'' references ''x'' so that when ''y'' is<br />
reduced ''x'' will not be a big unreduced chain anymore.<br />
<br />
Now lets fill in the pieces:<br />
<br />
<haskell><br />
> foldl' f z [] = z<br />
> foldl' f z (x:xs) = let z' = z `f` x <br />
> in seq z' $ foldl' f z' xs<br />
<br />
> sum3 = foldl' (+) 0<br />
<br />
> try3 = sum3 veryBigList<br />
</haskell><br />
<br />
If we now evaluate ''try3'' we get the correct answer and we get it very quickly:<br />
<br />
<haskell>500000500000</haskell><br />
<br />
Lets see what happens:<br />
<br />
<haskell><br />
try3 --><br />
foldl' (+) 0 [1..1000000] --><br />
foldl' (+) 1 [2..1000000] --><br />
foldl' (+) 3 [3..1000000] --><br />
foldl' (+) 6 [4..1000000] --><br />
foldl' (+) 10 [5..1000000] --><br />
-- ...<br />
-- ... You see that the stack doesn't overflow<br />
-- ...<br />
foldl' (+) 499999500000 [1000000] --><br />
foldl' (+) 500000500000 [] --><br />
500000500000<br />
</haskell><br />
<br />
You can clearly see that the inner redex is repeatedly reduced<br />
first.<br />
<br />
<br />
Usually the choice is between <hask>foldr</hask> and <hask>foldl'</hask>, since <hask>foldl</hask> and <hask>foldl'</hask> are the same except for their strictness properties, so if both return a result, it must be the same. <hask>foldl'</hask> is the more efficient way to arrive at that result because it doesn't build a huge thunk. However, if the combining function is lazy in its ''first'' argument, <hask>foldl</hask> may happily return a result where <hask>foldl'</hask> hits an exception:<br />
<br />
<haskell><br />
> (?) :: Int -> Int -> Int<br />
> _ ? 0 = 0<br />
> x ? y = x*y<br />
><br />
> list :: [Int]<br />
> list = [2,3,undefined,5,0]<br />
> <br />
> okey = foldl (?) 1 list<br />
><br />
> boom = foldl' (?) 1 list<br />
</haskell><br />
<br />
Let's see what happens:<br />
<br />
<haskell><br />
okey --><br />
foldl (?) 1 [2,3,undefined,5,0] --><br />
foldl (?) (1 ? 2) [3,undefined,5,0] --><br />
foldl (?) ((1 ? 2) ? 3) [undefined,5,0] --><br />
foldl (?) (((1 ? 2) ? 3) ? undefined) [5,0] --><br />
foldl (?) ((((1 ? 2) ? 3) ? undefined) ? 5) [0] --><br />
foldl (?) (((((1 ? 2) ? 3) ? undefined) ? 5) ? 0) [] --><br />
((((1 ? 2) ? 3) ? undefined) ? 5) ? 0 --><br />
0<br />
<br />
boom --><br />
foldl' (?) 1 [2,3,undefined,5,0] --><br />
1 ? 2 --> 2<br />
foldl' (?) 2 [3,undefined,5,0] --><br />
2 ? 3 --> 6<br />
foldl' (?) 6 [undefined,5,0] --><br />
6 ? undefined --><br />
<nowiki>*** Exception: Prelude.undefined</nowiki><br />
</haskell><br />
<br />
For another explanation about folds see the [http://haskell.org/haskellwiki/Fold Fold] article.</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Foldr_Foldl_Foldl%27&diff=25579Foldr Foldl Foldl'2009-01-08T18:32:21Z<p>Daniel.is.fischer: Fix a few typos</p>
<hr />
<div>To ''foldr'', ''foldl'' or ''foldl''' that's the question! This article demonstrates the differences between these different folds by a simple example.<br />
<br />
If you want you can copy/paste this article into your [http://haskell.org/haskellwiki/Haskell_mode_for_Emacs favorite editor] and run it.<br />
<br />
We are going to define our own folds so we hide the ones from the Prelude:<br />
<br />
<haskell>> import Prelude hiding (foldr, foldl)</haskell><br />
<br />
Say we want to calculate the sum of a very big list:<br />
<br />
<haskell>> veryBigList = [1..1000000]</haskell><br />
<br />
Lets start with the following:<br />
<br />
<haskell><br />
> foldr f z [] = z<br />
> foldr f z (x:xs) = x `f` foldr f z xs<br />
<br />
> sum1 = foldr (+) 0<br />
<br />
> try1 = sum1 veryBigList<br />
</haskell><br />
<br />
If we evaluate ''try1'' we get:<br />
<br />
<tt><nowiki>*** Exception: stack overflow</nowiki></tt><br />
<br />
Too bad... So what happened:<br />
<haskell><br />
try1 --><br />
foldr (+) 0 [1..1000000] --><br />
1 + (foldr (+) 0 [2..1000000]) --><br />
1 + (2 + (foldr (+) 0 [3..1000000])) --><br />
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) --><br />
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) --><br />
-- ...<br />
-- ... My stack overflows when there's a chain of around 500000 (+)'s !!!<br />
-- ... But the following would happen if you got a large enough stack:<br />
-- ...<br />
1 + (2 + (3 + (4 + (... + (999999 + (foldr (+) 0 [1000000]))...)))) --><br />
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + ((foldr (+) 0 []))))...)))) --><br />
<br />
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...)))) --><br />
1 + (2 + (3 + (4 + (... + (999999 + 1000000)...)))) --><br />
1 + (2 + (3 + (4 + (... + 1999999 ...)))) --><br />
<br />
1 + (2 + (3 + (4 + 500000499990))) --><br />
1 + (2 + (3 + 500000499994)) --><br />
1 + (2 + 500000499997) --><br />
1 + 500000499999 --><br />
500000500000<br />
</haskell><br />
<br />
The problem, as you can see, is that a large chain of (+)'s is<br />
created which eventually won't fit in your stack anymore. This will<br />
then trigger a stack overflow exception.<br />
<br />
For a nice interactive animation of the above behaviour see: http://foldr.com<br />
<br />
Lets think about how to solve it... <br />
<br />
One problem with the chain of (+)'s is that we can't make it<br />
smaller (reduce it) until at the very last moment when it's already<br />
too late.<br />
<br />
The reason we can't reduce it, is that the chain doesn't contain an<br />
expression which can be reduced (a so called "redex" for '''red'''ucible<br />
'''ex'''pression.) If it did we could reduce that expression before going<br />
to the next element.<br />
<br />
Well, we can introduce a redex by forming the chain in another way. If<br />
instead of the chain <tt>1 + (2 + (3 + (...)))</tt> we could form the chain<br />
<tt>(((0 + 1) + 2) + 3) + ...</tt> then there would always be a redex.<br />
<br />
We can form the latter chain by using a function called ''foldl'':<br />
<br />
<haskell><br />
> foldl f z [] = z<br />
> foldl f z (x:xs) = foldl f (z `f` x) xs<br />
<br />
> sum2 = foldl (+) 0<br />
<br />
> try2 = sum2 veryBigList<br />
</haskell><br />
<br />
Lets evaluate ''try2'':<br />
<br />
<tt><nowiki>*** Exception: stack overflow</nowiki></tt><br />
<br />
Good Lord! Again a stack overflow! Lets see what happens:<br />
<br />
<haskell><br />
try2 --><br />
foldl (+) 0 [1..1000000] --><br />
foldl (+) (0 + 1) [2..1000000] --><br />
foldl (+) ((0 + 1) + 2) [3..1000000] --><br />
foldl (+) (((0 + 1) + 2) + 3) [4..1000000] --><br />
foldl (+) ((((0 + 1) + 2) + 3) + 4) [5..1000000] --><br />
-- ...<br />
-- ... My stack overflows when there's a chain of around 500000 (+)'s !!!<br />
-- ... But the following would happen if you got a large enough stack:<br />
-- ...<br />
foldl (+) ((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) [1000000] --><br />
foldl (+) (((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) + 1000000) [] --><br />
<br />
((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) + 1000000 --><br />
(((((1 + 2) + 3) + 4) + ...) + 999999) + 1000000 --><br />
((((3 + 3) + 4) + ...) + 999999) + 1000000 --><br />
(((6 + 4) + ...) + 999999) + 1000000 --><br />
((10 + ...) + 999999) + 1000000 --><br />
<br />
(499998500001 + 999999) + 1000000 --><br />
499999500000 + 1000000<br />
500000500000 --><br />
</haskell><br />
<br />
For a nice interactive animation of the above behaviour see: http://foldl.com (actually this animation is not quite the same :-( )<br />
<br />
Well, you clearly see that the redexen <tt>0 + 1</tt>, <tt>(0 + 1) + 2</tt>,<br />
etc. are created. So why doesn't the chain reduce sooner than<br />
before?<br />
<br />
The answer is that GHC uses a lazy reduction strategy. This means<br />
that GHC only reduces an expression when its value is actually<br />
needed. <br />
<br />
The reduction strategy works by reducing the outer-left-most redex<br />
first. In this case it are the outer <tt>foldl (+) ... [1..10000]</tt><br />
redexen which are repeatedly reduced. <br />
So the inner <tt>(((0 + 1) + 2) + 3) + 4</tt> redexen only get reduced when<br />
the foldl is completely gone.<br />
<br />
We somehow have to tell the system that the inner redex should be<br />
reduced before the outer. Fortunately this is possible with the<br />
''seq'' function:<br />
<br />
<haskell>seq :: a -> b -> b</haskell><br />
<br />
''seq'' is a primitive system function that when applied to ''x'' and<br />
''y'' will first reduce ''x'', then reduce ''y'' and return the result of<br />
the latter. The idea is that ''y'' references ''x'' so that when ''y'' is<br />
reduced ''x'' will not be a big unreduced chain anymore.<br />
<br />
Now lets fill in the pieces:<br />
<br />
<haskell><br />
> foldl' f z [] = z<br />
> foldl' f z (x:xs) = let z' = z `f` x <br />
> in seq z' $ foldl' f z' xs<br />
<br />
> sum3 = foldl' (+) 0<br />
<br />
> try3 = sum3 veryBigList<br />
</haskell><br />
<br />
If we now evaluate ''try3'' we get the correct answer and we get it very quickly:<br />
<br />
<haskell>500000500000</haskell><br />
<br />
Lets see what happens:<br />
<br />
<haskell><br />
try3 --><br />
foldl' (+) 0 [1..1000000] --><br />
foldl' (+) 1 [2..1000000] --><br />
foldl' (+) 3 [3..1000000] --><br />
foldl' (+) 6 [4..1000000] --><br />
foldl' (+) 10 [5..1000000] --><br />
-- ...<br />
-- ... You see that the stack doesn't overflow<br />
-- ...<br />
foldl' (+) 499999500000 [1000000] --><br />
foldl' (+) 500000500000 [] --><br />
500000500000<br />
</haskell><br />
<br />
You can clearly see that the inner redex is repeatedly reduced<br />
first.<br />
<br />
For another explanation about folds see the [http://haskell.org/haskellwiki/Fold Fold] article.</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Mailing_lists&diff=25578Mailing lists2009-01-08T18:24:15Z<p>Daniel.is.fischer: Remove apparent spam</p>
<hr />
<div>There are three mailing lists to discuss issues related to Haskell in<br />
general, and several additional mailing lists for more detailed<br />
discussion topics, including one for each particular implementation of<br />
Haskell.<br />
<br />
* [http://haskell.org/mailman/listinfo/haskell Subscribe to haskell@haskell.org] (announces only, low traffic)<br />
* [http://haskell.org/mailman/listinfo/haskell-cafe Subscribe to haskell-cafe@haskell.org] (very busy, daily community discussion)<br />
* [http://haskell.org/mailman/listinfo/beginners Subscribe to beginners@haskell.org] (busy, daily community discussion)<br />
* [http://haskell.org/mailman/listinfo A comprehensive list of all mailing lists hosted at haskell.org]<br />
<br />
==Mailing lists in detail==<br />
<br />
<dl><dt>[mailto:haskell@haskell.org haskell@haskell.org] ([http://news.gmane.org/gmane.comp.lang.haskell.general read & search via gmane])</dt><br />
<dd>Announcements, discussion openers, technical questions. <br> [mailto:haskell@haskell.org haskell@haskell.org] is intended to be a low-bandwidth list, to which it is safe to subscribe without risking being buried in email. If a thread becomes longer than a handful of messages, please transfer to [mailto:haskell-cafe@haskell.org haskell-cafe@haskell.org].</dd><br />
<dt>[mailto:haskell-cafe@haskell.org haskell-cafe@haskell.org] ([http://news.gmane.org/gmane.comp.lang.haskell.cafe read & search via gmane])</dt><br />
<dd>General Haskell questions; extended discussions.<br> In Simon Peyton Jones' words: "forum in which it's acceptable to ask anything, no matter how naive, and get polite replies."<br />
<dt>[mailto:beginners@haskell.org beginners@haskell.org] ([http://news.gmane.org/gmane.comp.lang.haskell.beginners read & search via gmane])</dt><br />
<dd>Beginner-level, i.e., elementary, Haskell questions and discussions.<br> In the words of Benjamin L. Russell (the one who first suggested creating the mailing list and the current administrator): "Here, there is no such thing as a 'stupid question.'"</dd><br />
</dl><br />
<br />
===Mailing list tone===<br />
<br />
The division of the general list was introduced for people who want<br />
to stay in touch with what's happening in the Haskell world, but who don't want to be swamped with mail. Discussions of any kind can start on 'haskell', but should transfer to 'haskell-cafe' if they go beyond a few 'rounds'. '''Alternatively, if you are new to Haskell, then you have a choice: either haskell-cafe, or haskell-beginners.'''<br />
<br />
In practice, 'haskell' tends to be devoted mainly to announcements, 'haskell-cafe' tends to be devoted mainly to freeform discussion, and 'haskell-beginners' tends to be devoted mainly to beginner-level Haskell language discussions.<br />
<br />
The readership of the three mailing lists also varies. Whereas both 'haskell' and 'haskell-cafe' tend to be frequented by either language designers or researchers, 'haskell-beginners' tends to be frequented by beginner-level students and educators. 'Haskell-beginners' was created to address the needs of readers of 'haskell-cafe' who felt that the discussion there was either too academic, or too mathematical.<br />
<br />
When posting on 'haskell-cafe', remember:<br />
<br />
* Respect others. This is a civil discussion forum. Remember, the person on the other side of the keyboard is a person too, and is probably well-intentioned.<br />
<br />
* Try to keep discussions on-topic. Threads that have lost any relevance to the Haskell language should be moved elsewhere, including tangential or joking posts (though humor in the context of on-topic discussion is welcome.)<br />
<br />
* Think before sending. Avoid content-free posts, such as a message consisting merely of the phrase "+1." The etiquette for academic mailing list discussions is different from the etiquette for other Internet fora or for ordinary conversation. Remember that your email will be sent to thousands of people, some of whom are very busy. Ask yourself whether your post contributes anything of value to any of them.<br />
<br />
In the case of 'haskell-beginners', please keep in mind the following pointers when posting:<br />
<br />
* Since many readers of this mailing list are beginner-level students of Haskell, try to keep the discussion at a level that allows students of all backgrounds to participate in the discussion. I.e., when explaining difficult concepts, be careful not to assume an advanced background of the reader. For example, don't start a discussion on monads by saying: "A monad is a category theory-based data structure used to supplement pure computations with features like state, common environment or I/O." Instead, say: "A monad is a tool used in Haskell when we want to allow a program to do anything other than just return a value."<br />
<br />
* Again, since many readers of this mailing list are beginner-level students of Haskell, do not assume that readers have an advanced mathematics background, or that they know everything that may seem elementary to a computer science student. For example, if a student here asks whether the screen resolution is important in determining the precision of an algorithm to compute prime numbers by picking points randomly from a square, do not accuse the student of "polluting" the newsgroup by asking a question that "has nothing to do with Haskell." Understand that the student may not have enough mathematical or programming background to realize that screen resolution may be independent of the precision of the actual algorithm used to compute the prime numbers, which may then be represented on the screen independently of the precision of the algorithm itself. If beginner-level students are required to worry about offending somebody with a question that is too elementary every time they need an answer, they will stay beginners.<br />
<br />
===Subscription information===<br />
<br />
Haskell mailing lists are managed by [http://www.gnu.org/software/mailman/mailman.html mailman] -<br />
each list has a web interface. To subscribe, unsubscribe, or view the<br />
archives of a list visit the home page of the list, such as the [http://haskell.org/mailman/listinfo/haskell Haskell mailing list home page], the [http://haskell.org/mailman/listinfo/haskell-cafe Haskell Cafe mailing list home page], or the [http://haskell.org/mailman/listinfo/beginners Haskell-Beginners mailing list home page]. <br />
<br />
===Archiving===<br />
<br />
mail-archive.com provides an archive of all messages sent to the haskell list since March 1997. This includes messages from before the list was converted to mailman. You may search these archives: [http://www.mail-archive.com/haskell@haskell.org/ haskell archive], [http://www.mail-archive.com/haskell-cafe@haskell.org/ haskell-cafe archive], and [http://www.mail-archive.com/beginners@haskell.org/ haskell-beginners archive].<br />
<br />
MarkMail has a [http://haskell.markmail.org/ searchable archive] of all Haskell lists going back to around 2000.<br />
<br />
Also, the archives of the Haskell mailing list from September 1990 until 2006, before and after the list was converted to mailman, are [http://www.cse.unsw.edu.au/~dons/haskell-1990-2006/threads.html hosted here] (and as a [http://www.cse.unsw.edu.au/~dons/haskell-1990-2006.tar.bz2 tar file]).<br />
Related to this is the archives of [http://groups.google.com/group/comp.lang.functional/about?hl=en comp.lang.functional] going back to 1990.<br />
<br />
You may also [http://www.google.com/coop/cse?cx=015832023690232952875%3Acunmubfghzq search the mailing list] using the Google Coop Haskell Search Engine.<br />
<br />
====Archives====<br />
<br />
The following archives exist:<br />
<br />
haskell<br />
<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.general gmane] ([http://dir.gmane.org/gmane.comp.lang.haskell.general info]) 2006/12-present<br />
* [http://www.haskell.org/pipermail/haskell/ mailman] 2000/10-present<br />
* [http://www.mail-archive.com/haskell@haskell.org/ mail-archive] 1997/03-present<br />
* [http://www.cse.unsw.edu.au/~dons/haskell-1990-2006/threads.html dons archive] ([http://www.cse.unsw.edu.au/~dons/haskell-1990-2006.tar.bz2 tar]) 1990/09-2006/08<br />
<br />
haskell-cafe<br />
<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.cafe gmane] ([http://dir.gmane.org/gmane.comp.lang.haskell.cafe info]) 2002/04-present<br />
* [http://www.haskell.org/pipermail/haskell-cafe/ mailman] 2000/10-present<br />
* [http://www.mail-archive.com/haskell-cafe@haskell.org/ mail-archive] 1997/03-present<br />
<br />
haskell-beginners<br />
<br />
* [http://news.gmane.org/gmane.comp.lang.haskell.beginners gmane] ([http://dir.gmane.org/gmane.comp.lang.haskell.beginners info]) 2008/07-present<br />
* [http://www.haskell.org/pipermail/beginners/ mailman] 2008/07-present<br />
* [http://www.mail-archive.com/beginners@haskell.org/ mail-archive] 2008/07-present<br />
<br />
Any problems with haskell or haskell-cafe should be reported to [mailto:haskell-admin@haskell.org haskell-admin@haskell.org], and any problems with haskell-beginners should be reported to [mailto:DekuDekuplex@Yahoo.com DekuDekuplex@Yahoo.com].<br />
<br />
==More specific lists==<br />
<br />
* [http://haskell.org/mailman/listinfo A comprehensive list of all Mailing lists hosted at haskell.org]<br />
* [http://gmane.org/find.php?list=haskell Haskell lists at gmane]<br />
<br />
There are mailing lists for each implementation of Haskell,<br />
and for more detailed discussion topics. Questions, comments, and bug<br />
reports regarding a specific implementation should be sent directly<br />
to the appropriate list instead of the entire Haskell community.<br />
Separate topics such as documentation tools, the common FFI, and<br />
libraries, also have lists of their own.<br />
<br />
==Outside haskell.org==<br />
<br />
There are also Haskell related mailing lists that are not hosted at haskell.org.<br />
<br />
* [[Haskell art]]<br />
<br />
[[Category:Community]]</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Euler_problems/181_to_190&diff=19383Euler problems/181 to 1902008-02-23T23:09:48Z<p>Daniel.is.fischer: </p>
<hr />
<div>== [http://projecteuler.net/index.php?section=problems&id=181 Problem 181] ==<br />
Investigating in how many ways objects of two different colours can be grouped.<br />
<br />
Solution: This was my code, published here without my permission nor any attribution, shame on whoever put it here. [[User:Daniel.is.fischer|Daniel.is.fischer]]<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=182 Problem 182] ==<br />
RSA encryption.<br />
<br />
Solution:<br />
<haskell><br />
fun a1 b1 =<br />
sum [ e |<br />
e <- [2..a*b-1],<br />
gcd e (a*b) == 1,<br />
gcd (e-1) a == 2,<br />
gcd (e-1) b == 2<br />
]<br />
where<br />
a=a1-1<br />
b=b1-1<br />
problem_182=fun 1009 3643<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=183 Problem 183] ==<br />
Maximum product of parts.<br />
<br />
Solution:<br />
<haskell><br />
pmax x a=a*(log x-log a)<br />
tofloat x=encodeFloat x 0<br />
fun x=<br />
div n1 $gcd n1 x<br />
where<br />
e=exp 1<br />
n=floor(fromInteger x/e)<br />
n1=snd.maximum$[(b,a)|a<-[n..n+1],let b=pmax (tofloat x) (tofloat a)]<br />
n `splitWith` p = doSplitWith 0 n<br />
where doSplitWith s t<br />
| p `divides` t = doSplitWith (s+1) (t `div` p)<br />
| otherwise = (s, t)<br />
d `divides` n = n `mod` d == 0<br />
funD x<br />
|is25 k=(-x)<br />
|otherwise =x<br />
where <br />
k=fun x<br />
is25 x<br />
|s==1=True<br />
|otherwise=False<br />
where<br />
s=snd(splitWith (snd (splitWith x 2)) 5)<br />
problem_183 =sum[funD a|a<- [5..10000]]<br />
</haskell></div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Euler_problems/151_to_160&diff=19382Euler problems/151 to 1602008-02-23T23:09:00Z<p>Daniel.is.fischer: </p>
<hr />
<div>== [http://projecteuler.net/index.php?section=problems&id=151 Problem 151] ==<br />
Paper sheets of standard sizes: an expected-value problem.<br />
<br />
Solution:<br />
<haskell><br />
problem_151 = fun (1,1,1,1)<br />
<br />
fun (0,0,0,1) = 0<br />
fun (0,0,1,0) = fun (0,0,0,1) + 1<br />
fun (0,1,0,0) = fun (0,0,1,1) + 1<br />
fun (1,0,0,0) = fun (0,1,1,1) + 1<br />
fun (a,b,c,d) = <br />
(pickA + pickB + pickC + pickD) / (a + b + c + d)<br />
where<br />
pickA | a > 0 = a * fun (a-1,b+1,c+1,d+1)<br />
| otherwise = 0<br />
pickB | b > 0 = b * fun (a,b-1,c+1,d+1)<br />
| otherwise = 0<br />
pickC | c > 0 = c * fun (a,b,c-1,d+1)<br />
| otherwise = 0<br />
pickD | d > 0 = d * fun (a,b,c,d-1)<br />
| otherwise = 0 <br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=152 Problem 152] ==<br />
Writing 1/2 as a sum of inverse squares<br />
<br />
Note that if p is an odd prime, the sum of inverse squares of<br />
all terms divisible by p must have reduced denominator not divisible<br />
by p.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Ratio<br />
import Data.List<br />
<br />
invSq n = 1 % (n * n)<br />
sumInvSq = sum . map invSq<br />
<br />
subsets (x:xs) = let s = subsets xs in s ++ map (x :) s<br />
subsets _ = [[]]<br />
<br />
primes = 2 : 3 : 7 : [p | p <- [11, 13..79],<br />
all (\q -> p `mod` q /= 0) [3, 5, 7]]<br />
<br />
-- All subsets whose sum of inverse squares,<br />
-- when added to x, does not contain a factor of p<br />
pfree s x p = [(y, t) | t <- subsets s, let y = x + sumInvSq t,<br />
denominator y `mod` p /= 0]<br />
<br />
<br />
-- All pairs (x, s) where x is a rational number whose reduced<br />
-- denominator is not divisible by any prime greater than 3;<br />
-- and s is all sets of numbers up to 80 divisible<br />
-- by a prime greater than 3, whose sum of inverse squares is x.<br />
only23 = foldl fun [(0, [[]])] [13, 7, 5]<br />
where<br />
fun a p = <br />
collect $ [(y, u ++ v) |<br />
(x, s) <- a,<br />
(y, v) <- pfree (terms p) x p,<br />
u <- s]<br />
terms p = <br />
[n * p | <br />
n <- [1..80`div`p],<br />
all (\q -> n `mod` q /= 0) $<br />
11 : takeWhile (>= p) [13, 7, 5]<br />
]<br />
collect = <br />
map (\z -> (fst $ head z, map snd z)) .<br />
groupBy fstEq . sortBy cmpFst<br />
fstEq (x, _) (y, _) = x == y<br />
cmpFst (x, _) (y, _) = compare x y<br />
<br />
-- All subsets (of an ordered set) whose sum of inverse squares is x<br />
findInvSq x y = <br />
fun x $ zip3 y (map invSq y) (map sumInvSq $ init $ tails y)<br />
where<br />
fun 0 _ = [[]]<br />
fun x ((n, r, s):ns)<br />
| r > x = fun x ns<br />
| s < x = []<br />
| otherwise = map (n :) (fun (x - r) ns) ++ fun x ns<br />
fun _ _ = []<br />
<br />
-- All numbers up to 80 that are divisible only by the primes<br />
-- 2 and 3 and are not divisible by 32 or 27.<br />
all23 = [n | a <- [0..4], b <- [0..2], let n = 2^a * 3^b, n <= 80]<br />
<br />
solutions = <br />
[sort $ u ++ v |<br />
(x, s) <- only23,<br />
u <- findInvSq (1%2 - x) all23,<br />
v <- s<br />
]<br />
<br />
problem_152 = length solutions<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=153 Problem 153] ==<br />
Investigating Gaussian Integers<br />
<br />
Solution:<br />
This does not seem Haskell code to me.<br />
If the argument: Learning Haskell were valid pure Haskell code would have been given.<br />
<br />
<haskell><br />
#include <stdio.h><br />
#include <math.h><br />
typedef long long lolo;<br />
static const lolo sumTo( lolo n ) { return n * ( n + 1 ) / 2; }<br />
<br />
#define LL (1000)<br />
lolo ssTab[ LL ];<br />
int gcd(int a, int b) {<br />
if (b==0) return a;<br />
return gcd(b, a%b);<br />
}<br />
<br />
static const lolo sumSigma( lolo n ) {<br />
lolo a, r, s;<br />
<br />
if( n == 0 ) return 0;<br />
if( n < LL ) { r = ssTab[ n ]; if( r ) return r; }<br />
s = floor(sqrt( n ));<br />
r = 0;<br />
for( a = 1; a <= s; ++a ) r += a * ( n / a );<br />
for( a = 1; a <= s; ++a ) r += ( sumTo( n / a ) - sumTo ( n / ( a + 1 ) ) ) * a;<br />
if( n / s == s ) r -= s * s;<br />
if( n < LL ) ssTab[ n ] = r;<br />
<br />
return r;<br />
}<br />
<br />
int main() {<br />
const lolo m = 100000000;<br />
lolo t;<br />
int a, b;<br />
long ab;<br />
t = sumSigma(m);<br />
for( a = 1; a <=floor(sqrt(m)); ++a ) {<br />
for( b = 1; b <= a && a * a + b * b <= m; ++b ) {<br />
ab=(a*a+b*b);<br />
if( ( a | b ) & 1 && gcd( a, b ) == 1 ) {<br />
t += 2 * sumSigma( m / ab) * ( a == b ? a : a + b );<br />
}<br />
}<br />
}<br />
printf( "t = %lld\n", t );<br />
<br />
return 1;<br />
}<br />
problem_153 = main<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=154 Problem 154] ==<br />
Exploring Pascal's pyramid.<br />
<br />
Solution:<br />
This does not seem Haskell code to me.<br />
If the argument: Learning Haskell were valid pure Haskell code would have been given.<br />
<br />
<haskell><br />
<br />
#include <stdio.h><br />
int main(){<br />
int bound = 200000;<br />
long long sum = 0;<br />
int val2[bound+1], val5[bound+1]; // number of factors 2/5 in i!<br />
int v2 = 0, v5 = 0;<br />
int i;<br />
int n;<br />
for(n=0;n<=bound;n++)<br />
{val5[n]=n/5+n/25+n/125+n/625+n/3125+n/15625+n/78125; <br />
val2[n]=n/2+n/4+n/8+n/16+n/32+n/64+n/128+n/256+n/512+n/1024<br />
+n/2048+n/4096+n/8192+n/16384+n/32768+n/65536+n/131072;}<br />
<br />
v2 =val2[bound]- 11;<br />
v5 = val5[bound]-11;<br />
int j,k,vi2,vi5;<br />
for(i = 2; i < 65625; i++){<br />
if (!(i&1023)){<br />
// look how many we got so far<br />
printf("%d:\t%lld\n",i,sum);<br />
}<br />
vi5 = val5[i];<br />
vi2 = val2[i];<br />
int jb = ((bound - i) >> 1)+1;<br />
// I want i <= j <= k<br />
// by carry analysis, I know that if i < 4*5^5+2, then<br />
// j must be at least 2*5^6+2<br />
for(j = (i < 12502) ? 31252 : i; j < jb; j++){<br />
k = bound - i - j;<br />
if (vi5 + val5[j] + val5[k] < v5<br />
&& vi2 + val2[j] + val2[k] < v2){<br />
if (j == k || i == j){<br />
sum += 3;<br />
} else {<br />
sum += 6;<br />
}<br />
}<br />
}<br />
}<br />
printf("Total:\t%lld\n",sum);<br />
return 0;<br />
}<br />
problem_154 = main<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=155 Problem 155] ==<br />
Counting Capacitor Circuits.<br />
<br />
Solution:<br />
<haskell><br />
--http://www.research.att.com/~njas/sequences/A051389<br />
a051389=<br />
[1, 2, 4, 8, 20, 42,<br />
102, 250, 610, 1486, <br />
3710, 9228, 23050, 57718,<br />
145288, 365820, 922194, 2327914<br />
]<br />
problem_155 = sum a051389<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=156 Problem 156] ==<br />
Counting Digits<br />
<br />
Solution: This was my code, published here without my permission nor any attribution, shame on whoever put it here. [[User:Daniel.is.fischer|Daniel.is.fischer]]<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=157 Problem 157] ==<br />
Solving the diophantine equation 1/a+1/b= p/10n<br />
<br />
Solution:<br />
<haskell><br />
-- Call (a,b,p) a primitive tuple of equation 1/a+1/b=p/10^n<br />
-- a and b are divisors of 10^n, gcd a b == 1, a <= b and a*b <= 10^n<br />
-- I noticed that the number of variants with a primitive tuple<br />
-- is equal to the number of divisors of p.<br />
-- So I produced all possible primitive tuples per 10^n and<br />
-- summed all the number of divisors of every p<br />
<br />
import Data.List<br />
k `deelt` n = n `mod` k == 0<br />
<br />
delers n <br />
| n == 10 = [1,2,5,10]<br />
| otherwise = <br />
[ d |<br />
d <- [1..n `div` 5],<br />
d `deelt` n ] <br />
++ [n `div` 4, n `div` 2,n]<br />
fp n = <br />
[ n*(a+b) `div` ab |<br />
a <- ds,<br />
b <- dropWhile (<a) ds,<br />
gcd a b == 1,<br />
let ab = a*b,<br />
ab <= n <br />
]<br />
where<br />
ds = delers n<br />
numDivisors :: Integer -> Integer<br />
numDivisors n = product [ toInteger (a+1) | (p,a) <- primePowerFactors n]<br />
numVgln = sum . map numDivisors . fp<br />
<br />
main = do<br />
print . sum . map numVgln . takeWhile (<=10^9) . iterate (10*) $ 10 <br />
primePowerFactors x = [(head a ,length a)|a<-group$primeFactors x] <br />
merge xs@(x:xt) ys@(y:yt) = case compare x y of<br />
LT -> x : (merge xt ys)<br />
EQ -> x : (merge xt yt)<br />
GT -> y : (merge xs yt)<br />
<br />
diff xs@(x:xt) ys@(y:yt) = case compare x y of<br />
LT -> x : (diff xt ys)<br />
EQ -> diff xt yt<br />
GT -> diff xs yt<br />
<br />
primes, nonprimes :: [Integer]<br />
primes = [2,3,5] ++ (diff [7,9..] nonprimes) <br />
nonprimes = foldr1 f . map g $ tail primes<br />
where f (x:xt) ys = x : (merge xt ys)<br />
g p = [ n*p | n <- [p,p+2..]]<br />
primeFactors n =<br />
factor n primes<br />
where<br />
factor n (p:ps) <br />
| p*p > n = [n]<br />
| n `mod` p == 0 = p : factor (n `div` p) (p:ps)<br />
| otherwise = factor n ps<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=158 Problem 158] ==<br />
Exploring strings for which only one character comes lexicographically after its neighbour to the left.<br />
<br />
Solution:<br />
<haskell><br />
factorial n = product [1..toInteger n]<br />
fallingFactorial x n = product [x - fromInteger i | i <- [0..toInteger n - 1] ]<br />
choose n k = fallingFactorial n k `div` factorial k<br />
fun n=(2 ^ n - n - 1) * choose 26 n <br />
problem_158=maximum$map fun [1..26]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=159 Problem 159] ==<br />
Digital root sums of factorisations.<br />
<br />
Solution:<br />
<haskell><br />
import Control.Monad<br />
import Data.Array.ST<br />
import qualified Data.Array.Unboxed as U<br />
spfArray :: U.UArray Int Int<br />
spfArray = runSTUArray (do<br />
arr <- newArray (0,m-1) 0 <br />
loop arr 2<br />
forM_ [2 .. m - 1] $ \ x -><br />
loop2 arr x 2<br />
return arr <br />
)<br />
where<br />
m=10^6<br />
loop arr n<br />
|n>=m=return ()<br />
|otherwise=do writeArray arr n (n-9*(div (n-1) 9))<br />
loop arr (n+1)<br />
loop2 arr x n <br />
|n*x>=m=return ()<br />
|otherwise=do incArray arr x n<br />
loop2 arr x (n+1)<br />
incArray arr x n = do<br />
a <- readArray arr x<br />
b <- readArray arr n<br />
ab <- readArray arr (x*n)<br />
when(ab<a+b) (writeArray arr (x*n) (a + b))<br />
writ x=appendFile "p159.log"$foldl (++) "" [show x,"\n"]<br />
main=do<br />
mapM_ writ $U.elems spfArray<br />
problem_159 = main<br />
<br />
--at first ,make main to get file "p159.log"<br />
--then ,add all num in the file <br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=160 Problem 160] ==<br />
Factorial trailing digits<br />
<br />
We use the following two facts:<br />
<br />
Fact 1: <hask>(2^(d + 4*5^(d-1)) - 2^d) `mod` 10^d == 0</hask><br />
<br />
Fact 2: <hask>product [n | n <- [0..10^d], gcd n 10 == 1] `mod` 10^d == 1</hask><br />
<br />
We really only need these two facts for the special case of<br />
<hask>d == 5</hask>, and we can verify that directly by<br />
evaluating the above two Haskell expressions.<br />
<br />
More generally:<br />
<br />
Fact 1 follows from the fact that the group of invertible elements<br />
of the ring of integers modulo <hask>5^d</hask> has<br />
<hask>4*5^(d-1)</hask> elements.<br />
<br />
Fact 2 follows from the fact that the group of invertible elements<br />
of the ring of integers modulo <hask>10^d</hask> is isomorphic to the product<br />
of a cyclic group of order 2 and another cyclic group.<br />
<br />
Solution:<br />
<haskell><br />
problem_160 = trailingFactorialDigits 5 (10^12)<br />
<br />
trailingFactorialDigits d n = twos `times` odds<br />
where<br />
base = 10 ^ d<br />
x `times` y = (x * y) `mod` base<br />
multiply = foldl' times 1<br />
x `toPower` k = multiply $ genericReplicate n x<br />
e = facFactors 2 n - facFactors 5 n<br />
twos<br />
| e <= d = 2 `toPower` e<br />
| otherwise = 2 `toPower` (d + (e - d) `mod` (4 * 5 ^ (d - 1)))<br />
odds = multiply [odd | a <- takeWhile (<= n) $ iterate (* 2) 1,<br />
b <- takeWhile (<= n) $ iterate (* 5) a,<br />
odd <- [3, 5 .. n `div` b `mod` base],<br />
odd `mod` 5 /= 0]<br />
<br />
-- The number of factors of the prime p in n!<br />
facFactors p = sum . zipWith (*) (iterate (\x -> p * x + 1) 1) .<br />
tail . radix p<br />
<br />
-- The digits of n in base b representation<br />
radix p = map snd . takeWhile (/= (0, 0)) .<br />
iterate ((`divMod` p) . fst) . (`divMod` p)<br />
</haskell><br />
it have another fast way to do this .<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
mulMod :: Integral a => a -> a -> a -> a<br />
mulMod a b c= (b * c) `rem` a<br />
squareMod :: Integral a => a -> a -> a<br />
squareMod a b = (b * b) `rem` a<br />
pow' :: (Num a, Integral b) => (a -> a -> a) -> (a -> a) -> a -> b -> a<br />
pow' _ _ _ 0 = 1<br />
pow' mul sq x' n' = f x' n' 1<br />
where<br />
f x n y<br />
| n == 1 = x `mul` y<br />
| r == 0 = f x2 q y<br />
| otherwise = f x2 q (x `mul` y)<br />
where<br />
(q,r) = quotRem n 2<br />
x2 = sq x<br />
powMod :: Integral a => a -> a -> a -> a<br />
powMod m = pow' (mulMod m) (squareMod m)<br />
<br />
productMod =foldl (mulMod (10^5)) 1<br />
hFacial 0=1<br />
hFacial a<br />
|gcd a 5==1=mod (a*hFacial(a-1)) (5^5)<br />
|otherwise=hFacial(a-1)<br />
fastFacial a= hFacial $mod a 6250<br />
numPrime x p=takeWhile(>0) [div x (p^a)|a<-[1..]]<br />
p160 x=mulMod t5 a b<br />
where<br />
t5=10^5<br />
lst=numPrime x 5<br />
a=powMod t5 1563 $mod c 2500<br />
b=productMod c6 <br />
c=sum lst<br />
c6=map fastFacial $x:lst<br />
problem_160 = p160 (10^12)<br />
<br />
</haskell></div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Euler_problems/141_to_150&diff=19381Euler problems/141 to 1502008-02-23T23:07:51Z<p>Daniel.is.fischer: </p>
<hr />
<div>== [http://projecteuler.net/index.php?section=problems&id=141 Problem 141] ==<br />
Investigating progressive numbers, n, which are also square.<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
intSqrt :: Integral a => a -> a<br />
intSqrt n<br />
| n < 0 = error "intSqrt: negative n"<br />
| otherwise = f n<br />
where<br />
f x = if y < x then f y else x<br />
where y = (x + (n `quot` x)) `quot` 2<br />
isSqrt n = n==((^2).intSqrt) n<br />
takec a b =<br />
two++takeWhile (<=e12) <br />
[sq| c1<-[1..], let c=c1*c1,let sq=(c^2*a^3*b+b^2*c) ]<br />
where<br />
e12=10^12<br />
two=[sq|c<-[b,2*b],let sq=(c^2*a^3*b+b^2*c) ]<br />
problem_141=<br />
sum$nub[c|<br />
(a,b)<-takeWhile (\(a,b)->a^3*b+b^2<e12) <br />
[(a,b)|<br />
a<-[2..e4],<br />
b<-[1..(a-1)]<br />
],<br />
gcd a b==1,<br />
c<-takec a b,<br />
isSqrt c<br />
]<br />
where<br />
e4=120<br />
e12=10^12<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=142 Problem 142] ==<br />
Perfect Square Collection<br />
<br />
Solution:<br />
<haskell><br />
import List<br />
isSquare n = (round . sqrt $ fromIntegral n) ^ 2 == n<br />
aToX (a,b,c)=[x,y,z]<br />
where<br />
x=div (a+b) 2<br />
y=div (a-b) 2<br />
z=c-x<br />
{-<br />
- 2 2 2<br />
- a = c + d<br />
- 2 2 2<br />
- a = e + f<br />
- 2 2 2<br />
- c = e + b<br />
- let b=x*y then <br />
- (y + xb)<br />
- c= ---------<br />
- 2<br />
- (-y + xb)<br />
- e= ---------<br />
- 2<br />
- (-x + yb)<br />
- d= ---------<br />
- 2<br />
- (x + yb)<br />
- f= ---------<br />
- 2<br />
-<br />
- and <br />
- 2 2 2<br />
- a = c + d<br />
- then <br />
- 2 2 2 2<br />
- 2 (y + x ) (x y + 1)<br />
- a = ---------------------<br />
- 4<br />
-<br />
-}<br />
problem_142 = sum$head[aToX(t,t2 ,t3)|<br />
a<-[3,5..50],<br />
b<-[(a+2),(a+4)..50],<br />
let a2=a^2,<br />
let b2=b^2,<br />
let n=(a2+b2)*(a2*b2+1),<br />
isSquare n,<br />
let t=div n 4,<br />
let t2=a2*b2,<br />
let t3=div (a2*(b2+1)^2) 4<br />
]<br />
<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=143 Problem 143] ==<br />
Investigating the Torricelli point of a triangle<br />
<br />
Solution: This was my code, published here without my permission nor any attribution, shame on whoever put it here. [[User:Daniel.is.fischer|Daniel.is.fischer]]<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=144 Problem 144] ==<br />
Investigating multiple reflections of a laser beam.<br />
<br />
Solution:<br />
<haskell><br />
type Point = (Double, Double)<br />
type Vector = (Double, Double)<br />
type Normal = (Double, Double)<br />
<br />
sub :: Vector -> Vector -> Vector<br />
sub (x,y) (a,b) = (x-a, y-b)<br />
<br />
mull :: Double -> Vector -> Vector<br />
mull s (x,y) = (s*x, s*y)<br />
<br />
mulr :: Vector -> Double -> Vector<br />
mulr v s = mull s v<br />
<br />
dot :: Vector -> Vector -> Double<br />
dot (x,y) (a,b) = x*a + y*b<br />
<br />
normSq :: Vector -> Double<br />
normSq v = dot v v<br />
<br />
normalize :: Vector -> Vector<br />
normalize v <br />
|len /= 0 =mulr v (1.0/len)<br />
|otherwise=error "Vettore nullo.\n" <br />
where<br />
len = (sqrt . normSq) v <br />
<br />
proj :: Vector -> Vector -> Vector<br />
proj a b = mull ((dot a b)/normSq b) b<br />
<br />
reflect :: Vector -> Normal -> Vector<br />
reflect i n = sub i $ mulr (proj i n) 2.0<br />
<br />
type Ray = (Point, Vector)<br />
<br />
makeRay :: Point -> Vector -> Ray<br />
makeRay p v = (p, v)<br />
<br />
getPoint :: Ray -> Double -> Point<br />
getPoint ((px,py),(vx,vy)) t = (px + t*vx, py + t*vy)<br />
<br />
type Ellipse = (Double, Double)<br />
<br />
getNormal :: Ellipse -> Point -> Normal<br />
getNormal (a,b) (x,y) = ((-b/a)*x, (-a/b)*y)<br />
<br />
rayFromPoint :: Ellipse -> Vector -> Point -> Ray<br />
rayFromPoint e v p = makeRay p (reflect v (getNormal e p))<br />
<br />
test :: Point -> Bool<br />
test (x,y) = y > 0 && x >= -0.01 && x <= 0.01<br />
<br />
intersect :: Ellipse -> Ray -> Point<br />
intersect (e@(a,b)) (r@((px,py),(vx,vy))) =<br />
getPoint r t1<br />
where<br />
c0 = normSq (vx/a, vy/b)<br />
c1 = 2.0 * dot (vx/a, vy/b) (px/a, py/b)<br />
c2 = (normSq (px/a, py/b)) - 1.0<br />
(t0, t1) = quadratic c0 c1 c2 <br />
<br />
quadratic :: Double -> Double -> Double -> (Double, Double)<br />
quadratic a b c <br />
|d < 0= error "Discriminante minore di zero"<br />
|otherwise= if (t0 < t1) then (t0, t1) else (t1, t0)<br />
where<br />
d = b * b - 4.0 * a * c<br />
sqrtD = sqrt d<br />
q = if b < 0 then -0.5*(b - sqrtD) else 0.5*(b + sqrtD)<br />
t0 = q / a<br />
t1 = c / q <br />
<br />
calculate :: Ellipse -> Ray -> Int -> IO ()<br />
calculate e (r@(o,d)) n <br />
|test p=print n <br />
|otherwise=do<br />
putStrLn $ "\rHit " ++ show n<br />
calculate e (rayFromPoint e d p) (n+1)<br />
where<br />
p = intersect e r <br />
<br />
origin = (0.0,10.1)<br />
direction = sub (1.4,-9.6) origin<br />
ellipse = (5.0,10.0)<br />
<br />
problem_144 = do<br />
calculate ellipse (makeRay origin direction) 0<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=145 Problem 145] ==<br />
How many reversible numbers are there below one-billion?<br />
<br />
Solution:<br />
<haskell><br />
import List<br />
<br />
digits n <br />
{- 123->[3,2,1]<br />
-}<br />
|n<10=[n]<br />
|otherwise= y:digits x <br />
where<br />
(x,y)=divMod n 10<br />
-- 123 ->321<br />
dmm=(\x y->x*10+y)<br />
palind n=foldl dmm 0 (digits n) <br />
<br />
isOdd x=(length$takeWhile odd x)==(length x)<br />
isOdig x=isOdd m && s<=h<br />
where<br />
k=x+palind x<br />
m=digits k<br />
y=floor$logBase 10 $fromInteger x<br />
ten=10^y<br />
s=mod x 10<br />
h=div x ten<br />
<br />
a2=[i|i<-[10..99],isOdig i]<br />
aa2=[i|i<-[10..99],isOdig i,mod i 10/=0]<br />
a3=[i|i<-[100..999],isOdig i]<br />
m5=[i|i1<-[0..99],i2<-[0..99],<br />
let i3=i1*1000+3*100+i2,<br />
let i=10^6* 8+i3*10+5,<br />
isOdig i<br />
]<br />
<br />
fun i<br />
|i==2 =2*le aa2<br />
|even i=(fun 2)*d^(m-1)<br />
|i==3 =2*le a3<br />
|i==7 =fun 3*le m5<br />
|otherwise=0<br />
where<br />
le=length<br />
m=div i 2<br />
d=2*le a2<br />
<br />
problem_145 = sum[fun a|a<-[1..9]]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=146 Problem 146] ==<br />
Investigating a Prime Pattern<br />
<br />
Solution:<br />
<haskell><br />
import List<br />
isPrime x=millerRabinPrimality x 2<br />
--isPrime x=foldl (&& )True [millerRabinPrimality x y|y<-[2,3,7,61,24251]]<br />
six=[1,3,7,9,13,27]<br />
allPrime x=foldl (&&) True [isPrime k|a<-six,let k=x^2+a]<br />
linkPrime [x]=filterPrime x<br />
linkPrime (x:xs)=[y|<br />
a<-linkPrime xs,<br />
b<-[0..(x-1)],<br />
let y=b*prxs+a,<br />
let c=mod y x,<br />
elem c d]<br />
where<br />
prxs=product xs<br />
d=filterPrime x<br />
<br />
filterPrime p=<br />
[a|<br />
a<-[0..(p-1)],<br />
length[b|b<-six,mod (a^2+b) p/=0]==6<br />
]<br />
testPrimes=[2,3,5,7,11,13,17,23]<br />
primes=[2,3,5,7,11,13,17,23,29]<br />
test =<br />
sum[y|<br />
y<-linkPrime testPrimes,<br />
y<1000000,<br />
allPrime (y)<br />
]==1242490<br />
p146 =[y|y<-linkPrime primes,y<150000000,allPrime (y)]<br />
problem_146=[a|a<-p146, allNext a]<br />
allNext x=<br />
sum [1|(x,y)<-zip a b,x==y]==6<br />
where<br />
a=[x^2+b|b<-six]<br />
b=head a:(map nextPrime a)<br />
nextPrime x=head [a|a<-[(x+1)..],isPrime a]<br />
main=writeFile "p146.log" $show $sum problem_146<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=147 Problem 147] ==<br />
Rectangles in cross-hatched grids<br />
<br />
Solution:This was my code, published here without my permission nor any attribution, shame on whoever put it here. [[User:Daniel.is.fischer|Daniel.is.fischer]]<br />
<br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=148 Problem 148] ==<br />
Exploring Pascal's triangle.<br />
<br />
Solution:<br />
<haskell><br />
triangel 0 = 0<br />
triangel n <br />
|n <7 =n+triangel (n-1) <br />
|n==k7 =28^k <br />
|otherwise=(triangel i) + j*(triangel (n-i))<br />
where<br />
i=k7*((n-1)`div`k7)<br />
j= -(n`div`(-k7))<br />
k7=7^k<br />
k=floor(log (fromIntegral n)/log 7)<br />
problem_148=triangel (10^9)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=149 Problem 149] ==<br />
Searching for a maximum-sum subsequence.<br />
<br />
Solution:<br />
This does not seem Haskell code to me.<br />
If the argument: Learning Haskell were valid pure Haskell code would have been given.<br />
<br />
<haskell><br />
#include<stdio.h><br />
#define N 2000<br />
#define max(a,b) ((a) > (b) ? (a) : (b))<br />
int s[4000001];<br />
int MaxSubsequenceSum(int s[] , int n) {<br />
int j;<br />
int ThisSum, MaxSum ;<br />
ThisSum = MaxSum = 0;<br />
for ( j=0; j<n ; j++)<br />
{<br />
ThisSum += s[j];<br />
if (ThisSum> MaxSum)<br />
MaxSum = ThisSum;<br />
else if (ThisSum < 0)<br />
ThisSum = 0;<br />
}<br />
return MaxSum;<br />
}<br />
long long Generate(int ind){<br />
long long k = ind;<br />
if (ind <= 55) <br />
return ((100003 - 200003*k + 300007*k*k*k) % 1000000) - 500000;<br />
return (s[k-24]+s[k-55]+1000000)%1000000-500000;<br />
<br />
}<br />
int main()<br />
{<br />
int sums=0;<br />
int maxx=0;<br />
for (int i=1;i<4000001;i++){<br />
s[i]=(int)(Generate(i));<br />
}<br />
printf("%d %d \n",s[10],s[100]);<br />
int ks[N],kss[N];<br />
for (int k=0;k<N;k++){<br />
for(int b=0;b<N;b++)<br />
{ <br />
ks[b]=s[k*N+b+1]; <br />
kss[b]=s[b*N+k+1]; <br />
}<br />
sums=MaxSubsequenceSum(ks,N);<br />
sums=max(sums,MaxSubsequenceSum(kss,N));<br />
maxx=max (maxx,sums);<br />
}<br />
int ksi,ksj, x,y,y1;<br />
for (int k=-N+1;k<N;k++){<br />
ksi=ksj=0;<br />
for(int b=0;b<N;b++)<br />
{ <br />
x=k+b;<br />
y=b;<br />
y1=N-1-b;<br />
if (x>-1 && x<N && y>-1 && y<N)<br />
ks[ksi++]=s[x*N+y+1];<br />
if (x>-1 && x<N && y1>-1 && y1<N)<br />
kss[ksj++]=s[x*N+y1+1];<br />
}<br />
sums=MaxSubsequenceSum(ks,ksi);<br />
sums=max(sums,MaxSubsequenceSum(kss,ksj));<br />
maxx=max (maxx,sums);<br />
}<br />
printf("%d\n",maxx);<br />
}<br />
problem_149 = main<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=problems&id=150 Problem 150] ==<br />
Searching a triangular array for a sub-triangle having minimum-sum.<br />
<br />
Solution:<br />
This does not seem Haskell code to me.<br />
If the argument: Learning Haskell were valid pure Haskell code would have been given.<br />
<br />
<haskell><br />
#include <stdio.h><br />
<br />
int s[1024][1024];<br />
long long rs[1024][1024];<br />
<br />
int main()<br />
{<br />
int t=0,k,x=0,y=0,i,j,w,M=1000;<br />
long long answer=1000000000,cur;<br />
<br />
for(k=0;k<500500;k++) {<br />
t=((615949*t+797807+(1<<20))%(1<<20)+(1<<20))%(1<<20);<br />
s[x++][y]=t-(1<<19);<br />
if(x==y+1) x=0,y++;<br />
}<br />
for(j=0;j<M;j++) for(rs[0][j]=i=0;i<=j;i++) rs[i+1][j]=rs[i][j]+s[i][j];<br />
for(j=0;j<M;j++) for(i=0;i<=j;i++) {<br />
for(cur=0,w=1,k=j;k<M;k++,w++) {<br />
cur+=rs[i+w][k]-rs[i][k];<br />
if(cur<answer) answer=cur;<br />
}<br />
}<br />
printf("%lld\n",answer);<br />
}<br />
problem_150 = main<br />
</haskell></div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Euler_problems/71_to_80&diff=19380Euler problems/71 to 802008-02-23T23:05:10Z<p>Daniel.is.fischer: </p>
<hr />
<div>== [http://projecteuler.net/index.php?section=view&id=71 Problem 71] ==<br />
Listing reduced proper fractions in ascending order of size.<br />
<br />
Solution:<br />
<haskell><br />
-- http://mathworld.wolfram.com/FareySequence.html <br />
import Data.Ratio ((%), numerator,denominator)<br />
fareySeq a b<br />
|da2<=10^6=fareySeq a1 b<br />
|otherwise=na<br />
where<br />
na=numerator a<br />
nb=numerator b<br />
da=denominator a<br />
db=denominator b<br />
a1=(na+nb)%(da+db)<br />
da2=denominator a1<br />
problem_71=fareySeq (0%1) (3%7)<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=72 Problem 72] ==<br />
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?<br />
<br />
Solution:<br />
<br />
Using the [http://mathworld.wolfram.com/FareySequence.html Farey Sequence] method, the solution is the sum of phi (n) from 1 to 1000000.<br />
<haskell><br />
groups=1000<br />
eulerTotient n = product (map (\(p,i) -> p^(i-1) * (p-1)) factors)<br />
where factors = fstfac n<br />
fstfac x = [(head a ,length a)|a<-group$primeFactors x] <br />
p72 n= sum [eulerTotient x|x <- [groups*n+1..groups*(n+1)]]<br />
problem_72 = sum [p72 x|x <- [0..999]]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=73 Problem 73] ==<br />
How many fractions lie between 1/3 and 1/2 in a sorted set of reduced proper fractions?<br />
<br />
Solution:<br />
This was my code, published here without my permission nor any attribution, shame on whoever put it here. [[User:Daniel.is.fischer|Daniel.is.fischer]]<br />
<br />
== [http://projecteuler.net/index.php?section=view&id=74 Problem 74] ==<br />
Determine the number of factorial chains that contain exactly sixty non-repeating terms.<br />
<br />
Solution:<br />
<haskell><br />
import Data.List<br />
explode 0 = []<br />
explode n = n `mod` 10 : explode (n `quot` 10)<br />
<br />
chain 2 = 1<br />
chain 1 = 1<br />
chain 145 = 1<br />
chain 40585 = 1<br />
chain 169 = 3<br />
chain 363601 = 3<br />
chain 1454 = 3<br />
chain 871 = 2<br />
chain 45361 = 2<br />
chain 872 = 2<br />
chain 45362 = 2<br />
chain x = 1 + chain (sumFactDigits x)<br />
makeIncreas 1 minnum = [[a]|a<-[minnum..9]]<br />
makeIncreas digits minnum = [a:b|a<-[minnum ..9],b<-makeIncreas (digits-1) a]<br />
p74=<br />
sum[div p6 $countNum a|<br />
a<-tail$makeIncreas 6 1,<br />
let k=digitToN a,<br />
chain k==60<br />
]<br />
where<br />
p6=facts!! 6<br />
sumFactDigits = foldl' (\a b -> a + facts !! b) 0 . explode<br />
factorial n = if n == 0 then 1 else n * factorial (n - 1)<br />
digitToN = foldl' (\a b -> 10*a + b) 0 .dropWhile (==0)<br />
facts = scanl (*) 1 [1..9]<br />
countNum xs=ys<br />
where<br />
ys=product$map (factorial.length)$group xs <br />
problem_74= length[k|k<-[1..9999],chain k==60]+p74<br />
test = print $ [a|a<-tail$makeIncreas 6 0,let k=digitToN a,chain k==60]<br />
</haskell><br />
== [http://projecteuler.net/index.php?section=view&id=75 Problem 75] ==<br />
Find the number of different lengths of wire can that can form a right angle triangle in only one way.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Array<br />
<br />
triplets = <br />
[p | <br />
n <- [2..706],<br />
m <- [1..n-1],<br />
gcd m n == 1, <br />
let p = 2 * (n^2 + m*n),<br />
odd (m + n),<br />
p <= 10^6<br />
]<br />
<br />
hist bnds ns = <br />
accumArray (+) 0 bnds [(n, 1) |<br />
n <- ns,<br />
inRange bnds n<br />
]<br />
<br />
problem_75 = <br />
length $ filter (\(_,b) -> b == 1) $ assocs arr<br />
where<br />
arr = hist (12,10^6) $ concatMap multiples triplets<br />
multiples n = takeWhile (<=10^6) [n, 2*n..]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=76 Problem 76] ==<br />
How many different ways can one hundred be written as a sum of at least two positive integers?<br />
<br />
Solution:<br />
<br />
Here is a simpler solution: For each n, we create the list of the number of partitions of n<br />
whose lowest number is i, for i=1..n. We build up the list of these lists for n=0..100.<br />
<haskell><br />
build x = (map sum (zipWith drop [0..] x) ++ [1]) : x<br />
problem_76 = (sum $ head $ iterate build [] !! 100) - 1<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=77 Problem 77] ==<br />
What is the first value which can be written as the sum of primes in over five thousand different ways?<br />
<br />
Solution:<br />
<br />
Brute force but still finds the solution in less than one second.<br />
<haskell><br />
counter = foldl (\without p -><br />
let (poor,rich) = splitAt p without<br />
with = poor ++ <br />
zipWith (+) with rich<br />
in with<br />
) (1 : repeat 0)<br />
<br />
problem_77 = <br />
find ((>5000) . (ways !!)) $ [1..]<br />
where<br />
ways = counter $ take 100 primes<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=78 Problem 78] ==<br />
Investigating the number of ways in which coins can be separated into piles.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Array<br />
<br />
partitions :: Array Int Integer<br />
partitions = <br />
array (0,1000000) $ <br />
(0,1) : <br />
[(n,sum [s * partitions ! p|<br />
(s,p) <- zip signs $ parts n])|<br />
n <- [1..1000000]]<br />
where<br />
signs = cycle [1,1,(-1),(-1)]<br />
suite = map penta $ concat [[n,(-n)]|n <- [1..]]<br />
penta n = n*(3*n - 1) `div` 2<br />
parts n = takeWhile (>= 0) [n-x| x <- suite]<br />
<br />
problem_78 :: Int<br />
problem_78 = <br />
head $ filter (\x -> (partitions ! x) `mod` 1000000 == 0) [1..]<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=79 Problem 79] ==<br />
By analysing a user's login attempts, can you determine the secret numeric passcode?<br />
<br />
Solution:<br />
<haskell><br />
import Data.Char (digitToInt, intToDigit)<br />
import Data.Graph (buildG, topSort)<br />
import Data.List (intersect)<br />
<br />
p79 file= <br />
(+0)$read . intersect graphWalk $ usedDigits<br />
where<br />
usedDigits = intersect "0123456789" $ file<br />
edges = concat . map (edgePair . map digitToInt) . words $ file<br />
graphWalk = map intToDigit . topSort . buildG (0, 9) $ edges<br />
edgePair [x, y, z] = [(x, y), (y, z)]<br />
edgePair _ = undefined<br />
<br />
problem_79 = do<br />
f<-readFile "keylog.txt"<br />
print $p79 f<br />
</haskell><br />
<br />
== [http://projecteuler.net/index.php?section=view&id=80 Problem 80] ==<br />
Calculating the digital sum of the decimal digits of irrational square roots.<br />
<br />
Solution:<br />
<haskell><br />
import Data.Char<br />
problem_80=<br />
sum [f x |<br />
a <- [1..100],<br />
x <- [intSqrt $ a * t],<br />
x * x /= a * t<br />
]<br />
where<br />
t=10^202<br />
f = (sum . take 100 . map (flip (-) (ord '0') .ord) . show)<br />
</haskell></div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Talk:Euler_problems&diff=19305Talk:Euler problems2008-02-23T15:33:34Z<p>Daniel.is.fischer: </p>
<hr />
<div>As one of the teammembers of Project Euler I must say that you are doing Project Euler not a great favour by maintaining this site.<br />
How is it possible that you are so blinded by your enthousiasm of a particular programming environment that you lose out of sight the true nature of Project Euler: problem solving, disregarding all differences of programming languages.<br />
As all problems are there, even the most recent ones, those responsible for this must be found among our 100%-ers.<br />
Please realise how much work of us you are spoiling with this work and stop spoling our work. Better still: remove it altogether from public domain.<br />
Threatening to consider any amendment as vandalism is really a gotspe.<br />
It's you that are vandalising our work.<br />
<br />
Hans Klein (aka hk) <br />
<br />
-----<br />
These pages must be deleted.<br />
<br />
They are not in the spirit of Project Euler.<br />
<br />
They are ruining the fun of problems and the fun of climbing up the ladder.<br />
<br />
I am aware that whoever posted this is probably smart and would like us all to know.<br />
<br />
Meanwhile:<br />
<br />
RULE #1 of Project Euler:<br />
<br />
You do not discuss Project Euler solutions.<br />
<br />
RULE #2 of Project Euler:<br />
<br />
You do not discuss Project Euler solutions.<br />
<br />
Keep it in the problem threads.<br />
<br />
----<br />
<br />
I disagree. These are clearly marked as "spoilers". Anyone<br />
who wants to participate in Project Euler and enjoy its<br />
benefits knows that they should not peek at these solutions.<br />
<br />
On the other hand, this problem space is perfect for<br />
illustrating the power of Haskell, and for providing<br />
excellent examples of how to "think in Haskell".<br />
I would refer anyone thinking of learning Haskell to<br />
these pages - with the warning that they might<br />
first want to solve all of the problems in their<br />
current favorite programming language.<br />
<br />
My guess is that many people would look at the<br />
first few solutions, become hooked, and then<br />
redo the rest of them on their own in Haskell<br />
without peeking!<br />
<br />
----<br />
You kill the fun! <br />
<br />
There is only way to publish solution - just protect access to it <br />
with right solution answer, as Euler protects access <br />
to forum's threads.<br />
<br />
But in wiki - these pages must be deleted.<br />
<br />
----<br />
<br />
Note that if you delete these pages, it will be treated as vandalism and reverted. [[User:CaleGibbard|CaleGibbard]] 19:56, 21 February 2008 (UTC)<br />
<br />
----<br />
Category tags are great for making the Haskell wiki easier<br />
to navigate. But having category tags on all of the detail<br />
pages of these problem sets has the opposite effect - it<br />
just clutters the category pages.<br />
<br />
I am removing the category tags from all of the detail pages,<br />
and leaving them only on the main page.<br />
<br />
----<br />
<br />
Either restrict the access to these pages to those who have the solution or delete them, please. It's just not cricket to violate the Project Euler spirit. [[User:Daniel.is.fischer|Daniel.is.fischer]]</div>Daniel.is.fischerhttps://wiki.haskell.org/index.php?title=Talk:Euler_problems/181_to_190&diff=19304Talk:Euler problems/181 to 1902008-02-23T15:22:22Z<p>Daniel.is.fischer: </p>
<hr />
<div>As far as I can see this solution to problem 181 is the solution posted by Daniel.is.Fischer posted in our problem 181 forum.<br />
Now there are two possibilities:<br />
Daniel posted it here (unlikely) or this solution was "stolen" from that Forum and not your own work. Cannot you solve it on your own?<br />
<br />
I most certainly didn't put it here, and I'm rather annoyed about it. [[User:Daniel.is.fischer|Daniel.is.fischer]]</div>Daniel.is.fischer