3 ms·
There aren't any cycles, so this shouldn't be difficult. I'm not sure how efficient it'll be though, even with laziness.
by pmjordan 17y ago
There aren't any cycles, so this shouldn't be difficult. I'm not sure how efficient it'll be though, even with laziness.
- crux_ 17y agoAn easy first guess as to efficiency would be O(n) for insertions and deletions, since that's what you need to maintain a sorted list (which is the lowest level of a skip-list).
- chancho 17y agoIt doesn't have to be a linked list though. There are other purely functional sequence data structures which support O(log n) insertion and deletion, e.g. Haskell's Data.Sequence, which is a finger tree of some sort. If you could find a way to do binary search on one of these in better than O(log^2 n) time you'd pretty much have your purely functional skip list.