haskell
should fromAscList check its precondition?
Currently we have
import Data.Set
member 0 $ fromAscList [2,0] -- value is False
since https://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Set.html#v:fromAscList does not check monotonicity. Should it? Could it? (I mean, how much extra time would this need?) Was this ever discussed?
(similar question: https://github.com/twanvl/multiset/issues/9#issuecomment-490891786 )
The docs clearly say The precondition (input list is ascending) is not checked. so I think it's safe to say it was discussed. Would it be worth adding fromAscListChecked? Maybe. The point of this function is largely performance. If you don't know for certain that your input is ascending, you should use fromList.
It should be a matter of a few minutes to strengthen the constraint from Eq to Ord (a potentially breaking change; others' code may have to be modified to adjust, but likely not a lot of code will break, and the fix is always easy) and use compare instead of Eq. Then benchmark fromListWith with several element types and list lengths and see if we can get away with it performance-wise.
See also #981. I think it would make sense to have a Cabal flag that turns on precondition checks for debugging purposes, without needing to modify the calling code (in case it is deep inside some dependency).
should fromAscList check its precondition?
No, because the point of such functions is to avoid the cost of those checks.
I mean, how much extra time would this need?
For Set and Map it would be an arbitrary amount because it depends on the Ord instance. For IntSet and IntMap it would be cheap, but not zero.
If one is not sure whether their list satisfies the precondition, they should use fromList.
