Hacker News Reader

Comment by aurelwu | Hacker News Reader

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)

View on HN

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).

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.

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

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.

Reply on news.ycombinator.com