Re:Immer is a library of persistent and immutable data struc...
by nomad010 on Thursday September 12, 2019 @04:04AM
(#20949118)
Yes, immutable data structures can be used for capturing a temporal aspect without actually needing to model it explicitly in the underlying data.
Here's a document[1] explaining how to make a tree-like data structures persistent along with a motivating example of their use (at the end). The wikipedia page[2] for the problem also goes into other techniques and has some diagrams too.
tl;dr a naive approach to the point location query problem achieves O(N^2) space and O(logN) time per query, while simply modifying the data structure to be persistent achieves O(N) space while retaining O(logN) time per query.
Here's a document[1] explaining how to make a tree-like data structures persistent along with a motivating example of their use (at the end). The wikipedia page[2] for the problem also goes into other techniques and has some diagrams too.
tl;dr a naive approach to the point location query problem achieves O(N^2) space and O(logN) time per query, while simply modifying the data structure to be persistent achieves O(N) space while retaining O(logN) time per query.
[1] https://saco-evaluator.org.za/presentations/camp3_2017/persi... [2] https://en.wikipedia.org/wiki/Point_location