Bertram Felgenhauer wrote two wonderful implementations of power_list:
power_list :: [a] - [[a]]
power_list [] = [[]]
power_list (x:xs) = add_x (assert_first_empty $ power_list xs) x
where assert_first_empty ~([]:xs) = []:xs
add_x [] _ = []
add_x (y:ys) x
Richard O'Keefe [EMAIL PROTECTED] wrote:
Another change to the order to give us MORE sharing takes less time
AND less space. The surprise is how much less time.
Interesting stuff. My students and I briefly chatted about powerset
this morning and came up with the same function, but the very
I wrote:
This CSE-makes-it-worse property strikes me as interesting.
Has anyone worked on characterizing CSE space leaks (and avoiding
CSE in those cases)?
and Simon replied:
You might find chapter 23 The pragmatics of graph reduction in my
1987 book worth a look. It gives other
apfelmus wrote:
After some pondering, the List a data structure for merging is
really
ingenious! :) Here's a try to explain how it works:
Thanks apfelmus! A detailed explanation of this code is really
helpful for anyone trying to understand what is going on. The VIP/
Crowd analogy is
When advocating functional languages like Haskell, one of the claims
I've tended to make is that referential transparency allows the
language to be much more aggressive about things like common
subexpression elimination (CSE) than traditional imperative languages
(which need to worry about
Dave Bayer wrote:
Here is another prime sieve.
It's great to know people are still having fun with this stuff...
I've added your implementation to the zipfile available at
http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip
(FWIW, I added specializations for Int and Integer and also
Neil Mitchell wrote:
-O3 is slower than -O2 and -O in ghc? If you want fast code then
specify -O2, not -O3.
Oops. That ought to have been -O2.
But from what I can tell, -O3 is harmless (at least in this case).
Both invocations generate identical executables, at least for these
examples
Although I hate to resort to dictionaries, curiosity got the better
of me and I find the following.
According to both Merriam Webster and the OED, monad is indeed
pronounced exactly like gonad. BUT, in the UK at least, there is
more than way to pronounce gonad, so it doesn't necessarily
For those enjoying the fun with prime finding, I've updated the
source at
http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip
I've tweaked my code a little to improve its space behavior when
finding primes up to some limit, added an up-to-limit version of the
Naive Primes algorithm,
Claus Reinke wrote:
folklore3: merging the sieves, instead of stacking them as
implicit thunks
Here's Claus's code:
primes3 = 2 : folklore3 [] [3,5..]
folklore3 pns xs = x : folklore3 (insert (x,x*x) pns') xs'
where (x,pns',xs') = sieve3 pns xs
sieve3 ((p,n):pns) (x:xs) | xn =
Claus, you're absolutely right that my paper could be improved in a
number of ways, and that there is actually a surprising amount of
meat on these bones for further analysis. We'll see what happens.
If it actually gets accepted for JFP, it'll undoubtedly finally
appear as a revised
Someone asked if I'd include a classic C version of the Sieve in my
comparisons. Having done so, Lennart wrote (slightly rephrased):
How did you compare the C version with the Haskell versions? The
Haskell programs produce the Nth prime, whereas the C code produces
the last prime less than
*sigh* don't click send at 2:30am...
I wrote:
The algorithm named Naive in my table is called SimplePrimes in
the zip file, and the example named sieve in my table is called
NaivePrimes in the zip file.
The algorithm named Naive in my table is called SimplePrimes in the
zip file, and the
Ruben Zilibowitz wrote:
I see that there has been some discussion on the list about prime
finding algorithms recently. I just wanted to contribute my own
humble algorithm:
Thanks!
Comparing it to some of the algorithms in:
http://www.haskell.org/pipermail/haskell-cafe/2007-February/
Sorry, I'm a little late to this thread, but the topic of
sieve [] = []
sieve (x:xs) = x : sieve [y | y - xs, y `mod` x /= 0]
(as posted by Rafael Almeida) is somewhat dear to my heart, as I
wrote a paper about it last summer and sent it in to JFP. Still
waiting for a reply though.
Let's
apfelmus wrote:
I think that the `mod`-algorithm counts as sieve, it just does a
bad job at organizing the crossing off.
I'd say that it might count as a sieve, but *algorithmically* it is
not The Sieve of Eratosthenes. If you abstract away the
algorithmic details to a mathematical
16 matches
Mail list logo
