Подсчет потока элементов до нужного значения

Question

count принимает Stream[Int] и desiredNum аргументы. Он добавляет главу потока (в, я считаю, ленивый способ) до текущей суммы >=desiredNum.

Пример: count(Stream.continually(1), 2) должен получить выход 2 с 1 + 1 = 2.

Вот мой код:

def count(as: Stream[Int], desiredNum: Int): Option[Int] = { 
     def go(bs: Stream[Int], currentNum: Int, count: Int): Option[Int] = 
     bs match { 
     case x #:: xs if(currentNum >= desiredNum) => Some(count) 
     case x #:: xs => go(xs, currentNum + x, count + 1) 
     case Stream() => None   
     } 
     go(as, 0, 0) 
    } 

Тесты:

scala> count(Stream(1), 1) 
res0: Option[Int] = Some(1) 

scala> count(Stream.continually(1), 100) 
res0: Option[Int] = Some(100) 

EDIT Обратите внимание, что я изменил мой вопрос после того, видя, что я не проверял правильное значение в моем первом case заявлении. Первоначально я использовал x (глава Stream), а не currentNum. Это привело к бесконечному циклу.

Но существует ли конкретный предел на desiredNum в отношении ЦП и ОЗУ? Является ли эта функция правильно с использованием Stream? (Возможно, плохое использование ОЗУ в count?)

Answer 1

Я считаю, что ваш вопрос сводится к «is count tail recursive». И это. Поэтому никаких ссылок на значения промежуточных потоков (x) или вычислений (currentNum + 1) не требуется. Scala имеет аннотацию @tailrec, которая позволяет компилятору проверить, что ваша рекурсия находится в хвостовом положении и, таким образом, может выполнять оптимизацию хвостового вызова.