December 2000 - Haskell

RE: Haskell Productivity
by Peter Douglass 20 Dec '00

20 Dec '00

Hello all, You will need to manually reconnect the link I sent into a single line for it to work. > There is a thread on comp.lang.functional which may be of interest. > Here is a link that might work for you. > > http://www.deja.com/dnquery.xp?search=thread&svcclass=dnserver&recnum=%3c8lh 8ss$6le$1@bird.wu-wien.ac.at%3e%231/1

1 0

RE: Haskell Productivity
by Peter Douglass 20 Dec '00

20 Dec '00

There is a thread on comp.lang.functional which may be of interest. Here is a link that might work for you. http://www.deja.com/dnquery.xp?search=thread&svcclass=dnserver&recnum=%3c8lh 8ss$6le$1@bird.wu-wien.ac.at%3e%231/1 > -----Original Message----- > From: Steinitz, Dominic J > [mailto:Dominic.J.Steinitz@BritishAirways.com] > Sent: Wednesday, December 20, 2000 11:12 AM > To: haskell > Subject: Haskell Productivity > > > The Haskell website claims that > > "Ericsson measured an improvement factor of between 9 and 25 > in one set of experiments on telephony software". > > Presumably this is with Erlang not with Haskell. I have > searched for the reference that substantiates this claim but > I've only been able to find: > > http://set.gmd.de/~ap/femsys/wiger.html > > which talks about a productivity factor of 4 > > and > > http://www.md.chalmers.se/Cs/Research/Functional/Fudgets/haske ll-vs-ada-abstract.html which suggests that Haskell is about 2-3 times as productive as imperative languages. Can someone point me at some more references? Especially the one that talks about a productivity improvement of 9-25? Thanks, Dominic. ---------------------------------------------------------------------------- --------------------- 21st century air travel http://www.britishairways.com _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

1 0

Re: Haskell Productivity
by Paul Hudak 20 Dec '00

20 Dec '00

> Can someone point me at some more references? See http://haskell.org/papers/NSWC/jfp.ps. -Paul

1 0

Haskell Productivity
by Steinitz, Dominic J 20 Dec '00

20 Dec '00

The Haskell website claims that "Ericsson measured an improvement factor of between 9 and 25 in one set of experiments on telephony software". Presumably this is with Erlang not with Haskell. I have searched for the reference that substantiates this claim but I've only been able to find: http://set.gmd.de/~ap/femsys/wiger.html which talks about a productivity factor of 4 and http://www.md.chalmers.se/Cs/Research/Functional/Fudgets/haskell-vs-ada-abs… which suggests that Haskell is about 2-3 times as productive as imperative languages. Can someone point me at some more references? Especially the one that talks about a productivity improvement of 9-25? Thanks, Dominic. ------------------------------------------------------------------------------------------------- 21st century air travel http://www.britishairways.com

1 0

Re: Finding primes using a primes map with Haskell and Hugs98
by Colin.Runciman＠cs.york.ac.uk 20 Dec '00

20 Dec '00

> There are numerous ways of optimising sieving for primes, none of which > have much to do with this list. For example, two suggestions: > (1) for each k modulo 2*3*5*7, if k is divisible by 2/3/5 or 7, ignore, otherwise > sieve separately for this k on higher primes. (Or you might use products of > more or less primes, depending on memory and how high you were going.) > ... > I don't really see why any of this has anything to do with Haskell though. > When it comes to seriously icky bit-twiddling algorithms I don't think Haskell > has much to offer over C, especially as you'd have to make everything unboxed if > you want comparable speed. Forgive the self-reference, but the following short article is all about this very topic: C. Runciman, Lazy wheel sieves and spirals of primes, Journal of Functional Programming, v7, n2, pp219--226, March 1997.

1 0

Excessive restriction in ghc ?
by Sebastien Carlier 19 Dec '00

19 Dec '00

Hello. I am getting an error message from ghc 4.08.1 with the following code: > class Collection e ce | ce -> e where > empty :: ce > insert :: e -> ce -> ce > > class (Eq e, Collection e ce) => Set e ce where > member :: e -> ce -> Bool > union :: ce -> ce -> ce Main.lhs:7: Class type variable `e' does not appear in method signature union :: {- implicit forall -} ce -> ce -> ce Since `ce' uniquely determines `e', I would expect the compiler to assume that `e' appears in the method signature. Either I am misunderstanding something, or something may be missing in the compiler around rename/RnSource.lhs:249. Regards, Sebastien Carlier

3 3

RE: Excessive restriction in ghc ?
by Simon Peyton-Jones 19 Dec '00

19 Dec '00

Functional dependencies aren't fully implemented in 4.08 I'm afraid, and won't ever be. It'll be significantly better in 5.0, but we won't release that for a while yet. (Unless you care to build from the CVS tree.) Simon | -----Original Message----- | From: Sebastien Carlier [mailto:sebastien@posse42.net] | Sent: 19 December 2000 14:15 | To: haskell(a)haskell.org | Subject: Excessive restriction in ghc ? | | | Hello. | | I am getting an error message from ghc 4.08.1 with | the following code: | | > class Collection e ce | ce -> e where | > empty :: ce | > insert :: e -> ce -> ce | > | > class (Eq e, Collection e ce) => Set e ce where | > member :: e -> ce -> Bool | > union :: ce -> ce -> ce | | Main.lhs:7: | Class type variable `e' does not appear in method signature | union :: {- implicit forall -} ce -> ce -> ce | | Since `ce' uniquely determines `e', I would expect the | compiler to assume that `e' appears in the method signature. | Either I am misunderstanding something, or something may be | missing in the compiler around rename/RnSource.lhs:249. | | Regards, | Sebastien Carlier | | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell |

1 0

call for papers ICFP 2001
by Xavier Leroy 18 Dec '00

18 Dec '00

ICFP 2001: Call for Papers ICFP 2001: International Conference on Functional Programming Firenze (Florence), Italy; 3-5 September 2001 associated with PLI 2001: Colloquium on Principles, Logics, and Implementations of High-Level Programming Languages Important dates: Submission deadline 15 March 2001, 18:00 UTC Notification of acceptance or rejection 11 May 2001 Final paper due 29 June 2001 Conference 3-5 September 2001 Scope: ICFP 2001 seeks original papers on the full spectrum of the art, science, and practice of functional programming. The conference invites submissions on all topics ranging from principles to practice, from foundations to features, and from abstraction to application. The scope covers all languages that encourage programming with functions, including both purely applicative and imperative languages, as well as languages that support objects and concurrency. Papers setting new directions in functional programming, or describing novel or exemplary applications of functional programming, are particularly encouraged. Topics of interest include, but are not limited to, the following: * Foundations: formal semantics, lambda calculus, type theory, monads, continuations, control, state, effects. * Design: modules and type systems, concurrency and distribution, components and composition, relations to object-oriented and logic programming, multiparadigm programming. * Implementation: abstract machines, compile-time and run-time optimization, just-in-time compilers, memory management, foreign-function and component interfaces. * Transformation and Analysis: abstract interpretation, partial evaluation, program transformation, theorem proving, specification and verification. * Applications: scientific and numerical computing, symbolic computing and artificial intelligence, systems programming, databases, graphic user interfaces, multimedia programming, web programming. * Experience: FP in education and industry, ramifications on other paradigms and computing disciplines. * Functional pearls: elegant, instructive examples of functional programming. Submission guidelines: Please refer to the submission Web site http://cristal.inria.fr/ICFP2001/ Program committee: General chair Program committee Benjamin Pierce Karl Crary, Carnegie Mellon University University of Pennsylvania Marc Feeley, University of Montréal Giorgio Ghelli, University of Pisa Program chair Simon Peyton Jones, Microsoft Research John Hughes, Chalmers University Xavier Leroy Naoki Kobayashi, University of Tokyo INRIA Rocquencourt Julia Lawall, DIKU, U. Copenhagen Domaine de Voluceau, B.P. 105 Sheng Liang, Stratum8 78153 Le Chesnay, France John Reppy, Bell Labs, Lucent Technologies E-mail: Xavier.Leroy(a)inria.fr Scott Smith, John Hopkins University Fax: + 33 - 1 - 39 63 56 84 Carolyn Talcott, Stanford University Phone: + 33 - 1 - 39 63 55 61 Kwangkeun Yi, KAIST

1 0

Finding primes using a primes map with Haskell and Hugs98
by Shlomi Fish 18 Dec '00

18 Dec '00

Hi! As some of you may know, a Haskell program that prints all the primes can be as short as the following: primes = sieve [2.. ] where sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ] Now, this program roughly corresponds to the following perl program: ###### SNIP SNIP ##### #!/usr/bin/perl use strict; my (@primes, $a, $p); @primes = (2); MAIN_LOOP: for($a = 3; $a < 1000; $a++) { foreach $p (@primes) { if ($a % $p == 0) { next MAIN_LOOP; } } push @primes, $a; } print join(", ", @primes); ####### SNIP SNIP ##### The program can be more optimized for both speed and code size, but I wanted to make it as verbose as possible. The algorithm keeps a list of the primes, and for each new number checks if it is divisable by any of them and if not it adds it to the list. There is a different algorithm which keeps a boolean map which tells whether the number at that position is prime or not. At start it is initialized to all trues. The algorithm iterates over all the numbers from 2 to the square root of the desired bound, and if it encounters a prime number it marks all the numbers p*p, p*p+p, p*p+2*p, p*p+3*p, etc. as not prime. It is generally considered a better algorithm than the previous one, because it uses less costier operations (multiplications and additions instead of modulos.) The perl program that implements that algorithm is this: #### SNIP SNIP ##### #!/usr/bin/perl use strict; sub primes { my $how_much = shift; my (@array, $bound, $a, $b, @primes); @array = (1) x $how_much; $bound = int(sqrt($how_much))+1; for($a=2;$a<=$bound;$a++) { if ($array[$a]) { for($b=$a*$a;$b<$how_much;$b+=$a) { $array[$b] = 0; } push @primes, $a; } } for(;$a<$how_much;$a++) { if ($array[$a]) { push @primes, $a; } } return @primes; } print join(", ", primes(1000)); ##### SNIP SNIP ###### Now, I tried writing an equivalent Haskell program and the best I could do was the following: ---- SNIP SNIP ----- module Primes where import Prelude import Array how_much :: Int how_much = 1000 initial_primes_map :: Array Int Bool initial_primes_map = array (1, how_much) [ (i,True) | i <- [1 .. how_much] ] mybound :: Int mybound = ceiling(sqrt(fromInteger(toInteger(how_much)))) next_primes_map :: Int -> Array Int Bool -> Array Int Bool next_primes_map a primes_map = if (a == mybound) then primes_map else next_primes_map (a+1) ( if primes_map!a then primes_map // [ (i*a, False) | i <- [a .. (prime_bound a)] ] else primes_map ) prime_bound :: Int -> Int prime_bound a = (floor(fromInteger(toInteger(how_much))/fromInteger(toInteger(a)))) get_primes_map :: Array Int Bool get_primes_map = (next_primes_map 2 initial_primes_map) list_primes :: Array Int Bool -> Int -> [Int] list_primes primes_map n = if (n > how_much) then [] else ( if primes_map!n then n:(list_primes primes_map (n+1)) else list_primes primes_map (n+1) ) show_primes = show (list_primes get_primes_map 2) ---- SNIP SNIP ----- The problem is that when running it on hugs98 on a Windows98 computer with 64MB of RAM, I cannot seem to scale beyond 30,000 or so, as my boundary. When entering how_much as 50,000 I get the following message: ERROR: Garbage collection fails to reclaim sufficient space In perl I can scale beyond 100,000, and if I modify the code to use a bit vector (using vec) to much more. So my question is what am I or hugs are doing wrong and how I can write better code that implements this specific algorithm. >From what I saw I used tail recursion, (and hugs98 has proper tail recursion, right?), and there's only one primes_map present at each iteration (and thus, at all), so it shouldn't be too problematic. Does it have to do with the way hugs98 implements and Int to Bool array? 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.

4 4

Problem with functional dependencies
by qrczak＠knm.org.pl 17 Dec '00

17 Dec '00

The following module is rejected by both ghc -fglasgow-exts -fallow-undecidable-instances and hugs -98 ------------------------------------------------------------------------ class HasFoo a foo | a -> foo where foo :: a -> foo data A = A Int data B = B A instance HasFoo A Int where foo (A x) = x instance HasFoo A foo => HasFoo B foo where foo (B a) = foo a ------------------------------------------------------------------------ The error messsage says that the type inferred for foo in B's instance is not general enough: the rhs has type "HasFoo B Int => B -> Int", but "HasFoo B foo => B -> foo" was expected. Should it really be wrong? I don't know the details of type inference with fundeps, but intuitively it should work, yielding an instance HasFoo B Int. Could it be made legal please? With the fundep removed, it works. I need it for a preprocessor which generates instances like that for B without knowing the type to put as the second class argument. Fundeps aren't essential, but... -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0