August 2009 - Haskell-Cafe

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

28 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

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

(no subject)
by Stavenga, G.C. 15 Oct '09

15 Oct '09

Hi, I'm just started to learn Haskell. Coming from a programming contest background (where it is important to be able to solve problems in a small amount of code) I'm wondering what the best way is for simple IO. A typical input file (in a programming contest) is just a bunch of numbers which you want to read one by one (sometimes interspersed with strings). In C/C++ this is easily done with either scanf or cin which reads data separated by spaces. In Haskell I have not found an equally satisfactionary method. The methods I know of 1) Stay in the IO monad and write your own readInt readString functions. A lot of code for something easy. 2) Use interact together with words and put the list of lexemes in a State monad and define getInt where at least you can use read. 3) Use ByteString.Char8 which has readInt (but I couldn't find a readString). But one has to put it also in a State monad. I think that there must be standard function that can do this. What do experienced Haskellers use? Thanks in advance

10 11

Network.Curl and posting XML data
by Erik de Castro Lopo 07 Oct '09

07 Oct '09

Hi all, I need to do a HTTP post of XML data (Content-type == "text/xml") to a HTTP (eventually HTTPS) server and to retrieve both the response code and some returned XML data. I have had an extensive read of the haskell-curl docs: http://hackage.haskell.org/packages/archive/curl/1.3.5/doc/html/Network-Cur… as well as playing around with some code, but haskell-curl doesn't seem to support this. I've tried curlPost which along with not returning a response also insists on encoding my XML data as application/x-www-form-urlencoded which simply doesn't work. Anyone ben able to get something like this to work? Are there any alternatives to haskell-curl which will work for my application? Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

4 8

Can this be done?
by Cristiano Paris 01 Oct '09

01 Oct '09

I wonder whether this can be done in Haskell (see muleherd's comment): http://www.reddit.com/r/programming/comments/7wi7s/how_continuationbased_we… Cristiano

15 22

F# mailing list?
by Günther Schmidt 27 Sep '09

27 Sep '09

Hi guys, is there a mailing list for haskellers that defected to F#? Not that I was I going to, just asking, absolutely hypothetically. Uhm. Günther

3 3