Как я могу сделать эту функцию Scala (вариант "flatMap") хвостовой рекурсивной? - PullRequest
Новая
       13

Как я могу сделать эту функцию Scala (вариант "flatMap") хвостовой рекурсивной?

4 голосов
/ 10 декабря 2011

Я смотрю на следующий код

http://aperiodic.net/phil/scala/s-99/p26.scala

В частности 

def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

Я получаю StackOverflowError для больших значений, предположительно, потому что функция не является хвостовой рекурсивной. Есть ли способ преобразовать функцию для размещения больших чисел?

Ответы [ 3 ]

6 голосов
/ 10 декабря 2011

Это определенно не хвостовая рекурсия.f(sublist) ::: изменяет результаты рекурсивного вызова, превращая его в простую рекурсию с перебором стека вместо хвостовой рекурсии.

Один из способов убедиться, что ваши функции являются хвостовой рекурсией, - это поместить@annotation.tailrec для любой функции, для которой вы ожидаете получить хвостовую рекурсию.Компилятор сообщит об ошибке, если не выполнит оптимизацию хвостового вызова.

Для этого я бы добавил небольшую вспомогательную функцию, которая на самом деле является хвостовой рекурсией: 

def flatMapSublistsTR[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = {
  @annotation.tailrec
  def helper(r: List[B], ls: List[A]): List[B] = {
    ls match {
      case Nil => r
      case sublist@(_ :: tail) => helper(r ::: f(sublist), tail)
    }
  }
  helper(Nil, ls)
}

ДляПричины, не сразу очевидные для меня, результаты выходят в другом порядке, чем исходная функция.Но, похоже, это работает: -) Исправлено.

3 голосов
/ 10 декабря 2011

Вот еще один способ реализации функции: 

scala> def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
     |   List.iterate(ls, ls.size)(_.tail).flatMap(f)
flatMapSublists: [A, B](ls: List[A])(f: List[A] => List[B])List[B]

Простое сравнение между dave's flatMapSublistsTR и моим: 

scala> def time(count: Int)(call : => Unit):Long = {
     |    val start = System.currentTimeMillis
     |    var cnt =  count
     |    while(cnt > 0) {
     |       cnt -= 1
     |       call
     |    }
     |    System.currentTimeMillis - start
     | }
time: (count: Int)(call: => Unit)Long

scala> val xs = List.range(0,100)

scala> val fn = identity[List[Int]] _
fn: List[Int] => List[Int] = <function1>

scala> time(10000){ flatMapSublists(xs)(fn) }
res1: Long = 5732

scala> time(10000){ flatMapSublistsTR(xs)(fn) }
res2: Long = 347232

Где метод flatMapSublistsTR реализован как: 

def flatMapSublistsTR[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = {
  @annotation.tailrec
  def helper(r: List[B], ls: List[A]): List[B] = {
    ls match {
      case Nil => r
      case sublist@(_ :: tail) => helper(r ::: f(sublist), tail)
    }
  }
  helper(Nil, ls)
}
1 голос
/ 10 декабря 2011 
def flatMapSublists2[A,B](ls: List[A], result: List[B] = Nil)(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => result
      case sublist@(_ :: tail) => flatMapSublists2(tail, result ++ f(sublist))(f)
    }

Как правило, вам просто нужно добавить параметр результата результата для переноса из одной итерации в следующую, и выложить результат в конец вместо добавления конца в список.

Также этоНеверная вещь sublist@ может быть упрощена до

case _ :: tail => flatMapSublists2(tail, result ++ f(ls))(f)

Не по теме: вот как я решил проблему 26, без необходимости использования вспомогательных методов, подобных описанному выше.Если вы можете сделать этот хвост рекурсивным, возьмите золотую звезду. 

  def combinations[A](n: Int, lst: List[A]): List[List[A]] = n match {
    case 1 => lst.map(List(_))
    case _ => lst.flatMap(i => combinations (n - 1, lst.dropWhile(_ != i).tail) map (i :: _))
  }
...