December 2010 - Libraries

RFC: Adding a Hashable type class and HashMap/HashSet data types to HP
by Johan Tibell 02 Dec '10

02 Dec '10

Hi all, This is a request for early feedback on something that I'd like to propose for the next major HP release. Milan Straka showed [1] that it's possible to design a persistent set (and thus also map) for string-like keys that's about twice as fast as the current Data.Set using hashing and a Patricia tree (i.e. IntMap). The Clojure community has also managed to create a fast persistent map, based on Bagwell's hash array mapped trie. I'd like to propose that we get the necessary infrastructure in place for creating fast and easy to use hash-based data structure. Here's what I think is needed: * A type class for things that can be hashed, Hashable. class Hashable a where hash :: a -> Word An alternative would be to have `hash` return an Int, which would make the method easier to use with Haskell data structures, which are indexed using Ints, but Word feels like the more correct type to me. The Hashable type class would have to go in either base, containers, or a new package (there's currently a hashable package on Hackage.) * Instances of Hashable for common types, in particular ByteString and Text. I already have fast instances for Text and ByteString, based on MurmurHash2 [2]. * Two new data types in the containers package, Data.HashMap and Data.HashSet. These would be persistent data structures, initially based on IntMap, and have the same or similar API to Data.Map and Data.Set.. In the future we could also add mutable HashTables, operating in the ST monad, or other hash-based data types (persistent or mutable). Any comments? Johan 1. http://research.microsoft.com/~simonpj/papers/containers/containers.pdf 2. http://sites.google.com/site/murmurhash/

14 31

Improving X11.Image
by Mitar 01 Dec '10

01 Dec '10

Hi! I have made some improvements to Graphics.X11.Xlib.Image. Currently it is made as a independent library which provides extended functionality (mostly I was interested in saving screen shots of windows), but I could be easily moved to Graphics.X11.Xlib.Image. Please see attached files. image.c and image.h is additional C code required, Image.hsc is an interface to: PlaneMask, allPlanes, Image(..), getImage, getPixel, writeBitmapFile, getHeader, readColors, getXwdColor, freeReadColors, saveImage Some links: http://tronche.com/gui/x/xlib/graphics/XGetImage.html http://tronche.com/gui/x/xlib/utilities/XWriteBitmapFile.html saveImage is a helper function for saving screen shots. Mitar

1 0

Proposal: Export String from Data.String (and two related proposals)
by Bas van Dijk 01 Dec '10

01 Dec '10

Hello, I would like to make three proposals, in order of importance IMHO: 1. Export String from Data.String. Most modules in base and on Hackage of the form: Data.<type> also export <type>. I think it's surprising and confusing that Data.String doesn't conform to this pattern. 2. Unexport String from Data.Char. I feel less strongly about this one, but in general I think it is good that a symbol is exported from as few modules as possible. 3. Export the String operations: lines, words, unlines and unwords from Data.String. I feel even less strongly about this one. However these are operations on Strings so it makes sense to export them from Data.String. As a counter argument you could say these operations either receive or produce a _list_ of Strings so they only belong in Data.List. If we accept 3 then in the spirit of "export a symbol from as few modules as possible", you may expect a fourth proposal: Unexport the String operations: lines, words, unlines and unwords from Data.List. However I think this will break lots of programs. I have no problem also discussing this one though. Discussion deadline: 3 weeks from now: Wednesday 10 November. Ticket with patches: http://hackage.haskell.org/trac/ghc/ticket/4422 Regards, Bas

5 10