Mistyputt
commented
4 years ago I've played around with a naive implementation:
function mapArrayWithIndex<A, B>(f: (a: A, i: number) => B, array: A[], offset: number): [B[], number] {
const result = new Array(array.length);
for (let i = 0; i < array.length; ++i) {
result[i] = f(array[i], offset + i);
}
return [result, offset + array.length];
}
function mapNodeWithIndex<A, B>(f: (a: A, i: number) => B, node: Node, depth: number, offset: number, adjust: number): [Node, number] {
if (depth !== 0) {
const { array } = node;
var innerOffset = offset;
const result = new Array(array.length);
for (let i = 0; i < array.length; ++i) {
let [res, newOffset] = mapNodeWithIndex(f, array[i], depth - 1, innerOffset, adjust * 32);
innerOffset = newOffset;
result[i] = res
}
return [new Node(node.sizes, result), innerOffset];
} else {
let [res, newOffset] = mapArrayWithIndex(f, node.array, offset);
return [new Node(undefined, res), newOffset];
}
}
function mapPrefixWithIndex<A, B>(f: (a: A, i: number) => B, prefix: A[], length: number): B[] {
const newPrefix = new Array(length);
for (let i = length - 1; 0 <= i; --i) {
newPrefix[i] = f(prefix[i], length - 1 - i);
}
return newPrefix;
}
function mapAffixWithIndex<A, B>(f: (a: A, i: number) => B, suffix: A[], length: number, totalLength: number): B[] {
const priorLength = totalLength - length;
const newSuffix = new Array(length);
for (let i = 0; i < length; ++i) {
newSuffix[i] = f(suffix[i], priorLength + i);
}
return newSuffix;
}
/**
* Applies a function to each element in the given list, and its index, and returns a
* new list of the values that the function return.
*
*/
export function mapWithIndex<A, B>(f: (a: A, i: number) => B, l: List<A>): List<B> {
return new List(
l.bits,
l.offset,
l.length,
mapPrefixWithIndex(f, l.prefix, getPrefixSize(l)),
l.root === undefined ? undefined : mapNodeWithIndex(f, l.root, getDepth(l), getPrefixSize(l), 1)[0],
mapAffixWithIndex(f, l.suffix, getSuffixSize(l), l.length)
);
}Maybe one could use the depth and branchingFactor instead but this seems performance-wise to already fare better than zipWith. Here are my rudimentary benchmark results:
List.map 10 36818486.05 op/s ± 0.54% (86 samples)
List.mapWithIndex 10 32894014.39 op/s ± 0.39% (88 samples)
List.zipWith 10 4332197.10 op/s ± 0.63% (84 samples)
List.map 30000 14337.09 op/s ± 0.71% (88 samples)
List.mapWithIndex 30000 11587.69 op/s ± 0.54% (88 samples)
List.zipWith 30000 1240.52 op/s ± 0.61% (87 samples)
carleryd
paldepind
Hi
My use case frequently involves mapping a list of raw data into a UI representation that offers the ability to modify elements. For instance mapping a list into table rows, where the user may modify or delete rows. I was thinking having the index available when mapping would allow me to efficiently update the list on that index.
One could use List.zipWith(f, list, List.range(0,List.length(list))) or avoid the index and use List.find but maybe there is a place for a dedicated mapWithIndex function as that should theoretically be more efficient?
Does anyone else have similar use-cases and what is your solution?
Finally, thanks for a great lib!