Hacker News Reader

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

View on HN

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.

Reply on news.ycombinator.com