4 Summary: Persistent/Functional/Immutable data structures
5 Home-page: http://github.com/tobgu/pyrsistent/
6 Author: Tobias Gustafsson
7 Author-email: tobias.l.gustafsson@gmail.com
9 Description: Pyrsistent
11 .. image:: https://travis-ci.org/tobgu/pyrsistent.png?branch=master
12 :target: https://travis-ci.org/tobgu/pyrsistent
14 .. image:: https://badge.fury.io/py/pyrsistent.svg
15 :target: https://badge.fury.io/py/pyrsistent
17 .. image:: https://coveralls.io/repos/tobgu/pyrsistent/badge.svg?branch=master&service=github
18 :target: https://coveralls.io/github/tobgu/pyrsistent?branch=master
21 .. _Pyrthon: https://www.github.com/tobgu/pyrthon/
23 Pyrsistent is a number of persistent collections (by some referred to as functional data structures). Persistent in
24 the sense that they are immutable.
26 All methods on a data structure that would normally mutate it instead return a new copy of the structure containing the
27 requested updates. The original structure is left untouched.
29 This will simplify the reasoning about what a program does since no hidden side effects ever can take place to these
30 data structures. You can rest assured that the object you hold a reference to will remain the same throughout its
31 lifetime and need not worry that somewhere five stack levels below you in the darkest corner of your application
32 someone has decided to remove that element that you expected to be there.
34 Pyrsistent is influenced by persistent data structures such as those found in the standard library of Clojure. The
35 data structures are designed to share common elements through path copying.
36 It aims at taking these concepts and make them as pythonic as possible so that they can be easily integrated into any python
37 program without hassle.
39 If you want to go all in on persistent data structures and use literal syntax to define them in your code rather
40 than function calls check out Pyrthon_.
44 .. _Sequence: collections_
45 .. _Hashable: collections_
46 .. _Mapping: collections_
47 .. _Mappings: collections_
49 .. _collections: https://docs.python.org/3/library/collections.abc.html
50 .. _documentation: http://pyrsistent.readthedocs.org/
52 The collection types and key features currently implemented are:
54 * PVector_, similar to a python list
55 * PMap_, similar to dict
56 * PSet_, similar to set
57 * PRecord_, a PMap on steroids with fixed fields, optional type and invariant checking and much more
58 * PClass_, a Python class fixed fields, optional type and invariant checking and much more
59 * `Checked collections`_, PVector, PMap and PSet with optional type and invariance checks and more
60 * PBag, similar to collections.Counter
61 * PList, a classic singly linked list
62 * PDeque, similar to collections.deque
63 * Immutable object type (immutable) built on the named tuple
64 * freeze_ and thaw_ functions to convert between pythons standard collections and pyrsistent collections.
65 * Flexible transformations_ of arbitrarily complex structures built from PMaps and PVectors.
67 Below are examples of common usage patterns for some of the structures and features. More information and
68 full documentation for all data structures is available in the documentation_.
74 With full support for the Sequence_ protocol PVector is meant as a drop in replacement to the built in list from a readers
75 point of view. Write operations of course differ since no in place mutation is done but naming should be in line
76 with corresponding operations on the built in list.
78 Support for the Hashable_ protocol also means that it can be used as key in Mappings_.
80 Appends are amortized O(1). Random access and insert is log32(n) where n is the size of the vector.
84 >>> from pyrsistent import v, pvector
86 # No mutation of vectors once created, instead they
87 # are "evolved" leaving the original untouched
98 # Random access and slicing
105 >>> list(x + 1 for x in v3)
107 >>> pvector(2 * x for x in range(3))
114 With full support for the Mapping_ protocol PMap is meant as a drop in replacement to the built in dict from a readers point
115 of view. Support for the Hashable_ protocol also means that it can be used as key in other Mappings_.
117 Random access and insert is log32(n) where n is the size of the map.
121 >>> from pyrsistent import m, pmap, v
123 # No mutation of maps once created, instead they are
124 # "evolved" leaving the original untouched
126 >>> m2 = m1.set('c', 3)
127 >>> m3 = m2.set('a', 5)
129 pmap({'a': 1, 'b': 2})
131 pmap({'a': 1, 'c': 3, 'b': 2})
133 pmap({'a': 5, 'c': 3, 'b': 2})
137 # Evolution of nested persistent structures
138 >>> m4 = m(a=5, b=6, c=v(1, 2))
139 >>> m4.transform(('c', 1), 17)
140 pmap({'a': 5, 'c': pvector([1, 17]), 'b': 6})
143 # Evolve by merging with other mappings
144 >>> m5.update(m(a=2, c=3), {'a': 17, 'd': 35})
145 pmap({'a': 17, 'c': 3, 'b': 2, 'd': 35})
146 >>> pmap({'x': 1, 'y': 2}) + pmap({'y': 3, 'z': 4})
147 pmap({'y': 3, 'x': 1, 'z': 4})
149 # Dict-like methods to convert to list and iterate
151 pvector([('a', 5), ('c', 3), ('b', 2)])
159 With full support for the Set_ protocol PSet is meant as a drop in replacement to the built in set from a readers point
160 of view. Support for the Hashable_ protocol also means that it can be used as key in Mappings_.
162 Random access and insert is log32(n) where n is the size of the set.
166 >>> from pyrsistent import s
168 # No mutation of sets once created, you know the story...
169 >>> s1 = s(1, 2, 3, 2)
171 >>> s3 = s1.remove(1)
179 # Full support for set operations
181 pset([1, 2, 3, 4, 5])
193 A PRecord is a PMap with a fixed set of specified fields. Records are declared as python classes inheriting
194 from PRecord. Because it is a PMap it has full support for all Mapping methods such as iteration and element
195 access using subscript notation.
199 >>> from pyrsistent import PRecord, field
200 >>> class ARecord(PRecord):
211 Traceback (most recent call last):
212 AttributeError: 'y' is not among the specified fields for ARecord
216 It is possible to add type information to the record to enforce type checks. Multiple allowed types can be specified
217 by providing an iterable of types.
221 >>> class BRecord(PRecord):
222 ... x = field(type=int)
223 ... y = field(type=(int, type(None)))
225 >>> BRecord(x=3, y=None)
228 Traceback (most recent call last):
229 PTypeError: Invalid type for field BRecord.x, was float
232 Custom types (classes) that are iterable should be wrapped in a tuple to prevent their
233 members being added to the set of valid types. Although Enums in particular are now
234 supported without wrapping, see #83 for more information.
238 Fields are not mandatory by default but can be specified as such. If fields are missing an
239 *InvariantException* will be thrown which contains information about the missing fields.
243 >>> from pyrsistent import InvariantException
244 >>> class CRecord(PRecord):
245 ... x = field(mandatory=True)
250 ... except InvariantException as e:
251 ... print(e.missing_fields)
257 It is possible to add invariants that must hold when evolving the record. Invariants can be
258 specified on both field and record level. If invariants fail an *InvariantException* will be
259 thrown which contains information about the failing invariants. An invariant function should
260 return a tuple consisting of a boolean that tells if the invariant holds or not and an object
261 describing the invariant. This object can later be used to identify which invariant that failed.
263 The global invariant function is only executed if all field invariants hold.
265 Global invariants are inherited to subclasses.
269 >>> class RestrictedVector(PRecord):
270 ... __invariant__ = lambda r: (r.y >= r.x, 'x larger than y')
271 ... x = field(invariant=lambda x: (x > 0, 'x negative'))
272 ... y = field(invariant=lambda y: (y > 0, 'y negative'))
274 >>> r = RestrictedVector(y=3, x=2)
276 ... r.set(x=-1, y=-2)
277 ... except InvariantException as e:
278 ... print(e.invariant_errors)
280 ('y negative', 'x negative')
283 ... except InvariantException as e:
284 ... print(e.invariant_errors)
288 Invariants may also contain multiple assertions. For those cases the invariant function should
289 return a tuple of invariant tuples as described above. This structure is reflected in the
290 invariant_errors attribute of the exception which will contain tuples with data from all failed
295 >>> class EvenX(PRecord):
296 ... x = field(invariant=lambda x: ((x > 0, 'x negative'), (x % 2 == 0, 'x odd')))
300 ... except InvariantException as e:
301 ... print(e.invariant_errors)
303 (('x negative', 'x odd'),)
308 It's possible to specify factory functions for fields. The factory function receives whatever
309 is supplied as field value and the actual returned by the factory is assigned to the field
310 given that any type and invariant checks hold.
311 PRecords have a default factory specified as a static function on the class, create(). It takes
312 a *Mapping* as argument and returns an instance of the specific record.
313 If a record has fields of type PRecord the create() method of that record will
314 be called to create the "sub record" if no factory has explicitly been specified to override
319 >>> class DRecord(PRecord):
320 ... x = field(factory=int)
322 >>> class ERecord(PRecord):
323 ... d = field(type=DRecord)
325 >>> ERecord.create({'d': {'x': '1'}})
326 ERecord(d=DRecord(x=1))
330 It is also possible to have fields with ``pyrsistent`` collections.
334 >>> from pyrsistent import pset_field, pmap_field, pvector_field
335 >>> class MultiRecord(PRecord):
336 ... set_of_ints = pset_field(int)
337 ... map_int_to_str = pmap_field(int, str)
338 ... vector_of_strs = pvector_field(str)
343 PRecords support serialization back to dicts. Default serialization will take keys and values
344 "as is" and output them into a dict. It is possible to specify custom serialization functions
345 to take care of fields that require special treatment.
349 >>> from datetime import date
350 >>> class Person(PRecord):
351 ... name = field(type=unicode)
352 ... birth_date = field(type=date,
353 ... serializer=lambda format, d: d.strftime(format['date']))
355 >>> john = Person(name=u'John', birth_date=date(1985, 10, 21))
356 >>> john.serialize({'date': '%Y-%m-%d'})
357 {'birth_date': '1985-10-21', 'name': u'John'}
360 .. _instar: https://github.com/boxed/instar/
366 A PClass is a python class with a fixed set of specified fields. PClasses are declared as python classes inheriting
367 from PClass. It is defined the same way that PRecords are and behaves like a PRecord in all aspects except that it
368 is not a PMap and hence not a collection but rather a plain Python object.
372 >>> from pyrsistent import PClass, field
373 >>> class AClass(PClass):
385 Checked collections currently come in three flavors: CheckedPVector, CheckedPMap and CheckedPSet.
389 >>> from pyrsistent import CheckedPVector, CheckedPMap, CheckedPSet, thaw
390 >>> class Positives(CheckedPSet):
391 ... __type__ = (long, int)
392 ... __invariant__ = lambda n: (n >= 0, 'Negative')
394 >>> class Lottery(PRecord):
395 ... name = field(type=str)
396 ... numbers = field(type=Positives, invariant=lambda p: (len(p) > 0, 'No numbers'))
398 >>> class Lotteries(CheckedPVector):
399 ... __type__ = Lottery
401 >>> class LotteriesByDate(CheckedPMap):
402 ... __key_type__ = date
403 ... __value_type__ = Lotteries
405 >>> lotteries = LotteriesByDate.create({date(2015, 2, 15): [{'name': 'SuperLotto', 'numbers': {1, 2, 3}},
406 ... {'name': 'MegaLotto', 'numbers': {4, 5, 6}}],
407 ... date(2015, 2, 16): [{'name': 'SuperLotto', 'numbers': {3, 2, 1}},
408 ... {'name': 'MegaLotto', 'numbers': {6, 5, 4}}]})
410 LotteriesByDate({datetime.date(2015, 2, 15): Lotteries([Lottery(numbers=Positives([1, 2, 3]), name='SuperLotto'), Lottery(numbers=Positives([4, 5, 6]), name='MegaLotto')]), datetime.date(2015, 2, 16): Lotteries([Lottery(numbers=Positives([1, 2, 3]), name='SuperLotto'), Lottery(numbers=Positives([4, 5, 6]), name='MegaLotto')])})
412 # The checked versions support all operations that the corresponding
414 >>> lottery_0215 = lotteries[date(2015, 2, 15)]
415 >>> lottery_0215.transform([0, 'name'], 'SuperDuperLotto')
416 Lotteries([Lottery(numbers=Positives([1, 2, 3]), name='SuperDuperLotto'), Lottery(numbers=Positives([4, 5, 6]), name='MegaLotto')])
418 # But also makes asserts that types and invariants hold
419 >>> lottery_0215.transform([0, 'name'], 999)
420 Traceback (most recent call last):
421 PTypeError: Invalid type for field Lottery.name, was int
423 >>> lottery_0215.transform([0, 'numbers'], set())
424 Traceback (most recent call last):
425 InvariantException: Field invariant failed
427 # They can be converted back to python built ins with either thaw()
428 # or serialize() (which provides possibilities to customize serialization)
429 >>> thaw(lottery_0215)
430 [{'numbers': set([1, 2, 3]), 'name': 'SuperLotto'}, {'numbers': set([4, 5, 6]), 'name': 'MegaLotto'}]
431 >>> lottery_0215.serialize()
432 [{'numbers': set([1, 2, 3]), 'name': 'SuperLotto'}, {'numbers': set([4, 5, 6]), 'name': 'MegaLotto'}]
438 Transformations are inspired by the cool library instar_ for Clojure. They let you evolve PMaps and PVectors
439 with arbitrarily deep/complex nesting using simple syntax and flexible matching syntax.
441 The first argument to transformation is the path that points out the value to transform. The
442 second is the transformation to perform. If the transformation is callable it will be applied
443 to the value(s) matching the path. The path may also contain callables. In that case they are
444 treated as matchers. If the matcher returns True for a specific key it is considered for transformation.
449 >>> from pyrsistent import inc, freeze, thaw, rex, ny, discard
450 >>> v1 = freeze([1, 2, 3, 4, 5])
451 >>> v1.transform([2], inc)
452 pvector([1, 2, 4, 4, 5])
453 >>> v1.transform([lambda ix: 0 < ix < 4], 8)
454 pvector([1, 8, 8, 8, 5])
455 >>> v1.transform([lambda ix, v: ix == 0 or v == 5], 0)
456 pvector([0, 2, 3, 4, 0])
458 # The (a)ny matcher can be used to match anything
459 >>> v1.transform([ny], 8)
460 pvector([8, 8, 8, 8, 8])
462 # Regular expressions can be used for matching
463 >>> scores = freeze({'John': 12, 'Joseph': 34, 'Sara': 23})
464 >>> scores.transform([rex('^Jo')], 0)
465 pmap({'Joseph': 0, 'Sara': 23, 'John': 0})
467 # Transformations can be done on arbitrarily deep structures
468 >>> news_paper = freeze({'articles': [{'author': 'Sara', 'content': 'A short article'},
469 ... {'author': 'Steve', 'content': 'A slightly longer article'}],
470 ... 'weather': {'temperature': '11C', 'wind': '5m/s'}})
471 >>> short_news = news_paper.transform(['articles', ny, 'content'], lambda c: c[:25] + '...' if len(c) > 25 else c)
472 >>> very_short_news = news_paper.transform(['articles', ny, 'content'], lambda c: c[:15] + '...' if len(c) > 15 else c)
473 >>> very_short_news.articles[0].content
475 >>> very_short_news.articles[1].content
478 # When nothing has been transformed the original data structure is kept
479 >>> short_news is news_paper
481 >>> very_short_news is news_paper
483 >>> very_short_news.articles[0] is news_paper.articles[0]
486 # There is a special transformation that can be used to discard elements. Also
487 # multiple transformations can be applied in one call
488 >>> thaw(news_paper.transform(['weather'], discard, ['articles', ny, 'content'], discard))
489 {'articles': [{'author': 'Sara'}, {'author': 'Steve'}]}
493 PVector, PMap and PSet all have support for a concept dubbed *evolvers*. An evolver acts like a mutable
494 view of the underlying persistent data structure with "transaction like" semantics. No updates of the original
495 data structure is ever performed, it is still fully immutable.
497 The evolvers have a very limited API by design to discourage excessive, and inappropriate, usage as that would
498 take us down the mutable road. In principle only basic mutation and element access functions are supported.
499 Check out the documentation_ of each data structure for specific examples.
501 Examples of when you may want to use an evolver instead of working directly with the data structure include:
503 * Multiple updates are done to the same data structure and the intermediate results are of no
504 interest. In this case using an evolver may be a more efficient and easier to work with.
505 * You need to pass a vector into a legacy function or a function that you have no control
506 over which performs in place mutations. In this case pass an evolver instance
507 instead and then create a new pvector from the evolver once the function returns.
511 >>> from pyrsistent import v
513 # In place mutation as when working with the built in counterpart
518 >>> e = e.extend([5, 6])
523 # The evolver is considered *dirty* when it contains changes compared to the underlying vector
527 # But the underlying pvector still remains untouched
531 # Once satisfied with the updates you can produce a new pvector containing the updates.
532 # The new pvector will share data with the original pvector in the same way that would have
533 # been done if only using operations on the pvector.
534 >>> v2 = e.persistent()
536 pvector([1, 22, 3, 4, 5, 7])
538 # The evolver is now no longer considered *dirty* as it contains no differences compared to the
539 # pvector just produced.
543 # You may continue to work with the same evolver without affecting the content of v2
546 # Or create a new evolver from v2. The two evolvers can be updated independently but will both
547 # share data with v2 where possible.
548 >>> e2 = v2.evolver()
551 pvector([11, 22, 3, 4, 5, 7])
553 pvector([1111, 22, 3, 4, 5, 7])
560 These functions are great when your cozy immutable world has to interact with the evil mutable world outside.
564 >>> from pyrsistent import freeze, thaw, v, m
565 >>> freeze([1, {'a': 3}])
566 pvector([1, pmap({'a': 3})])
567 >>> thaw(v(1, m(a=3)))
573 Pyrsistent is developed and tested on Python 2.7, 3.5, 3.6, 3.7 and PyPy (Python 2 and 3 compatible). It will most
574 likely work on all other versions >= 3.4 but no guarantees are given. :)
579 .. _27: https://github.com/tobgu/pyrsistent/issues/27
581 There is currently one known compatibility issue when comparing built in sets and frozensets to PSets as discussed in 27_.
582 It affects python 2 versions < 2.7.8 and python 3 versions < 3.4.0 and is due to a bug described in
583 http://bugs.python.org/issue8743.
585 Comparisons will fail or be incorrect when using the set/frozenset as left hand side of the comparison. As a workaround
586 you need to either upgrade Python to a more recent version, avoid comparing sets/frozensets with PSets or always make
587 sure to convert both sides of the comparison to the same type before performing the comparison.
592 Pyrsistent is developed with performance in mind. Still, while some operations are nearly on par with their built in,
593 mutable, counterparts in terms of speed, other operations are slower. In the cases where attempts at
594 optimizations have been done, speed has generally been valued over space.
596 Pyrsistent comes with two API compatible flavors of PVector (on which PMap and PSet are based), one pure Python
597 implementation and one implemented as a C extension. The latter generally being 2 - 20 times faster than the former.
598 The C extension will be used automatically when possible.
600 The pure python implementation is fully PyPy compatible. Running it under PyPy speeds operations up considerably if
601 the structures are used heavily (if JITed), for some cases the performance is almost on par with the built in counterparts.
606 PEP 561 style type hints for use with mypy and various editors are available for most types and functions in pyrsistent.
608 Type classes for annotating your own code with pyrsistent types are also available under pyrsistent.typing.
613 pip install pyrsistent
618 Available at http://pyrsistent.readthedocs.org/
620 Brief presentation available at http://slides.com/tobiasgustafsson/immutability-and-python/
625 Tobias Gustafsson https://github.com/tobgu
627 Christopher Armstrong https://github.com/radix
629 Anders Hovmöller https://github.com/boxed
631 Itamar Turner-Trauring https://github.com/itamarst
633 Jonathan Lange https://github.com/jml
635 Richard Futrell https://github.com/Futrell
637 Jakob Hollenstein https://github.com/jkbjh
639 David Honour https://github.com/foolswood
641 David R. MacIver https://github.com/DRMacIver
643 Marcus Ewert https://github.com/sarum90
645 Jean-Paul Calderone https://github.com/exarkun
647 Douglas Treadwell https://github.com/douglas-treadwell
649 Travis Parker https://github.com/teepark
651 Julian Berman https://github.com/Julian
653 Dennis Tomas https://github.com/dtomas
655 Neil Vyas https://github.com/neilvyas
657 doozr https://github.com/doozr
659 Kamil Galuszka https://github.com/galuszkak
661 Tsuyoshi Hombashi https://github.com/thombashi
663 nattofriends https://github.com/nattofriends
665 agberk https://github.com/agberk
667 Waleed Khan https://github.com/arxanas
669 Jean-Louis Fuchs https://github.com/ganwell
671 Carlos Corbacho https://github.com/ccorbacho
673 Felix Yan https://github.com/felixonmars
675 benrg https://github.com/benrg
677 Jere Lahelma https://github.com/je-l
679 Max Taggart https://github.com/MaxTaggart
681 Vincent Philippon https://github.com/vphilippon
683 Semen Zhydenko https://github.com/ss18
685 Till Varoquaux https://github.com/till-varoquaux
687 Michal Kowalik https://github.com/michalvi
689 ossdev07 https://github.com/ossdev07
691 Kerry Olesen https://github.com/qhesz
693 johnthagen https://github.com/johnthagen
698 Want to contribute? That's great! If you experience problems please log them on GitHub. If you want to contribute code,
699 please fork the repository and submit a pull request.
703 .. _tox: https://tox.readthedocs.io/en/latest/
705 Tests can be executed using tox_.
707 Install tox: ``pip install tox``
709 Run test for Python 2.7: ``tox -epy27``
714 * Update README with any new contributors and potential info needed.
715 * Update _pyrsistent_version.py
716 * python setup.py sdist upload
717 * Commit and tag with new version: git add -u . && git commit -m 'Prepare version vX.Y.Z' && git tag -a vX.Y.Z -m 'vX.Y.Z'
718 * Push commit and tags: git push && git push --tags
722 Pyrsistent can be considered stable and mature (who knows, there may even be a 1.0 some day :-)). The project is
723 maintained, bugs fixed, PRs reviewed and merged and new releases made. I currently do not have time for development
724 of new features or functionality which I don't have use for myself. I'm more than happy to take PRs for new
725 functionality though!
727 There are a bunch of issues marked with ``enhancement`` and ``help wanted`` that contain requests for new functionality
728 that would be nice to include. The level of difficulty and extend of the issues varies, please reach out to me if you're
729 interested in working on any of them.
731 If you feel that you have a grand master plan for where you would like Pyrsistent to go and have the time to put into
732 it please don't hesitate to discuss this with me and submit PRs for it. If all goes well I'd be more than happy to add
733 additional maintainers to the project!
736 Classifier: Intended Audience :: Developers
737 Classifier: License :: OSI Approved :: MIT License
738 Classifier: Operating System :: OS Independent
739 Classifier: Programming Language :: Python :: 3.5
740 Classifier: Programming Language :: Python :: 3.6
741 Classifier: Programming Language :: Python :: 3.7
742 Classifier: Programming Language :: Python :: Implementation :: PyPy