4 ms·

Yours is the obvious solution but the problem is a simple example to help people understand the more complex idea of transducers. It's for situations where the

Yours is the obvious solution but the problem is a simple example to help people understand the more complex idea of transducers. It's for situations where the code inside the for loop is so complex that it would be nice to organize it with functional programming principals. The problem with functional programming is that the obvious approach is not efficient since it passes the array several times. So the goal is to make the functional approach as efficient as the imperative for loop. Now if you do that by hand, you end up with some messy code. So the article shows how you can combine the operations with a helper library in a structured way. That said, it kind of reminds me of The Evolution of a Haskell Programmer [0] [0] https://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/10%20Haskell%20Programmer%20Evolution.html https://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/10%20...

cousin_it 7y ago
For me it's the other way around. A for loop is a general purpose solution that changes continuously with the problem: whenever I need to gather some extra data, just add some hairs to the for loop. The time complexity is obvious, so is the space complexity (how much data is in memory at any given time), and it's easy to pause and debug. But if you have a bunch of FP combinators and recursion schemas, when the problem changes slightly, you have to unfold the whole origami crane and re-fold it carefully again. It's what James Hague called a puzzle language. The puzzle nature of FP can sometimes prevent the simplest solution to a problem. For example, try writing a function that accepts a list of N numbers between 1 and N and returns its histogram (list of counts of each number). There's an imperative solution in O(N) time with one for loop. But in FP, I'm not sure O(N) can be achieved, and even O(N log N) requires tree-like data structures that aren't needed in imperative.
- aurelwu 7y ago
  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
- ur-whale 7y ago
  100% agree with you. I've always been uneasy with FP-style coding for three reasons: - you have strictly no idea how your code will be evaluated by the CPU. Some people love that aspect. It makes me immensely queasy. I might be a control freak. - as much as I love the idea an cleanliness of composing functions, having to abandon mutability for that is way too hefty a price to pay. There are situations where overwriting memory is the darndest best way to do things. Yes, side-effects are hard to code with, but just like gotos, there are situations where they are the best solution. - I've always felt that FP coders are way too focused the beauty of their code rather that the industrial strength of it, which includes: readability, how easy it is to change, efficiency. Proper production code shouldn't be origami puzzles.
  - ElFitz 7y ago
    Totally beside the point (which I agree with), but your bullet list renders horribly on mobile devices (lengthy horizontal scrolls >.<')
    - ur-whale 7y ago
      I have indeed heard of these "mobile devices" you speak of :p but for some weird HN algorithmic reason, I can't edit my comment anymore ...
- tomxor 7y ago
  > just add some hairs to the for loop. The time complexity is obvious, so is the space complexity (how much data is in memory at any given time) Exactly, when refactoring code the first thing I do is remove all the boxes, create a huge monolithic procedure, then I can see all the inefficiencies, optimise and simplify it, then break it into better fitting boxes (if necessary). I don't follow the lingo for all the patterns, but ultimately they are usually just different ways of wrapping up things in boxes. I think they are wooden bullets, the most important thing is to not make boxes too quickly, it should be the very last thing you do after figuring out what the code needs to in it's entirety holistically. I think the bane of most software complexity is actually people being too scared of taming large contexts, so instead they wrap themselves in a hell of spaghetti boxes, just deferring issues and creating inefficiency and obscurity.
z3t4 7y ago
FP works very well in short simple examples. If the for loop would be any more complex the FP solution would probable be incomprehensible. Optimizers however love small immutable and steteless functions so FP would likely be faster then the imperative version. For example by making it run parallel, caching, inlining, etc
- layoutIfNeeded 7y ago
  >FP would likely be faster then the imperative version [citation needed] I highly doubt that even the most sophisticated JS engines would produce faster machine code from the functional spaghetti than a simple for loop.
philjohn 7y ago
The fact that it creates multiple intermediate arrays is a sign of the bad design in js ... and why (IMHO) if you want to do functional programming, sticking to a functional programming language can be a better option.

cousin_it 7y ago

For me it's the other way around. A for loop is a general purpose solution that changes continuously with the problem: whenever I need to gather some extra data, just add some hairs to the for loop. The time complexity is obvious, so is the space complexity (how much data is in memory at any given time), and it's easy to pause and debug. But if you have a bunch of FP combinators and recursion schemas, when the problem changes slightly, you have to unfold the whole origami crane and re-fold it carefully again. It's what James Hague called a puzzle language. The puzzle nature of FP can sometimes prevent the simplest solution to a problem. For example, try writing a function that accepts a list of N numbers between 1 and N and returns its histogram (list of counts of each number). There's an imperative solution in O(N) time with one for loop. But in FP, I'm not sure O(N) can be achieved, and even O(N log N) requires tree-like data structures that aren't needed in imperative.

aurelwu 7y ago
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
ur-whale 7y ago
100% agree with you. I've always been uneasy with FP-style coding for three reasons: - you have strictly no idea how your code will be evaluated by the CPU. Some people love that aspect. It makes me immensely queasy. I might be a control freak. - as much as I love the idea an cleanliness of composing functions, having to abandon mutability for that is way too hefty a price to pay. There are situations where overwriting memory is the darndest best way to do things. Yes, side-effects are hard to code with, but just like gotos, there are situations where they are the best solution. - I've always felt that FP coders are way too focused the beauty of their code rather that the industrial strength of it, which includes: readability, how easy it is to change, efficiency. Proper production code shouldn't be origami puzzles.
- ElFitz 7y ago
  Totally beside the point (which I agree with), but your bullet list renders horribly on mobile devices (lengthy horizontal scrolls >.<')
  - ur-whale 7y ago
    I have indeed heard of these "mobile devices" you speak of :p but for some weird HN algorithmic reason, I can't edit my comment anymore ...
tomxor 7y ago
> just add some hairs to the for loop. The time complexity is obvious, so is the space complexity (how much data is in memory at any given time) Exactly, when refactoring code the first thing I do is remove all the boxes, create a huge monolithic procedure, then I can see all the inefficiencies, optimise and simplify it, then break it into better fitting boxes (if necessary). I don't follow the lingo for all the patterns, but ultimately they are usually just different ways of wrapping up things in boxes. I think they are wooden bullets, the most important thing is to not make boxes too quickly, it should be the very last thing you do after figuring out what the code needs to in it's entirety holistically. I think the bane of most software complexity is actually people being too scared of taming large contexts, so instead they wrap themselves in a hell of spaghetti boxes, just deferring issues and creating inefficiency and obscurity.

z3t4 7y ago

FP works very well in short simple examples. If the for loop would be any more complex the FP solution would probable be incomprehensible. Optimizers however love small immutable and steteless functions so FP would likely be faster then the imperative version. For example by making it run parallel, caching, inlining, etc

layoutIfNeeded 7y ago
>FP would likely be faster then the imperative version [citation needed] I highly doubt that even the most sophisticated JS engines would produce faster machine code from the functional spaghetti than a simple for loop.

philjohn 7y ago

The fact that it creates multiple intermediate arrays is a sign of the bad design in js ... and why (IMHO) if you want to do functional programming, sticking to a functional programming language can be a better option.