Хвост-рекурсивный ограниченный поток пар целых чисел (Scala)?

Я очень новичок в Scala, так что прости мое невежество! Я пытаюсь перебрать пары целых чисел, которые ограничены максимумом. Например, если максимум равен 5, то итерация должна вернуть:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5)

Я решил попробовать и рекурсивно вернуть это как поток:

    @tailrec
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = {
        if (i == maximum && j == maximum) Stream.empty
        else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum)
        else (i, j) #:: _pairs(i, j + 1, maximum)
    }

Без аннотации tailrec код работает:

scala> _pairs(0, 0, 5).take(11)
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> _pairs(0, 0, 5).take(11).toList
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4))

Но это не достаточно хорошо для меня. Компилятор правильно указывает, что последняя строка _pairs не возвращает _pairs:

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position
    else (i, j) #:: _pairs(i, j + 1, maximum)
                ^

Итак, у меня есть несколько вопросов:

  • Непосредственно обращаясь к реализации выше, как один хвост рекурсивно возвращает поток [(Int, Int)]?
  • Делая шаг назад, какой самый эффективный способ памяти перебирать ограниченные последовательности целых чисел? Я не хочу перебирать Range, потому что Range расширяет IndexedSeq, и я не хочу, чтобы последовательность существовала полностью в памяти. Или я не прав? Если я переберу Range.view, я избегу его попадания в память?

В Python (!) Все, что я хочу, это:

In [6]: def _pairs(maximum):
   ...:     for i in xrange(maximum+1):
   ...:         for j in xrange(maximum+1):
   ...:             yield (i, j)
   ...:             

In [7]: p = _pairs(5)

In [8]: [p.next() for i in xrange(11)]
Out[8]: 
[(0, 0),
 (0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (0, 5),
 (1, 0),
 (1, 1),
 (1, 2),
 (1, 3),
 (1, 4)]

Спасибо за вашу помощь! Если вы считаете, что мне нужно читать ссылки / документы по API / что-нибудь еще, пожалуйста, скажите мне, потому что я стремлюсь учиться.

Источник

2 ответа

Решение

Это не хвостовая рекурсия

Давайте предположим, что вы составляли список вместо потока: (позвольте мне использовать более простую функцию, чтобы выразить свою точку зрения)

def foo(n: Int): List[Int] =
  if (n == 0)
    0 :: Nil
  else
    n :: foo(n - 1)

В общем случае в этой рекурсии, после foo(n - 1) возвращает функция должна сделать что-то со списком, который она возвращает - она ​​должна объединить другой элемент в начале списка. Таким образом, функция не может быть хвостовой рекурсией, потому что после рекурсии нужно что-то сделать со списком.

Без рекурсии хвоста, для некоторого большого значения n Вы исчерпали пространство стека.

Обычный список решений

Обычное решение было бы передать ListBuffer в качестве второго параметра, и заполните это.

def foo(n: Int) = {
  def fooInternal(n: Int, list: ListBuffer[Int]) = {
    if (n == 0) 
      list.toList
    else {
      list += n
      fooInternal(n - 1, list)
    }
  }
  fooInternal(n, new ListBuffer[Int]())
}

То, что вы делаете, называется " хвостовой рекурсией по модулю минусов ", и эта оптимизация выполняется автоматически компиляторами LISP Prolog, когда они видят шаблон хвостовой рекурсии по модулю, так как это очень распространено. Компилятор Scala не оптимизирует это автоматически.

Потоки не нуждаются в хвостовой рекурсии

Потоки не нуждаются в хвостовой рекурсии, чтобы избежать исчерпания стекового пространства - это потому, что они используют хитрый трюк, чтобы не выполнять рекурсивный вызов foo в том месте, где оно появляется в коде. Вызов функции оборачивается в thunk и вызывается только в тот момент, когда вы действительно пытаетесь получить значение из потока. Только один звонок foo активен одновременно - никогда не бывает рекурсивным.

Я написал предыдущий ответ, объясняющий, как #:: оператор работает здесь на Stackru. Вот что происходит, когда вы вызываете следующую рекурсивную функцию потока. (Это рекурсивный в математическом смысле, но он не вызывает функцию изнутри вызова функции, как вы обычно ожидаете.)

def foo(n: Int): Stream[Int] =
  if (n == 0)
    0 #:: Nil
  else
    n #:: foo(n - 1)

Ты звонишь foo(10), он возвращает поток с уже вычисленным одним элементом, а хвост - это thunk, который вызовет foo(9) в следующий раз вам понадобится элемент из потока. foo(9) сейчас не вызывается - скорее, вызов связан с lazy val внутри потока и foo(10) возвращается немедленно. Когда вам, наконец, нужно второе значение в потоке, foo(9) вызывается, и он вычисляет один элемент и устанавливает хвост потока, который будет вызывать foo(8), foo(9) немедленно возвращается без звонка foo(8), И так далее...

Это позволяет создавать бесконечные потоки без нехватки памяти, например:

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1)

(Будьте осторожны, какие операции вы вызываете в этом потоке. Если вы пытаетесь сделать forEach или map, вы будете заполнять всю кучу, но используя take хороший способ работы с произвольным префиксом потока.)

Более простое решение в целом

Вместо того, чтобы иметь дело с рекурсией и потоками, почему бы просто не использовать Scala for цикл?

def pairs(maximum:Int) =
  for (i <- 0 to maximum;
       j <- 0 to maximum)
    yield (i, j)

Это материализует всю коллекцию в памяти и возвращает IndexedSeq[(Int, Int)],

Если вам нужен конкретный поток, вы можете преобразовать первый диапазон в Stream,

def pairs(maximum:Int) =
  for (i <- 0 to maximum toStream;
       j <- 0 to maximum)
    yield (i, j)

Это вернет Stream[(Int, Int)], Когда вы получаете доступ к определенной точке в последовательности, она будет материализована в памяти и будет оставаться в ней до тех пор, пока у вас есть ссылка на любую точку в потоке перед этим элементом.

Вы можете получить еще лучшее использование памяти, преобразовав оба диапазона в представления.

def pairs(maximum:Int) =
  for (i <- 0 to maximum view;
       j <- 0 to maximum view)
    yield (i, j)

Это возвращает SeqView[(Int, Int),Seq[_]] он вычисляет каждый элемент каждый раз, когда вам это нужно, и не сохраняет предварительно вычисленные результаты.

Вы также можете получить итератор (который вы можете пройти только один раз) таким же образом

def pairs(maximum:Int) =
  for (i <- 0 to maximum iterator;
       j <- 0 to maximum iterator)
    yield (i, j)

Что возвращает Iterator[(Int, Int)],

Источник

Может быть, итератор лучше подходит для вас?

class PairIterator (max: Int) extends Iterator [(Int, Int)] {
  var count = -1
  def hasNext = count <= max * max 
  def next () = { count += 1; (count / max, count % max) }
}

val pi = new PairIterator (5)
pi.take (7).toList
Источник
Другие вопросы по тегам