Repository navigation
Should RandomAccessList and PersistentVector be merged? #58
Description
While working on #54, I started to realize that the RandomAccessList data structure wasn't just similar to PersistentVector, it WAS a PersistentVector that simply iterated in reverse order, and when accessed by index, accessed the item at (count-1)-idx instead. This strikes me as unnecessary duplication of code. Why not just add one function to PersistentVector named reversedIterator, then implement RandomAccessList as something like this instead?
type RandomAccessList =
inherit PersistentVector
val lastIndex = count - 1
override this.Item with get i =
base.[lastIndex - i]
override this.rangedIterator(startIndex, endIndex) =
base.reversedIterator(lastIndex - startIndex, lastIndex - endIndex)
override this.reversedIterator(startIndex, endIndex) =
base.rangedIterator(lastIndex - startIndex, lastIndex - endIndex)
override this.ofSeq items =
// items |> Seq.rev |> base.ofSeq // F# 4.0
items |> List.ofSeq |> List.rev |> Seq.ofList |> base.ofSeq // F# 3.1
override this.Last = invalidOp "Can't take Last of a RandomAccessList"
override this.Head = base.Last
// etc., etc., etc.(Note: the above is not valid F# code; I left out constructor parameters, generic types, and so on. Think of it as F# pseudocode).
The RandomAccessList module could stay pretty much the same, as most of its contents are simply calling the corresponding methods of the RandomAccessList type (or the RandomAccessList class, in C# terminology). But the duplication of code could be done away with.
Activity
jackfoxy commentedon Apr 29, 2018
@rmunn this is a good idea, and since there are already unit tests in place, probably can be done safely (after reviewing unit tests for some comfort level of completion).
I would also be more comfortable seeing a BenchmarkDotNet comparison before and after of both collections, just to confirm it doesn't impact performance.
I would accept such a PR.
jackfoxy commentedon Feb 23, 2020
I created RandomAccessList from @forki 's implementation of PersistentVector.
I have a new found interest in RandomAccessList. I have found it is the ideal implementation of Vector in a project I am working on, so I am interested in bringing it up to date.
I'm not interested in doing this code merge and interface myself. I will be adding functions to its module.
github-actions commentedon Apr 25, 2026
🤖 This is an automated response from Repo Assist.
Good design question — here is an updated analysis of where things stand.
Current relationship between the two types
RandomAccessListis a separately-implemented persistent data structure using a skew-binary random-access list, whilePersistentVectoruses a 32-branching trie. They are not the same structure with a reversed iterator:head/tail(first/last)conj(append to end)So
RandomAccessList.headreturns the last-added element, whilePersistentVector.headreturns the first-added. This is a semantic difference, not merely a reversed view.Is merging still worth it?
The maintainer's 2020 comment indicates interest in keeping
RandomAccessListas a distinct, actively improved structure. Given the different algorithmic properties and the O(1) head/tail advantage ofRandomAccessList, a merge would likely sacrifice performance at the interface boundary.More tractable option
Rather than merging the types, it might be worth documenting the tradeoffs so consumers can make an informed choice. A short prose comparison in the README or XML docs would help. If the maintenance burden of two similar structures is the concern, sharing more test utilities (property test generators etc.) could help without risking correctness.
Happy to contribute either a documentation PR or further investigation if that would help.