Fantasy-land: Suggestion to add "CFoldable"

[dmitriz]

In line with the discussion in https://github.com/ramda/ramda/issues/2160, I wonder about the consensus to add CFoldable aka Commutative-Foldable, where reduce only needs to be defined and obey the laws for the commutative accumulators.

[i-am-tom]

The problem with this is that we can't impose commutativity on the function (which is what would need to be done for this to work). Honestly, I think the best option is to agree unanimously that objects simple aren't stable enough to be considered Foldable types. I'm not even sure they're stable enough to be considered Functor types!

[paldepind]

@dmitriz

I don't think an addition to the spec is necessary. Objects are foldable despite what the consensus in the linked Ramda thread is. It's easy to prove that Objects are foldable since you can easily implent reduce on them.

@i-am-tom

Honestly, I think the best option is to agree unanimously that objects simple aren't stable enough to be considered Foldable types.

Why not? Keys are stored in insertion order? I find that to be quite intuitive behavior and it certainly meens that a law abiding reduce can be implemented on Object.

[safareli]

you just need to sort keys first https://github.com/sanctuary-js/sanctuary-type-classes/blob/master/index.js#L902

[i-am-tom]

@paldepind This is certainly not guaranteed https://stackoverflow.com/a/5525820/4022180, but @safareli's suggestion is the one that I have previously suggested as a best answer to this issue. However, given the lack of standard-enforced order, I _do_ think that we can't (well, shouldn't) rely on the functor laws holding. Of course, a slightly lax instance is _massively_ beneficial, so I think we should probably let it slide with a caveat - especially given that we can't (shouldn't) do equivalence with ordering anyway. The (lawful) practical incongruence is nil.

[paldepind]

@i-am-tom

This is certainly not guaranteed https://stackoverflow.com/a/5525820/4022180

Luckily for us that answer is wrong :smile: It's very unfortunate that misinformation is what people get from a Google search. SO is not a good source for such questions—looking directly at the spec is much better.

However, given the lack of standard-enforced order

The standard is very clear about enforcing order. It's described right here. The order described is the one you get from Object.keys, etc. As I said, normal non-numeric keys are given in insertion order, i.e. property creation order. Numerical keys like "12" are given in sorted order.

So, the correct answer to the SO question you linked is actually yes, if you define an object like this:

var obj = {};
obj.prop1 = "Foo";
obj.prop2 = "Bar";`

The spec absolutely guarantees that you will get the keys in insertion order if you iterate over them with Object.keys.

That is fantastic 😄 It means that if we want to we can make objects both foldables and functors.

Here is a nice article that breaks down what the spec states and confirms what I'm saying above.

[i-am-tom]

@paldepind These appear to be ES2015-specific links, which would suggest that this _isn't_ the case before ES2015, which means this is surely still unreliable behaviour for BC reasons?

[paldepind]

@i-am-tom It has been implemented like that in all engines for a long time. Way before it found its way into the spec. So there is no issue with relying on it in code.

In fact the reason why it was added to the standard is that all engines had that behavior anyway and much code relied on it. So adding it to the spec was a win-win.

[i-am-tom]

@paldepind Oh, awesome! I had no idea :D Well, in that case, :+1: to your original message <3

[paldepind]

@i-am-tom

Well, in that case, 👍 to your original message <3

Nice, thank you 😄

[masaeedu]

Should there perhaps be an extra laws only subclass of Semigroup called CommutativeSemigroup/CommutativeMonoid or something like that? CFoldable is then just Foldable with a stronger constraint on its foldMap.

[puffnfresh]

Abelian (semi)group is another common name in mathematics.

[puffnfresh]

I don't understand CFoldable though. Usually we'd just choose an order and move on. Can that not be done?

[masaeedu]

@puffnfresh Are you asking why CFoldable is needed instead of just using the commutative monoid with Foldable? The problem here is that more things are CFoldable than are Foldable. In fact every Foldable is also a CFoldable (passing a commutative monoid is fine where an arbitrary monoid is expected), but not vice versa.

[dmitriz]

@puffnfresh

I don't understand CFoldable though. Usually we'd just choose an order and move on. Can that not be done?

CFoldable is a different abstraction with different contract -- requiring commutativity for the function.

The problem with choosing the order,
it is not part of the abstraction normally associated with objects.
You would like to think of objects being equal regardless of their key insertion order.
You would like to feel safe to refactor your code from

var obj = {a:1, b:2}

to

var obj = {b:2, a:1}

However, with reduce depending on the key order, that refactoring is not safe.

The CFoldable spec should alert the user to the commutativity requirement,
in order to guarantee refactor safety and referential transparency.
(Just like traversable requires to work with applicatives.)

[puffnfresh]

@dmitriz you are not safe to make that refactor. How does CFoldable change that?

[dmitriz]

@puffnfresh
By declaring the object as a CFoldable, which requires the function passed to be valued in commutative semigroup. Such as all, some, max, min, add and many others.
That makes reduce safe and you can refactor as above without any thinking.

Of course, this only affects the reduce method.
Other methods such as Object.keys are not as safe but they are not part of this spec.

[puffnfresh]

@dmitriz I don't understand what is gained. You can refactor Foldable when you use a commutative function already. You can't change order of keys in a file because of Object.keys already.

I have motivations for CFoldable but I just don't think JavaScript Objects are one of them.