Every time I see this blog I'm extremely interested in the content, but the stylized presentation is so jarring and tough to read. I doubt this is an original qualm and I'm fully able to switch to reading mode in Firefox to mitigate this problem, but frankly it's off-putting.
On the other hand I have zero issues with the design, like it aesthetically and find it a refreshing change to see a blog clearly designed to be functional and refreshingly different.
Impressive amount of code and words. I think I'd think twice before approving this in a code review, though.
Why is this not the obvious solution to the stated problem?
function avgPopularity(slang) {
let sum = 0;
let count = 0;
for (item of slang) {
if (item.popularity > 0) {
sum += item.popularity;
count += 1;
}
}
return sum / count;
}
Transducers in theclojure sense often carry hidden mutable state. This is a solved problem for languages with either heavily optimizing compilers (the atria transducers by ableton for c++ are pure and with visible state) or by type system magic (Haskell, but there you should just use conduits).
Because a bunch of those lines are concerned with the boring mechanics of how to compute this thing rather than what is being computed. It’s reasonable to say having a big system of composable transducers is pointless for one computation. It’s harder for 1000.
This point isn’t about transducers specifically but more about avoiding specifying the things you don’t care about. Eg, in Common Lisp (which was old enough to somewhat care about how to iterate things):
(defun avg-popularity (list)
(loop for item in list
when (plusp (popularity item))
sum pop into s
count t into c
finally (return (/ s c))))
This avoids having to care about the mechanics of how to sum or count things and I think it’s too sequential, when you don’t really care about that. One can certainly imagine a simpler to express solution in e.g. apl.
Note that to make it correct Common Lisp, you'd write it like that:
(defun avg-popularity (list)
(loop
for item in list
for pop = (popularity item)
when (plusp pop)
sum pop into s
and
count t into c
finally (return (/ s c))))
Two changes: 1) making `pop' be a thing, and 2) `when' clause of loop only applies to the next clause by default (here, `sum pop into s'), you need to include `and' to chain it with the next one so that both are guarded by `when' condition.
Of course trivial toy examples demand simple answers. But as you add more processing (partitioning + further operations on partitions, take every nth, stop when some predicate is true...), transducers let you build each in isolation and compose them easily. Your obvious solution might start to get a bit strained, and the code for any single process in the chain can't be reused.
You could (usually, but not always) compose the functions you're passing into filter and map and use reduce instead to do both operations in a single pass.
(Edit: This is a big point in the article -- apologies, I hadn't finished reading it yet.)
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]
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.
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)
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.
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
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.
> 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.
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
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.
Your solution requires that slang be fully populated upfront, while the article shows a solution that can operate on a stream of data, an item at a time.
The reason to use transducers instead of a for loop here is that it allows you to expose a library function which takes a transducer as input. It's hard to refactor the for loop above to allow someone consuming this function to specify additional things they want to aggregate due to an API change in the definition of the 'slang' type, but with transducers you just take one as an argument.
because there is dirty mutation and it relies entirely on side effects to work. (this is sarcastic, that is exactly how one should go about this one example case.)
It however is a completely different thing when longer chains of filter / map need to come along and the true power of transducers is needed.
In clojure I've had to use transducers at least three times in the course of the last four years!
I recently wrote a srfi (scheme request for implementation) for transducers, if anyone is interested. The code is guile-specific, but is easily portable to other schemes. It is still a draft, so it is bound to change: https://srfi.schemers.org/srfi-171/srfi-171.html
I am somewhat confused here, I primarily do C# so I am used to IEnumerable and Linq for doing this kind of stuff and you would just do .Where().Select().Average() without worrying about intermediate memory usage. In C# you do this stuff with millions of results from a database (although you would do in the db if you can, but might be a flat file too).
Linq with IEnumerable doesn't necessarily create intermediate list (js arrays) in memory unless it has to like say .OrderBy()
So I basically assumed js was the same since it has generators but its seems map and filter etc don't support them yet?:
It's so depressing that JavaScript is growing in use, especially when I see articles like TFA. I hate that momentum has allowed a clusterf*ck of a language to become the standard for front end and now one of the top 3 for back-end.
In almost all cases you don't need to worry this much about performance. Just traverse the array three times and move on. Go measure and improve if it becomes an issue.
The concept of transducers - I think of it is a conveyor belt of functionality - is great and I periodically run into problems where having an easy to use JavaScript transducer system would be great. Right now I'm processing sets of markdown files, reading shortcodes from them, generating html, applying more shortcodes, adding variables and then using mustache ... It is just a conveyor belt, but with lots of little odds and ends - perfect for a transducer, especially with async.
I recommend ignoring transducers unless you know you really need push-based iteration, which probably isn't the case. Generators are generally a superior approach otherwise.
50 comments
[ 2.0 ms ] story [ 108 ms ] threadPlease, I have a wide screen, let me use it.
Why is this not the obvious solution to the stated problem?
This point isn’t about transducers specifically but more about avoiding specifying the things you don’t care about. Eg, in Common Lisp (which was old enough to somewhat care about how to iterate things):
This avoids having to care about the mechanics of how to sum or count things and I think it’s too sequential, when you don’t really care about that. One can certainly imagine a simpler to express solution in e.g. apl.(Edit: This is a big point in the article -- apologies, I hadn't finished reading it yet.)
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%20...
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.
[1] Of course we have plenty of other reasons to use it, but I digress.
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
I've always been uneasy with FP-style coding for three reasons:
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.
[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.
The reason to use transducers instead of a for loop here is that it allows you to expose a library function which takes a transducer as input. It's hard to refactor the for loop above to allow someone consuming this function to specify additional things they want to aggregate due to an API change in the definition of the 'slang' type, but with transducers you just take one as an argument.
It however is a completely different thing when longer chains of filter / map need to come along and the true power of transducers is needed.
In clojure I've had to use transducers at least three times in the course of the last four years!
Linq with IEnumerable doesn't necessarily create intermediate list (js arrays) in memory unless it has to like say .OrderBy()
So I basically assumed js was the same since it has generators but its seems map and filter etc don't support them yet?:
https://dev.to/nestedsoftware/lazy-evaluation-in-javascript-...
So then you get a solution like this that looks to me very confusing vs a fluent style.
Please tell me I am missing something
Here's Clojure's explanation of transducers: https://clojure.org/reference/transducers
The whole concept is explained more clearly and with far fewer words and code; and the final result is pretty, or at least clean and tidy.
I don't know how JS generators work but Python users seemed to think Python's generators cover most transducer use cases.
d3.mean(victorianSlang, d => d.popularity)
This implicitly ignores invalid values (null, NaN or undefined) after coercing to a number.
Ramada looks interesting ...
This is the best example of a forced pattern.