- Haskell-Cafe - Haskell.org

Re: Learning Haskell and FP
by senganb＠ia.nsc.com 29 Dec '00

29 Dec '00

> * The Design Patterns Haskell Companion > by [someone(s) reading this list?] I agree except I would also like to see more on Haskell space-leaks and how to find them. Lazyness is great for structuring programs and garbage collection helps rapid prototyping immensely. However it makes it difficult to find the cause of that 128Mb heap overflow once you have 2000 lines of code. Yes the profiler gives you an idea of which function is using a lot of heap, but not exactly where. E.g. I rewrote my monads ultra stritly and the heap consumption fell by half, even though I'm not convinced being so strict isn't just masking some other problem: > (MN c1) >>= fc2 = MN $ \s0 -> case c1 s0 of { (r1,io1,s1) -> > case fc2 r1 of { ( MN c2 ) -> > case c2 s1 of { (r2,io2,s2) -> > (r2,io1 >> io2,s2) }}} Such a "community written book" might be good for http://www.lightandmatter.com/cgi-bin/asbrowsesubject.cgi?class=Q Sengan

1 0

Haskell question
by Scott 29 Dec '00

29 Dec '00

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

3 2

Re: Haskell question
by Mike Gunter 29 Dec '00

29 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 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