[Haskell-cafe] Re[2]: [Haskell] My summer of code project: HsJudy

[Bulat Ziganshin]

(moved to haskell-cafe)

Hello Jean-Philippe,

Tuesday, May 30, 2006, 2:58:01 PM, you wrote:

>> 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

> I'm not sure there is significant overlap between what we're doing.
> I'd be delighted to cooperate if you think this is possible though.

well, what i think: while all the actual work will be performed by
Caio himself, we can help him (and to ourselves as possible future
users of this lib) by describing infrastructure in that he need to
insert his work and pointing to "adjancent" projects

so, Caio, now i write for you, better organizing my previous post:

1. In terms of Haskell, Judy is a library of _mutable_ collections of
_unboxed_ elements. i pointed you to the Array wiki page, where
differences between boxed and unboxed, mutable and immutable
datastructures are described

2. Collections is a library of _immutable_ datastructures, and
Jean-Philippe especially omitted any support for mutable
datastructures - because it's the whole story of it's own. So, you
don't need to write your work as part of the Collections library

3. Nevertheless, Collections has GREAT organization and it will be
very helpful to study it. in particular, see at the Data.Collections
module, what describes various classes into which all collections are
fitted, and hierarchy between them

4. Next, when you will search for the datatypes/classes whose
interface you can imitate, you will find only Data.HashTable - other
datatypes in standard libraries are either immutable (say, Map) or
need contiguous indexes (say, MArray). So you will need to create your
own interface and here you can borrow from the Collections lib. Just
see at the differences between IArray and MArray classes. They are
very close, only MArray class update arrays on-the-place and has
additional 'Monad m' on all it's return types. say,

class IArray a e where
  unsafeAt :: (Index i) => a i e -> i -> e

becomes

class MArray a e m where
  unsafeRead :: (Index i) => a i e -> i -> m e

You can do the same with Collections classes. instead of reinventing
the wheel, you can add letter 'M' to it :)

say,

class Monoid c => Map c k a | c -> k a where
    insert :: k -> a -> c -> c
    delete :: k -> c -> c
    member :: k -> c -> Bool

would become

class (Monoid c, Monad m) => MapM c k a | c -> k a where
    insertM :: k -> a -> c -> m ()
    deleteM :: k -> c -> m ()
    memberM :: k -> c -> m Bool


5. as i already said, then you should use StablePtr and any form of
hashing/seriazliation in order to map between boxed (Haskell) and
unboxed (C) values. and then you can develop series of Diff
transformers what emulates immutable collections via mutable ones (say
interface of class Map via the interface of class MapM), DiffArray can
serve as template here

6. There is no class framework for container types other than this
Data.Collections module, so implementing it's close imitation (with
monadic operations) will help future users to easily learn and use
both interfaces

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