Pointers in Haskell
While reading through What a Jane Street software engineering interview is like, I came across the usage of a doubly-linked list (LL) data structure.
We were implementing memoization, using a HashMap. A memory leak could occur if the cache was unbound.
Hence we bound the cache, and use apolicy.
Hence we need to maintain ordering. We want to do this in O(1) time.
We store a pointer to the start and end of the LL.
When looking up an element:
- It exists in HashMap -> Splice out of LL, cons to LL.
- Does not exist -> Max bound? If maxbound -> pop last elem of LL, cons new elem to LL. If not maxbound -> cons new elem to LL.
Each time we store to hashmap, also store a pointer to the position on LL.
This involves mutation, is there a way we can implement this in a pure way, and get O(1) performance as well?