- Haskell - Haskell.org

Re: series
by John Hughes 15 Aug '01

15 Aug '01

hello, i just want to ask a simple question: does somebody have or know = where to find a haskell program that calculates the number e, that is = the list of infinite digits? Because i think it may be possible to do = it, but i haven=B4t find the way to do it. what i am looking for is something like the ertostenes sifts, that = prints every prime number until it run out of memory... thank you, Luis It's a nice problem, which I encountered many years ago as one of the first examples I saw of lazy evaluation! Ah dear, I managed to make an off-by-one error in the code! "2.2718..." indeed! A corrected version is below. John ------------------------------------------------------------------------ Here's a way to compute all the digits of e. We use the series e = 2 + 1 + 1 + 1 + ... -- -- -- 2! 3! 4! which we can think of as representing e as 2.11111... in a strange number system with a varying base. In this number system, the fraction 0.abcd... represents a + b + c + d + ... -- -- -- -- 2! 3! 4! 5! To convert such a fraction to decimal, we multiply by 10, take the integer part for the next digit, and continue with the fractional part. Multiplying by 10 is easy: we just multiply each "digit" by 10, and then propagate carries. The hard part is knowing how far carries might propagate: since we carry leftwards in an infinite expansion, we must be careful to avoid needing to inspect the entire fraction in order to decide on the first carry. But each fraction we work with is less than one, so after multiplying by 10, it is less than 10. The "carry out" from each digit can be at most 9, therefore. So if a carry of 9 from the next digit would not affect the carry out from the current one, then that carry out can be emitted immediately. Since the base soon becomes much larger than 10, then this is likely to happen quickly. No doubt there are much better ways than this of solving the problem, but this one works. > carryPropagate base (d:ds) > | carryguess == (d+9) `div` base > = carryguess : (remainder+nextcarry) : fraction > | otherwise > = (dCorrected `div` base) : (dCorrected `mod` base) : fraction > where carryguess = d `div` base > remainder = d `mod` base > nextcarry:fraction = carryPropagate (base+1) ds > dCorrected = d + nextcarry > e = ("2."++) $ > tail . concat $ > map (show.head) $ > iterate (carryPropagate 2 . map (10*) . tail) $ > 2:[1,1..]

2 1

Re: series
by John Hughes 15 Aug '01

15 Aug '01

hello, i just want to ask a simple question: does somebody have or know = where to find a haskell program that calculates the number e, that is = the list of infinite digits? Because i think it may be possible to do = it, but i haven=B4t find the way to do it. what i am looking for is something like the ertostenes sifts, that = prints every prime number until it run out of memory... thank you, Luis It's a nice problem, which I encountered many years ago as one of the first examples I saw of lazy evaluation! The point is, of course, to produce the infinite stream of digits of e itself, not some approximation to it, as a couple of solutions posted earlier do. I'm attaching my solution (a literate Haskell script) which produces about 250 digits before hugs runs out of memory. John Hughes ----------------------------------------------------------------------------- Here's a way to compute all the digits of e. We use the series e = 2 + 1 + 1 + 1 + ... -- -- -- 2! 3! 4! which we can think of as representing e as 2.11111... in a strange number system with a varying base. In this number system, the fraction 0.abcd... represents a + b + c + d + ... -- -- -- -- 2! 3! 4! 5! To convert such a fraction to decimal, we multiply by 10, take the integer part for the next digit, and continue with the fractional part. Multiplying by 10 is easy: we just multiply each "digit" by 10, and then propagate carries. The hard part is knowing how far carries might propagate: since we carry leftwards in an infinite expansion, we must be careful to avoid needing to inspect the entire fraction in order to decide on the first carry. But each fraction we work with is less than one, so after multiplying by 10, it is less than 10. The "carry out" from each digit can be at most 9, therefore. So if a carry of 9 from the next digit would not affect the carry out from the current one, then that carry out can be emitted immediately. Since the base soon becomes much larger than 10, then this is likely to happen quickly. No doubt there are much better ways than this of solving the problem, but this one works. > carryPropagate base (d:ds) > | carryguess == (d+9) `div` base > = carryguess : (remainder+nextcarry) : fraction > | otherwise > = (dCorrected `div` base) : (dCorrected `mod` base) : fraction > where carryguess = d `div` base > remainder = d `mod` base > nextcarry:fraction = carryPropagate (base+1) ds > dCorrected = d + nextcarry > e = ("2."++) $ > concat $ > map (show.head) $ > iterate (carryPropagate 2 . map (10*) . tail) $ > 2:[1,1..]

1 0

series. Reply
by S.D.Mechveliani 15 Aug '01

15 Aug '01

Luis Pablo Michelena <lmichele(a)multi.com.uy> writes on the subject `series' > where to find a haskell program that calculates the number e, that is > the list of infinite digits? > [..] > what i am looking for is something like the ertostenes sifts, that > prints every prime number until it run out of memory ... In what way the Heratosphenes sieve for prime numbers may relate to finding approximations of number e ? As to finding the infinite list of digits for e = lim (1 + 1/n)^n, n -> infinity here the program is suggested for finding (eAppr n) :: Rational such that |e - (eAppr n)| < 1/2^(n-3) : import Ratio eAppr :: Integer -> Rational eAppr n = appr 0 (1%1) (0%1) where appr k member res = --- member = 1/(k!), if --- res = sum [1/i! | i <- [0..k]] k==n then res else appr (k+1) (member/(fromInteger (k+1))) (res+member) Several decimal digits can be obtained, then, like this: fromRational (eAppr 6) :: Double --> 2.716666666666667 fromRational (eAppr 20) :: Double --> 2.718281828459045 Explanation. According to Calculus, we have e = lim (eApp n), where eAppr n = sum [1/k! | k <- [0..n]] n -> infinity and |e - (eAppr n)| < 3/n! <= 1/2^(n-3). Therefore, eAppr(n+3) differs from e in less than 1/2^n. I believe, this fact will help us to find first true k digits of e for any given k. If people would not give other good solution and if you ask me to complete this task, then I'll try to do this. Regards, ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Haskell workshop: 10-minute slots
by Ralf Hinze 14 Aug '01

14 Aug '01

Folks, The Haskell Workshop in Firenze on 2nd September is now only a couple of weeks away. If you'd like to attend but haven't yet registered, please do so as soon as possible. For further details, see: http://music.dsi.unifi.it/pli01/registration/index.html The workshop programme is available here (including the proceedings): http://www.cs.uu.nl/~ralf/hw2001.html In addition to longer presentations on accepted papers, a number of slots for participants to make 10-minute informal presentations are available. If you'd like to request such a slot, please drop me an email. Note: the talk need not be polished, the wackier the better. Cheers, Ralf

1 0

PLEAC - Programming Language Examples Alike Cookbook
by Simon Peyton-Jones 14 Aug '01

14 Aug '01

Folks, [copied from the Caml mailing list; thanks to Pixel] I came across the PLEAC project recently. There's a Haskell section in it, and it looks like something to which people on this list would be well qualified to contribute. Olaf, John: worth a link from haskell.org? Simon http://pleac.sourceforge.net/ http://pleac.sourceforge.net/pleac-faq.html http://freshmeat.net/projects/pleac The aim of the project is to rewrite Perl CookBook's code in other programming languages, to: - provide an easy resource for quick learning of some languages field (file IOs, string manipulation, etc) - better see the differences and strengths of the languages - provide a quick reference for language comparisons - and, erhm, advocate the graphical layout of a good Emacs configuration There is a web infrastructure enabling syntaxically colorized sourcecode, and the Perl code has been imported from what's given for free at oreilly (also, the copyright stuff has been addressed with oreilly). We would very much enjoy a OCaml version, which has not yet begun for the moment. As for now, the Merd version is around 30% complete ; the Ruby version is around 25% complete ; the Haskell and Python versions are around 10% complete ; and embryonic Nasm and Masd versions are also available. [...caml stuff...] You may subscribe to the ML if interested (see the web for details). cu Pixel.

1 0

inference with functional dependencies
by Avi Pfeffer 14 Aug '01

14 Aug '01

Inferring equality between types when there are functional dependencies seems to be less powerful than I expected. Here's a simple example: class Eq b => C a b | a -> b data T a = forall b . C a b => T b data U a = forall b . C a b => U b compare :: T a -> U a -> Bool compare (T x) (U y) = x == y I expected the compiler (GHC) would be able to deduce that the b type in the representation of T a and U a must be the same, since both stand in a C a b relationship, and a functionally determines b in that relationship. Instead I get the message: Inferred type is less polymorphic than expected Quantified type variable `b1' is unified with `b' When checking a pattern that binds x :: b y :: b1 In an equation for function `Test.compare': Test.compare (T x) (U y) = x == y Is this expected behavior? Is there a way for me to provide the necessary hints so that code like this could be accepted? Thanks, Avi Pfeffer -- Avi Pfeffer avi(a)eecs.harvard.edu www.eecs.harvard.edu/~avi Maxwell Dworkin 251 Division of Engineering and Applied Sciences Tel: (617) 496-1876 Harvard University Fax: (617) 496-1066

2 1

RE: Haskell Kernel
by Simon Peyton-Jones 14 Aug '01

14 Aug '01

It's not formally defined, I'm afraid. The Haskell report simply desribes how to translate some constructs into simpler ones. It does not formally define the set of simpler one. (This isn't something I propose to fix in the revised Haskell 98 report!) Simon | -----Original Message----- | From: Juan Carlos Arévalo Baeza [mailto:jcab@roningames.com] | Sent: 10 August 2001 23:13 | To: Haskell List | Subject: Haskell Kernel | | | | Is there any place where I could find detailed | documentation on the Haskell kernel? The Haskell Report | doesn't seem to have much on this. | | Salutaciones, | JCAB | email: jcab(a)roningames.com | ICQ: 101728263 | The Rumblings are back: http://www.JCABs-Rumblings.com | | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

RE: Unary minus (was: micro-rant)
by Simon Peyton-Jones 14 Aug '01

14 Aug '01

Folks I suggest we transfer this discussion about unary minus to haskell-cafe(a)haskell.org. As the original poster noted, it is not a subject on which the existing Haskell report is ambiguous or inconsistent, so I don't propose to make any change in Haskell 98. The next version of Haskell, maybe. Simon | -----Original Message----- | From: Jerzy Karczmarczuk [mailto:karczma@info.unicaen.fr] | Sent: 13 August 2001 16:12 | Cc: haskell(a)haskell.org | Subject: Unary minus (was: micro-rant) | | | matt hellige: | | > ... i think people would | > be pretty frustrated if "-56.2" worked but not "-x"... | | Weell, the Cleaners around have to live with it. -5 works. | For variables they write ~x. But "-" in front of a number is | not a lexical entity, but a syntactic one, so f -5 and f (-5) | are a bit different. | | I didn't follow this discussion, but please avoid this mess | in Haskell. | | Jerzy Karczmarczuk | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

Re: micro-rant
by Marcin 'Qrczak' Kowalczyk 13 Aug '01

13 Aug '01

Tue, 7 Aug 2001 20:20:49 -0700, Memovich, Gary <GARY.MEMOVICH(a)kla-tencor.com> pisze: > As long as were trying to clean up a final version of the Haskell > 98 report, lets simplify it a little by getting rid of unary minus. I'm against removing it, even if compatibility was not an issue. Yes, it's an irregularity. But it's convenient, readable, and it allows using negative constants in patterns. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

3 2

Haskell Kernel
by Juan Carlos Ar�valo Baeza 10 Aug '01

10 Aug '01

Is there any place where I could find detailed documentation on the Haskell kernel? The Haskell Report doesn't seem to have much on this. Salutaciones, JCAB email: jcab(a)roningames.com ICQ: 101728263 The Rumblings are back: http://www.JCABs-Rumblings.com

1 0