- Haskell-Cafe - Haskell.org

finding primes
by S.D.Mechveliani 21 Dec '00

21 Dec '00

Hello, On generating prime numbers, people wrote ... | import Array | primes n = [ i | i <- [2 ..n], not (primesMap ! i)] where | primesMap = accumArray (||) False (2,n) multList | [..] I think that it is good for functional programming to avoid arrays, as possible. Shlomi Fish <shlomif(a)vipe.technion.ac.il> writes > [..] > primes :: Int -> [Int] > > primes how_much = sieve [2..how_much] where > sieve (p:x) = > p : (if p <= mybound > then sieve (remove (p*p) x) > else x) where > remove what (a:as) | what > how_much = (a:as) > | a < what = a:(remove what as) > | a == what = (remove (what+step) as) > | a > what = a:(remove (what+step) as) > remove what [] = [] > step = (if (p == 2) then p else (2*p)) > sieve [] = [] > mybound = ceiling(sqrt(fromIntegral how_much)) > > I optimized it quite a bit, but the concept remained the same. > > Anyway, this code can scale very well to 100000 and beyond. But it's not > exactly the same algorithm. > [..] C.Runciman <Colin.Runciman(a)cs.york.ac.uk> gives a paper reference about this. Aslo may I ask what do you mean by "can scale to 100000", the value of a prime or its position No in the list? Anyway, here are my attempts: ----------------------------------- 1. primes1 = s [(2::Int)..] :: [Int] where s (p:ns) = p: (s (filter (notm p) ns)) notm p n = (mod n p) /= 0 main = putStr $ shows (primes1!!9000) "\n" After compiling by GHC-4.08 -O2 it yields 93187 in 115 sec on Intel-586, 160 MHz. ----------------------------------- 2. The DoCon program written in Haskell (again, no arrays) gives about 10 sec (for Integer values). Also it finds, for example, first 5 primes after 10^9 as follows: take 5 $ filter isPrime [(10^9 ::Integer) ..] --> [1000000007,1000000009,1000000021,1000000033,1000000087] This takes 0.05 sec. But DoCon uses a particular isPrime test method: Pomerance C., Selfridge J.L., Wagstaff S.S.: The pseudoprimes to 25*10^9. Math.Comput., 1980, v.36, No.151, pp.1003-1026. After 25*10^9 it becomes again, expensive. ------------------ Sergey Mechveliani mechvel(a)botik.ru

2 1

finding primes
by S.D.Mechveliani 21 Dec '00

21 Dec '00

Hello, I wrote recently on generating prime numbers > [..] > The DoCon program written in Haskell (again, no arrays) gives > [..] > take 5 $ filter isPrime [(10^9 ::Integer) ..] > --> > [1000000007,1000000009,1000000021,1000000033,1000000087] > > This takes 0.05 sec. > [..] But it is better to refer to the BAL library for Haskell (basAlgPropos) http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/ It is easier to use. ------------------ Sergey Mechveliani mechvel(a)botik.ru

1 0

Preprocessor File Extension Conventions
by Ashley Yakeley 12 Dec '00

12 Dec '00

At 2000-12-11 03:26, Marcin 'Qrczak' Kowalczyk wrote: >When multiple preprocessors are being applied, it's not obvious what >extensions to use. I tried to allow such stacking in my hsc2hs >preprocessor by letting it accept any name ending in "c" and creating the >output file with this "c" removed, thus turning foo.hsc into foo.hs and >foo.lhsc into foo.lhs. > >Perhaps it would be better to mark a source to be preprocessed by >appending a whole new extension with its own dot instead of modifying the >old extension, like autoconf turning config.h.in into config.h. I prefer the other way around. For instance, compiling 'foo.c' gives object file 'foo.c.o'. A parser might start as a bison file 'parser.y', converted to 'parser.y.h' and 'parser.y.c', and compiled to object file 'parser.y.c.o'. The advantage is that you can look at the filename and see how the file was made (or how it should be made by a make tool). Also, 'foo.a' (assembly) and 'foo.c' won't collide. So 'foo.hsc' could go to 'foo.hsc.hs', and 'foo.lhsc' could go to 'foo.lhsc.hs'. >Preprocessors in general may produce more files. For example hsc2hs >sometimes produces .c and .h files as well. This requires a naming >convention too. ... 'foo.hsc.c', 'foo.hsc.h'. -- Ashley Yakeley, Seattle WA

1 0

RE: GHCi (was Re: Mixture of Integer and Float arithmetic without "fromIntegral "?)
by Simon Marlow 11 Dec '00

11 Dec '00

> On Fri, Dec 08, 2000 at 12:37:59AM -0800, Simon Peyton-Jones wrote: > > (GHCi is the revised Plan.) > > > > Incidentally, GHCi is just about working. It acts as a compiler > > with a built-in 'make' too. This is good, not because it > figures out > > dependencies, which is easy, but because it remembers the > results of one > > compilation for the next. This about doubles the speed of > compilation > > for large systems. Mixed interpreted/compiled code is on the way. > > Will it be easy to add support for preprocessors? > > Classic Hugs has a flag -F for specifying a preprocessor for > all source > files, and I've hacked an option to redefine the set of source file > suffixes. Then the preprocessor can be written to do different things > depending on the suffix. Is this sort of thing compatible with GHCi? In principle, yes. But there are several stages to GHC's compilation cycle; where exactly the user-specified preprocessing stage would fit in is something we'd need to discuss. Cheers, Simon

2 1

RE: Mixture of Integer and Float arithmetic without "fromIntegral "?
by Simon Peyton-Jones 11 Dec '00

11 Dec '00

| > OK, OK, I've just added -fno-monomorphism-restriction to GHC. | | Great! Will there also be a similar option for Stg Hugs? Yes. But it'll be GHCi, the interactive version of GHC, rather than STG Hugs. (GHCi is the revised Plan.) Incidentally, GHCi is just about working. It acts as a compiler with a built-in 'make' too. This is good, not because it figures out dependencies, which is easy, but because it remembers the results of one compilation for the next. This about doubles the speed of compilation for large systems. Mixed interpreted/compiled code is on the way. Simon

4 3

Re: GHCi, Hugs (was: Mixture ...)
by Ketil Malde 11 Dec '00

11 Dec '00

Koen Claessen <koen(a)cs.chalmers.se> writes: [Dead/dying compilers/interpreter] > I know of nobody who is starting to implement a Haskell > compiler from scratch. What do people think: is this > a worrying situation? Only if the remaining tools are insufficient, IMHO. It is questionable whether the Haskell community is large enough to support the development and maintenance of three compilers and two interpreters. Popular languages like Python and Perl have far fewer implementations, and even C and C++ only really have GCC in the free software world. It's good to have multiple tools, but at least for me, I can't seem to get around to try out tools for the sake of doing it, so I'm stuck on GHC, since it was the first I ran across, and it does an adequate (actually great, but adequate is sufficient) job of it. It'd be good if left-behind tools were using a BSD(-like) licence, in the event that anybody - commercial or otherwise - who wanted to pick them up again, were free to do so. -kzm -- I'm I haven't seen further, it is by standing in the footprints of giants

1 0

RE: Rank-2 polymorphism & type inference
by Simon Peyton-Jones 09 Dec '00

09 Dec '00

| < p y = (let f :: c -> Bool; f x = op (y >> return x) in f, y ++ []) | < q y = (y ++ [], let f :: c -> Bool; f x = op (y >> return x) in f) | < | System CT accepts both. No type signature is required. | | The types inferred for p and q are, resp.: | | Forall a,b. [a] -> (b -> Bool, [a]) and | Forall a,b. [a] -> ([a], b -> Bool) That's not the type we wanted, though. We wanted Forall a. [a] -> (Forall b. b->Bool, [a]) and similarly the other one. That's the reason for the type signature on f, which is short for (forall c. c->Bool). If you leave out the type signature then all Haskell compilers are happy. (Of course, this isn't a very useful example, but it's the smallest one that shows up the problem.) Simon

3 3

Announce: Pan release 2000-12-06
by Conal Elliott 08 Dec '00

08 Dec '00

There is a new release of Pan, a Haskell-embedded language and compiler for image synthesis, at http://research.microsoft.com/~conal/Pan I've also updated the Pan gallery with many new images for your enjoyment. The main features of this release, relative to 2000-10-04 are + Anti-aliasing for much smoother-looking images! + Render larger than the view. + ActiveX control for web pages or PowerPoint. + A recently given interactive presentation. Enjoy. - Conal ---- General description --- Pan is an experimental embedded language and compiler for image synthesis and manipulation, based on functional programming. You can get the compiler and do some Haskell programming do make your own effects, or get some of the precompiled effects and twiddle parameters to your heart's content. It's fun! The Pan compiler turns descriptions of images and image effects into efficient machine code for use with the Pan viewer program, web-page embedding (viewable with Internet Explorer 5.5 or later), or as a PhotoShop plug-in. All have automatically generated GUIs for control of the image synthesis/manipulation parameters with real-time redisplay. In the Pan viewer case the parameter settings may be saved into a small file for use later or sharing with others. See the Pan home page at http://research.microsoft.com/~conal/Pan, where you'll find a gallery of sample images and animations, papers on the language and implementation, instructions for use, and the binary and source releases. For now, Pan-generated effects run only on Windows. We welcome help in porting to other platforms. Also, the compiler assumes you have the Microsoft Visual C++, though we think it wouldn't be very hard to support other compilers and again we welcome help. Please let us know what you do with Pan, both trouble you run into and examples you construct with it (conal(a)microsoft.com)

1 0

RE: GHCi, Hugs (was: Mixture ...)
by Simon Peyton-Jones 08 Dec '00

08 Dec '00

| This puzzles me a bit. From talking with people at the | Haskell Workshop, I understood that GHCi would only be an | interactive compiler. | | The disadvantage with that is that compilation time might be | very long. But it was said that that is the price we pay. | | The only advantage I can see with interpreted code is the | fact that it can be compiled (or "processed") much faster. | Will GHCi reach speeds up to Hugs level? It'll definitely be mixed compiled/interpreted. No, compiling won't be nearly as fast as Hugs, but it will, we earnestly hope be "fast enough". Execution should be faster than Hugs; apart from anything else you'll get compiled libraries. | One bad thing with Hugs is that, for large systems, the | loading/processing time gets longer, and, worse, is repeated | every time one loads the system. This is especially bad when | using "runhugs". Hopefully GHCi will work better in that | case! Yes, a lot better. The idea is only to recompile things that have changed. | Another thing that worries me is that Hugs will die. Not | only because I like Hugs a lot, but also that it is yet | another Haskell system that is dying. I think that is a very reasonable concern. I certainly want to see Hugs alive and kicking. Simon

1 0

HaXml question
by Michael Zawrotny 08 Dec '00

08 Dec '00

This question is probably a bit low-brow compared to the normal discussions of type systems, rank-2 polymorphism... Anyway, here goes nothing. I'm working on getting up to speed on haskell in general and HaXml in particular. I read through the ICFP paper that came with the distribution, but it was a bit dense for a beginner. Is there anything out there that is more oriented towards people who are less fluent in haskell? I think that my problem may be a lack of understanding of the whole idea of what combinators are and how they work. What I would like to do is something like the Xtract tool that comes with HaXml, but to select an element based on the path criteria specified (as Xtract already does), but that also satisfies an arbitrary predicate function that I would specify (e.g. a function that normalizes case and then tests for equality, regexp match, etc.). If anybody can help out on either front, I would greatly appreciate it. Thanks, Mike

1 0