Hacker News Reader

Comment by c-smile | Hacker News Reader

This sample

    function keyByUsernameReducer(acc, person) {
      return {...acc, [person.username]: person};
    }
    const peopleObj = peopleArr.reduce(keyByUsernameReducer,   {});

has O(n*n) complexity and memory consumption of the same magnitude.

This, while being not so functional pure, is better I think:

    function keyByUsernameReducer(acc, person) {
      acc[person.username] = person;
      return acc;
    }

But still... needless function call on each iteration.

View on HN

You can also use `.map()` and `Object.fromEntries` if you really don’t want to mutate the accumulator:

    function keyByUsername(person) {
      return [person.username, person];
    }

    const peopleObj = Object.fromEntries(peopleArr.map(keyByUsername));

But you should probably be using a `Map` for this anyway:

    const peopleMap = new Map(peopleArr.map(keyByUsername));

You don't need a function, this is my little trick to convert an array to object

peopleObj = peopleArr.reduce( (a,x) => (a[x.username]=x, a), {} );

I too prefer to use the "inefficient" notation because it just feels wrong (kind of an antipattern in the functional sense if you will) to mutate the argument. And as long as you are not dealing with a huge input list, this doesn't really matter at all.

Also, why would the memory complexity be n * n? Sure, a new object is created in each iteration, but its not like you have to keep the previous ones in memory - all but the last one can be garbage collected.

It’s n^2 time, not space. Each property of the object gets copied each time around, and the number of properties being copied increases each time around.

It’s probably a good idea to start considering this kind of copying an antipattern. The good news is that the correct implementation doesn’t have to involve mutating any arguments, just a local with unambiguous ownership:

  const keyBy = (iterable, key) => {
      const map = new Map();

      for (const value of iterable) {
          map.set(key(value), value);
      }

      return map;
  };

  const peopleObj = keyBy(peopleArr, person => person.username);

If you have an array, you even get to keep using array methods, which everyone loves:

  const keyBy = (array, key) =>
      new Map(
          array.map(value => [key(value), value])
      );

"new object is created in each iteration"

Not just created, but properties are being populated one by one.

"can be garbage collected"

And what do you think is computational complexity of garbage collector?

Yes, memory allocation in JS (GCable environment) is cheap. But garbage collection per se is not, it is at least O(N) complex.

I never claimed garbage collection was free, but the point was memory complexity and not computational complexity. So claiming that the implementation would be O(n * n) in terms of memory complexity still doesn't make sense to me.

memory complexity in JS translates into time complexity needed for GC cycles.

and again, you are arguing about time complexity, while I don't, but I guess we can now just call it a day...

There's nothing wrong with mutating an argument. The whole reason JS passes objects by reference is so that you can do it.

I tend to treat my data structures as immutable, even when they technically aren't.

There are tons of wrongs with mutating arguments. The fact that it is possible to mutate arguments in JavaScript does not make it a good idea. Such functions cannot be trusted (how can you know what happens when you call it?), and they are hard to test.

There is _always_ a better alternative to mutating arguments in a function.

Sure, but here it's a local mutation, it won't leak to the rest of the program. There is nothing wrong with mutating acc in reduce.

I agree, should you always test the reducing function separately outside the reduce? And if so, what's the real benefit of not mutating accumulator? Seems silly to just copy a transient value which is immediately discarded and then do it for all reduced elements. Does the original reference to the object even stay during the iterations? Hmm, I guess it does.

To me it seems weird to be so puristic about a simple reduce-function, which by-design leads you to mutate the accumulator. I mean for object-accumulators it definitely is just a massive waste to not to just mutate the argument directly without copying. Although as a disclaimer I have to say I am big fan of simple code, were it FP or not. So if you have a messy reduce-function I guess having it immutable makes it a somewhat easier to manage.

This is a different argument than what megous was making (JS's support for mutating arguments validating that it's a good practice in a broad sense)

"Unobservable" or local mutation is completely fine (and pretty common in most functional programs that get to any significant scale)

> There are tons of wrongs with mutating arguments. The fact that it is possible to mutate arguments in JavaScript does not make it a good idea. Such functions cannot be trusted (how can you know what happens when you call it?), and they are hard to test.

I know what happens by reading the function. Pretty much any function that calls a method on some object mutates its argument. It makes little difference if you abstract this mutation behind the method, or do it directly, or do it via a helper function that takes the object as an argument.

> There is _always_ a better alternative to mutating arguments in a function.

No. Most of those are usually more wasteful, because if you can't mutate objects, you'll have to throw them away at every mutation.

Pretty much all issues I ever had with mutation was when object was shared between multiple users, and some users were incorrectly muttating it during some operation that was meant to be temporary.

For example you store params for a AJAX call in some object and for some AJAX calls you just want to modify one of the params for some AJAX call and instead of {...params, prop: 'newval'} you just do params.newval.

But that is a mistake you do a few times, and then learn to recognize when you're doing temporary changes to use copies of objects. Anyway, it is harmful to avoid mutation at all costs.

I prefer to limit mutation to changing what a local variable refers to: mutations that escape into the calling context can create all sorts of really nasty headaches.

> I know what happens by reading the function. Pretty much any function that calls a method on some object mutates its argument. It makes little difference if you abstract this mutation behind the method, or do it directly, or do it via a helper function that takes the object as an argument.

Are we talking about functions in general, or small accumulator functions here? I would argue that mutating arguments in general is a really bad pattern that certainly will lead to weird and subtle bugs in the long run. It is also completely unnecessary – you have inputs and outputs for a reason. You might know what happens if you read the function yourself, but you can never assume that everyone else will.

> No. Most of those are usually more wasteful, because if you can't mutate objects, you'll have to throw them away at every mutation.

No, you don’t. This is an implementation detail. Libraries like immutable.js [1] (and several others, I believe) makes it possible to work with immutable data structures without cloning anything.

> Anyway, it is harmful to avoid mutation at all costs.

We can more or less agree on this one :) My comment was unnecessary bastant. I have used mutations in reducer aggregators myself. But, avoiding mutation removes a source of bugs, without sacrificing readability or functionality.

[1] https://immutable-js.github.io/immutable-js/

> how can you know what happens when you call it?

Documentation, good API design. Real-world example of a function I call pretty often (which I’m also interested in knowing your better alternative to):

  const extend = (dest, from) => {
      for (const x of from) {
          dest.push(x);
      }
  };

It doesn’t return anything, so I’d say it’s pretty clear its entire purpose is to mutate one argument.

(Non-stack-overflowing version of dest.push(...x), by the way.)

I just came across a test that passed spuriously because it passed an object to a function that mutated one of its arguments and then used that object in the assertions.

> There are tons of wrongs with mutating arguments.

What leads you to this dogma?

Why is mutation of a tightly scoped local variable bad?

The initial accumulator of a reducer usually does not exist until the reducer is invoked, or is defined as an arg to the reducer.

What possible harm could result from mutating it in a tight loop until it is returned?

This is not to say that mutation is fine in all circumstances. That's crazy. There are tradeoffs.

But to declare an entire technique off limits, what are your reasons? You seem to assume your own conclusion.

Just use https://underscorejs.org/#groupBy. This is it's reason for existence.

Reply on news.ycombinator.com