diff options
Diffstat (limited to 'documentation/book/the_lux_programming_language/chapter_15.md')
| -rw-r--r-- | documentation/book/the_lux_programming_language/chapter_15.md | 22 |
1 files changed, 13 insertions, 9 deletions
diff --git a/documentation/book/the_lux_programming_language/chapter_15.md b/documentation/book/the_lux_programming_language/chapter_15.md index c87494929..d30feb1cf 100644 --- a/documentation/book/the_lux_programming_language/chapter_15.md +++ b/documentation/book/the_lux_programming_language/chapter_15.md @@ -15,26 +15,29 @@ That is why there are so many different types of data-structures, and so many di But not all such implementations fit into the functional paradigm of keeping all your data immutable, and most implementations of data-structures are actually mutable, and meant for imperative programming. Now, let's not be naïve. + Everybody can figure out that making a data-structure immutable and just copying the whole thing every time you want to make a change would make those data-structures prohibitively expensive to use. Luckily for us, there is a way to have immutable data-structures that have _reasonable performance_. + The reason why they are _fast enough_ to be used, is that they are designed to re-use as many nodes as they can whenever an update needs to be done, in order to avoid wasteful re-work wherever possible. Make no mistake, they are still not as fast as their mutable counterparts (which you can still access by doing host-interop), but they are designed with high-performance in mind, and so they tend to be _fast enough_ for most use-cases. Lux offers a variety of these persistent data-structures. + Here are some examples: -## Rows +## Sequences - Located in `library/lux/data/collection/row`. + Located in `library/lux/data/collection/sequence`. These are similar to lists in that they are sequential data-structures, but there are a few differences: -1. Whereas lists prepend values to the front, rows append them to the back. -2. Random access on lists has a complexity of O(N), whereas it's O(log N) for rows. +1. Whereas lists prepend values to the front, sequences append them to the back. +2. Random access on lists has a complexity of O(N), whereas it's O(log N) for sequences. -Rows are a great substitute for lists whenever random access is a must, and their implementation ensures updates are as cheap as possible. +Sequences are a great substitute for lists whenever random access is a must, and their implementation ensures updates are as cheap as possible. ## Queues @@ -52,7 +55,7 @@ This is your standard key-value data-structure. Known by other names (tables, maps, etc), dictionaries give you efficient access and updating functionality. -All you need to do is give it a `Hash` instance (from `library/lux/abstract/hash`) for your _"key"_ type, and you're good to go. +All you need to do is give it a `Hash` implementation (from `library/lux/abstract/hash`) for your _"key"_ type, and you're good to go. ## Sets @@ -68,17 +71,18 @@ This is a killer combination. Instead of using mutable data-structures for your changing program data, you can just use persistent data-structures, with the mutability being delegated the the STM system. -This will make concurrently working with these data-structures a piece of cake, since you never have to worry about synchronizing/locking anything to avoid simultaneous updating, or any of the other crazy things programmers have to do to avoid data corruption. +This will make working concurrently with these data-structures a piece of cake, since you never have to worry about synchronizing/locking anything to avoid simultaneous updating, or any of the other crazy things programmers have to do to avoid data corruption. ## Arrays: the not-so-persistent data structures Located in `library/lux/data/collection/array`. -The `library/lux/data/collection/array` module features mutable arrays you can use if you need fast access and mutation and are willing to run the risks involved with using mutable data. +The `library/lux/data/collection/array` module features mutable arrays you can use if you need fast random access and mutation and are willing to run the risks involved with using mutable data. -Another possible use is to implement other data-structures (and, as it turns out, rows, dictionaries and sets all rely on arrays in their implementations). +Another possible use is to implement other data-structures (and, as it turns out, sequences and dictionaries both rely on arrays for their implementations). Also, it's worth nothing that in the _JVM_, this corresponds to _object arrays_. + If you want primitive arrays, you should check out the functionality for that in `library/lux/ffi`. --- |