immutables
==========

.. image:: https://travis-ci.org/MagicStack/immutables.svg?branch=master
    :target: https://travis-ci.org/MagicStack/immutables

.. image:: https://ci.appveyor.com/api/projects/status/tgbc6tq56u63qqhf?svg=true
    :target: https://ci.appveyor.com/project/MagicStack/immutables

An immutable mapping type for Python.

The underlying datastructure is a Hash Array Mapped Trie (HAMT)
used in Clojure, Scala, Haskell, and other functional languages.
This implementation is used in CPython 3.7 in the ``contextvars``
module (see PEP 550 and PEP 567 for more details).

Immutable mappings based on HAMT have O(log N) performance for both
``set()`` and ``get()`` operations, which is essentially O(1) for
relatively small mappings.

Below is a visualization of a simple get/set benchmark comparing
HAMT to an immutable mapping implemented with a Python dict
copy-on-write approach (the benchmark code is available
`here <https://gist.github.com/1st1/292e3f0bbe43bd65ff3256f80aa2637d>`_):

.. image:: bench.png


Installation
------------

``immutables`` requires Python 3.5+ and is available on PyPI::

    $ pip install immutables


immutables.Map
--------------

The ``Map`` object implements ``collections.abc.Mapping`` ABC
so working with it is very similar to working with Python dicts.

The only exception are its ``Map.set()`` and ``Map.delete()`` methods
which return a new instance of ``Map``:

.. code-block:: python

    m1 = Map()  # an empty Map
    m2 = m1.set('key1', 'val1')  # m2 has a 'key1' key, m1 is still empty

    m3 = m2.set('key2', 'val2')
    m3 = m3.delete('key1')  # m3 has only a 'key2' key


Further development
-------------------

* An immutable version of Python ``set`` type with efficient
  ``add()`` and ``discard()`` operations.

* Add support for efficient ``Map.update()`` operation, allow to
  pass a set of key/values to ``Map()``, and add support for
  pickling.


License
-------

Apache 2.0
e'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/guix/log/?id=505258172e7bc2b67469b395cb46e38ef2f3069e'>root</a>/<a href='/guix/log/build-aux?id=505258172e7bc2b67469b395cb46e38ef2f3069e'>build-aux</a>/<a href='/guix/log/build-aux/cuirass?id=505258172e7bc2b67469b395cb46e38ef2f3069e'>cuirass</a>/<a href='/guix/log/build-aux/cuirass/evaluate.scm?id=505258172e7bc2b67469b395cb46e38ef2f3069e'>evaluate.scm</a></div><div class='content'><table class='list nowrap'><tr class='nohover'><th class='left'>Age</th><th class='left'>Commit message (<a href='/guix/log/build-aux/cuirass/evaluate.scm?id=505258172e7bc2b67469b395cb46e38ef2f3069e&amp;showmsg=1'>Expand</a>)</th><th class='left'>Author</th></tr>
<tr><td><span title='2022-05-26 11:41:05 +0200'>2022-05-26</span></td><td><a href='/guix/commit/build-aux/cuirass/evaluate.scm?id=d90bd5642a3663cc7d5124068fadbf8fa28b3207'>cuirass: Create just as many threads as needed.</a><span class='msg-avail'>...</span></td><td>Ludovic Courtès</td></tr>
<tr><td><span title='2022-05-26 11:41:05 +0200'>2022-05-26</span></td><td><a href='/guix/commit/build-aux/cuirass/evaluate.scm?id=98a6642298be6663b9d318b7dea46d1dba275839'>cuirass: Fork inferior processes before creating threads.</a><span class='msg-avail'>...</span></td><td>Ludovic Courtès</td></tr>
<tr><td><span title='2022-05-20 18:46:07 +0200'>2022-05-20</span></td><td><a href='/guix/commit/build-aux/cuirass/evaluate.scm?id=598f7289db9955584457ffc11c8504f3938a1618'>cuirass: Close each inferior upon completion.</a><span class='msg-avail'>...</span></td><td>Ludovic Courtès</td></tr>