13 ms·

Not all functional programming idioms work in all languages. On my computer, the article's imperative range(6000) took 0.05 ms and the "functional" range(6000)

Not all functional programming idioms work in all languages. On my computer, the article's imperative range(6000) took 0.05 ms and the "functional" range(6000) took 400 ms. The whole [...cur, cur.length+1] thing turns a linear algorithm into a quadratic one. It wouldn't happen in all languages, but that's how JavaScript's arrays work. My advice is that if you really want to do stuff like this, choose appropriate data structures (i.e., learn about persistent data structures). Except in this case the imperative version is already totally fine. It is modifying an array that it created itself. You have all of the benefits of avoiding shared mutable state already. Also, the difference in performance would become even worse, except that for range(7000) I already get "Maximum call stack size exceeded" on the recursive one. The imperative implementation handles 10000000 without breaking a sweat. My second advice is to not use recursion to process arrays in languages (like JavaScript) that have a very limited call stack size.

onsclom 4y ago
Great points! I am still trying to figure out how to best use functional programming with JavaScript. I've found writing performance critical parts imperatively while being conscious about shared mutable state is a decent compromise. > My second advice is to not use recursion to process arrays languages (like JavaScript) that have a very limited call stack size. Can also confirm this, here was my process on the some of the harder days in Advent of Code: 1. I wonder if I can solve this in a pure functional style with JavaScript 2. Yay, it works on the example input 3. Oh, I hit the call stack limit on the real input 4. Time to rewrite the recursion as a loop lol
- toastal 4y ago
  Shame since ECMAScript 2015 was supposed to give of proper tail calls in JavaScript, but Blink chickened out and so did Gecko.
- VaxWithSex 4y ago
  5. refactor loop as loop function
- mixedCase 4y ago
  > I am still trying to figure out how to best use functional programming with JavaScript. IME avoid recursion, use immutability in the large while avoiding in local scope beyond a simple .map.filter chain, and on the backend I allow myself fp-ts to have sane error handling (I assumed TypeScript there but I'd just not ever use vanilla JS nowadays). With that said I'd really, really rather use a compile to JS lang that does the optimizations for you, specially for frontend use cases.
- galaxyLogic 4y ago
  > trying to figure out how to best use functional programming with JavaScript Use ES6 classes to guard every property read and write behind a method-call. You can avoid mutable state by making methods return only primitive data, including JSON. Then nobody can modify such state from the outside. You control and can easily observe all state-changes.
uuvs8 4y ago
And suddenly you care a lot about the "how", not just the "what". Voiding the whole "but it's declarative!" argument. At least in imperative code the "how" is explicit. In functional code it's implicit and you need intimate knowledge about compiler and/or runtime to know what's going to happen.
- Annatar 4y ago
  [dead]
- MrManatee 4y ago
  I kind of agree that it's possible to slightly overstate the declarativeness argument. Functional-style JavaScript is not that declarative. Not in the way SQL is. But also, writing imperative code doesn't guarantee explicit performance characteristics. Whether you mutate references or not, you still need to know which operations are fast and which are slow. In JavaScript, concatenation, [...array1, ...array2], is non-mutating and slow. Adding an element to the end, array.push(x), is mutating and fast. But adding an element to the beginning, array.unshift(x), is mutating and slow. So even if you're sticking to mutation, you still need to know that push is fast and unshift is slow. And yeah, sorry, "in JavaScript" is not quite right. I meant in my browser. This is not part of the spec, and it's not mentioned in the documentation. Is it the same in other browsers? Who knows. To me, this is just as much "you need intimate knowledge about compiler and/or runtime to know what's going to happen".
  - recursive 4y ago
    > array.unshift(x), is mutating and slow This year it's slow. I wouldn't count on that being true in five years. I mean, it might, it might not. There's a risk in optimizing too much for current conditions. You can easily end up over-fitting for the current set of coincidences, and end up with less readable code that's actually slower in the long run. But by all means, measure and improve until it's fast enough.
- psychoslave 4y ago
  You never know what the compiler is going to produce until you look at what it actually produced, whatever language you are using. Unless there is clear evidences upfront that the project will be a piece of software where local performance is highly critical, it makes sense to favor code readability and maintainability over optimality. Of course, you can have different level of code quality whatever the paradigm retained. Most languages out there will allow you to mix different paradigms anyway. Given this fact, we would surely better served with an article like "When to favor expression in each paradigm available in your favorite language".
fredrikholm 4y ago
Pre-allocating the size of the array lowers that number even more. Persistent data structure are really useful, and are (often) magnitudes more efficient than DIY-immutable data structures. Imperative ones however, like you mentioned, are often (comparatively) near ideal by virtue of being imperative.
YuukiRey 4y ago
I wrote a blog post once, https://www.fbrs.io/ramda/ https://www.fbrs.io/ramda/, where I compared a functional solution and a vanilla solution. I tried to cover both performance and some vague notion of readability. In the end the vanilla solution won in both areas. And I say that as an FP and Haskell fan boy.
- dmitriid 4y ago
  Ramda is what you get when people try to zealously make Haskell out of Javascript. The same happens in many other languages where people try to force Haskell idioms into languages. Edit. For some reason people equate "functional" with Haskell, even though Javascript (and most modern languages) is perfectly capable of expressing functional idioms without the descent into madness. Your vanilla solution is already a functional solution. Literally no need for `transduce pipe map over lens`
  - zelphirkalt 4y ago
    > [...] is perfectly capable of expressing functional idioms without the descent into madness. Except of course deep recursion, which needs to be rewritten into a not so readable externalized stack or some kind of loop replacement. There are difficulties involved with rewriting some recursions as loops and some loops as recursion. Of course, if JS engines adhered to the standard, they would all have TCO by now and the problem would not exist.
    - hgsgm 4y ago
      All you have to do is use a relocatable stack/heap hybrid like Go does.
  - chrisweekly 4y ago
    What's wrong with Ramda?
    - dmitriid 4y ago
      Unusable unreadable unnecessary complex abstractions in a language that doesn't need them. Also, extremely non-performant. As you can see even in the blog post: straightforward readable code using built-in functionality is turned into 8-12 imports, a bunch of auxillary functions and multiple function calls that obscure the actual functionality. At 35 times speed penalty and 2 times memory penalty.
riwsky 4y ago
“Functional Programming—When and Where”
akho 4y ago
The functional version is written in a style that uses tail recursion, which is not optimized in JS. It’s linear if arrays are not copied, which should be the case with TCO. Both versions are quadratic if arrays are actual arrays and require a single chunk of memory. (push may need to copy the entire array)
zelphirkalt 4y ago
> On my computer, the article's imperative range(6000) took 0.05 ms and the "functional" range(6000) took 400 ms. The whole [...cur, cur.length+1] thing turns a linear algorithm into a quadratic one. It wouldn't happen in all languages, but that's how JavaScript's arrays work. My advice is that if you really want to do stuff like this, choose appropriate data structures (i.e., learn about persistent data structures). That is a good point and should perhaps have been timed before being put as an example. Arrays themselves are usually quite the mutable data structure as well, so I think your advice about learning persistent data structures is spot on. Sometimes one can simulate a persistent data structure by using copying the whole or parts for some operations and use those only when one needs a separate copy.
noctune 4y ago
And persistent memory structures also tends to have a cost. For example, persistent maps are usually O(lg n) lookup and insert rather than O(1) usually seen in mutable maps. If I remember correctly this is a pretty fundamental limitation of persistent structures, so it's not like there is a better persistent map data structure out there waiting.
- consilient 4y ago
  Lazy structures can usually get the log(n) back when you amortize over many operations.
  - noctune 4y ago
    Sure, but for some structures it amortizes to log(n) where mutable structures can amortize to O(1).

onsclom 4y ago

Great points! I am still trying to figure out how to best use functional programming with JavaScript. I've found writing performance critical parts imperatively while being conscious about shared mutable state is a decent compromise. > My second advice is to not use recursion to process arrays languages (like JavaScript) that have a very limited call stack size. Can also confirm this, here was my process on the some of the harder days in Advent of Code: 1. I wonder if I can solve this in a pure functional style with JavaScript 2. Yay, it works on the example input 3. Oh, I hit the call stack limit on the real input 4. Time to rewrite the recursion as a loop lol

toastal 4y ago
Shame since ECMAScript 2015 was supposed to give of proper tail calls in JavaScript, but Blink chickened out and so did Gecko.
VaxWithSex 4y ago
5. refactor loop as loop function
mixedCase 4y ago
> I am still trying to figure out how to best use functional programming with JavaScript. IME avoid recursion, use immutability in the large while avoiding in local scope beyond a simple .map.filter chain, and on the backend I allow myself fp-ts to have sane error handling (I assumed TypeScript there but I'd just not ever use vanilla JS nowadays). With that said I'd really, really rather use a compile to JS lang that does the optimizations for you, specially for frontend use cases.
galaxyLogic 4y ago
> trying to figure out how to best use functional programming with JavaScript Use ES6 classes to guard every property read and write behind a method-call. You can avoid mutable state by making methods return only primitive data, including JSON. Then nobody can modify such state from the outside. You control and can easily observe all state-changes.

uuvs8 4y ago

And suddenly you care a lot about the "how", not just the "what". Voiding the whole "but it's declarative!" argument. At least in imperative code the "how" is explicit. In functional code it's implicit and you need intimate knowledge about compiler and/or runtime to know what's going to happen.

Annatar 4y ago
[dead]
MrManatee 4y ago
I kind of agree that it's possible to slightly overstate the declarativeness argument. Functional-style JavaScript is not that declarative. Not in the way SQL is. But also, writing imperative code doesn't guarantee explicit performance characteristics. Whether you mutate references or not, you still need to know which operations are fast and which are slow. In JavaScript, concatenation, [...array1, ...array2], is non-mutating and slow. Adding an element to the end, array.push(x), is mutating and fast. But adding an element to the beginning, array.unshift(x), is mutating and slow. So even if you're sticking to mutation, you still need to know that push is fast and unshift is slow. And yeah, sorry, "in JavaScript" is not quite right. I meant in my browser. This is not part of the spec, and it's not mentioned in the documentation. Is it the same in other browsers? Who knows. To me, this is just as much "you need intimate knowledge about compiler and/or runtime to know what's going to happen".
- recursive 4y ago
  > array.unshift(x), is mutating and slow This year it's slow. I wouldn't count on that being true in five years. I mean, it might, it might not. There's a risk in optimizing too much for current conditions. You can easily end up over-fitting for the current set of coincidences, and end up with less readable code that's actually slower in the long run. But by all means, measure and improve until it's fast enough.
psychoslave 4y ago
You never know what the compiler is going to produce until you look at what it actually produced, whatever language you are using. Unless there is clear evidences upfront that the project will be a piece of software where local performance is highly critical, it makes sense to favor code readability and maintainability over optimality. Of course, you can have different level of code quality whatever the paradigm retained. Most languages out there will allow you to mix different paradigms anyway. Given this fact, we would surely better served with an article like "When to favor expression in each paradigm available in your favorite language".

fredrikholm 4y ago

Pre-allocating the size of the array lowers that number even more. Persistent data structure are really useful, and are (often) magnitudes more efficient than DIY-immutable data structures. Imperative ones however, like you mentioned, are often (comparatively) near ideal by virtue of being imperative.

YuukiRey 4y ago

I wrote a blog post once, https://www.fbrs.io/ramda/ https://www.fbrs.io/ramda/, where I compared a functional solution and a vanilla solution. I tried to cover both performance and some vague notion of readability. In the end the vanilla solution won in both areas. And I say that as an FP and Haskell fan boy.

dmitriid 4y ago
Ramda is what you get when people try to zealously make Haskell out of Javascript. The same happens in many other languages where people try to force Haskell idioms into languages. Edit. For some reason people equate "functional" with Haskell, even though Javascript (and most modern languages) is perfectly capable of expressing functional idioms without the descent into madness. Your vanilla solution is already a functional solution. Literally no need for `transduce pipe map over lens`
- zelphirkalt 4y ago
  > [...] is perfectly capable of expressing functional idioms without the descent into madness. Except of course deep recursion, which needs to be rewritten into a not so readable externalized stack or some kind of loop replacement. There are difficulties involved with rewriting some recursions as loops and some loops as recursion. Of course, if JS engines adhered to the standard, they would all have TCO by now and the problem would not exist.
  - hgsgm 4y ago
    All you have to do is use a relocatable stack/heap hybrid like Go does.
- chrisweekly 4y ago
  What's wrong with Ramda?
  - dmitriid 4y ago
    Unusable unreadable unnecessary complex abstractions in a language that doesn't need them. Also, extremely non-performant. As you can see even in the blog post: straightforward readable code using built-in functionality is turned into 8-12 imports, a bunch of auxillary functions and multiple function calls that obscure the actual functionality. At 35 times speed penalty and 2 times memory penalty.

riwsky 4y ago

“Functional Programming—When and Where”

akho 4y ago

The functional version is written in a style that uses tail recursion, which is not optimized in JS. It’s linear if arrays are not copied, which should be the case with TCO. Both versions are quadratic if arrays are actual arrays and require a single chunk of memory. (push may need to copy the entire array)

zelphirkalt 4y ago

> On my computer, the article's imperative range(6000) took 0.05 ms and the "functional" range(6000) took 400 ms. The whole [...cur, cur.length+1] thing turns a linear algorithm into a quadratic one. It wouldn't happen in all languages, but that's how JavaScript's arrays work. My advice is that if you really want to do stuff like this, choose appropriate data structures (i.e., learn about persistent data structures). That is a good point and should perhaps have been timed before being put as an example. Arrays themselves are usually quite the mutable data structure as well, so I think your advice about learning persistent data structures is spot on. Sometimes one can simulate a persistent data structure by using copying the whole or parts for some operations and use those only when one needs a separate copy.

noctune 4y ago

And persistent memory structures also tends to have a cost. For example, persistent maps are usually O(lg n) lookup and insert rather than O(1) usually seen in mutable maps. If I remember correctly this is a pretty fundamental limitation of persistent structures, so it's not like there is a better persistent map data structure out there waiting.

consilient 4y ago
Lazy structures can usually get the log(n) back when you amortize over many operations.
- noctune 4y ago
  Sure, but for some structures it amortizes to log(n) where mutable structures can amortize to O(1).