September 2009 - Haskell-Cafe

Performance of functional priority queues
by Richard O'Keefe 29 Dec '09

29 Dec '09

There's a current thread in the Erlang mailing list about priority queues. I'm aware of, for example, the Brodal/Okasaki paper and the David King paper. I'm also aware of James Cook's priority queue package in Hackage, have my own copy of Okasaki's book, and have just spent an hour searching the web. One of the correspondents in that thread claims that it is provably impossible to have an efficient priority queue implementation without mutability. I think he's cuckoo. But I'd like to have some numbers to back me up. Can anyone point me to some actual benchmark results comparing priority queue performance *with* mutation and priority queue performance *without* mutation, in the same functional or mostly-functional language?

16 24

Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
by Dave Bayer 29 Dec '09

29 Dec '09

Here is another prime sieve. It is about half the length of the fastest contributed code (ONeillPrimes) and nearly as fast until it blows up on garbage collection: > % cat ONeillPrimes.hs | grep -v "^--" | wc > 185 1105 6306 > % cat BayerPrimes.hs | grep -v "^--" | wc > 85 566 2418 > > [Integer] -O 1*10^6 2*10^6 3*10^6 4*10^6 5*10^6 > --------------------------------------------------------- > ONeillPrimes | 3.555 | 7.798 | 12.622 | 18.927 | 23.529 > BayerPrimes | 3.999 | 8.895 | 18.003 | 22.977 | 38.053 I wrote this as an experiment in coding data structures in Haskell's lazy evaluation model, rather than as explicit data. The majority of the work done by this code is done by "merge"; the multiples of each prime percolate up through a tournament consisting of a balanced tree of suspended "merge" function calls. In order to create an infinite lazy balanced tree of lists, the datatype > data List a = A a (List a) | B [a] is used as scaffolding. One thinks of the root of the infinite tree as starting at the leftmost child, and crawling up the left spine as necessary. What I'm calling a "venturi" > venturi :: Ord a => [[a]] -> [a] merges an infinite list of infinite lists into one list, under the assumption that each list, and the heads of the lists, are in increasing order. This could be a generally useful function. If one can think of a better way to write "venturi", swapping in your code would in particular yield a faster prime sieve. I found that a tertiary merge tree was faster than a binary merge tree, because this leads to fewer suspensions. One can speed this code up a bit by interleaving strict and lazy calls, but I prefer to leave the code short and readable. It is bizarre that > trim p = let f m x = mod x m /= 0 in filter (f p) lurks in the prime sieve code, but it is only used with primes of size up to the square root of the largest output prime. I tried more thoughtful alternatives, and they all slowed down the sieve. Sometimes dumb is beautiful. Thanks to apfelmus for various helpful remarks that lead me to think of this approach. Here is the code: > module BayerPrimes (venturi,primes) where > > -- Code for venturi :: Ord a => [[a]] -> [a] > > merge :: Ord a => [a] -> [a] -> [a] -> [a] > merge xs@(x:xt) ys@(y:yt) zs@(z:zt) > | x <= y = if x <= z > then x : (merge xt ys zs) > else z : (merge xs ys zt) > | otherwise = if y <= z > then y : (merge xs yt zs) > else z : (merge xs ys zt) > merge _ _ _ = undefined > > data List a = A a (List a) | B [a] > > mergeA :: Ord a => List a -> List a -> List a -> List a > mergeA (A x xt) ys zs = A x (mergeA xt ys zs) > mergeA (B xs) ys zs = mergeB xs ys zs > > mergeB :: Ord a => [a] -> List a -> List a -> List a > mergeB xs@(x:xt) ys@(A y yt) zs = case compare x y of > LT -> A x (mergeB xt ys zs) > EQ -> A x (mergeB xt yt zs) > GT -> A y (mergeB xs yt zs) > mergeB xs (B ys) zs = mergeC xs ys zs > mergeB _ _ _ = undefined > > mergeC :: Ord a => [a] -> [a] -> List a -> List a > mergeC xs@(x:xt) ys@(y:yt) zs@(A z zt) > | x < y = if x < z > then A x (mergeC xt ys zs) > else A z (mergeC xs ys zt) > | otherwise = if y < z > then A y (mergeC xs yt zs) > else A z (mergeC xs ys zt) > mergeC xs ys (B zs) = B $ merge xs ys zs > mergeC _ _ _ = undefined > > root :: Ord a => List a -> [List a] -> [a] > root (A x xt) yss = x : (root xt yss) > root (B xs) (ys:zs:yst) = root (mergeB xs ys zs) yst > root _ _ = undefined > > wrap :: [a] -> List a > wrap [] = B [] > wrap (x:xt) = A x $ B xt > > triple :: Ord a => [List a] -> [List a] > triple (x:y:z:xs) = mergeA x y z : (triple xs) > triple _ = undefined > > group :: Ord a => [List a] -> [List a] > group (x:y:xt) = x : y : (group $ triple xt) > group _ = undefined > > venturi :: Ord a => [[a]] -> [a] > venturi (x:xt) = root (wrap x) $ group $ map wrap xt > venturi _ = undefined > > -- Code for primes :: Integral a => [a] > > diff :: Ord a => [a] -> [a] -> [a] > diff xs@(x:xt) ys@(y:yt) = case compare x y of > LT -> x : (diff xt ys) > EQ -> (diff xt yt) > GT -> (diff xs yt) > diff _ _ = undefined > > trim :: Integral a => a -> [a] -> [a] > trim p = let f m x = mod x m /= 0 in filter (f p) > > seed :: Integral a => [a] > seed = [2,3,5,7,11,13,17] > > wheel :: Integral a => [a] > wheel = drop 1 [ m*j + k | j <- [0..], k <- ws ] > where m = foldr1 (*) seed > ws = foldr trim [1..m] seed > > multiples :: Integral a => [a] -> [[a]] > multiples ws = map fst $ tail $ iterate g ([], ws) > where g (_,ps@(p:pt)) = ([ m*p | m <- ps ], trim p pt) > g _ = undefined > > primes :: Integral a => [a] > primes = seed ++ (diff wheel $ venturi $ multiples wheel)

6 8

Will GHC finally support epoll in 2009?
by Levi Greenspan 11 Dec '09

11 Dec '09

Ticket #635 "Replace use of select() in the I/O manager with epoll/kqueue/etc." (http://hackage.haskell.org/trac/ghc/ticket/635) dates back from 2005. Now its 2009 and GHC can handle hundreds of thousands of threads, yet having more than 1024 file descriptors open is still impossible. This limitation is a real bottle neck and prevents some cool developments on server side, like scalable comet servers. Instead others (e.g. Erlang guys) post stories about how they achived 1 million comet users (cf. http://www.metabrew.com/article/a-million-user-comet-application-with-mochi… ). Hence my question - is it likely that GHC will support epoll in 2009? Cheers and happy new year! - Levi

6 11

can there be (hash-table using) O(n) version of this (I think currently) n log n algo?
by Thomas Hartman 09 Dec '09

09 Dec '09

The code below is, I think, n log n, a few seconds on a million + element list. I wonder if it's possible to get this down to O(N) by using a hashtable implemementation, or other better data structure. Further, is there a hashtable implementation for haskell that doesn't live in IO? Maybe in ST or something? import Data.HashTable import qualified Data.Set as S import Data.List (foldl') testdata = [1,4,8,9,20,11,20,14,2,15] ++ [1..(10^6)] wantedsum = 29 -- set data structure -- findsums locates pairs of integers in a list that add up to a wanted sum. findsums :: [Int] -> Int -> S.Set (Int,Int) findsums xs wanted = snd . foldl' f (S.empty,S.empty) $ xs where f (candidates,successes) next = if S.member (wanted-next) candidates then (candidates, S.insert (next,wanted-next) successes) else (S.insert next candidates,successes) -- hashtable data structure -- result: t -- fromList [(15,14),(16,13),(17,12),(18,11),(19,10),(20,9),(21,8),(22,7),(23,6),(24,5),(25,4),(26,3),(27,2),(28,1)] -- probably O(n log n) complexity since using tree based Data.Set (a few seconds on million+ element list) t = findsums testdata wantedsum

9 10

Building network package on Windows
by Iavor Diatchki 02 Dec '09

02 Dec '09

Hi, I have been trying to build the package "network" from hackage (version 2.2.1.3) on Windows Vista, and I could really use some help. Building on the command line, or under cygwin completely failed (command line due to cabal not being able to execute something---possibly configure---although it would not say; cygwin first due to lack of gcc, which is tested but, apparently, the outcome ignored, and after gcc was installed some incompatibility with the header files which were detected but reported unusable). I managed to build the library under MinGW with msys without serious obstacles. I can also build my package against the result and all is well. Unfortunately, if I try to use my package to build an executable application I get a linker error, reporting a missing symbol during linking: C:\Users\diatchki\AppData\Roaming\cabal\network-2.2.1.3\ghc-6.10.3/libHSnetwork-2.2.1.3.a(Socket.o):fake:(.text+0xb014): undefined reference to `getnameinfo' collect2: ld returned 1 exit status Now, "getnameinfo" is present in the header files, and it is also defined in the library ws2_32.a which is being passed to GHC so I am not sure what is going on. Any ideas? Searching the web suggests that the problem may be somehow related to the standard calling conventions but I don't really understand. Also, if I understand correctly, this functionality is related to IPv6 support, which I do not need at the moment, so it would be great if it could be easily disabled in some way. Any ideas, suggestion, workarounds, etc. would be greatly appreciated, -Iavor PS: I am using GHC 6.10.3

5 9

Re: [Haskell-cafe] Atom - help.
by Tom Hawkins 28 Nov '09

28 Nov '09

Calling foreign functions that return values is problematic for the compiler -- I haven't invested enough time to come up with a good solution. The work around is to assign the result to an external variable. The drawback is the result will not be available until the rule executing the action has completed. results <- bool' "result" -- Global, external variable to capture result. action (\ [a, b, c] -> printf "result = function(%s, %s %s)" a b c) [a, b, c] -Tom On Sat, Jun 13, 2009 at 5:03 AM, Radamés Ajna<radamajna(a)gmail.com> wrote: > hi there, > > I've been working with haskell and atom dsl, however I'm new to haskell.. > John Van Enk inspired me with programming arduino->atmegas , with haskell, > So here is my problem. > With an action , action :: ([String] -> String) -> [UE] -> Atom () , > it's possible make calls to some precoded C functions like, > > setLED v = action (\[x] -> "setLED(" ++ x ++ ")") [v'] > where v' = ue . value $ v > > where setLed is a precode function. > > I want call a precoded C function that returns some value, but action > always give me Atom () , > that's I would like to do but I don't know how .. > > Atom (V Int8) < ---- "int read()" > > > thanks... > related links > http://hackage.haskell.org/package/atom-0.0.5 > http://blog.sw17ch.com/wordpress/?p=111 > http://leepike.wordpress.com/2009/05/05/an-atomic-fibonacci-server-explorin… > > > > Radamés > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 2

Problems with Language.Haskell.Interpreter and errors
by Martin Hofmann 11 Nov '09

11 Nov '09

Hi, The API of Language.Haskell.Interpreter says, that 'runInterpreter' runInterpreter :: (MonadCatchIO m, Functor m) => InterpreterT m a -> m (Either InterpreterError a) returns 'Left' in case of errors and 'GhcExceptions from the underlying GHC API are caught and rethrown as this'. What kind of errors do a generate here, why are they not caught by runInterpreter and how can I catch them? I assumed to get a 'Left InterpreterError' from the first and an error in MonadCatchIO in the second. > :m +Language.Haskell.Interpreter > let estr1 = "let lst [a] = a; lst _ = error \"foo\" in lst []" > let estr1 = "let lst [a] = a; in lst []" > runInterpreter (setImportsQ [("Prelude", Nothing)] >> eval estr1 ) Right "*** Exception: foo > runInterpreter ( eval estr2) Right "*** Exception: <interactive>:1:101-111: Non-exhaustive patterns in function lst Thanks a lot

2 7

RE: Haskell as a first language?
by Simon Peyton-Jones 07 Nov '09

07 Nov '09

Haskell is a great language! Check out haskell.org. I'm ccing the Haskell Cafe which is read by many people better qualified to answer your question than me. (Since I've been working on Haskell for many years, I am not well qualified to say how it seems to a beginner.) S | -----Original Message----- | From: Charles Turner [mailto:charlie.h.turner@googlemail.com] | Sent: 11 July 2009 22:52 | To: Simon Peyton-Jones | Subject: Haskell as a first language? | | I'll make this short! Do you think Haskell is a good language to start | with? I am brand new to programming and have been using Scheme, some of | my peers suggest I should use Haskell. It seems "professional" to me. | Has features that a beginner should not worry about. What would you | suggest. (I'm not worried about bias) | | Thank you very much for your time. | | Charles Turner.

17 17

Fwd: [Haskell-cafe] Market Place for Haskell development teams?
by Alberto G. Corona 28 Oct '09

28 Oct '09

forwarded to the list: Curt, Rubi and Pyton came into existencie without their internet libraries, but they would´nt be popular without them. Although I conffess I don´t know the history in detail. Academics is not mainstream. 2009/9/29 Curt Sampson <cjs(a)starling-software.com> > On 2009-09-29 13:18 +0200 (Tue), Alberto G. Corona wrote: > > > Java is part of the Java platform, that brought OS independence and > > interoperability at the right time. .Download-execution on the client > > was also a reason for the initial success of Java in the Internet era. > > I was a die-hard Java hacker from 1999 until some undetermined time in > the early-to-mid-2000s. (I abandoned it more or less completely sometime > around late 2005, if I recall correctly.) > > This may be somewhat anecdotal evidence, but I disagree with both > of your statements here. > Of course, I´m not talking about real advantages of Java or any PL. I told about the reasons that people used at the time to introduce the language in the mainstream, either is desirable this for haskell or not. I think it is. Nobody consider the runtime download of Java code important nowadays. Not even the cross-platform features. but it was marketeed at his time as such. > > Rubi and Python came with libraries targeted to Rapid development of > > Internet applications. > > No, neither originally "came" with that. > Rubi and Pyton came into existencie without their internet libraries, but they would´nt be popular without them. Although I conffess I don´t know the history in detail. > > What is the vehicle that haskell can use to enter the mainstream?. > > That may be the wrong question. "Avoid success at all costs" still > rings true to me. A year or so ago I seemed like one of the few on > the haskell-libraries list voting in favour of fixing API problems in > libraries, rather than etching in stone those problems in the name of > backwards compatibility so that we could "become more popular." > > Said above. We have different goals. > Do you really want, in 2020, to look back at the 2010 revision of the > Haskell standard and think, "we entrenched things that for a decade > everybody agreed was dumb"? > I see no problem in haskell having both. experimental and fixed versions. Haskell 2020 for you and me and haskell 2010 for my commercial code. Both woukd ve maintained and enriched by far more people. > > I can tell you, even when you're a Java enthusiast, there's nothing > more depressing than looking at java.util.Date and thinking, "That > should have been immutable, but it's going to be mutable for the rest of > eternity. We will never fix that." > > But let's try this again: > > > What is the vehicle that haskell can use to enter the mainstream?. > > Become more stupid. > > Is that a better answer? I'm not just a geek; I do marketing too (this > is what happens when you start your own company), and if you asked me, > using the utmost of my technical knowledge and marketing skills, to make > Haskell popular, this is what I'd recommend. > > Become more stupid may mean "give exactly what the people want" that transaltes to be more stable, give libraries, platforms etc. That is not a extra effor. that will come naturally as more people use the language. some people is naturally more abstract. some are more practical. > (I suppose it's a sign of my professionalism that to do this would > nearly break my heart, but if you wanted me to tell you the best way to > do this, and I couldn't tell you to get lost, that's what I'd say.) > > > Many people will play with Haskell in the spare time, and many of them > > will be permitted to develop some non critical applications at work. > > But that is all. > > Hm. So I suppose that this options trading system I'm working on, which > is the sole way our business makes money and is entirely written in > Haskell, doesn't actually exist. > > Congratulations.!! > > I think that all the current niches are filled, but new niches are > coming. > > Haskell already has a good niche. In fact, a brilliant one. We have > a whole bunch of academics doing truly wonderful stuff (imagine the > world without monads!--thank you Philip Wadler (and Eugenio Moggi)) > that the rest of us (relatively) dumb idiots can use to make our lives > better. We've got several very good implementations of the language, > one of which is a truly shit-hot compiler[1]. And we can use that to do > commercial applications quite comfortably[2]. > > Right. ;) > My personal opinion is, yes, let's let Haskell stick to the niche where > it's great, but it changes so fast that it's scary to everybody else. To > echo Paul Graham, I'm extremely happy to see my competition use Java. > > [1] Like that's so important. Ruby's standard implementation to this day > is an interpreter that implements all the popular extensions and has a > reasonably decent FFI. In Haskell-land, we call that "Hugs." It's only > because we have GHC as well that we can look down on Hugs; in the Ruby > (and Python, and PHP) worlds, they're saying that interpreters are just > fine for all sorts of "enterprise applications." > > [2] (Warning: self-promotion): > http://www.starling-software.com/misc/icfp-2009-cjs.pdf > > > Financial applications are an example of higher level programming > > where tasks usually performed by humans are now automatized and there > > is no or few traditions about that. The need to think at a higher > > level without being worried by side effects and other details are > > specially needed in such kind of areas. That's where haskell could > > have its own niche. > > Actually, I think that Haskell has a niche there not because of that > sort of thing, but merely because it's better than Java at doing what > Java does well, but scary enough that only small groups of brave > people who are comfortable with risk would ever attempt to use it. The > financial sector happens to have a lot more of those than many others. > > same concept in more plain words. I guess. > cjs > -- > Curt Sampson <cjs(a)starling-software.com> +81 90 7737 2974 > Functional programming in all senses of the word: > http://www.starling-software.com >

14 29

Re: [Haskell-beginners] map question
by Gregory Propf 21 Oct '09

21 Oct '09

Remember that there is asymmetry between (+) and (-). The former has the commutative property and the latter does not so: (+) 3 4 = 7 and (+) 4 3 = 7 but (-) 3 4 = -1 and (-) 4 3 = 1 --- On Thu, 9/17/09, Tom Doris <tomdoris(a)gmail.com> wrote: From: Tom Doris <tomdoris(a)gmail.com> Subject: Re: [Haskell-beginners] map question To: "Joost Kremers" <joostkremers(a)fastmail.fm> Cc: beginners(a)haskell.org Date: Thursday, September 17, 2009, 6:06 AM This works: map (+ (-1)) [1,2,3,4] 2009/9/17 Joost Kremers <joostkremers(a)fastmail.fm> Hi all, I've just started learning Haskell and while experimenting with map a bit, I ran into something I don't understand. The following commands do what I'd expect: Prelude> map (+ 1) [1,2,3,4] [2,3,4,5] Prelude> map (* 2) [1,2,3,4] [2,4,6,8] Prelude> map (/ 2) [1,2,3,4] [0.5,1.0,1.5,2.0] Prelude> map (2 /) [1,2,3,4] [2.0,1.0,0.6666666666666666,0.5] But I can't seem to find a way to get map to substract 1 from all members of the list. The following form is the only one that works, but it doesn't give the result I'd expect: Prelude> map ((-) 1) [1,2,3,4] [0,-1,-2,-3] I know I can use an anonymous function, but I'm just trying to understand the result here... I'd appreciate any hints to help me graps this. TIA Joost -- Joost Kremers, PhD University of Frankfurt Institute for Cognitive Linguistics Grüneburgplatz 1 60629 Frankfurt am Main, Germany _______________________________________________ Beginners mailing list Beginners(a)haskell.org http://www.haskell.org/mailman/listinfo/beginners -----Inline Attachment Follows----- _______________________________________________ Beginners mailing list Beginners(a)haskell.org http://www.haskell.org/mailman/listinfo/beginners

13 21