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

Efficient access to entry for singleton Map #673

Open
dmbarbour opened this Issue Jun 7, 2018 · 1 comment

Comments

Projects
None yet
2 participants
@dmbarbour

dmbarbour commented Jun 7, 2018

Efficient Access to Entry for Singleton Map

I propose a function is added to the Map module that can directly access the MapOne value from the tree. Something like this:

let tryMapOne (m:Map<'K,'V>) : ('K * 'V) option =
    match (m.tree) with
    | MapOne r -> Some r
    | _ -> None

Currently, to test and access single-entry maps has a lot of unnecessary overhead, e.g. we create a seq then test whether it's empty, take Seq.head, then test also whether the tail is empty.

Why would we test for single-entry maps? Well, my current use case is to maintain invariant structure of a radix tree, where I'm currently using a Map to represent the set of children. Upon removing a child, I need to know whether I have a singleton (no longer a split point in the trie). If so, I may need to recombine tree nodes. But I'm certain there are other use cases, much as we frequently test for single-entry lists.

Pros and Cons

Adding this function would improve performance for a niche use case. It won't break existing code, and the implementation is trivial. The only con I can think of is adding a little to the documentation.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): XS

Related suggestions: Maybe add to Set as well.

Affidavit (please submit!)

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I or my company would be willing to help implement and/or test this
@0x53A

This comment has been minimized.

Contributor

0x53A commented Jun 7, 2018

If #625 (target typed collection expression) were implemented, then you could use

let tryMapOne (m:Map<'K,'V>) : ('K * 'V) option =
    match (m.tree) with
    | [ r ] -> Some r
    | _ -> None

and the compiler would (hopefully) be smart enough to NOT construct a throwaway map just to compare it but instead directly check m.

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