January 2010 - Haskell-Cafe

Dependency trickery
by Andrew Coppin 17 Jan '10

17 Jan '10

Suppose I write some code that can work with Gtk2hs or wxHaskell. How do I go about making that into a package? Specifically, how do I make it so that you don't have to install Gtk2hs *and* wxHaskell to build it? Do I have to actually make it into two seperate packages to do that? Also, supposing we have another package which requires the first, but doesn't care whether it's using Gtk2hs or wxHaskell. How do I do that? Obviously the answer depends on what happens in the previous step. If I make two seperate packages, for example, and they both export the same module, can I just add optional dependancies on both? Does Cabal support that? Not that I'm attempting to *do* this, you understand. I'd just like to know if it's possible...

3 3

AlternativePrelude extension
by Sjur Gjøstein Karevoll 17 Jan '10

17 Jan '10

Here's an idea I'd like to air: A new extension called AlternativePrelude. Like the NoImplicitPrelude extension we have already, this would disable implicitly importing the Prelude in every other module, but would also implicitly import a substitute. The purpose is to make it easier to play around with alternative preludes. Today we have to specify NoImplicitPrelude, but also explicitly import our alternative everywhere, making the transition between the different preludes that much more painful. With this new extension, the alternative prelude can be specified in the cabal file, or on the command line when building. This will hopefully make the alternative prelude efforts a little bit more mainstream, giving us more data we can use to consider modifications to the current standard prelude. I'm thinking the syntax would be something like AlternativePrelude="MyPrelude". This is new among the extensions in that it requires a parameter. An alternative is an ImplicitImport extension that doesn't disable the implicit importing of the Prelude, but while this does serve the same purpose as the AlternativePrelude proposal, I think it might be easier to use it for nefarious purposes. -- Sjur Gjøstein Karevoll

6 6

ANN: amqp-0.1
by Holger Reinhardt 17 Jan '10

17 Jan '10

Hi, I've built an AMQP library. It currently only works with RabbitMQ and supports most of the 0-8 spec. If you don't know that AMQP is, this is a good introduction: http://blogs.digitar.com/jjww/2009/01/rabbits-and-warrens/ I have not done much testing, so this should be regarded as alpha quality. Get it here: http://hackage.haskell.org/package/amqp For some reason it doesn't compile on Hackage. It says "At least the following dependencies are missing: network-bytestring >=0.1.2". Is there a way to solve this? Regards, Holger

2 1

Language simplicity
by Andrew Coppin 17 Jan '10

17 Jan '10

OK people, it's random statistics time! Haskell '98 apparently features 25 reserved words. (Not counting "forall" and "mdo" and so on, which AFAIK are not in Haskell '98.) So how does that compare to other languages? C: 32 C++: 62 Borland Turbo Pascal: ~50 [without the OOP extensions added later] Eiffel: 59 VB: The source I checked listed in excess of 120 reserved words, but I'm dubious as to how "reserved" they really are. (Is CInt really reserved? I doubt it!) It also depends wildly on which of the bazillion VB dialects you mean. Java: 50 JavaScript: 36 Smalltalk: 0 Lisp: AFAIK, there are no truly reserved words in Lisp, only predefined functions. (??) Python: 31 Ruby: 38 Tcl: Same analysis as for Lisp I believe. As you can see, this conclusively proves... something. Hmm, I wonder if there's some way to compare the size of the language specification documents? :-} PS. It comes as absolutely no surprise to me that C++ has the most keywords. But then, if I were to add AMOS Professional, that had well over 800 keywords at the last count...

25 56

Presentation about ICFP'09 programming contest
by Janis Voigtländer 17 Jan '10

17 Jan '10

Hi Haskell folk, If you are in Madrid tomorrow (Monday), you will likely not want to miss the video presentation by Andy Gill and his group about the techniques behind their running the ICFP'09 programming contest: http://www.program-transformation.org/PEPM10/SpecialFeature The presentation is scheduled to start 17:15, in the PEPM workshop room. Ciao, Janis. -- Jun.-Prof. Dr. Janis Voigtländer http://www.iai.uni-bonn.de/~jv/ mailto:jv@iai.uni-bonn.de

1 0

Haskell Weekly News: Issue 146 - January 17, 2010
by jfredett＠gmail.com 17 Jan '10

17 Jan '10

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20100117 Issue 146 - January 17, 2010 --------------------------------------------------------------------------- Welcome to issue 146 of HWN, a newsletter covering developments in the [1]Haskell community. This has been a pretty light week in terms of discussion and announcments, but even in this comparative news lull we have the release of several new versions of packages. Inlcluding the start of a new IDE, some new job and graduate program openings, and some really excellent blog noise. Until next week, Haskellers, your Haskell Weekly News. Announcements haskell-src-exts 1.7.0. Niklas Broberg [2]announced a new release of haskell-src-exts Lite Haskell IDE. Mambo Banda [3]announced a new Haskell IDE, as part of his effort to learn Haskell. Functional Programming Bibliography. James Russell [4]announced the Functional Programming Bibliography, a new resource for the FP community. It, though in it's early stages, contains oer 1500 references (most of which are Haskell-related) to resources within the Functional Programming World. hakyll-1.0. Jasper Van der Jeugt [5]announced the release of version 1.0 of his static site generation tool, hakyll. From all (one) of us at the HWN, contragulations on the big 1.0! afv-0.0.0. Tom Hawkins [6]announced the initial release of 'Atom's Formal Verifier', a tool for verifying C code generated by Atom chp-2.0.0, chp-plus-1.0.0. Neil Brown [7]announced released new versions of his Comminicating Haskell Processes (CHP) packages. CHP is a message-passing concurrency library for Haskell. The major change in this version is a split of CHP into two packages, one containing core functionality, and one containing additional capabilities. Update for type-level library (0.2.4). Seyed Hosein Attarzadeh Niaki [8]announced a new version of his type-level library for type-level programming. This is a minor update to fix compatibility issues with dependencies. Two PhD positions in theoretical computer science. Alexandra Silva [9]announced vacancies for PhD positions in theoretical computer science at Leiden University. HaXml-1.20.1. Malcolm Wallace [10]announced a new, stable release of HaXml AST 2010 reminder--call for papers and presentations. John Hughes [11]reminded us of the AST 2010 call for papers and presentations. The submission deadline is only one week away. Job at Mylife. Julien Verlaguet [12]announced an availabiity for an OCaml developer at MyLife. Open Position (PhD student or Postdoc), U Tubingen, Germany. Torsten Grust [13]announced an open PhD/Postdoc position at the University of Tubingen in Germany. (ED: Apologies for the improper 'u' -- it should have an umlaut, but the compilation software is not cooperating) Palindromes 0.2. Johan Jeuring [14]announced a new release of the Palindromes package, including many new features and upgrades. Discussion From records to a type class. Taru Karttunen [15]asked about turning records into type classes, in an effort to make his bindings for Fuse more elegant. AlternativePrelude extension. Sjur Gjostein Karevoll [16]suggested a language pragma for alternative preludes. (ED: Again, apologies for the look-alike, but improper character). Blog noise [17]Haskell news from the [18]blogosphere. Blog posts from people new to the Haskell community are marked with >>>, be sure to welcome them! * Holumbus: [19]Linking Hayoo! Search Results. * Jeff Heard: [20]SPDE, Semi-functional programming for Processing. * Neil Mitchell: [21]Using .ghci files to run projects. * Neil Mitchell: [22]Better .ghci files. * Neil Brown: [23]Darcs. * Neil Brown: [24]Splitting CHP. * Darcs: [25]darcs weekly news #50. * Bryan O'Sullivan: [26]Progress on GHC's I/O manager. * Michael Snoyman: [27]New blog address. * Conal Elliot: [28]Exact Numeric Integration. I had missed this one last week (amidst the myriad, I failed to see it), so it is presented in this week's edition. Quotes of the Week * Jafet: <gwern> closures are a poor man's object <ddarius> objects are a poor man's closure <Berengal> objects are a rich man's structs <Jafet> Poor programmers should start unions * monochrom: Time flies like an Arrow. Space leaks like a Monad. * monochrom: Haskell already has natural language support. Just switch your natural language to simple-typed lambda calculus. * edwardk: @remember Baugn @remember lambdabot fasta says: I think the @remember command is way overused. * Berengal: data Neither a b = Left | Right * Cale: Removing monad comprehensions was actually the snowball which caused the avalanche of fail in Haskell 98 About the Haskell Weekly News New editions are posted to [29]the Haskell mailing list as well as to [30]the Haskell Sequence and [31]Planet Haskell. [32]RSS is also available, and headlines appear on [33]haskell.org. To help create new editions of this newsletter, please see the information on [34]how to contribute. Send stories to jfredett . at . gmail . dot . com. The darcs repository is available at darcs get [35]http://patch-tag.com/r/jfredett/HWN2/pullrepo HWN2 . References 1. http://haskell.org/ 2. http://article.gmane.org/gmane.comp.lang.haskell.cafe/69197 3. http://article.gmane.org/gmane.comp.lang.haskell.cafe/69176 4. http://article.gmane.org/gmane.comp.lang.haskell.cafe/69153 5. http://article.gmane.org/gmane.comp.lang.haskell.cafe/69106 6. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68995 7. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68943 8. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68940 9. http://article.gmane.org/gmane.comp.lang.haskell.general/17727 10. http://article.gmane.org/gmane.comp.lang.haskell.general/17725 11. http://article.gmane.org/gmane.comp.lang.haskell.general/17724 12. http://article.gmane.org/gmane.comp.lang.haskell.general/17723 13. http://article.gmane.org/gmane.comp.lang.haskell.general/17722 14. http://article.gmane.org/gmane.comp.lang.haskell.general/17721 15. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/69207 16. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/69194 17. http://planet.haskell.org/ 18. http://haskell.org/haskellwiki/Blog_articles 19. http://holumbus.fh-wedel.de/blog/?p=30 20. http://vis.renci.org/jeff/2010/01/15/spde-semi-functional-programming-for-p… 21. http://neilmitchell.blogspot.com/2010/01/using-ghci-files-to-run-projects.h… 22. http://neilmitchell.blogspot.com/2010/01/better-ghci-files.html 23. http://chplib.wordpress.com/2010/01/14/darcs/ 24. http://chplib.wordpress.com/2010/01/11/splitting-chp/ 25. http://blog.darcs.net/2010/01/darcs-weekly-news-50.html 26. http://www.serpentine.com/blog/2010/01/11/progress-on-ghcs-io-manager/ 27. http://snoyberg.wordpress.com/2010/01/10/new-blog-address/ 28. http://conal.net/blog/posts/exact-numeric-integration/ 29. http://www.haskell.org/mailman/listinfo/haskell 30. http://sequence.complete.org/ 31. http://planet.haskell.org/ 32. http://sequence.complete.org/node/feed 33. http://haskell.org/ 34. http://haskell.org/haskellwiki/HWN 35. http://patch-tag.com/r/jfredett/HWN2/pullrepo%20HWN2

1 0

Data.Ring -- Pre-announce
by John Van Enk 16 Jan '10

16 Jan '10

Hi List, I recently needed a ring structure (circular list with bi-directional access) and didn't see anything obvious on Hackage. I threw something together fairly quickly and would like some feedback before tossing it on Hackage. I'd really appreciate if some one would: 1. make sure the code looks goodish (127 lines with full docs) 2. make sure my tests look saneish If I hear nothing, I'll assume wild support and push to Hackage. Code: http://github.com/sw17ch/data-ring/blob/master/src/Data/Ring.hs Tests: http://github.com/sw17ch/data-ring/blob/master/tests/quickcheck.hs Package Root: http://github.com/sw17ch/data-ring Thanks ahead of time, John Van Enk

16 25

What's going on here?
by michael rice 16 Jan '10

16 Jan '10

I don't see anything wrong with this function, which just subtracts 1 from the first element of an Int list (if there is a first element). Michael My function: dropFirst :: [Int] -> [Int] dropFirst [] = [] dropFirst (x:xs) = (x-1) : xs My output: > :l dropfirst [1 of 1] Compiling Main ( dropfirst.hs, interpreted ) Ok, modules loaded: Main. *Main> dropFirst [3 4 5 6] <interactive>:1:11: No instance for (Num (t -> t1 -> t2 -> Int)) arising from the literal `3' at <interactive>:1:11-17 Possible fix: add an instance declaration for (Num (t -> t1 -> t2 -> Int)) In the expression: 3 4 5 6 In the first argument of `dropFirst', namely `[3 4 5 6]' In the expression: dropFirst [3 4 5 6] *Main>

3 3

ANNOUNCE: nntp 0.0.3
by Maciej Piechotka 16 Jan '10

16 Jan '10

Rather a 'bug-fix' release. Intended to add additional symbols to group names. I'd like to add support for explicit fetching some headers only and giving the message a more MIME-like behaviour but I'm afraid there is nowhere written how XHDR/HDR would behave with multiline headers nor I found a suitable package (mime[1] seems to not include even parsing the headers only and mime-string[2] does not take into account comments which may or may not be a problem with Message-ID comparaison). Regards [1] http://hackage.haskell.org/package/mime [2] http://hackage.haskell.org/package/mime-string

1 0

RFC: Space-leak-free, efficient symbol table implementation.
by Thomas Schilling 16 Jan '10

16 Jan '10

Hello Café, Symbol tables are a very common data structure in compilers but the most common implementation uses a hash table as a global variable which results in a space leak. If we decide to use several symbol tables we still cannot join different symbol tables. After some Googling I found the following implementation. It could still be argued that there are some smaller space leaks left, but decide for yourself. The use case I have in mind is a collection of several long-running compiler worker threads, that for the most part write their result to disk but may occasionally need to communicate with each other (and agree on symbol identities.) I'd appreciate comments / code review on the following code. I think it's fairly well-commented. Thanks, / Thomas {-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -funbox-strict-fields #-} -- | -- Module : Data.Atom.UF -- Copyright : (c) Thomas Schilling 2010 -- License : BSD-style -- -- Maintainer : nominolo(a)gmail.com -- Stability : experimental -- Portability : portable -- -- Symbols without a central symbol table. -- -- Symbols provide the following efficient operations: -- -- - /O(1)/ equality comparison (in practise) -- - /O(1)/ ordering comparison (in practise) -- - /O(n)/ creation -- -- This can be implemented by using a global variable mapping strings -- to symbols and a counter assigning ids to symbols. However, this -- has two problems: -- -- 1. It has a space leak. No symbols can ever be removed from this -- table. For example, if we add the symbol @\"foo\"@ the first -- time it might get assigned id 1, if we then delete it and -- insert it again it might get assigned id 42. However, there -- may still be symbols in memory which got assigned id 1. -- Instead, symbols should be garbage collected like other data. -- Using weak pointers has bad effects on performance due to -- garbage collector overhead. -- -- 2. It is not reliable to compare symbols created using different -- symbol tables. They would most likely get assigned different -- ids. -- -- This implementation of symbols allows *optional* use of a symbol -- table. If a symbol table is used, this implementation will tend to -- use less memory and its operations will be a little bit faster at -- the beginning. For longer runs, it won't make a big difference -- though, since the representation is self-optimising. -- -- Inspired by Richard O'Keefe's message to Erlang's eeps mailing list -- <http://www.erlang.org/cgi-bin/ezmlm-cgi/5/057>, which in turn was -- inspired by the Logix implementation of Flat Concurrent Prolog. -- -- -- * Implementation -- -- Each symbol is represented a pointer to the symbol info, which -- consists of: -- -- * a 'String' -- * a 'Hash' -- * a null-able parent pointer to an equivalent symbol info -- -- Creating the same symbol twice will at first be represented as two -- different entities. -- -- @ -- .----+-------+-----. -- A -----> | 42 | "foo" | nil | -- '----+-------+-----' -- B --. -- '--> .----+-------+-----. -- C -----> | 42 | "foo" | nil | -- '----+-------+-----' -- @ -- -- (Note that @A@, @B@ and @C@ are @IORefs@.) -- -- When comparing @A@ and @B@ we use the following properties: -- -- 1. If @A@ and @B@ are identical then they must be equal. -- -- 2. If they point to the same object, they must equal. -- -- 3. If they have different hashes, they are different. -- -- Unless there is a hash collision, we can decide equality and -- ordering for all symbols that have been built with the same hash -- table. -- -- If the two objects have no parent, have the same hash, and the same -- string, we now make one the first the parent of the other and -- update the pointer of @B@ accordingly. If there are no references -- to the second object left it can now be garbage collected. -- -- If an object already has a parent pointer we follow each object's -- parents to the roots and compare the roots. This process might -- again result in updates to @A@ or @B@ and various parent pointers. -- -- In the example above, after @A == B@ we have: -- -- @ -- .----+-------+-----. -- A -----> | 42 | "foo" | nil | -- .--> '----+-------+-----' -- B --' ^ -- .----+-------+--|--. -- C -----> | 42 | "foo" | * | -- '----+-------+-----' -- @ -- -- After @C == A@ or @C == B@ we have. -- -- @ -- A -----> .----+-------+-----. -- .--> | 42 | "foo" | nil | -- B --'.-> '----+-------+-----' -- | ^ -- | .----+-------+--|--. -- C ---' | 42 | "foo" | * | -- '----+-------+-----' -- @ -- -- The second object will now be garbage collected. -- -- In fact, after the first @A == B@, the remaining updates could use -- some help from the garbage collector. This could be done by -- somehow forcibly (and unsafely) replacing the second object by an -- update frame and then rely on the GC's indirection shortening -- feature. This is /very/ unsafe, since some code may rely \"know\" -- that the object is already evaluated. E.g., C's pointer could be -- tagged (c.f. \"Faster Laziness Using Dynamic Pointer Tagging\"). -- It /might/ work if we can match the physical layout of both -- structures, but it's equally likely that hell freezes over, so I'll -- leave that as an exercise for more braver hackers. -- -- * TODO -- -- - generalise to arbitrary hashable objects. need not be -- restricted to 'String'. -- -- - make thread-safe. (we only need a lock for the uncommon cases) -- -- - make sure the pointer update code is correct and has no bad -- cases -- -- - implement IntMap variant\/wrapper that respects that two -- different objects may have the same key (however unlikely). -- module Data.Atom.UF ( Symbol, intern, internInto, SymTab(..) ) where import Data.Word ( Word32 ) import Data.Char ( ord ) import Data.Bits ( xor ) import Data.IORef import System.IO.Unsafe import Control.Monad -- ( unless ) import System.Mem.Weak import System.Mem import Data.Maybe -- ------------------------------------------------------------------- -- Public API: -- | A symbol. newtype Symbol = Symbol (IORef SymbolInfo) instance Eq Symbol where x == y = cmpSymbol x y == EQ instance Ord Symbol where compare = cmpSymbol instance Show Symbol where show = showSym -- | Create a new local symbol. For best performance use -- 'internInto' together with a symbol table / map. intern :: String -> Symbol class SymTab s where lookupSymbol :: s -> String -> Maybe Symbol insertSymbol :: String -> Symbol -> s -> s -- | Insert a symbol into an existing table. internInto :: SymTab s => s -> String -> (s, Symbol) -- ------------------------------------------------------------------- -- Internals data SymbolInfo = SymInfo {-# UNPACK #-} !Word32 -- hash {-# UNPACK #-} !(IORef Link) -- parent [really unpack]? String type Link = Maybe SymbolInfo internInto st str = case lookupSymbol st str of Just sym -> (st, sym) _ -> let sym = intern str in (insertSymbol str sym st, sym) showSym :: Symbol -> String showSym (Symbol r) = unsafePerformIO $ do -- dupable/inline is fine, too, since the string never changes (SymInfo _ _ str) <- readIORef r return str intern s = unsafePerformIO $ do lnk <- newIORef Nothing r <- newIORef $ SymInfo (hash s) lnk s return (Symbol r) mkSymbolInfo :: String -> SymbolInfo mkSymbolInfo s = unsafePerformIO $ do lnk <- newIORef Nothing return $ SymInfo (hash s) lnk s cmpSymbol :: Symbol -> Symbol -> Ordering cmpSymbol (Symbol r1) (Symbol r2) | r1 == r2 = EQ | otherwise = unsafePerformIO $ do -- We only read. It should be safe to use unsafeInlineIO for -- the two reads. sym1@(SymInfo h1 l1 s1) <- readIORef r1 sym2@(SymInfo h2 l2 s2) <- readIORef r2 case h1 `compare` h2 of -- If the hashes are different they cannot be the same symbol LT -> return LT GT -> return GT EQ | sameSym sym1 sym2 -> -- The two references are not the same, but they point to -- the same object. That's fine, we can't optimise any -- further. return EQ -- END OF COMMON CASE -- -- If the symbols have been built using the same symbol table -- we will only reach this case if we have a hash collision or -- the symbols were built from different symbol tables. -- -- TODO: Extract into NOINLINE function, wrap unsafePerformIO, -- and use an MVar-based lock. | otherwise -> do -- The hashes are the same. It could be a collision, or the -- symbol was created using a different symbol table. -- -- Case 1: The symbols have already be joined, but this -- Symbol's IORef still points to the old version. We can -- determine this by following the union/find structure. rep1 <- repr sym1 rep2 <- repr sym2 let string_cmp = s1 `compare` s2 -- lazy! if sameSym rep1 rep2 || string_cmp == EQ then do -- They should in fact be the same symbol. Update the -- atoms and the symbol infos if necessary. -- TODO: Use MVar / lock. unless (sameSym sym1 rep1) $ do writeIORef r1 rep1 writeIORef l1 (Just rep1) -- path shortening unless (sameSym sym2 rep1) $ do writeIORef r2 rep1 writeIORef l2 (Just rep1) return EQ else do -- They are not the same, and they shouldn't return string_cmp {-# NOINLINE cmpSymbol #-} -- We abuse the fact that IORefs give us an identity (i.e., observable -- sharing) and that we need the IORef anyway. sameSym :: SymbolInfo -> SymbolInfo -> Bool sameSym (SymInfo _ r1 _) (SymInfo _ r2 _) = r1 == r2 repr :: SymbolInfo -> IO SymbolInfo repr sym@(SymInfo _ r _) = do parent <- readIORef r -- TODO: perform path shortening. case parent of Nothing -> return sym Just sym' -> repr sym' test1 = do let s1@(Symbol r1) = intern "foo" s2@(Symbol r2) = intern "foo" print $ r1 == r2 -- should be False -- create a weak reference to the second symbol, so we can observe -- when it is garbage collected w <- mk_weak =<< readIORef r2 print $ s1 == s2 -- should print True print =<< liftM2 sameSym (readIORef r1) (readIORef r2) -- should print True putStrLn "GCing" performGC -- this should print goodbye, representing the -- fact that the second symbol has been garbage -- collected. print . isJust =<< deRefWeak w -- should print False (object has been collected) where mk_weak o = mkWeakPtr o (Just (putStrLn "goodbye")) -- ------------------------------------------------------------------- -- Fowler / Noll / Vo (FNV) hash. Original code expected 'unsigned -- char' input. Don't know whether it behaves worse for unicode -- chars. hash :: String -> Word32 hash str = go magic_start (map ord str) where magic_start = 2166136261 :: Word32 go :: Word32 -> [Int] -> Word32 go !h [] = h go !h (c:cs) = go ((h * 16777619) `xor` fromIntegral c) cs

2 1