Heinrich Apfelmus apfelmus at quantentunnel.de writes:
Will Ness wrote:
Heinrich Apfelmus writes:
Here an example where the VIP merge would give a different result
bad = tfold $ (1:10:undefined) : (2:3:5:undefined) : (4:undefined) :
error bad
The reason
Will Ness will_n48 at yahoo.com writes:
... they *both* turn out to be
*completely* and utterly *wrong* :) in a general case (although probably for
different reasons).
Sorry, my bad. Thought in terms of merge, but the definiton used in VIP code
was really an union.
When definition
-
List-Ordered.html#v:mergeAll
Will Ness
primes = 2: primes'
where
primes' = 3: 5: [7,9..] `minus` tfold
[ [p*p,p*p+2*p..] | p - primes' ]
tfold ((x:xs):t)= x : xs `union` tfold (pairs t)
pairs ((x:xs):ys:t) = (x: union xs ys) : pairs t
Hi,
For those who remember the discussion about this about a year ago, it turns out
there was a simpler version after all lurking somewhere in there (or is it
_out_?).
I've just posted it to the haskellwiki's Prime Numbers page:
primes = 2: primes'
where
primes' = 3: 5: [7,9..]
Derek Elkins derek.a.elkins at gmail.com writes:
On Wed, Jan 20, 2010 at 9:42 AM, Will Ness will_n48 at yahoo.com wrote:
Derek Elkins derek.a.elkins at gmail.com writes:
On Sun, Jan 17, 2010 at 2:22 PM, Will Ness will_n48 at yahoo.com wrote:
Hello cafe,
I wonder, if we have
Heinrich Apfelmus apfelmus at quantentunnel.de writes:
Will Ness wrote:
You can check it out on the Haskellwiki Prime Numbers page (work still in
progress, the comparison tables are missing). We had also a recent thread
here
in cafe under FASTER primes. The original idea of Heinrich
Derek Elkins derek.a.elkins at gmail.com writes:
On Sun, Jan 17, 2010 at 2:22 PM, Will Ness will_n48 at yahoo.com wrote:
Hello cafe,
I wonder, if we have List.insert and List.union, why no List.merge (:: Ord
a =
[a] - [a] - [a]) and no List.minus ? These seem to be pretty general
Christian Maeder Christian.Maeder at dfki.de writes:
Will Ness schrieb:
I meant strictly increasing ordered lists, without multiples, for which the
two
operations, 'merge' and 'minus', would also have to produce like lists, i.e
strictly increasing, without multiples.
Why don't you
Hello cafe,
I wonder, if we have List.insert and List.union, why no List.merge (:: Ord a =
[a] - [a] - [a]) and no List.minus ? These seem to be pretty general
operations.
Brief look into haskell-prime-report/list.html reveals nothing.
Could we please have them?
On the wider perspective, is
Daniel Fischer daniel.is.fischer at web.de writes:
Am Donnerstag 14 Januar 2010 08:25:48 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Mittwoch 13 Januar 2010 10:43:42 schrieb Heinrich Apfelmus:
I wonder whether it's really the liveness of pair
Daniel Fischer daniel.is.fischer at web.de writes:
Am Mittwoch 13 Januar 2010 10:43:42 schrieb Heinrich Apfelmus:
I wonder whether it's really the liveness of pair in
mergeSP (a,b) pair
= let sm = spMerge b (fst pair)
in (a ++ fst sm, merge (snd sm) (snd pair))
Daniel Fischer daniel.is.fischer at web.de writes:
Am Freitag 08 Januar 2010 19:45:47 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
mergeSP :: Integral a = People a - People a - People a
mergeSP p1@(P a _) p2 = P (a ++ vips mrgd) (dorks mrgd)
where
Daniel Fischer daniel.is.fischer at web.de writes:
Am Donnerstag 07 Januar 2010 11:43:44 schrieb Heinrich Apfelmus:
Will Ness wrote:
Heinrich Apfelmus writes:
The below code is now a well-behaved memory citizen (3MB for the 100
millionth prime, about the same as the PQ code
Daniel Fischer daniel.is.fischer at web.de writes:
Am Samstag 09 Januar 2010 08:04:20 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Freitag 08 Januar 2010 19:45:47 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
It's not tail
Daniel Fischer daniel.is.fischer at web.de writes:
Am Donnerstag 07 Januar 2010 11:43:44 schrieb Heinrich Apfelmus:
Will Ness wrote:
Hm? In my world view, there is only reduction to normal form and I don't
see how allocate its own storage fits in there. Okasaki having shown
Daniel Fischer daniel.is.fischer at web.de writes:
The below code is now a well-behaved memory citizen (3MB for the 100
millionth prime, about the same as the PQ code). It still is considerably
slower than the PQ code.
In terms of MUT times as reported by +RTS -sstderr - as well as
Daniel Fischer daniel.is.fischer at web.de writes:
roll = scanl (+)
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:
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
wheel11 = res
where
snms = scanl (+) 11 (take 47 wheel)
nums =
Will Ness will_n48 at yahoo.com writes:
That might be why Daniel's structure is better: it plunges down faster than
mine.
treefold structure was:
(2+4) + ( (4+8) + ( (8+16) + ( (16+32) + ( (32+64) + ...
dpths: 3 4 4 5 5 66 77 8
Daniel Fischer daniel.is.fischer at web.de writes:
Am Freitag 08 Januar 2010 19:45:47 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
It's not tail-recursive, the recursive call is inside a celebrate.
It is (spMerge that is). It calls tail-recursive celebrate
Heinrich Apfelmus apfelmus at quantentunnel.de writes:
Will Ness wrote:
But I get the impression that GHC isn't working through equational
reasoning?..
I see all this talk about thunks etc.
Sure it does. Concerning the thunks, they're part of the implementation
of the reduction
Will Ness will_n48 at yahoo.com writes:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness:
euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks)
primes = 2:euler [3,5..]
Re-write:
primes = euler $ rollFrom [2
Daniel Fischer daniel.is.fischer at web.de writes:
Am Mittwoch 06 Januar 2010 00:09:07 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer:
Fix rfold:
rfold f [x] = x
rfold f xs = rfold f (pairwise f
Daniel Fischer daniel.is.fischer at web.de writes:
Am Montag 04 Januar 2010 16:30:18 schrieb Will Ness:
For me, a real smart compiler is one that would take in e.g. (sum $ take n
$ cycle $ [1..m]) and spill out a straight up math formula, inside a few
ifs maybe (just an aside
Daniel Fischer daniel.is.fischer at web.de writes:
Am Montag 04 Januar 2010 19:16:32 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Montag 04 Januar 2010 13:25:47 schrieb Will Ness:
Euler's sieve is
sieve (p:ps) xs = h ++ sieve ps (t `minus` map (p
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness:
... There are two attempts to eliminate 45.
I would say there are two requests to not have 45 in the output.
Thers are many possible ways to phrase it.
You solution
Daniel Fischer daniel.is.fischer at web.de writes:
So we must make sure that the list of composites that primes' consumes is
not the same as that which primes'' consumes.
yes that is what I had done too. Duplicated everything. Turns out, it works
exactly as you told it would when using the
Daniel Fischer daniel.is.fischer at web.de writes:
Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer:
memory still grows, but much slower, in my tests, due to the much smaller
GC time, it's a bit faster than the version with the original tfold.
Not for larger inputs (but not
Daniel Fischer daniel.is.fischer at web.de writes:
Am Sonntag 03 Januar 2010 09:54:37 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
But there's a lot of list constructuion and deconstruction necessary for
the Euler sieve.
yes. Unless, of course, s
Heinrich Apfelmus apfelmus at quantentunnel.de writes:
Will Ness wrote:
I keep thinking that storage duplication with span, filter etc. is not
really
necessary, and can be replaced with some pointer chasing - especially when
there's only one consumer present for the generated
Daniel Fischer daniel.is.fischer at web.de writes:
Am Sonntag 03 Januar 2010 09:54:37 schrieb Will Ness:
The quesion of a memory blowup with the treefolding merge still remains.
For some reason using its second copy for a feeder doesn't reduce the
memory (as reported by standalone
Daniel Fischer daniel.is.fischer at web.de writes:
Am Montag 04 Januar 2010 13:25:47 schrieb Will Ness:
Euler's sieve is
sieve (p:ps) xs = h ++ sieve ps (t `minus` map (p*) [p,p+2..])
where (h,t) = span ( p*p) xs
Not quite. That's a variant
Emil Axelsson emax at chalmers.se writes:
For me, a real smart compiler is one that would take in e.g. (sum $
take n $
cycle $ [1..m]) and spill out a straight up math formula, inside a few ifs
maybe (just an aside).
(Also an aside, I couldn't resist...)
Then I'm sure you'd
Daniel Fischer daniel.is.fischer at web.de writes:
Am Samstag 02 Januar 2010 14:13:29 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Mittwoch 30 Dezember 2009 20:46:57 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29
Will Ness will_n48 at yahoo.com writes:
... It was a big STOP sign on the way to
Postponed Filters - Euler's - Bird's merged multiples - tree-merging (with
wheel) road of little steps, and used as a justification for her to make a
big leap across the chasm towards the PQ code
Daniel Fischer daniel.is.fischer at web.de writes:
Am Mittwoch 30 Dezember 2009 20:46:57 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 20:16:59 schrieb Daniel Fischer:
especially the claim that going by primes squares
Daniel Fischer daniel.is.fischer at web.de writes:
Am Mittwoch 30 Dezember 2009 01:04:34 schrieb Will Ness:
While I haven't detected that with the primes code, I find that in my
ghci your code is approximately 2.5 times faster than ONeill or Bayer
when interpreted (no difference
Daniel Fischer daniel.is.fischer at web.de writes:
No, it's my own code. Nothing elaborate, just sieving numbers 6k±1, twice as
fast as the haskellwiki code (here) and uses only 1/3 the memory. For the
record:
.
thanks! will need to sift through it thoroughly... :) :)
BTW I
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 20:16:59 schrieb Daniel Fischer:
especially the claim that going by primes squares
is a pleasing but minor optimization,
Which it is not. It is a major optimisation. It reduces the algorithmic
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 04:38:21 schrieb Will Ness:
Now _this_, when tested as interpreted code in GHCi, runs about 2.5x times
faster than Priority Queue based code from Melissa O'Neill's ZIP package
mentioned at the haskellwiki
Eugene Kirpichov ekirpichov at gmail.com writes:
2009/12/29 Will Ness will_n48 at yahoo.com:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 04:38:21 schrieb Will Ness:
Now _this_, when tested as interpreted code in GHCi, runs about 2.5x
times
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 04:38:21 schrieb Will Ness:
Now _this_, when tested as interpreted code in GHCi, runs about 2.5x times
faster than Priority Queue based code from Melissa O'Neill's ZIP package
mentioned at the haskellwiki
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 14:34:03 schrieb Will Ness:
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag 29 Dezember 2009 04:38:21 schrieb Will Ness:
Now _this_, when tested as interpreted code in GHCi, runs about
Daniel Fischer daniel.is.fischer at web.de writes:
Gee, seems my mail server reads your posts very thoroughly today :)
I hope it's not a bad thing. :)
Am Dienstag 29 Dezember 2009 14:58:10 schrieb Will Ness:
If I realistically needed primes generated in a real life setting, I'd
apfelmus apfelmus at quantentunnel.de writes:
Dave Bayer wrote:
What I'm calling a venturi
venturi :: Ord a = [[a]] - [a]
merges an infinite list of infinite lists into one list, under the
assumption that each list, and the heads of the lists, are in
increasing order.
I
apfelmus apfelmus at quantentunnel.de writes:
~~ This is a repost, with apologies to anyone who sees this twice (I've replied
to a two years old thread, and it doesn't show up in GMANE as I thought it
would). ~~
Dave Bayer wrote:
What I'm calling a venturi
venturi :: Ord a =
Will Ness will_n48 at yahoo.com writes:
wheelSums = roll 0 wdiffs
roll = scanl (+)
wheel = wdiffs ++ wheel
wdiffs = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wdiffs
Apparently that works
Steve stevech1097 at yahoo.com.au writes:
On Tue, 2009-11-03 at 10:52 -0500, Will wrote:
I've just tried it and it was twice slower than mine. (?) I didn't use
the [Int]
signature in both. [...] It runs twice as fast with it).
Although your
code has an advantage that it is very easy
Jason Dagit dagit at codersbase.com writes:
By the way, do you understand where the speedup with Int is coming from? As I
understand it, there are two main places. One is that the type class dictionary
passing can be removed (GHC might figure this out already, I'd need to check the
core to be
Hi Steve,
Steve stevech1097 at yahoo.com.au writes:
Hi Will,
I had previously tested the Melissa O'Neil prime function (using the
primes 0.1.1 package) and found it to be fast (for a functional
approach), but with high memory use.
To fully test a prime function, I think you should:
Sjoerd Visscher sjoerd at w3future.com writes:
[...] 2 doesn't have to be in the list of smaller primes, as
we're only generating odd numbers:
primes = 2 : 3 : 5 : 7 : sieve [3] (drop 2 primes)
sieve qs@(q:_) (p:ps)
= [x | x-[q*q+2,q*q+4..p*p-2], and [(x`rem`p)/=0 | p-qs]]
Will Ness will_n48 at yahoo.com writes:
But more importantly I want it to be known that there's a lot that can be done
here, in a natural functional lazy kind of way, before resorting to priority
queues and mutable arrays. We could always just use C too. ;)
I mean it as an introductory code
Sjoerd Visscher sjoerd at w3future.com writes:
Excuse me, 2 doesn't have to be in the list of smaller primes, as
we're only generating odd numbers:
primes = 2 : 3 : 5 : 7 : sieve [3] (drop 2 primes)
sieve qs@(q:_) (p:ps)
= [x | x-[q*q+2,q*q+4..p*p-2], and [(x`rem`p)/=0 | p-qs]]
Shelby Moore shelby at coolpage.com writes:
* 1856 Thermo Law: entire universe (a closed system, i.e. everything)
trends to maximum disorder.
On the very, *very*, VERY long timescale.
In the meantime, chaos creates clashes of matter, which cause local energy
outbursts (i.e. galaxies),
Will Ness will_n48 at yahoo.com writes:
primes = 2: 3: sieve 0 primes' 5
primes' = tail primes
sieve k (p:ps) x
= [x | x - [x,x+2..p*p-2],
and [(x`rem`p)/=0 | p - take k primes']]
++ sieve (k+1) ps (p*p+2)
(thanks to Leon P.Smith for his brilliant
Jason Dagit dagit at codersbase.com writes:
On Mon, Nov 2, 2009 at 1:59 PM, Will Ness will_n48 at yahoo.com wrote:
Will Ness will_n48 at yahoo.com writes:
One _crucial_ tidbit I've left out: _type_signature_.
Adding (:: [Int]) speeds this code up more than TWICE!
:) :)
If you are okay
First, here it is:
primes = 2: 3: sieve 0 primes' 5
primes' = tail primes
sieve k (p:ps) x
= [x | x-[x,x+2..p*p-2], and [(x`rem`p)/=0 | p-take k primes']]
++ sieve (k+1) ps (p*p+2)
(thanks to Leon P.Smith for his brilliant idea of directly generating
the spans of odds
Jason Dagit dagit at codersbase.com writes:
On Mon, Oct 19, 2009 at 5:53 PM, Will Ness will_n48 at yahoo.com wrote:
You think of functions, where domain matters (for purists?). In syntax
only the result matter, does it read? Does it have an intended meaning?
How is it a mistake
wren ng thornton wren at freegeek.org writes:
Will Ness wrote:
(`foldl`2) works.
(`-`2) should too.
The `` syntax is for converting lexical identifiers into infix
operators. Symbolic identifiers are already infix, which is why ``
So it would be a no-op then. Why make
Tom Tobin korpios at korpios.com writes:
On Mon, Oct 19, 2009 at 5:34 PM, Will Ness will_n48 at yahoo.com wrote:
This syntax already exists. The '`' symbol is non-collating already, so
using it for symbol chars doesn't change anything (it's not that it
can be a part of some name, right
Gregory Propf gregorypropf at yahoo.com writes:
I actually meant it as sort of a joke but maybe it's not after all.
Seriously though, using anything non-ASCII in source code is a bad idea,
because there are lots of fonts and editors in the world.
It seems natural to me to have (`-`2)
Luke Palmer lrpalmer at gmail.com writes:
Or you could use the subtract function.
map (subtract 2) [3,4,5]
[1,2,3]
I don't want to.
I don't think syntax sugar is worth it in this case.
I do. Operators are great because they make our intent visible, immediately
apparent. Long
61 matches
Mail list logo
