Path: ...!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: ANN: Dogelog Player 1.2.4 (Non-Backtracking Hashtable)
Date: Thu, 7 Nov 2024 11:53:14 +0100
Message-ID: <vgi66p$9n2c$1@solani.org>
References: <vg5onm$cig5$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 7 Nov 2024 10:53:13 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="318540"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.19
Cancel-Lock: sha1:MPAOssmfRdKHmShyx0uSSZq/qQA=
In-Reply-To: <vg5onm$cig5$1@solani.org>
X-User-ID: eJwFwYEBgDAIA7CXZKMFzpEK/59ggkujwgk6FpvpRzy8qDnLiSfazL/ZnDZHCLgxke84q/tRVimtVDIP/TgjFPw=
Bytes: 2607
Lines: 50


A further library(util/tree) was realized, that
uses the rules of Okasaki's Red-Black tree with
destructive updates. change_arg/3 has become
our favorite gadget to realize imperative
datastructures in Prolog.

No setup_call_cleanup/3 brakets are needed, since
we can rely on its Prolog garbage collector
integration. We compared hash table versus red
black tree. For the million row challenge we see
an overhead below 10%.

See also:

Okasaki Red-Black Trees in Dogelog Player
https://twitter.com/dogelogch/status/1854471966234730536

Okasaki Red-Black Trees in Dogelog Player
https://www.facebook.com/groups/dogelog

Mild Shock schrieb:
> Dear All,
> 
> We are happy to announce a new edition of
> the Dogelog player:
> 
> - New library(misc/dict):
>    We have moved some predicates from the library(misc/json)
> into our own library(misc/dict).  We made sure that the
> data structure of the Prolog dicts now follows the
> input order semantics.
> 
> - New library(util/hash):
>    To enable the implementation of hash tables, Novacore
> now has a term_hash/2 predicate.  The implementation
> differs from the Prolog dict in that change_arg/3 is
> used for destructive updates.  We have also dispensed
> with the input order.
> 
> - Improved library(sequence):
>    Hash tables can easily be used to model sets of keys,
> for example by using the value "true" as an indicator.
> This allowed us to re-implement the distinct/1 predicate.
> The use of numbervars/3 ensures that key variants
> are identified.
> 
> Have Fun!
> 
> Jan Burse, http://www.xlog.ch/ , 02.11.2024