Back to General and Gameplay Programming

Imperative Haskell programming

General and Gameplay Programming Programming

Started by ravengangrel July 11, 2009 07:01 AM

15 comments, last by Daerax 14 years, 9 months ago

ravengangrel

406

Author

July 11, 2009 07:01 AM

Some time ago a bunch of guys here recommended me Haskell as my first functional language. I've read some tutorials and followed the advice of one guy to try to solve the problems in Project Euler to get some pratice. I have solved a couple of problems and found Haskell to be really cool to this sort of math programming, but I have found one that seems an inherently imperative problem.

Quote:By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13. What is the 10001^(st) prime number?

without optimizing too much, this seems fairly easy in c (assuming number doesn't overflows, about which I can't be sure):


int i = 0;
long long number = 2;
while (i < 10001)
{
    if (isPrime(number++))
        i++;
}

Now I'm very puzzled about how to solve this in Haskell. I think we can make a recursive list requiring that each element is strictly greater than the previous one and that each element is prime. Is this the functional way to do this? Any better approach? I don't want the solution, just a theoretical discussion about the functional way to do this sort of things.

dmatter

4,872

July 11, 2009 07:18 AM

Rewrite that C code as a recursive solution, that should then more easily translate into Haskell [smile].

David Gill :: GitHub :: twitter .

DevFred

840

July 11, 2009 07:34 AM

When looking for the n-th number that satisfies some condition, it is idiomatic in Haskell to just describe all numbers that satisfy that condition, and then simply pick the n-th one from the list.

import Data.List (nubBy)primes = nubBy (\prime candidate -> gcd prime candidate > 1) [2..]

Usage:

GHCi, version 6.10.2: http://www.haskell.org/ghc/  :? for helpLoading package ghc-prim ... linking ... done.Loading package integer ... linking ... done.Loading package base ... linking ... done.[1 of 1] Compiling Main             ( prime.hs, interpreted )Ok, modules loaded: Main.*Main> primes !! 1031*Main> primes !! 100547*Main> primes !! 10007927*Main>

The 1000th number already takes quite a while to compute. You definitely need a more sophisticated method of generating prime numbers in order to compute the 10001th prime number before the universe ends ;)

ScottMayo

126

July 11, 2009 07:52 AM

Haskell is a very cool language for many sorts of problems, and there are some twisted problems which are simpler in Haskell than any imperative language. But it's nothing you turn to if you need execution speed. Prime number generation requires speed, if you want big primes.

I've used it occasionally for playing with an idea, and once I get my idea working I move the implementation to something faster.

Ezbez

1,164

July 11, 2009 08:23 AM

@ScottMayo - If Haskell truly is too slow to find the 10001st prime in under a minute, then I would agree with you that it shouldn't be used for anything beyond experimentation. However, I find that claim *highly* unlikely. I've got no experience in Haskell, but my dumb brute-force solution written in Scheme solves this problem in around 1 second. That's without using even a sieve of Eratosthenes.

DevFred

840

July 11, 2009 09:16 AM

Quote:Original post by Ezbez
If Haskell truly is too slow to find the 10001st prime in under a minute

It's the algorithm's fault, not Haskell's. For faster alternatives, look here.

Ezbez

1,164

July 11, 2009 09:46 AM

Quote:Original post by DevFred
Quote:Original post by Ezbez
If Haskell truly is too slow to find the 10001st prime in under a minute

It's the algorithm's fault, not Haskell's. For faster alternatives, look here.

I'm expressing doubt that Haskell couldn't calculate the 10001st prime in the absolute most direct brute-force method (ie: a direct translation of the C code in the OP) in under a minute. I'm well aware of better algorithms (I mentioned the sieve of Eratosthenes in my previous post), yet I note that even in "slow" interpreted languages like Scheme the dumb, brute-force method still takes only a second.

I haven't used Haskell - is Haskell truly so slow that such an approach would be infeasible? Is Haskell really orders of magnitude slower than Scheme for such tasks?

Daerax

1,207

July 11, 2009 11:28 AM

Haskell is not an imperative language. It actually has no support for mutability. Much state based things in it are really just elaborate hacks - UnsafeIO monad. Trying to translate imperative algorithims straight is not going to learn you anything. None idiomatic haskell is ugly and verbose and pointless. Here is a simple sieve based prime generator that is the brute force way of haskell:

sieve (n : xs) = n : sieve (filter (\ m -> (rem m n) /= 0) xs)primes = sieve [2..]take 1000 primes -- will instantly list first 1000 primes.

It is short and clear and the naive way. But far more elegant than the naive imperative manner. To improve stuff like that you look to other stuff like Fermat little theorem.

Although Haskell is fast enough for most problems if you need metal biting speed the ugly sacrifices required to get it is pointless better to use other language (BitC soon). But Haskell tends to be faster than scheme.

ScottMayo

126

July 11, 2009 03:26 PM

Quote:
I haven't used Haskell - is Haskell truly so slow that such an approach would be infeasible? Is Haskell really orders of magnitude slower than Scheme for such tasks?

No. It's not really that bad; the lazy execution scheme does a good job of skipping irrelevant work. But I was assuming that there's no real interest in identifying the 100001'th prime - that one's not hard to find, and occurs shortly after 104729 - but in getting big primes. And for that sort of work you want tight algorithms and bare-metal speeds, on distributed processors.

Haskell is kind of cool, but I never end up building anything with it that I keep. It's great for getting your head around a problem, though.

Zahlman

1,682

July 11, 2009 03:54 PM

If you really want to look at it ground-up in the functional way:

The N+1th prime is the smallest prime number larger than the Nth prime.

The smallest prime number larger than X is

X+1, if X+1 is prime;
otherwise, the smallest prime number larger than X+1.

So we recurse in two ways: on prime count, and on values above the previous prime.

Imperative Haskell programming

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Imperative Haskell programming

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines