3

I am using a functional programming style to solve the Leetcode easy question, Count the Number of Consistent Strings. The premise of this question is simple: count the amount of values for which the predicate of "all values are in another set" holds.

I was able to do this pretty concisely like so:

class Solution {
    fun countConsistentStrings(allowed: String, words: Array<String>): Int {
      val permitted = allowed.toSet()
      return words.count{it.all{it in permitted}}
    }
}

I know that Java streams are lazy, but have read Kotlin is only lazy when asSequence is used and are otherwise eager.

For reductions to a boolean based on a predicate using any, none, or all, it makes the most sense to me that this should be done lazily (e.g. a single false in all should evaluate the whole expression to false and stop evaluating the predicate for other elements).

Are these operations implemented this way, or are they still done eagerly like other operations in Kotlin. If so, there a way to do them lazily?

4 Answers 4

3

No, those methods are not lazy.

First, bear in mind that there are multiple methods with each of those names: two defined on Sequence, two defined on each of thirteen types of array, two on Map, and one on Iterable. It's clear you're interested only in those defined on Sequence, as those other types don't support laziness.

So, let's look at the docs! The docs for Sequence.any(), for Sequence.none(), and for Sequence.all() methods all say:

The operation is terminal.

To confirm what this means, the docs for the kotlin.sequences package, say:

If the sequence operation returns another sequence, which is produced lazily, it's called intermediate, and otherwise the operation is terminal.

So those methods are not lazy; when executed, they cause the sequence to be evaluated as far as is needed to produce the required value. (However, they don't evaluate it any further than is needed, which may be what you're asking. After all, that's the point of using Sequences!)

(In fact, you can see from their types that there's no way they could be lazy: each of them returns a Boolean value, which is either true or false. To support lazy evaluation, they'd need to return a Future or similar object with a getter that could be called to produce a final result. But a Boolean already is that final result.)

2
  • "However, they don't evaluate it any further than is needed, which may be what you're asking" I think I have some definitions that I need to review. This is what I am asking.
    – AaronC
    Jan 12, 2022 at 1:26
  • Since that's what you're asking, you should also note, the same functions on Iterable instead of Sequence also do not evaluate any further than is needed. See @broot's answer. The advantage with Sequence in certain cases is that is also skips intermediate operations for elements that don't need to be evaluated to determine the terminal result.
    – Tenfour04
    Jan 12, 2022 at 2:39
3

I think you overinterpret what lazily and eagerly mean. Like "eagerly" means to always do everything in the most inefficient way possible.

Lazy collections (Streams API, sequences) try to postpone calculating their contents until necessary. On the other hand regular collections perform operations immediately when requested. But that doesn't mean if we ask a regular collection for its first element, it will iterate over all of them for no reason.

As a matter of fact, these functions are implemented in almost exactly the same way for both iterables and sequences. The difference is in other transformations and operators. Below is an example for any():

public inline fun <T> Iterable<T>.any(predicate: (T) -> Boolean): Boolean {
    if (this is Collection && isEmpty()) return false
    for (element in this) if (predicate(element)) return true
    return false
}

public inline fun <T> Sequence<T>.any(predicate: (T) -> Boolean): Boolean {
    for (element in this) if (predicate(element)) return true
    return false
}
1

The docs don't explicitly say, but this is easy enough to test.

class A : Iterable<String>, Iterator<String> {
  public override fun iterator(): Iterator<String> {
    return this
  }
  public override fun hasNext(): Boolean {
    return true
  }
  public override fun next(): String {
    return "test"
  }
}

fun main(args: Array<String>) {
  val a = A()
  println(a.any { x -> x == "test" })
  println(a.none { x -> x == "test" })
  println(a.all { x -> x != "test" })
}

Here, A is a silly iterable class that just produces "test" forever and never runs out. Then we use any, none, and all to check whether it produces "test" or not. It's an infinite iterable, so if any of these three functions wanted to try to exhaust it, the program would hang forever. But you can run this yourself, and you'll see a true and two false's. The program terminates. So each of those three functions stopped when it found, respectively, a match, a non-match, and a non-match.

Try it online!

1

In short, Sequences in Kotlin are somewhat similar to Java Streams in that they have many lazy functions that simply return another Sequence.

However, all, any and none are immediate regardless of whether you call them on a Sequence or an Iterable. You can tell they are not lazy because they return a Boolean instead of another Sequence, and in their documentation, they are described as terminal, which means they evaluate and iterate the Sequence immediately.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.