Add key iteration function to dictionaries

[turbolent]

Issue To Be Solved

Dictionaries currently have a let keys: [K] field (where K is the type of the keys), which returns all keys of the dictionary.

Dictionaries may stores a lot of elements, so the resulting keys array might be very expensive to produce.

Suggested Solution

Similar to the new storage iteration functions, add a new function to Dictionary which allows iterating over keys of the dictionary:

fun forEachKey(_ f: ((K): Bool))

The Bool return value of the iteration function f determines whether iteration continues; true will proceed to the next key, while false will terminate iteration. The specific order in which the objects are iterated over is undefined, as is the behavior when a key is added or removed from the dictionary.

[dreamsmasher]

To clarify, did you mean a signature closer to

fun forEachKey(_ f: (K): Bool): ()

?

[turbolent]

@dreamsmasher ah, right, the parameter should be a function! Fixed the signature in the description

[dreamsmasher]

Maybe we should open a FLIP to change the syntax for function types to something more clear, like T -> U

[bluesign]

for N keys:

let keys: [K] vs calling N times fun forEachKey(_ f: ((K): Bool)) what is the difference here? Obviously there is something but I am missing.

The specific order in which the objects are iterated over is undefined, as is the behavior when a key is added or removed from the dictionary.

This is a big problem actually, makes iterator a bit pointless. ( for large collections )

[turbolent]

@bluesign

for N keys:

let keys: [K] vs calling N times fun forEachKey(_ f: ((K): Bool)) what is the difference here? Obviously there is something but I am missing.

No, a user would not call forEachKey N times, they would call it once, and forEachKey in turn calls the given function f up to N times, for eahc key of the dictionary.

The documentation should maybe describe this and provide an example to avoid misunderstandings.

[bluesign]

No, a user would not call forEachKey N times, they would call it once, and forEachKey in turn calls the given function f up to N times, for eahc key of the dictionary.

@turbolent: yeah I meant ((K): Bool) calling N times here, what will be the difference here ? in computation cost? or memory cost etc? If it was dictionary, I would understand the as N get bigger cost is increasing but why with the array ?

[dreamsmasher]

No, a user would not call forEachKey N times, they would call it once, and forEachKey in turn calls the given function f up to N times, for eahc key of the dictionary.

@turbolent: yeah I meant ((K): Bool) calling N times here, what will be the difference here ? in computation cost? or memory cost etc? If it was dictionary, I would understand the as N get bigger cost is increasing but why with the array ?

The difference is direct iteration vs creating an intermediate array then iterating over that. This reduces the amount of requests to the storage layer if you exit early.

[bluesign]

This reduces the amount of requests to the storage layer if you exit early.

Yeah this: "if you are lucky", is not a so good idea in my opinion. Isn't it better to fail always vs fail rarely ?

[turbolent]

@bluesign

what will be the difference here ? in computation cost? or memory cost etc? If it was dictionary, I would understand the as N get bigger cost is increasing but why with the array ?

You could imagine a caller chunking the keys into smaller parts and returning them individually, vs returning all keys at once, which might be prohibitively expensive.

For example, to skip the first few keys, then collect some, and finally ignore the rest:

let dictionary: {UInt64: String} = // ...
let someKeys: [UInt64] = []
var i = 0
dictionary.forEachKey(fun (key: UInt64): Bool {
    if i < 10 {
        i = i + 1
        return true
    } else if i < 20 { 
        i = i + 1
        someKeys.append(key)
        return true
    } else {
        return false
    }
})

[turbolent]

@bluesign

"if you are lucky", is not a so good idea in my opinion. Isn't it better to fail always vs fail rarely ?

What do you mean by this? I don't quite follow.

[bluesign]

if we have "keys" that will cause computation limit to exceed, then also if sum of all key iteration will be same computation cost, if I am searching for a key, it will fail in some cases and succeed in others ( depending on random key ordering )

[bluesign]

For example, to skip the first few keys, then collect some, and finally ignore the rest:

This is super bad example though, considering ordering of the keys is random. But I mean it can be used for iteration yes.

On a second thought, if you are running script very valuable, but on transactions it is a bit dead end.