October 2009 - Haskell-Cafe

Arch Haskell News: Nov 23 2008
by Don Stewart 16 Jan '10

16 Jan '10

News about Haskell on Arch Linux * Arch now has 734 Haskell packages now * That’s an increase of 29 new packages in the last 8 days! * 3.6 new Haskell releases are occuring each day. Noteworthy, * haskell-hledger-0.2: “A ledger-compatible text-based accounting tool.” * gitit-0.3.1: “Wiki using HAppS, git, and pandoc.” * lhc-20081121: “Lhc Haskell Compiler” * haskell-hosc-0.6: “Haskell Open Sound Control” * haskell-flickr-0.3.2: “Haskell binding to the Flickr API” * haskell-delicious-0.3.2: “Accessing the del.icio.us APIs from Haskell (v2)” * haskell-mediawiki 0.2.3: “Interfacing with the MediaWiki API” * darcs-2.1.2.2: “a distributed, interactive, smart revision control system” Full update list, http://archhaskell.wordpress.com/2008/11/24/arch-haskell-news-nov-23-2008/ -- Don

24 56

How to fulfill the "code-reuse" destiny of OOP?
by Magicloud Magiclouds 13 Jan '10

13 Jan '10

Hi, I think when people talk about OOP, especially the inheriting, their focus mainly is on functions (methods). My concern here is about the data member inheriting. In OOP, when I inherit a class, I also got the members of it. But in haskell, how to inherit a "data"? -- 竹密岂妨流水过山高哪阻野云飞

19 27

Approaches to dependent types (DT)
by pat browne 11 Jan '10

11 Jan '10

Hi, I am trying to understand the concept of dependent types as described in Haskell literature (Hallgren 2001),(Hinze,Jeuring et al. 2006). I am particularly interested in understanding two flavours of dependency mentioned by Hinze et al: 1) Types depending on values called dependent types 2) Types depending on types called parametric and type-indexed types I think that ascending levels of abstraction are important here: values - types - classes (Hallgren 2001). Here is a Haskell example of the use of DT: class Named object name | object -> name where name :: object -> name instance (Eq name, Named object name) => Eq object where object1 == object2 = (name object1) == (name object2) I think that the intended semantics are: 1) Objects have names and can be compared for equality using these names. 2) Two objects are considered equal (identical) if they have the same name. 3) The type of a name depends on the type of the object, which gets expressed as a type dependency (object -> name). I am not sure about the last semantic it might be interpreted as "the named object depends on..". This may indicate a flaw in my understanding of DT. I am aware that dependent types can be used to express constraints on the size of lists and other collections. My understanding of Haskell's functional dependency is that object -> name indicates that fixing the type object should fix the type name (equivalently we could say that type name depends on type object). The class definition seems to show a *type-to-type* dependency (object to name), while the instance definition shows how a name value is used to define equality for objects which could be interpreted as a *value-to-type* dependency (name to object) in the opposite direction to that of the class. My questions are: Question 1: Is my understanding correct? Question 2: What flavour of DT is this does this example exhibit? Best regards, Pat Hallgren, T. (2001). Fun with Functional Dependencies. In the Proceedings of the Joint CS/CE Winter Meeting, Varberg, Sweden, January 2001. Hinze, R., J. Jeuring, et al. (2006). Comparing Approaches to Generic Programming in Haskell. Datatype-generic programming: international spring school, SSDGP 2006.

6 7

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

Fwd: [Haskell-cafe] Haskell for Physicists
by Don Stewart 05 Dec '09

05 Dec '09

Hey all, Following up on this, I'm presenting a position paper tomorrow on the use of EDSLs to improve productivity and lower cost when developing code for new high performance architectures (like GPUs). http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-… It advocates for Haskell + EDSLs, much as we have been discussing in this thread. -- Don

6 6

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