November 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

Re: ANNOUNCE: Clutterhs 0.1
by Gour 08 Jan '10

08 Jan '10

On Sat, 28 Nov 2009 23:18:00 -0500 >>>>>> "Matt" == Matt Arsenault <arsenm2(a)rpi.edu> wrote: Hi Matt, Matt> This is a very early announcement for an initial release of Matt> bindings for Clutter 1.0, now on Matt> Hackage,http://hackage.haskell.org/package/clutterhs Thanks a lot for this project. I'm just thinking about using Haskell on Moblin OS. ;) Matt> It uses c2hs, and depends on gtk2hs from darcs for the Matt> glib/gobject bindings. Overall, its usage should be similar to Matt> gtk2hs. This is very cool. Matt> This is my first Haskell project, and suggestions on the API, bug Matt> reports, etc. are appreciated. What do you think about binding Moblin's nbtk (now it's called mx) ? Otoh, are you aware of: http://github.com/elliottt/clutter & http://github.com/yav/clutter Sincerely, Gour -- Gour | Hlapicina, Croatia | GPG key: F96FF5F6 ----------------------------------------------------------------

4 7

Haskell Hackathon in Boston January 29th-31st?
by Ravi Nanavati 01 Jan '10

01 Jan '10

After all of the fun I had at Hac Phi, I've been thinking for a while that it would be fun to organize a Boston hackathon (to have all of the hackathon fun without the long drive). After some recent chats with my MIT friends, it seems like the weekend just after IAP (January 29th-January 31st) might be a good one. I've created a page to start organizing this hackathon (which I'm calling HacBOS unless someone comes up with a catchier name) here: http://www.haskell.org/haskellwiki/HacBOS If you'd be interested in attending a Boston hackathon, please add yourself to the possible attendees list on that page. If the proposed weekend does NOT work for you, but you're still interested in attending a Boston hackathon please indicate what other weekends during MIT's IAP (January 4th-January 29th) might work for you. I'm looking forward to making HacBOS happen! Thanks, - Ravi Nanavati

2 1

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

Cabal
by Philippos Apolinarius 18 Dec '09

18 Dec '09

I made small improvements in the Small Japi Binding, and asked how to make it available. I received a few private messages advising me to build and package the library using a tool called cabal. Since I have used installation tools for PLT, R and LaTeX libraries, I thought cabal was something similar. However, I noticed that there are a lot of complaints against cabal. Therefore, I decided to install cabal, and try it. It seems that it is easier to install packages by hand than using cabal. Here is a typical cabal session: D:\ghc\ghcapi>cabal update Downloading the latest package list from hackage.haskell.org D:\ghc\ghcapi>cabal install mkcabal Resolving dependencies... Downloading pcre-light-0.3.1... Configuring pcre-light-0.3.1... Downloading readline-1.0.1.0... Configuring readline-1.0.1.0... cabal: Error: some packages failed to install: mkcabal-0.4.2 depends on readline-1.0.1.0 which failed to install. pcre-light-0.3.1 failed during the configure step. The exception was: exit: ExitFailure 1 readline-1.0.1.0 failed during the configure step. The exception was: exit: ExitFailure 1 As one can see, it is much more difficult to use than R installation tools, or MikTeX installation tools. If cabal is so difficult, why use it? I am sure that I have done something very stupid mistake, but believe me, a lot of people is trying to use cabal and failing. I am not sure that it is a good idea to distribute libraries using cabal. However, this is irrelevant, because I am sure that creating a package with cabal is well beyond my powers. It is much easier to write a complete JAPI library, than packaging it in cabal. __________________________________________________________________ Looking for the perfect gift? Give the gift of Flickr! http://www.flickr.com/gift/

5 11

Are there standard idioms for lazy, pure error handling?
by John Millikin 13 Dec '09

13 Dec '09

I'm working on a library which needs to operate on large data sets, so I'd like to use lazy values. The library consists of pure functions from Text to [Event] and back. Normally, I use Maybe or Either for error handling in pure code, but using these precludes lazy evaluation. Using exceptions requires any errors to be handled in IO, which is annoying. The "idealized" signatures of the functions are: ---------------------------------------- import qualified Data.Text.Lazy as TL data Event = EventA | EventB | EventC parse :: TL.Text -> Either ParseError [Event] serialize :: [Event] -> Either SerializeError TL.Text ---------------------------------------- I've considered two possible error handling modes, both adapted from procedural language style. The first is simply including errors in the event list. ---------------------------------------- import qualified Data.Text as T parse :: TL.Text -> [Either ParseError Event] serialize :: [Event] -> [Either SerializeError T.Text] -- use TL.fromChunks ---------------------------------------- The second uses monadic callbacks, based on side effects: ---------------------------------------- parse :: Monad m => (Event -> m ()) -> (ParseError -> m ()) -> TL.Text -> m () serialize :: Monad m => (T.Text -> m ()) -> (SerializeError -> m ()) -> [Event] -> m () ---------------------------------------- The main problem I see with these is that they don't indicate or enforce that an error terminates the event/text streams. The first allows multiple errors in a row, or events to follow an error. The second just "feels" ugly, because using it in pure code requires clients to build a Writer (possibly wrapped with ErrorT) and deal with the associated plumbing. Is there any sort of standard idiom for handling this problem? It seems that somebody must have run across it before, but the resources I can find on lazy error handling all assume the code is impure (returning IO, etc).

14 24

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