- Haskell-Cafe - Haskell.org

Re: Haskell question
by Mike Gunter 28 Dec '00

28 Dec '00

This is fairly subtle. The fact that the numbers are printed with a decimal point hints that they are floating point numbers. Floating-point arithmetic's inexactness makes equality tests less valuable than for, e.g., Integer arithmetic. If you change the "**"s to "^"s you'll get [3,4], etc. (or [3,4,5] if you change "[x,y]" to "[x,y,z]"). mike gunter E.g.: Main> [[x,y,z] | x<-[1..50],y<-[1..50],z<-[1..50],x^2+y^2==z^2] [[3,4,5],[4,3,5],[5,12,13],[6,8,10],[7,24,25], ... ] > Hello! > I am reading Discrete Mathematics Using a computer by Hall and O'Donnell > and in the introduction to hugs section, they give this example: > [[x,y] | x<-[1..50],y<-[1..50],z<-[1..50],x**2+y**2==z**2] > now I type it in and expect it to return a number of results, but it > doesn't, it shows: > [[8.0,15.0,17.0],[14.0,48.0,50.0],[15.0,8.0,17.0],[15.0,20.0,25.0],[20.0,15.0,25.0],[21.0,28.0,35.0],[27.0,36.0,45.0],[28.0,21.0,35.0],[30.0,40.0,50.0],[36.0,27.0,45.0],[40.0,30.0,50.0],[48.0,14.0,50.0]] > My question is where is [3.0,4.0,5.0],[5.0,12.0,13.0]? > I have looked everywhere I could think of to see what I am doing wrong, but > I have no idea. Maybe a rounding error somewhere? > Thank you, > Scott Anderson

1 0

RE: Haskell question
by Conal Elliott 28 Dec '00

28 Dec '00

It's probably due to rounding. If you use "^" instead of "**", defaulting to integers, you'll get the triples you expected. - Conal -----Original Message----- From: Scott [mailto:adric@wipcradio.cc] Sent: Thursday, December 28, 2000 3:05 PM To: Haskell-Cafe(a)haskell.org Subject: Haskell question Hello! I am reading Discrete Mathematics Using a computer by Hall and O'Donnell and in the introduction to hugs section, they give this example: [[x,y] | x<-[1..50],y<-[1..50],z<-[1..50],x**2+y**2==z**2] now I type it in and expect it to return a number of results, but it doesn't, it shows: [[8.0,15.0,17.0],[14.0,48.0,50.0],[15.0,8.0,17.0],[15.0,20.0,25.0],[20.0,15. 0,25.0],[21.0,28.0,35.0],[27.0,36.0,45.0],[28.0,21.0,35.0],[30.0,40.0,50.0], [36.0,27.0,45.0],[40.0,30.0,50.0],[48.0,14.0,50.0]] My question is where is [3.0,4.0,5.0],[5.0,12.0,13.0]? I have looked everywhere I could think of to see what I am doing wrong, but I have no idea. Maybe a rounding error somewhere? Thank you, Scott Anderson _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Boolean Primes Map (continued)
by Shlomi Fish 22 Dec '00

22 Dec '00

Well, after some thought, I decided to try re-writing the boolean primes map program only using a list instead of an array. I came up with this program: primes :: Int -> [Int] primes how_much = (iterate 2 initial_map) where initial_map :: [Bool] initial_map = (map (\x -> True) [ 0 .. how_much]) iterate :: Int -> [Bool] -> [Int] iterate p (a:as) | p > mybound = process_map p (a:as) | a = p:(iterate (p+1) (mymark (p+1) step (2*p) as)) | (not a) = (iterate (p+1) as) where step :: Int step = if p == 2 then p else 2*p mymark :: Int -> Int -> Int -> [Bool] -> [Bool] mymark cur_pos step next_pos [] = [] mymark cur_pos step next_pos (a:as) = if (cur_pos == next_pos) then False:(mymark (cur_pos+1) step (cur_pos+step) as) else a:(mymark (cur_pos+1) step next_pos as) mybound :: Int mybound = ceiling(sqrt(fromIntegral(how_much))) process_map :: Int -> [Bool] -> [Int] process_map cur_pos [] = [] process_map cur_pos (a:as) | a = cur_pos:(process_map (cur_pos+1) as) | (not a) = (process_map (cur_pos+1) as) I don't know too much about Haskell yet, so it is possible this program can be further optimized using some Haskell built-ins. Now, this program can scale to 100,000 and beyond, as opposed to the array version which only got until 30,000 or 40,000. It's a pity Haskell doesn't handle arrays very well, but I guess every language has its faults. Regards, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish shlomif(a)vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: shlomif(a)techie.com The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one.

1 0

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 11 Dec '00

11 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