Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Should RandomAccessList and PersistentVector be merged? #58

Open
rmunn opened this issue Feb 16, 2016 · 2 comments
Open

Should RandomAccessList and PersistentVector be merged? #58

rmunn opened this issue Feb 16, 2016 · 2 comments

Comments

@rmunn
Copy link
Contributor

rmunn commented Feb 16, 2016

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.

@jackfoxy
Copy link
Contributor

@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
Copy link
Contributor

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants