New collection methods for 6.0.0

[kushti]

Methods to add in 6.0

From #418:

• BitShiftLeft
• BitShiftRight
• BigShiftRightZeroed

From #479 and also reverse

• reverse
• distinct
• lastIndexOf
• startsWith
• endsWith

Consider

• outerJoin from https://github.com/ScorexFoundation/sigmastate-interpreter/issues/472

"Currently it partially implemented. See also corresponding TODOs referring to this issue."

Methods which were proposed but will not be implemented in ErgoTree :

• zipWith (https://github.com/ScorexFoundation/sigmastate-interpreter/issues/419) as it can be replaced with zip and map , for example, instead of def add(c1: Coll[Byte], c2: Coll[Byte]): Coll[Byte] = c1.zipWith(c2, { (x, y) => x + y }) we can do smth like def add(c1: Coll[Byte], c2: Coll[Byte]): Coll[Byte] = c1.zip(c2).map({ (c: (Byte, Byte)) => (c._1 + c._2).toByte }), and we can do example from #419 once bitwise ^ is supported

• find - can be replaced with filter and extracting first element

• union can be replaced with something like just ++ or ++ and distinct if we need to remove duplicates

• diff can be replaced by something like c1.filter({(b: Byte) => c2.indexOf(b, 0) == -1 }), Scala SDK's diff is more nuanced , but was the plan about replicating it?

• mapReduce - ??? - no details provided in #479, but could be replaced with map with lambda I guess

• sum - can be replaced by fold

• prefixLength - could be replaced by mapping collection to another one with predicate results, and then finding first false there

• groupBy - ??? it is producing Map in Scala SDK, what was the plan here?

However, they support can be added to the frontend compiler, thus the compiler will replace the method with ones existing in the tree

[aslesarenko]

diff can be replaced by something like c1.filter({(b: Byte) => c2.indexOf(b, 0) == -1 })

This will have O(n^2) complexity, which is, combined with unlimited collection lengths can lead to potential attack vectors. The diff can be implemented with O(n) complexity using HashMap.

mapReduce - ??? - no details provided

This is quite generic operation which can be used in many use cases (for example groupBy can be implemented with mapReduce). Same motivation as for diff, direct implementation can be O(n) using HashMap internally, which is not possible since we don't have Map type in ErgoTree.

groupBy - ??? it is producing Map in Scala SDK, what was the plan here?

having mapReduce we can implement groupBy as: def groupBy(key: T => K): Coll[(K, Coll[T])] = mapReduce(t => (key(t), Coll(t)), ((_,t1), (_, t2)) => t1 ++ t2) This is not very efficient (and the cost will be high), but at least possible. So, the plan was to have native implementation using ArrayBuilders internally.