Consider avoiding unnecessary cloning by traversals

[polytypic]

Currently traversals such as L.elems and L.values, when used through e.g. L.modify, do not attempt to detect when the result is actually equal to the input. For example,

L.modify(L.elems, x => x, xs)

effectively clones the xs array (assuming it has no undefined elements). Given that we are dealing with immutable data structures, it would be possible to do a shallow equality comparison to detect when the output would be the same as the input and return the original input instead.

Note that e.g. the standard xs.map(x => x) also clones the array, which is also unnecessary assuming one is dealing with immutable data structures.

Of course, adding such detection directly to the implementation of L.elems slows it down. In some benchmarks it seems that e.g. L.modify(L.elems, x => x+1, xs) slows down by up to about 25%. That should be close to the worst case. Also, the slowdown only applies to operations that return the modified data structure (e.g. L.set, L.remove, L.transform) and does not apply to folds over traversals.

It can also be done as a separate pass, e.g.

const unclone = (x, i, C, xi2yC) =>
  C.map(y => {
    const n = y.length
    if (x.length !== n) return y
    for (let i = 0; i < n; ++i) if (!I.identicalU(x[i], y[i])) return y
    return x
  }, xi2yC(x, i))

but that has much higher overhead.

It is not entirely clear whether adding the cloning avoidance is worth it, but there are definitely cases where cloning avoidance would be a nice to have feature. Currently I'm leaning more towards changing the implementation to avoiding cloning. That is because I have now several applications of optics where cloning avoidance would be advantageous. There also seem to be no other downside to cloning avoidance except for the performance hit, because Partial Lenses do not support the use case of mutating data structures returned by optics operations.

Feedback and 👍 or 👎 votes are welcome!

[polytypic]

As of version 13.10.0, cloning avoidance has now been explicitly sanctioned, but not guaranteed. When an operation uses the Identity applicative (this includes the L.modify, L.set, L.remove, and L.transform operations), the L.elems and L.branchOr (and variations of it) traversals currently avoid unnecessary cloning.