On Thu, 15 Nov 2018, Zemyla wrote:
It's not actually impossible to have an in RAM structure that exceeds the largest positive value for Int. Data.Sequence.replicate does it by exploiting sharing. replicate n a uses O(lg n) space.
length $ let x = Data.Sequence.Replicate maxBound 'a' :> 'b' in mappend x x 0
One could also imagine a data structure like Multiset/Bag, where every element has a count and 'length' returns the total count.
Also, I really would like to have all the length and count-based functions in base, containers, etc. take or return Words, but there's way too much inertia behind Ints, even if it means you have to check for negative numbers (which really runs counter to the main thesis behind Haskell; i.e. have your types say what you mean).
We would also need a bound-checked counterpart to Word. Currently, (-1)::Word or (2-3)::Word is accepted without a runtime error. Consequently, 'newTake (-1) xs' would likely return the full list xs.