fsprojects / fsharpx.collections Goto Github PK

I have old project, that uses FSharp.PowerPack and I want to move some parts to FSharpx.Collections.
After namespace transformation, I ran into a problem:
PowerPack contains other collections, in particular, Tagged.Map
https://github.com/fsprojects/powerpack-archive/blob/master/src/FSharp.PowerPack/TaggedCollections.fs

There's some types in my project, like:
type NamesMap<'v> = Tagged.Map<NameTypes.SomeName, 'v, NameTypes.NameComparer>
Can you recommend, what's the most convenient way to transform this code into your collections? Is it possible to transform, without code modification?

Thank you.

Based on https://github.com/fsharp/FSharpLangDesign/blob/master/FSharp-4.0/ListSeqArrayAdditions.md

https://www.nuget.org/packages/FSharpx.Collections/1.12.1 has a broken nuspec. The dependency on FSharp.Core is listed as <dependency id="FSharp.Core" version="" /> which causes the NuGet client to install FSharp.Core.2.0.0.0 even in a .NET 4.5.2 project.

Description

The PersistentVector class (and any other list-like classes that know their own length as an O(1) operation, such as RandomAccessList) should probably implement the IReadOnlyCollection<'T> interface. It's a very simple interface, only requiring a Count property. The only tricky thing is that IReadOnlyCollection<'T> was added to .Net relatively recently, so it's only in .Net Framework starting with .Net Framework 4.5, it's only in Windows Phone starting with Windows Phone 8.1, and so on. So adding this interface would tend to break compatibility with some older .Net implementations, and thus it should be behind a compile-time flag that can turn it off if FSharpx.Collections is being built for an older profile. See, for example, how the FSCORE_PORTABLE_OLD flag is defined for some protable profiles (like profile 47), and how that flag is used to skip compiling non-portable bits on older systems.

Pros

Once the ISeq implementation gets merged in, it will be able to handle PersistentVectors far more efficiently in any situation where a count is required (such as the Array.ofSeq implementation that wants to know the length of the incoming data so it can pre-allocate an array to store the result). It would be a shame if a highly-efficient, persistent, immutable collection like PersistentVector ended up causing unnecessary O(N) operations that could have been skipped by simply adding a one-line interface implementation.

Cons

The need to keep FSharpx.Collections portable to older .Net versions will necessarily increase the complexity of the project's build system; compiler directives are never nice things to see in one's code. The alternative to a compiler directive would be to explicitly abandon support .Net 4.0 and earlier, Windows Phone 8.0 and earlier, and so on.

I want to use FSharpx.Collections (and other FSharpx.* packages) in project which should be signed with strong name.
Can you please publish FSharpx.* packages with signed assemblies?

The GitHub link on http://fsprojects.github.io/FSharpx.Collections/ redirects to https://github.com/fsprojects/FSharpx.Collectionsd/ instead of https://github.com/fsprojects/FSharpx.Collections/

Some (merge and insert) of the given complexities for the pairing heap implementation seem to be wrong (it might be a copy-pasting error).
They are not coherent with Chris Okasaki's Functional Data Structures (p25), neither wikipedia (which has a source for the complexity of the delemin operation).

The correct values should be :

• insert : O(1) worst case
• merge : O(1) worst case
• tryMerge : O(1) worst case

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.

Description

The FSharpx.Collections build should move to target net45 as an absolute minimum, and leave net40 behind. FSharp.Core now requires net45 as of version 4.2.1, which means that if I want to use FSharpx.Collections in a project I now have to specify a dependency on FSharp.Core < 4.2. I've done a quick, unscientific survey of GitHub and found that the only projects that use FSharpx.Collections but still depend on .NET 4.0 are ones that haven't been updated in five years; anything currently maintained is at least on .NET 4.5 or higher. So as far as I can tell, there will be basically no cost to moving FSharpx.Collections to .NET 4.5.

Besides which, moving to .NET 4.5 will allow us to implement IReadOnlyCollection in the collections where it makes sense, which may enable future optimizations like this one.

see http://sourceforge.net/p/sasa/code/ci/default/tree/Sasa.Collections/Vector.cs

The convention is usually that linear data structures implement Length and map-like structures implement Count.

Time and time again I face the issue of having to replace a Map with a list of pairs, because I need the original order to be preserved.
Would be nice to have a collection like that, even if it's just having both Map and a list of keys under the hood

Description

Duplicate keys should result in adding comma separated value.

See remarks https://msdn.microsoft.com/en-us/library/xsc9a449(v=vs.110).aspx

Note poor design in .NET System.Collections.Specialized results in following bad behavior:

let a = NameValueCollection()
a.Add("1", "uno")
a.Add("1", "one")
a.Add("1", "one,and one")

a.["1"];
val it : string = "uno,one,one,and one"

Repro steps

see existing unit test

Expected behavior

Please provide a description of the behavior you expect.

Actual behavior

Currently concat results in duplicate entries of same key instead of CSV

Description

https://github.com/fsprojects/FSharpx.Collections/blob/29180453c46b173a6b69fe3aa3313f634723ad68/src/FSharpx.Collections/Collections.fs#L452-452

let inline catOptions (xs:Option<'a> list) = List.choose id

Should be either of

let inline catOptions : Option<'a> list -> 'a list = List.choose id
let inline catOptions (xs:Option<'a> list) = List.choose id xs

Repro steps

Attempt to use catOptions in code.

Expected behavior

catOptions should have the signature Option<'a> list -> 'a list.

Actual behavior

The signature is Option<'b> list -> Option<'a> list -> 'a list.

Known workarounds

use List.choose id instead.

Related information

• Operating system
  Affects all
• Branch
  Master
• .NET Runtime, CoreCLR or Mono Version
  Affects all

The build.fsx script currently creates AssemblyInfo.fs files in the wrong location. This has been fixed in ProjectScaffold -- see fsprojects/ProjectScaffold#151 -- but that fix needs to make its way into Fsharpx.Collections. We could either grab the latest ProjectScaffold, or just grab fsprojects/ProjectScaffold@dc7d7aa to fix this one issue without affecting other files.

Without this fix, the AssemblyInfo.fs files are being created in the wrong directory. Current output:

Created AssemblyInfo file "src/home/rmunn/code/fsharp/FSharpx.Collections/src/FSharpx.Collections/AssemblyInfo.fs".
Created AssemblyInfo file "src/home/rmunn/code/fsharp/FSharpx.Collections/src/FSharpx.Collections.Experimental/AssemblyInfo.fs".

Those relative paths expand to /home/rmunn/code/fsharp/FSharpx.Collections/src/home/rmunn/code/fsharp/FSharpx.Collections/src/FSharpx.Collections.Experimental/AssemblyInfo.fs and /home/rmunn/code/fsharp/FSharpx.Collections/src/home/rmunn/code/fsharp/FSharpx.Collections/src/FSharpx.Collections/AssemblyInfo.fs, which is clearly wrong.

Output after bugfix (remove the src @@ from one line of build.fsx) is applied:

Created AssemblyInfo file "/home/rmunn/code/fsharp/FSharpx.Collections/src/FSharpx.Collections/AssemblyInfo.fs".
Created AssemblyInfo file "/home/rmunn/code/fsharp/FSharpx.Collections/src/FSharpx.Collections.Experimental/AssemblyInfo.fs".

PersistentHashMap.containsKey returns false negatives, if the value of the key-value pair is null.

This can also manifest if the value is None, or the value is unit. In fact, I discovered this because I was trying to treat PersistentHashMap<'a, unit> like a persistent hash set. This is because, internally, .NET stores None and unit as null.

Example:

open FSharpx.Collections

[<EntryPoint>]
let main (argv : string array) : int = 
    let key = "key"
    let value = None // or ()
    let map = PersistentHashMap.add key value PersistentHashMap.empty
    // Assertion fails
    assert (PersistentHashMap.containsKey key map)
    0

The NuGet Gallery is now serving a corrupt FSharpx.Collections.1.9.4.nupkg. This started happening sometime between Friday and today, Monday. Our builds failed until I put an working copy in our AppVeyor NuGet feed.

get-filehash $env:localappdata\nuget\cache\FSharpx.Collections.1.9.4.nupkg -algorithm md5

md5 of working: B76B5AA6534862913BFC0F0B6775E3D8
md5 of corrupt: 8AB7F69C9AB17E919CA96A07FB8D4B48

This can see that the file is corrupt by trying to open it up with NuGet Package Explorer:

paket restore fails correctly with:

nuget restore appears to not do the check and does not fail.

i just created an f# project for a console application and used NuGet to install FSharpx.Collections 1.14.0. i made a simple function to see how LazyList works. it compiles fine but when it runs, i get the following exception:

System.IO.FileLoadException was unhandled
Message: An unhandled exception of type 'System.IO.FileLoadException' occurred in myproject.exe
Additional information: Could not load file or assembly 'FSharp.Core, Version=4.4.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' or one of its dependencies. The located assembly's manifest definition does not match the assembly reference. (Exception from HRESULT: 0x80131040)

on NuGet it says "Dependencies: FSharp.Core (≥ 3.0.0)". but in my Project > Properties > Application, it says "Target F# runtime: F# 3.1 (FSharp.Core, 4.3.1.0)" (the default). i'm using vs2013upd4

can you fix this?

/cc @jackfoxy

@jackfoxy why do we need this? Couldn't we just use vector?

I am referencing F# 4 from an assembly and FSharpx.Collections. When I attempt to use RandomAccessList.tryUpdate I get

System.MissingMethodException : Method not found: 'Microsoft.FSharp.Core.FSharpOption`1<FSharpx.Collections.RandomAccessList`1<!0>> FSharpx.Collections.RandomAccessList`1.TryUpdate(Int32, !0)'.

If I switch my assembly to reference F# 3.1 the exception does not occur.

Docs can be found at http://forki.github.io/FSharpx.Collections/

needed for #1

Description

Are these still required for 4.61 interop with other .NET languages? What about netstandard2.0 and +?

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
[<Extension>]
[<CompiledName("something")>]

Have you considered releasing FSharpX collections as a PCL library? It appears that several of the implementations utilize APIs not in the 259 PCL profile (threading APIs for instance), but a bait and switch approach could be used to support the most common platform (net45, android, ios and win phone).

The NonEmptyList type currently does not have a zip implementation. This comes in handy quite often.

• PersistentMap
• TransientMap
• create docs as in #2

/cc @jackfoxy

I am reviewing the code of PersistentHashMap, I am wonder if the following code is correct

member this.ensureEditable(thread1, count1, array1) =
  if !thread = !thread then  // This test looks like its always true, shouldn't one of the operands be thread1
    this.array <- array1
    this.count <- count1
    this
  else HashCollisionNode(thread1, hashCollisionKey, count1, array1)

I am no expert on how to implement a PersistentHashMap so I might have misunderstood something.

so that we can GitHub link it via Paket.

I just make a clone and try to build head of master with build.cmd. Build failed with next message:

Status:        Failure
---------------------------------------------------------------------
  1) Building D:\projects\FSharpx.Collections\FSharpx.Collections.sln failed with exitcode 1.
  2) FS0366: D:\projects\FSharpx.Collections\src\FSharpx.Collections.Experimental\BinomialHeap.fs(219,15): No implementation was given for 'abstract member IPriorityQueue.Length
 : int'. Note that all interface members must be implemented and listed under an appropriate 'interface' declaration, e.g. 'interface ... with member ...'.
---------------------------------------------------------------------

D:\projects\FSharpx.Collections>git branch
* master

// cc @jackfoxy

Hi,

I extracted all the collectections (including FSharpx.Collections.Experimental) from fsharpx and put them into this project.
I think it hsould be as easy as possible to use them and a dependency on FSharpx (the whole project) is often a big no-no.

This project has already > 1700 unit tests and some API documentation (will add FSharp.Formatting build task).

But what name/namespace should it get?

Here are some ideas:

• fsharp/Fsharpx.Collections
• fsharp/Fsharp.Collections
• fsharp/Fsharp.Data.Collections
• forki/Fsharpx.Collections
• ??

// cc @dsyme @ovatsus @mausch @tpetricek @mausch @jackfoxy @panesofglass

I propose to add an implementation of Bagwell and Rompf's RRB-Tree Vectors (Relaxed Radix-Balanced Trees) to FSharpx.Collections. They are similar to PersistentVector, but allow for efficient slicing and concatenation. Slicing an RRB vector is effectively constant-time since it takes O(log32 N) time. Concatenating two RRB Vectors together is also O(log32 N) but with a large constant multiplier, as much as 1024 in the worst case, so it should really be considered O(log N) for all practical purposes.

Clojure implementation of RRB vectors: https://github.com/clojure/core.rrb-vector
Scala implementation: https://github.com/nicolasstucki/scala-rrb-vector

Papers about RRB vectors:

• Bagwell and Rompf's original paper
• Further paper by Stucki, Rompf, and Ureche, (and Bagwell, posthumously credited)
• Master's thesis by Jean Niklas L'orange on RRB Vector performance improvements through the use of transient vectors (PDF at http://hypirion.com/thesis.pdf)
• Master's thesis by Nicolas Stucki on the Scala implementation of RRB Vectors (alternate printable version available, as well as slides from Stucki's thesis presentation)

Travis CI build is currently failing due to a Paket issue of some kind: something about Travis CI's setup apparently makes it fail when Paket is run in "magic" mode. See fsprojects/Paket#2588 for more details, and https://travis-ci.org/fsprojects/FSharpx.Collections/builds/247094934 for the most current failing build on the master branch.

Not having those forces me to use Seq.distinctBy instead. I'll give it a try at adding those myself tomorrow.

Edit:

They are easy enough to write.

let distinctBy keyf (array:ResizeArray<_>) =
    let temp = ResizeArray()
    let hashSet = HashSet(HashIdentity.Structural)
    for v in array do
        if hashSet.Add(keyf v) then
            temp.Add(v)
    temp

let distinct (array:ResizeArray<_>) =
    let temp = ResizeArray()
    let hashSet = HashSet(HashIdentity.Structural)
    for v in array do
        if hashSet.Add(v) then
            temp.Add(v)
    temp

The above is almost a carbon copy of the functions of the same name for Arrays inside the F# Collections source. Though now that I know HashSets are used inside the functions I might as well have used them myself.

I'll have a look at inserting them into the Fsharpx.Collections.

CircularBuffer has no tests. Also it would be nice to have a comment which says how this structure differs from RingBuffer, which also exists in the codebase.

@forki? @jackfoxy?

I'm just curious about the API decision to make the PriorityQueue require an IComparable (along with the isDescending parameter for PriorityQueue.empty) instead of using a comparison function parameter for PriorityQueue.empty.

To me, It seems like passing in a comparison function would be the more idiomatic thing, but I'm pretty new to FP/F# and would love to hear how I'm wrong =).

I have noticed that some of the collections implemented here rely on a mutable Option field to store the hashCode and that field is changed inside GetHashCode, making the collection "thread unsafe", even in collections that I would assume thread safe. Should not the code inside GetHashCode be surrounded by a lock? Is my thinking wrong in any way, or am I assuming what I should not?

Hi
this is not an issue about a bug. Rather i'm a bit lost, and I'd like to know if among the data structures implemented in this library, there is a heap-like data structure supporting removal of an element in the middle of the priorityqueue/heap, and perhaps finding an element as well.

something like
https://code.msdn.microsoft.com/windowsdesktop/Net-Implementation-of-a-d3ac7b9d
however i have some reasons to believe the code above has some bugs.

I've googled to look for implementations elsewhere and couldn't find any, or at least any that i was able to use.

Link from docs to api docs is broken

It would be useful (mostly for C# interop) if PersistentVector implemented IReadOnlyList.

The data structure is called PersistentVector. We should rename the IVector in IPersistenzVector to avoid confusion with mathematical vectors.

See #1

Possible addition to FSharpx.Collections?

Abstract
The data structures under-pinning collection API (e.g. lists, sets, maps) in the standard libraries of programming languages are used intensively in many applications.
The standard libraries of recent Java Virtual Machine languages, such as Clojure or Scala, contain scalable and well-performing immutable collection data structures that are implemented as Hash-Array Mapped Tries (HAMTs).HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts. This particularly prohibits their application in programs which process larger data sets.
In this paper, we propose changes to the HAMT design that increase the overall performance of immutable sets and maps. The resulting general purpose design increases cache locality and features a canonical representation. It outperforms Scala’s and Clojure’s data structure implementations in terms of memory footprint and runtime efficiency of iteration (1.3–6.7 x) and equality checking (3–25.4 x).

http://michael.steindorfer.name/publications/oopsla15.pdf

Just glancing through the code, and saw an obvious bug in ByteString

/// Compares two byte strings based on their structure.
static member Compare (a:ByteString, b:ByteString) =
    let x,o,l = a.Array, a.Offset, a.Count
    let x',o',l' = b.Array, b.Offset, b.Count
    if o = o' && l = l' && x = x' then 0
    elif x = x' then
        if o = o' then if l < l' then -1 else 1
        else if o < o' then -1 else 1 
    else let left, right = x.[o..(o+l-1)], x'.[o'..(o'+l'-1)] in
         if left = right then 0 elif left < right then -1 else 1

The problem is with the:

    elif x = x' then
        if o = o' then if l < l' then -1 else 1
        else if o < o' then -1 else 1 

Consider: If we have an array of all zeroes, for example, then take two slices of that array of the same size but at different offsets, this will compare them as non-equal.

A corrected version:

    if (x == x') && (o == o') then Compare(l,l') else
    ... normal structural comparison ...

I'm not sure I trust the rest of that structural comparison to be especially efficient.

(to anyone watching by e-mail: sorry about submitting before detailing the bug)

// cc @jackfoxy

for i in RandomAccessList.empty do
    ignore()

Fails with

System.IndexOutOfRangeException : Index was outside the bounds of the array.
   at FSharpx.Collections.RandomAccessList`1.ArrayFor(Int32 i) in D:\code\FSharpx.Collections\src\FSharpx.Collections\RandomAccessList.fs:line 199
   at FSharpx.Collections.RandomAccessList`1.rangedIterator[T](Int32 startIndex, Int32 endIndex) in D:\code\FSharpx.Collections\src\FSharpx.Collections\RandomAccessList.fs:line 227
   at FSharpx.Collections.RandomAccessList`1.System-Collections-Generic-IEnumerable`1-GetEnumerator() in D:\code\FSharpx.Collections\src\FSharpx.Collections\RandomAccessList.fs:line 327