Hash consing (was: Re: sqlite3)

[Po Lu]

LdBeth <andpuke@foxmail.com> writes:

> It seems no one has yet pointed out "preserving EQness" is actually
> hash-consing[1], a technique has been developed in Lisp and now well
> known in Functional Programming communities.
>
> It has main features that:
>
> 1. Keeps only one copy of (structurally) EQUAL objects and therefore
> 2. reduce storage usage
> 3. reduce the time needed to do a EQUAL comparsion to EQ.
> 4. useful for function memoization
>
> It is definitely useful, but I think we could make it into a separated
> package, probably.

I wonder how hash consing would make sense in a language like Emacs Lisp
that has `rplaca' and `rplacd'.

Perhaps we would need some kind of immutable cons data type.