November 2009 - Haskell-Cafe

Essence of Functional Programming for Imperative Programmers
by Shelby Moore 04 Nov '09

04 Nov '09

New concise guide I am creating: http://www.coolpage.com/commentary/economic/shelby/Functional_Programming_E… I was able to condense Category theory and implementation of Monads to one screen: http://www.coolpage.com/commentary/economic/shelby/Functional_Programming_E… Overall, I think I have a unique method for comparing and condensing the explanation of the transistion from imperative to pure functional. What you think? It is a work-in-progress, so corrections, feedback, and flames are welcome. I will do the OOP section next and incorporate the explanations from these posts: http://www.haskell.org/pipermail/haskell-cafe/2009-November/068440.html (data vs. Module) http://www.haskell.org/pipermail/haskell-cafe/2009-November/068432.html (interface vs. virtual) P.S. The link will not change if you want to link to it now. If you mirror it, please update your mirrors periodically. There is no copyright claimed, I don't believe in copyrights any more. I intend to publish everything as PUBLIC DOMAIN (i.e. no license at all, because licenses impact composability). If I want to charge, I will put functionality behind an unpublished interface (i.e. Module). P.P.S. I only started learning functional programming about a week ago.

1 0

Word128, Word256
by Maurício CA 04 Nov '09

04 Nov '09

Hi, Do you think we could have the range of sizes for Int* and Word* expanded to allow also 128 and 256 bits sizes? My reason is that I have a long standing issue trying to bind to C numerical libraries using complex numbers, as those are usually structs passed by value. See this from GNU GSL: typedef struct { double dat[2]; } gsl_complex; I imagine I could do: type GslComplex = Word128 -- size would depend on architecture and then write foreign declarations to have: get_real :: GslComplex -> CDouble get_imag :: GslComplex -> CDouble gsl_complex_sin :: GslComplex -> GslComplex gsl_complex_cos :: GslComplex -> GslComplex Do you think this is a reasonable request? Thanks for your attention, Maurício

4 8

Hugs Trex for GHC / JHC / UHC / ... ?
by Peter Verswyvelen 03 Nov '09

03 Nov '09

I briefly read about Hugs record system Trex, and at first sight this was really nice! I know this question was asked a long time ago already, but are there any plans to add this extension to GHC? What about the other compilers, like JHC, UHC, etc? Is it possible to emulate Trex (lots of other record systems exist), *and* get the same easy to understand errors? What were the problems with Trex (if any)? Thanks, Peter Verswyvelen

2 1

Re: [Haskell-cafe] ANNOUNCE: dbus-core 0.5 and dbus-client 0.1
by John Millikin 03 Nov '09

03 Nov '09

The purpose behind the weird signature there is so that the computations in DBus.Bus can be passed directly to mkClient. Because of the design of dbus-client, you probably don't want to keep the connection around separately. ----- client <- mkClient getSessionBus ----- Here's a quick-and-dirty skeleton for sending notifications: ----- {-# LANGUAGE OverloadedStrings #-} import DBus.Bus import DBus.Client import DBus.Types -- Definition of notification object / interface notifications = Proxy (RemoteObject (mkBusName' "org.freedesktop.Notifications") (mkObjectPath' "/org/freedesktop/Notifications")) (mkInterfaceName' "org.freedesktop.Notifications") -- Callbacks; in real systems, these would probably be more complex onError x = putStrLn ("ERROR\n\n" ++ show x ++ "\n\n") onReturn x = putStrLn ("RETURN\n\n" ++ show x ++ "\n\n") -- A real library might accept additional parameters -- by the way: signature of Notify() is "susssasa{sv}i" notify c = call' params onError onReturn where params = [{- build parameters for your library here -}] call' = call client notifications (mkMemberName' "Notify") [] main = do client <- mkClient getSessionBus notify client {- main loop / mvar / whatever your library uses -} ----- On Tue, Nov 3, 2009 at 14:07, Max Rabkin <max.rabkin(a)gmail.com> wrote: > Hi John > > I'm trying to implement a pure Haskell library for notifications (like > libnotify). Unfortunately I don't know my way around dbus too well. > > Is there a reason for > > mkClient :: IO (Connection, BusName) -> IO Client > > instead of > > mkClient :: Connection -> IO Client > > ? > > mkClient simply discards the bus name, so in the event that one > doesn't have a bus name, one must create a fake one. Also, it executes > the IO action right away, so there is no need for it to take an IO > argument. All in all, this means I must write > > getClient = mkClient (flip (,) undefined <$> getSessionConnection) > > instead of > > getClient = mkClient =<< getSessionConnection. > > Perhaps you have a good reason for it? > > Regards, > Max > > On Fri, Oct 30, 2009 at 11:44 PM, John Millikin <jmillikin(a)gmail.com> wrote: >> These are pure-Haskell client libraries for using the D-Bus protocol. >> D-Bus is heavily used for inter-application IPC on Free and >> open-source desktop platforms, such as Linux, OpenSolaris, and >> FreeBSD. These libraries allow applications written in Haskell to >> inter-operate with other components of recent GNOME, KDE, and XFCE >> desktops. >> >> This is the first "real" release of these libraries; dbus-core has >> been published on Hackage for some time, but mostly just to make sure >> I got the Cabal bits right. I feel they are now stable / featureful >> enough for public use. >> >> Both are available on Hackage: >> >> http://hackage.haskell.org/package/dbus-core >> http://hackage.haskell.org/package/dbus-client >> >> --------- >> >> "dbus-core" is an implementation of the D-Bus protocol, specifically >> the parts relevant to clients. Eventually, it will probably grow some >> functions useful for implementing a message bus as well. It includes >> type mapping / conversion, an implementation of the wire format >> (marshaling / unmarshaling), data types for the currently defined >> message types (METHOD_CALL, METHOD_RETURN, ERROR, and SIGNAL) and a >> basic parser / generator for introspection documents. It is roughly >> equivalent in purpose to libdbus. >> >> By itself, a protocol implementation is somewhat cumbersome to use, so >> "dbus-client" is a high-level wrapper. It provides some abstractions >> like remote object proxies, exported object trees, synchronous method >> calls, signal reception, and name reservation. Messages are received >> and processed in separate IO threads, allowing asynchronous method >> call and signal handling. >> >> The purpose between splitting the library into two packages is >> stability; "dbus-core", ideally, will change only rarely -- >> performance improvements, new message / data types, etc. It provides a >> base level of functionality which more specialised libraries may use. >> "dbus-client" is an example of what such a library could look like, >> though for now it's not very Haskell-y (IO everywhere, exceptions, >> explicit locking). By separating the protocol from the client libs, >> alternative client libs can safely depend on the protocol >> implementation. >> >> --------- >> >> To see a sample of the library working, there's a clone of the >> "dbus-monitor" utility in <dbus-core/Examples>. Documentation is >> currently a bit lacking, so for now, the best documentation is the PDF >> of the source code itself, and the (rather barren) Haddock output: >> >> https://dl.getdropbox.com/u/1947532/dbus-core_0.5.pdf >> https://dl.getdropbox.com/u/1947532/dbus-core_0.5/index.html >> >> https://dl.getdropbox.com/u/1947532/dbus-client_0.1.pdf >> https://dl.getdropbox.com/u/1947532/dbus-client_0.1/index.html >> >> Once more people have used it without any major API issues, I'll write >> up a manual and populate the Haddock entries. >> >> Please respond with any feedback, difficulties, or suggestions. I'm >> particularly interested in ways to improve the public API, since I >> would rather make any breaking changes *before* anything big depends >> on these libraries. >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >

1 0

Re: Simple FAST lazy functional primes
by Steve 03 Nov '09

03 Nov '09

Hi Will, I had previously tested the Melissa O'Neil prime function (using the primes 0.1.1 package) and found it to be fast (for a functional approach), but with high memory use. To fully test a prime function, I think you should: 1. Test for more than the first 10^6 primes. Generating all primes to 10^6 is quite easy for modern computers. Most prime generating functions will run in less than 1 sec and look fast. Try generating all primes to 10^7 and 10^8 then you will see how 'fast' these lazy functional methods really are. 2. Measure memory use. As you move above 10^6 and test primes up to 10^7, 10^8, and 10^9, memory use becomes very important. A prime function with excessive memory use will soon consume all of the system's memory. Here's another primes function which performs quite well. primes :: [Int] primes = 2 : filter (isPrime primes) [3,5..] where isPrime (p:ps) n | mod n p == 0 = False | p*p > n = True | otherwise = isPrime ps n isPrime [] _ = False -- never used, but avoids compiler warning Here's some results from my PC, for generating primes to 10^8. 10**6 10**7 10**8 secs MiB secs MiB secs MiB ------------------------------- 1 0.01 0 0.1 2 2 14 2 0.56 7 11.1 43 270 306 3 0.61 7 11.8 44 260 342 4 0.43 36 5.4 345 900 not finished 1 using a Haskell ST Array 2 your primes function 3 my primes function, listed above 4 Melissa O'Neil method from primes 0.1.1 package To summarise the results from the tests I've run: - if you want fast functional primes, forget it, its not possible. - if you just want fast primes, then use C, or a Haskell array. - if performance does not matter and slow primes are acceptable, then use the purely functional approach. Regards, Steve

2 1

ANN: timeplot - a program for visualizing time series from log files
by Eugene Kirpichov 03 Nov '09

03 Nov '09

Hi. I've released timeplot on hackage: http://hackage.haskell.org/package/timeplot Timeplot is a program for visualizing time series from log files. The typical usage scenario: - Take a big log file of your program (100k-1m lines is OK) - Preprocess it with an awk one-liner to obtain a trace for timeplot - Plot the trace with timeplot, telling it which chart type (one of 8) to use for each "track" of the trace. For example, you can plot the frequencies of response times falling into 0..100ms, 100..500ms, 500..1000ms and >1000ms over 5-minute time intervals, or plot their 25% and 50% quantiles. - Behold the resulting graphics and discover anomalies and interesting process interdependencies in your program. Take a look at the description with lots of pretty pictures and a tutorial: http://www.haskell.org/haskellwiki/Timeplot -- Eugene Kirpichov Web IR developer, market.yandex.ru

1 0

Simple FAST lazy functional primes
by Will Ness 03 Nov '09

03 Nov '09

First, here it is: primes = 2: 3: sieve 0 primes' 5 primes' = tail primes sieve k (p:ps) x = [x | x<-[x,x+2..p*p-2], and [(x`rem`p)/=0 | p<-take k primes']] ++ sieve (k+1) ps (p*p+2) (thanks to Leon P.Smith for his brilliant idea of directly generating the spans of odds instead of calling 'span' on the infinite odds list). This code is faster than PriorityQueue-based sieve (granted, using my own ad-hoc implementation, so YMMV) in producing the first million primes (testing was done running the ghc -O3 compiled code inside GHCi). The relative performance vs the PQ-version is: 100,000 300,000 1,000,000 primes produced 0.6 0.75 0.97 I've recently came to the Melissa O'Neill's article (I know, I know) and she makes the incredible claim there that the square-of-prime optimization doesn't count if we want to improve the old and "lazy" uprimes = 2: sieve [3,5..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0] Her article gave me the strong impression that she claims that the only way to fix this code is by using Priority Queue based optimization, and then goes on to present astronomical gains in speed by implementing it. Well, I find this claim incredible. First of all, the "naive" code fires up its nested filters much too early, when in fact each must be started only when the prime's square is reached (not only have its work started there - be started there itself!), so that filters are delayed: dprimes = 2: 3: sieve (tail dprimes) [5,7..] where sieve (p:ps) xs = h ++ sieve ps (filter ((/=0).(`rem`p)) (tail t)) where (h,t)=span (< p*p) xs This code right there is on par with the PQ-base code, only x3-4 slower at generating the first million primes. Second, the implicit control structure of linearly nested filters, piling up in front of the supply stream, each with its prime-number-it-filters-by hidden inside it, needs to be explicated into a data structure of primes-to-filter-by (which is in fact the prefix of the primes list we're building itself), so the filtering could be done by one function call instead of many nested calls: xprimes = 2: 3: sieve 0 primes' [5,7..] where primes' = tail xprimes sieve k (p:ps) xs = noDivs k h ++ sieve (k+1) ps (tail t) where (h,t)=span (< p*p) xs noDivs k = filter (\x-> all ((/=0).(x`rem`)) (take k primes')) >From here, using the brilliant idea of Leon P. Smith's of fusing the span and the infinite odds supply, we arrive at the final version, kprimes = 2: 3: sieve 0 primes' 5 where primes' = tail kprimes sieve k (p:ps) x = noDivs k h ++ sieve (k+1) ps (t+2) where (h,t)=([x,x+2..t-2], p*p) noDivs k = filter (\x-> all ((/=0).(x`rem`)) (take k primes')) Using the list comprehension syntax, it turns out, when compiled with ghc -O3, gives it another 5-10% speedup itself. So I take it to disprove the central premise of the article, and to show that simple lazy functional FAST primes code does in fact exist, and that the PQ optimization - which value of course no-one can dispute - is a far-end optimization.

5 14

Lecture Notes Advanced Functional programming available
by S. Doaitse Swierstra 03 Nov '09

03 Nov '09

I am happy to announce that the rworked lecture notes for the 6th Advance Functional programming summer school have become available. For further information about the lecture notes: http://www.springer.com/computer/programming/book/978-3-642-04651-3?cm_mmc=… Contents: • Umut Acar (Toyota Technological Institute, University of Chicago, USA): Self-Adjusting Computation • Richard Bird (University of Oxford, UK): Spider Spinning • Olivier Danvy (University of Aarhus, DK): On deriving abstract machines from interpreters and calculi • Johan Jeuring (Utrecht University, NL): Libraries for Generic Programming in Haskell • Ulf Norell (Chalmers University, SE): Dependently Typed Programming in Agda • Simon Peyton Jones and Satnam Singh (update) (Microsoft Research, UK): Parallel Functional Programming • Rinus Plasmeijer (Radboud University Nijmegen, NL): Specifying Interactive Workflows for the Web Doaitse

4 3

Applicative but not Monad
by Yusaku Hashimoto 03 Nov '09

03 Nov '09

Hello cafe, Do you know any data-type which is Applicative but not Monad? Cheers, -~nwn

18 28

ANN: BlogLiterately-0.2
by Robert Greayer 03 Nov '09

03 Nov '09

Due to overwhelming popular demand*, BlogLiterately (version 0.2) has been released on Hackage. It's a simple tool for uploading posts written in markdown and (optionally) literate Haskell to web logs. It relies heavily on Pandoc for markdown processing, but adds a few twists like syntax highlighting via hscolour. The original version was described here: http://greayer.wordpress.com/2009/10/26/blogging-literately-in-haskell/ The new version (the first version on hackage) has been updated a bit -- to take advantage of Pandoc highlighting extensions and to support blog categories, mainly. The primary documentation is just the haskell package page: http://hackage.haskell.org/package/BlogLiterately It's only been tested with a WordPress blog (mine) but ought to work with any blogging software that supports the MetaWeblog API. Send bug reports, etc. to me... Thanks! * -- 2 people asked

1 0