- Haskell-Cafe - Haskell.org

Genuine Eratosthenes sieve [Was: Optimization fun]
by oleg＠pobox.com 12 Feb '07

12 Feb '07

It has been already remarked that any algorithm of finding prime numbers that uses division or `mod` operations cannot be called (Eratosthenes) sieve. The insight of Eratosthenes is finding primes without resorting to division or multiplication. In his time, doing either of those operations was quite expensive (especially given the way numbers were written in Ancient Greece). Thus Eratosthenes devised one of the early examples of trading space for time. These days it's the other way around: it is far easier for a modern CPU to divide numbers than to access memory. So, the original algorithm is of historical interest it seems. Still, in the interest of purity, here it is, in Haskell. As the original Eratosthenes sieve, this algorithm uses only successor and predecessor operations. -- repl_every_n n l replaces every (n+1)-th element in a list (_:l) with 0 {- The following leaks memory! repl_every_n :: Int -> [Int] -> [Int] repl_every_n n l = case splitAt n l of (l1,_:l2) -> l1 ++ 0:(repl_every_n n l2) -} -- But this seems to run in constant space... repl_every_n :: Int -> [Int] -> [Int] repl_every_n n l = repl_every_n' n l where repl_every_n' 0 (_:t) = 0: repl_every_n n t repl_every_n' i (h:t) = h: repl_every_n' (pred i) t primes = 2:(loop [3,5..]) where loop l = case dropWhile (==0) l of (h:t) -> h:(loop (repl_every_n (pred h) t)) main = putStrLn $ "Last 10 primes less than 100000: " ++ show (take 10 $ reverse $ takeWhile (< 100000) primes) {- Last 10 primes less than 1000: [997,991,983,977,971,967,953,947,941,937] -} {- Last 10 primes less than 10000: [9973,9967,9949,9941,9931,9929,9923,9907,9901,9887] -} {- Last 10 primes less than 100000: [99991,99989,99971,99961,99929,99923,99907,99901,99881,99877] -}

2 1

Re: [Haskell-cafe] Lambada and connecting Haskell to a Weblogic server
by Joel Reymont 11 Feb '07

11 Feb '07

Yep, don't have access to the Weblogic server. I'm re-evaluating my options, though, since I'm lazy by nature. On Feb 11, 2007, at 12:30 PM, Neil Bartlett wrote: > Joel, > > Implementing Java RMI in Haskell sounds like a nightmare. Why not > use HTTP? You could easily write a wrapper Servlet that speaks XML > or JSON over HTTP, and deploy that to the Weblogic server. Unless > you don't have permission to deploy anything to that server for > whatever reason. -- http://wagerlabs.com/

1 0

Re: [Haskell-cafe] What's wrong with "cgi-undecidable"?
by Matthew Brecknell 11 Feb '07

11 Feb '07

<keepbal(a)gmail.com> said: > Then another problem,after I unregistered cgi-2006.9.6,the > fastcgi-2006.10.9could't work well with > cgi-1.0 . You might need fastcgi-1.0: http://www.cs.chalmers.se/~bringert/darcs/haskell-fastcgi > Actually,I was trying my best to install hope: > http://www.cs.chalmers.se/~bringert/darcs/hope and lasted for three > days, > it's really too hard. Would I be right to think that your problems are not specifically related to the cgi/fastcgi/hope code-base, but more general problems diagnosing package version conflicts? The Haskell community has been working hard to improve various aspects of the user experience. Perhaps if you describe the kinds of issues you had (and any solutions you've found), others on the list might be motivated to provide a better experience for future users.

5 5

Beginner Question
by vishy anand 10 Feb '07

10 Feb '07

I have just started on my journey in learning Haskell.I have started off reading wikibook,then will read yet another tutorial on haskell.Please guide me if I am on right track thks

3 2

Fwd: [Haskell-cafe] Optimization fun
by Peter Berry 10 Feb '07

10 Feb '07

Gah! Gmail has really broken defaults for posting to lists. On 10/02/07, Creighton Hogg <wchogg(a)gmail.com> wrote: > Hello Haskell-ers, > So a friend and I were thinking about making code faster in Haskell, and I > was wondering if there was a way to improve the following method of > generating the list of all prime numbers. It takes about 13 seconds to run, > meanwhile my friend's C version took 0.1. I'd love to learn a bit more > about how to optimize Haskell code. Which subproblem takes 13 seconds? (Surely generating a list of all primes will take an infinite amount of time, since there are infinitely many of them?) -- Peter Berry <pwberry(a)gmail.com> Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html

3 2

Re: [Haskell-cafe] Haskell soltion ofr I/O: is it monads or uniqueness types, after all?
by Stefan O'Rear 10 Feb '07

10 Feb '07

Gah. For the first time ever, I seem to have accidentally done a reply to sender. (IE Bulat please ignore this message) On Sat, Feb 10, 2007 at 07:25:19PM +0300, Bulat Ziganshin wrote: > Hello haskell-cafe, > > just another interesting discussion in russian forum raised such idea: > > we all say that monads are the haskell way to do i/o. is it true? may > be, uniqueness types, just like in Clean and Mercury, are real way, and > monads are only the way to write programs that use uniqueness types > easier? > > so, IO monad is like any other monad - it simplifies writing of > complex code, but by itself it don't solve any problems. all code that > can be written with monads can also be written using ordinal function > calls. we know it for IO monad too - in ghc, we can use low-level > representation of IO type and write imperative code without use of > any monad operators Just because Jhc, GHC, and Yhc (any others? any non-others?) all use RealWorld# tokens, doesn't mean it's the only way to implement IO. Note that unsafePerformIO will need to be a primitive... data Process = Getc (Char -Process) | Putc Char (() -Process) | forall a. NewIORef a (IORef a -Process) | forall a. ReadIORef (IORef a) (a -Process) | forall a. WriteIORef (IORef a) a (() -Process) | Exit {- IORef is specifically mentioned because it is the canonical example of something IO can do that 1.2-style streams can't -} type IO = Cont Process -- using Cont monad's monad getChar = Cont $ Getc putChar = Cont . Putc newIORef = Cont . NewIORef readIORef = Cont . ReadIORef writeIORef a b = Cont $ WriteIORef a b exit = Cont $ \_ -Exit {- in runtime, forgive my rusty C -} int main() { init_runtime_foo(); thunk* tree = hseval("runCont main Exit") while(1) { whnf(tree); switch (tree->tag) { case _Getc: char ch = getchar(); thunk* hch = hs_wrapchar(ch); tree = hsmkapp( tree->payload(0) , hch ); continue; ... case _Exit: return 0; } } } of course, this doesn't refute the non-primitive-ness of IO, but it does refute the uniqueness types part.

2 2

Haskell soltion ofr I/O: is it monads or uniqueness types, after all?
by Bulat Ziganshin 10 Feb '07

10 Feb '07

Hello haskell-cafe, just another interesting discussion in russian forum raised such idea: we all say that monads are the haskell way to do i/o. is it true? may be, uniqueness types, just like in Clean and Mercury, are real way, and monads are only the way to write programs that use uniqueness types easier? so, IO monad is like any other monad - it simplifies writing of complex code, but by itself it don't solve any problems. all code that can be written with monads can also be written using ordinal function calls. we know it for IO monad too - in ghc, we can use low-level representation of IO type and write imperative code without use of any monad operators -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 1

Embedding ghc
by Joel Reymont 10 Feb '07

10 Feb '07

Has anyone tried embedding ghc into their app? How big are the resulting binaries? Thanks, Joel -- http://wagerlabs.com/

1 0

Query
by vishy anand 10 Feb '07

10 Feb '07

hi i am going through yaht tutorial and exercise 4.6 and 4.7..i understood 4.6,but not 4.7 in which fromTuple (One a ) = Left (Left a ) and fromTuple (Two a b ) = Left (Right (a,b) ) function r written..why use Either type..cant i just say fromTuple (Two a b )=(a,b)

2 1

What's wrong with "cgi-undecidable"?
by keepbal 09 Feb '07

09 Feb '07

http://darcs.haskell.org/packages/cgi-undecidable/ There only 3 or 4 lines of source code, but it can't be installed. The ghc version is 6.6 . Undecidable.hs:23:0: Duplicate instance declarations: instance [overlap ok] (MonadTrans t, MonadCGI m, Monad (t m)) => MonadCGI (t m) -- Defined at Undecidable.hs:23:0 instance [overlap ok] (MonadTrans t, MonadCGI m, Monad (t m)) => MonadCGI (t m) -- Defined in Network.CGI.Monad

2 1