fsprojects / fsprojects/FSharpx.Collections

Should RandomAccessList and PersistentVector be merged?

Open
#58 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

help wanted 2.0
Dominant language
F#
Stars
253
Forks
76
Avg merge
49m
Merged PRs (30d)
1

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.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Read the existing RandomAccessList and PersistentVector implementations and the discussion in #54; compare their indexing and iterator behavior with the pseudocode here. Done means the project has a decided approach to sharing or merging the implementations while preserving the differing access and iteration behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
fsharp
Domain
tooling
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
32/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.