Contradictory documentation for toList

[ruuda]

Quoting the documentation of version 1.3.2:

toList: O(n). Returns the elements of the priority queue in ascending order. Equivalent to toAscList.

toAscList: O(n log n). ...

Something here is not correct. Also, toListU does not mention its complexity at all. Should toListU be O(n) and toList a synonym for toAscList?

[lspitzner]

Indeed, I will look into this later. Also found this in Data.PQueue.Prio.Max:

-- | /O(n log n)/.  Equivalent to 'toAscList'.
[..]
toList = toDescList

[lspitzner]

When fixing the complexity i trusted the original authors annotations on the basic fold* operations, as the erroneous documentation can be explained by bad copy-pasting in these few instances. I have not tested properly via benchmark.

[lspitzner]

I'll make a new release for the next ghc version.

[ruuda]

Thanks!