[Haskell] My summer of code project: HsJudy

[Bulat Ziganshin]

Hello Caio,

Tuesday, May 30, 2006, 5:29:46 AM, you wrote:

> I'm Caio Marcelo and my project for this Summer of Code is "Fast
> Mutable Collection Types for Haskell", I'll be implementing a lot of
> APIs for data collections (like Map and Arrays) using Judy library as
> backend.

my comments to your README:

>Design an API based on existing Haskell libraries. This involves
>studying the Haskell API and seeing which ones would have Judy-based
>support, good candidates are Map, IntSet and IntMap.

Judy implements _mutable_ array/map/set, so closest interfaces for
your lib will be MArray and HashTable. DiffArray is a general way to
make IArray (interface) on the base of MArray (interface), that is
usable with any datastructure implementing MArray interface

afaik, in orer to store Haskell objects in external datastructures,
one should use StablePtr (see the module Foreign.StablePtr). i'm not
sure that GHC will be efficient when working with large number of
StablePtrs. of course, it will be not required for storing simple
(unboxed) values, such as Int or Double. for further info about
unboxed containers and immutable vs mutable containers read
http://haskell.org/haskellwiki/Arrays


you should also see to the Collections package:
darcs get --partial http://darcs.haskell.org/packages/collections/
although it contains only _immutable_ datastructures at this
moment. may be, you can codevelop with Bernardy interface for mutable
maps/sets


> all Haskell software that uses common data structures like Maps and
> Arrays would benefit from a faster implementation

sorry, i don't think so. especially for Arrays ;)


> Some work[4] has already been done in Judy1 (mapping from words to bits)

Data.HashTable contains two hash functions. you can start with it and
develop hashing class:

class Hash a where
  hash :: a-> Int32

instance Hash String where
  hash = hashString


>It's possible that no Haskell API matches some functionalities (like
>'unbounded' Arrays);

this functionality is supported in my revision of Array libraries. i
will inform you as i it will be published


> If you want to know more about it, take a look at my SoC blog at

the Judy library itself:
http://judy.sf.net
http://mesh.dl.sourceforge.net/sourceforge/judy/Judy-1.0.3.tar.gz


and last but not least :)  feel free to ask us in the haskell-cafe
and on IRC


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com