mndrix / ddata Goto Github PK

When working with partial lists, one can Tail=[] to "seal" the list and prevent it from gaining any more elements. A similar feature would helpful with declarative arrays.

Arrays currently use 1-based indexing. That's in line with Prolog tradition (see arg/3 and nth/3). There are arguments in favor of 0-based indexing. I don't know that the arguments outweigh the value of tradition but I want to give them some more thought.

An upsert operation behaves like an insert if the key is absent and an update if the key is present. In some contexts, one doesn't know whether a map contains a specific key but wants to make sure that a new map does contain it.

%% upsert(+Key,?Value,?Map0,Map)
%
%  True if Map maps Key to Value and mappings for all other keys are
%  identical to those in Map0.

A naive implementation is something like:

upsert(Key,Value,Map0,Map) :-
    ( insert(Key,Value,Map0,Map) -> true; update(Key,Value,Map0,Map) ).

There might be a faster implementation which avoids traversing the tree twice. I'm also doubtful that this implementation works in all desired modes.

It can be helpful to add a single new element to an array without caring which index is assigned to that element. I borrowed the name conj from Clojure but am not opposed to something else.

Although this predicate is not as declarative as some of the other array predicates, it's practical enough that I think it's worth including.

%% conj(?Array,+X) is semidet.
%
%  Adds X to Array.  Fails if Array is sealed.
%
%  ?- array:conj(A,a), array:conj(A,b), array:list(A,List).
%  List = [a,b].

If I have an array representing [a,b,c,d], I should be able to take a "slice" out of the middle and have an array representing [b,c]. I don't know if this should apply only to persistent arrays or to declarative arrays too.

When profiling map and pmap, the biggest consumers of CPU time (after GC) is computations related to the hash. Part of this is converting the hash bytes into a big integer. The other is performing math operations on this big integer.

By using a list of bytes as the hash, we should be able to defer most of that computation until later. For sparse maps, deferring the computation effectively eliminates it.

I don't think this will cause extra GC pressure because the hash lists will be shared between trees.

The basic design is to store the hash in a term like hash(AvailableBits,NextByte,Bytes). A quick sketch of using this term in hash_residue_n/3

hash_residue_n(hash(Available,Byte,Bytes),Residue,N) :-
    plump_shift(Shift),
    compare(Ord,Available,Shift),
    hash_residue_n(Ord,hash(Available,Byte,Bytes),Residue,N).

hash_residue_n((=),hash(_,N,[NextByte|Bytes]),hash(8,NextByte,Bytes),N).
hash_residue_n((>),hash(Available,Byte0,Bytes),hash(Left,Byte,Bytes),N) :-
    plump_shift(Shift),
    plump_mask(Mask),
    N is Mask /\ Byte,
    Byte is Byte0 >> Shift,
    Left is Available - Shift.
hash_residue_n((<),hash(Available,Byte0,[NextByte|Bytes]),hash(Left,Byte1,Bytes),N) :-
    plump_shift(Shift),
    NeedMoreBits is Shift - Available,
    Mask is (1 << NeedMoreBits) - 1,
    ExtraBits is ByteNext /\ Mask,
    N is (ExtraBits << NeedMoreBits) /\ Byte0,
    Byte1 is (ByteNext >> NeedMoreBits),
    Left is 8 - NeedMoreBits.

The predicate insert/4 allows one to add a new key-value mapping. It doesn't allow one to change an existing mapping. We want an interface something like this:

%% update(+Key,?Old,?New,?Map0,?Map)
%
%  True if Map0 associates Key with Old and Map associates Key with New.
%  Map0 and Map are identical in all other mappings.

update/4 is a thin wrapper around update/5 which ignores the value of Old.

A naive implementation is:

update(Key,Old,New,Map0,Map) :-
    insert(Key,Old,Map1,Map0),
    insert(Key,New,Map1,Map).

That won't work in all desired modes. It also generates some unnecessary garbage. The predicate should descend through the tree based on Key's hash then relate the two nodes to indicate the change in value.

The pmap module is both an interface and an implementation of that interface. Ideally one changes an import line from use_module(library(pmap/hamt)) to use_module(library(pmap/dict)) and doesn't have to change any code. The new implementation is automatically used everywhere it's needed.

I'd also like to be able to reuse the existing pmap test suite across all these implementations. They should all behave identically and the test suite shouldn't make any assumptions about the implementation.

I'd like to have implementations based on:

• dicts
• key-value lists (see pairs)
• rbtrees
• assoc

I'm not sure if we need one for both rbtrees and assoc. Those fill a similar niche but rbtrees are more performant.