For (let i = len - 1; i > 0; i /= 2)


#1

How to write that in Kotlin without exposing variable “i” and implement it gracefully?


#2

You can use generateSequence for this. I’m not sure it is the best way, but it is cleaner than using a while loop.

for (i in generateSequence(length - 1) {last -> (last / 2).let { if(it > 0) it else null }})

generateSequence will have a “next” element as long as it is not null ( I hope that makes sense). The other advantage to it is, that it is lazily executed.


#3

Thanks for your help. It does work well. But I think it’s a little bit long(half of my screen).
What do you think about removing for(;;) in Kotlin?


#4

I think there was a discussion about this here previously. I personally like the for (i in 0..100 step 3) syntax. I think it is much cleaner than the old for(;;). Yours is the first example I have seen so far, where the old syntax is superior.

Btw I would pull the generateSequence part out into its own function and just call for(i in halvingSequence(lenght - 1). That again would make your code cleaner and you can easily use it in other places as well.


#5

I want the old syntax comes back. Q.Q The new syntax is not flexible, it can only be used in limited scene.


#6

I think it is a good example why for(;;) was removed. In this case what we have is an iteration with uncontrollable number of steps. It could have side effects and very hard to debug (something could be broken on step number 100000). Also it could pollute the memory.

The kotlinish way to treat this case would be infinite lazy sequence:

val sequence = buildSequence {
    var value = start
    while (value > 0){ // add any other conditions
       value /= 2
       yield(value)
    }
}

sequence.forEach{ <do something>}

In this case, you generate and consume numbers when you need them without creating intermediate large array. You can also limit the number of iterations and perform a lot of interesting sequence operations without additional complications.


#7

I think it is making a simple thing complex. I just want to get a simple sequence for a simple function. It’s not making things easier.


#8

This is an improvement of @Wasabi375 suggestion

for (i in generateSequence(len - 1) { it / 2 }.takeWhile { it > 0 })

#9

First, your code is broken. The loop does not terminate when len is greater than or equal to 1. Please take the time to ensure that your code samples are correct.

Second, even after switching to i > 0, the loop seems very odd. What is its purpose? If we know what you want to achieve, the best implementation in Kotlin can be decided upon. Now we only have a strange loop to improve.


#10

Thank you.


#11

Edit: I misunderstood @SackCastellon. I did not know about takeWhile as I explained later. Both his and my version are working. I leave my original post here for context.

@SackCastellon I think you where thinking of takeIf. I forgot about it in my example. Fixing yours it would be

for (i in generateSequence(length - 1) {  last -> (last / 2).takeIf {it > 0 } }) {
...

Take if must be inside the generateSequence call. As @jstuyts pointed out your version would create a non terminating loop. generateSequence will generate a new entry as long as it is not null. By pulling the takeIf into the sequence the sequence is terminating.


#12

I am trying to implement Heap, i = (i - 1) / 2 for calculating parent’s index.

fun insert(value: Int) {
        nodes.add(value)
//        for ((child, parent) in generateSequence(nodes.lastIndex to (nodes.lastIndex - 1) / 2) {
//            it.second to (it.second - 1) / 2
//        }.takeWhile { it.second >= 0 && nodes[it.second] < nodes[it.first] }) {
//            nodes[child] = nodes[parent].also { nodes[parent] = nodes[child] }
//        }

        for ((child, parent) in generateSequence(nodes.lastIndex to (nodes.lastIndex - 1) / 2) {
            (it.second to (it.second - 1) / 2).takeIf { it.second >= 0 && nodes[it.second] < nodes[it.first] }
        }) {
            nodes[child] = nodes[parent].also { nodes[parent] = nodes[child] }
        }
    }

#13

One more question.
How to implement it without exposing variables? (I know run {} can do that but it’s too ugly)

int[] arr = {/*...*/};
for (int a = 0, b = 1, c = 2; b < arr.length; b = a * 2 + 1, c = b + 1) {
    a = c < arr.length && arr[c] > arr[b] ? c : b;
}

#14

Both my code:

for (i in generateSequence(len - 1) { it / 2 }.takeWhile { it > 0 })

And yours:

for (i in generateSequence(len - 1) { (it / 2).takeIf { it > 0 } })

Produce the same result, the difference resides on how the work under the hood.

My code generates a sequence like 16, 8, 4, 2, 1, 0, 0, 0, ... but the takeWhile() function tels the secuence to stop giving elemets when one of them doesn’t satisfy { it > 0 }

However, your code generates a sequence like 16, 8, 4, 2, 1, null, null, null, ... (because takeIf() is inside the nextFunction) but by default, sequences stop giving elements when one of them is null.

So, in the end, we have the same result which would be 16, 8, 4, 2, 1 in this case.


#15

Woops, sry you are right. I did not know about takeWhile and assumed you meant to use takeIf. In that case I prefer your version. I will edit my answer accordingly to not spread missinformation.


#16

Sorry, I still don’t understand what you are trying to achieve. You are adding a value to nodes, and then you are modifying values in nodes at multiple locations.

It is also very unclear what is happening because of the “idiomatic” Kotlin.

So I am afraid I cannot help you with my solution to your problem.


#18

Just a kind of data structure Heap.


#19

I won’t ask you what you need this for, I don’t think that’s necessary to be able to answer the question.
I think you should use a while loop. “Keep it simple stupid” (edit, see: KISS Principle, thanks to ilya from JetBrains for pointing out that I should add the reference).
In the end, the java for loop will do the exact same thing.

If you don’t want the variable exposed, I can’t really help there. I guess you can just declare the variable i and then reuse it though, if you need another loop?

var i: Int

i = <some start value>
while (i > 0) {
    <do something>
    i /= 2
}

<repeat code>

You can go with the more kotlin-y solutions like what SackCastellon posted as well, but as you can see, you needed to ask around to find out how to do it. Everyone can use a while loop and everyone can understand a while loop.


#20

Alternatively, you can use something like the below. I don’t think this helper function exists in the stdlib.

fun example() {

    forLegacy(20, { it / 2 }, { it > 0 }) l@ { i ->
        // to continue
        return@l
    }

    forLegacyWithBreak(20, { it / 2 }, { it > 0 }) l@ { i ->
        // to break
        breakLoop()
        return@l
    }

}

inline fun <T> forLegacy(start: T, next: (T) -> T, cond: (T) -> Boolean, action: (T) -> Unit) {
    var cur = start
    while (cond(cur)) {
        action(cur)
        cur = next(cur)
    }
}

class ForWithBreak {
    var broken = false
    fun breakLoop() {
        broken = true
    }
}

inline fun <T> forLegacyWithBreak(start: T, next: (T) -> T, cond: (T) -> Boolean, action: ForWithBreak.(T) -> Unit) {
    val receiver = ForWithBreak()
    var cur = start
    while (cond(cur) && !receiver.broken) {
        receiver.action(cur)
        cur = next(cur)
    }
}

Advantages:

  • It functions exactly like a legacy for loop, with the exception that you can’t declare multiple variables
  • It produces the same bytecode (with the exception of the breakable one)
  • Doesn’t create multiple lambda objects like generateSequence does (because it’s inlined)

#21

TBH I’m glad Kotlin dropped for(;;) and I don’t see why anyone should use for(i in Iterable) directly in their code (apart from it being a more familiar syntax). After all, you can just write Iterable.foreach { ... } and it will inline the same code in the call site. Anyway back to your question and having the above in mind I would write:

generateSequence(len - 1) { it / 2 }.takeWhile { it > 0 }.forEach {_ -> ... }

I added _ because you said you want to hide the number itself from the code inside your block. Also because this is just a sequence you can probably use some of the many transformation functions on sequences and avoid the forEach entirely. But

Going a step further you can generalize any for(;;) loop as follows:

for( <initial_value_declaration> ; <break_conditions> ; <action_steps> )

generateSequence(<initial_value_declaration>) { <action_steps> }.takeWhile { <break_conditions> }.forEach

It is more verbose than Java which is a rare thing in Kotlin :slight_smile:

I have no idea what your code does, but I just reformatted it the way I would write it and used named pairs in all blocks for consistency.

generateSequence(nodes.lastIndex to (nodes.lastIndex - 1) / 2) { (child, parent) ->
    parent to (parent - 1) / 2
}.takeWhile { (child, parent) ->
    parent >= 0 && nodes[parent] < nodes[child]
}.forEach { (child, parent) ->
    nodes[child] = nodes[parent]
    nodes[parent] = nodes[child]
}