4 ms·
The hurdle is that when you're going through the input, you need to update the output out of order. An imperative array can be updated out of order in O(1) time
by cousin_it 7y ago
The hurdle is that when you're going through the input, you need to update the output out of order. An imperative array can be updated out of order in O(1) time, but FP data structures can't do that. Strict vs lazy doesn't seem to help. I have no source, but I've given this problem to some strong Haskell programmers and they couldn't solve it (without using escape hatches like ST).
- mrgriffin 7y agoAs a professional Haskeller who solves numerical computation problems I wouldn't call ST an escape hatch. You're right that I can't think of a "pure" way to compute a histogram, but I doubt anyone uses Haskell specifically to prevent all mutations but rather to carefully control where mutation can occur[1]. I'd wager referential transparency is "good enough purity" for almost all tastes. [1] Of course we have plenty of other reasons to use it, but I digress.