4 ms·

That seems to be such a basic task. Please take it not as me not believing it but could you provide some source about there not being a known O(N) solution for

That seems to be such a basic task. Please take it not as me not believing it but could you provide some source about there not being a known O(N) solution for that problem, I'd like to know what the hurdles are and why there might be no solution at all or why finding one is so difficult. (I tried googling it but failed to find something useful)

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 ago
  As 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.
ur-whale 7y ago
Because of the whole immutability dogma of FP languages, you can't do this simply in a clean FP style: ++(histogram[sampleId]); which is the heart of a simple histogram computation.
setr 7y ago
https://old.reddit.com/r/haskell/comments/3bqlis/how_do_you_compute_a_histogram_in_a_pure_language/csoya8q/ https://old.reddit.com/r/haskell/comments/3bqlis/how_do_you_... Found a decent discussion on the matter. Main issue at hand is that its not really FP in question, but datastructures, and more specifically, how far you extend immutability semantics. In this case, if you forgo immutability requirement, you can trivially mantain semantic purity while still updating the simple array. But with immutability, you can’t construct an array, so you’re locked behind log(n) datastructures

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 ago
As 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.

ur-whale 7y ago

Because of the whole immutability dogma of FP languages, you can't do this simply in a clean FP style: ++(histogram[sampleId]); which is the heart of a simple histogram computation.

setr 7y ago

https://old.reddit.com/r/haskell/comments/3bqlis/how_do_you_compute_a_histogram_in_a_pure_language/csoya8q/ https://old.reddit.com/r/haskell/comments/3bqlis/how_do_you_... Found a decent discussion on the matter. Main issue at hand is that its not really FP in question, but datastructures, and more specifically, how far you extend immutability semantics. In this case, if you forgo immutability requirement, you can trivially mantain semantic purity while still updating the simple array. But with immutability, you can’t construct an array, so you’re locked behind log(n) datastructures