尾部递归:Scala中的过滤器嵌套列表

Question

嵌套列表中的以下函数过滤器(删除1'S(：

def filter(list : List[Any], acc : List[Any] = Nil) : List[Any] = {
  list match {
    case Nil => acc
    case (l : List[_]) :: tail =>
      val nested = filter(l)
      if (nested.isEmpty) filter(tail, acc)
      else
        filter(tail, acc :+ nested)
    case 1 :: tail =>     filter(tail, acc)
    case other :: tail => filter(tail, acc :+ other)
  }
}

输入

filter(List(1, 3, 4, List(1, 4 ,5), List(1)))

输出

res0: List[Any] = List(3, 4, List(4, 5))

我的问题是：我该如何制作尾巴递归？我的主要问题是如何处理嵌套列表：val nested = filter(l, Nil)

谢谢

Answer 1

好吧，认为您可以使用 free monad 来解决此问题，例如在Typelevel Cats lib中。

"org.typelevel" %% "cats-free" % "1.0.1"

背后的想法是移动递归，该递归无法将其转换为代码的另一部分，其中这是可行的

因此，如果您想了解如何解决此类任务，则需要阅读Runar Oli Bjarnason的本文(并且可能观看此演示文稿(。之后，您可以尝试用自己写的蹦床(基于纸张和视频(来解决问题：

首先让我们以某种方式重新编写过滤器(这不是必要的，我只是在纸上的偶数/奇数示例中，下面我显示如何根据您的变体进行相同的操作(：

private def filterList(l: List[Any]): Option[Any] = {
  l.foldLeft(Option.empty[List[Any]]) {
    case (acc, next) if acc.isEmpty =>
      filter1(next).map(_ :: Nil)
    case (acc, next) =>
      acc.map(_ ++ filter1(next))
  }
}
private def filter1(a: Any): Option[Any] = a match {
  case 1 => Option.empty[Any]
  case l: List[Any] => filterList(l)
  case t => Some(t)
}
def filter(l: List[Any]): List[Any] = {
  filterList(l) match {
    case Some(l: List[Any]) => l
    case _ => Nil
  }
}

现在，假设Trampoline已经可用(并且可用，请参见下文(，并使用蹦床重写：

def filterList(l: List[Any]): Trampoline[Option[Any]] = {
  l.foldLeft[Trampoline[Option[List[Any]]]](Done(Option.empty[List[Any]])) {
    case (acc, next) =>
      acc.flatMap {
        case None => filter1(next).map(_.map(_ :: Nil))
        case v =>
          filter1(next).map (r => v.map(_ ++ r))
      }
  }
}
def filter1(a: Any): Trampoline[Option[Any]] = a match {
  case 1 => Done(Option.empty[Any])
  case l: List[Any] => More(() => filterList(l))
  case t => Done(Some(t))
}
def filter(l: List[Any]): List[Any] = {
  filterList(l).runT match {
    case Some(l: List[Any]) => l
    case _ => Nil
  }
}

Trampoline实现(基于纸张和视频(

sealed trait Trampoline[+A] {
  final def runT: A =
    this match {
      case Done(a) => a
      case More(k) => k().runT
      case t: FlatMap[Any, A] => t match {
        case Done(a) FlatMap f => f(a).runT
        case More(k) FlatMap f => k().flatMap(f).runT
        case FlatMap(xg: FlatMap[Any, A], f) =>
          xg.a.flatMap(a => xg.f(a)).runT
      }
    }
  def map[B](f: A => B): Trampoline[B] =
    flatMap(x => More(() => Done(f(x))))
  def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = this match {
    case FlatMap(a, g: Any) => FlatMap(a, (x: Any) => g(x) flatMap f)
    case x => FlatMap(x, f)
  }
}
case class More[+A](k: () => Trampoline[A])
  extends Trampoline[A]
case class Done[+A](result: A)
  extends Trampoline[A]
case class FlatMap[A, B](a: Trampoline[A], f: A => Trampoline[B])
  extends Trampoline[B]

现在，使用所有这些零件，您可以检查现在您已经拥有无堆栈的递归实现。我使用这样的代码进行测试：

def check(i: Int, output: Boolean) {
  val l = (1 to i).foldLeft(List[Any](1, 2, 3)) {
    case (l, _) =>
      List[Any](1, 2, 3, l, List(1))
  }
  val res = filter(l)
  if (output) {
    println(s"Depth: $i, result: " + res)
  }
}
check(3, true)
check(10000, false)

它在StackOverflowError的非trampoline方法上失败，并在修改后成功完成。

用猫更新

我尝试使用cats-free lib尝试了相同的方法。它也可以很好地工作：

import cats.free._
import cats.implicits._
def filterList(l: List[Any]): Trampoline[Option[Any]] = {
  l.foldLeft[Trampoline[Option[List[Any]]]](Trampoline.done(Option.empty[List[Any]])) {
    case (acc, next) =>
      acc.flatMap {
        case None => filter1(next).map(_.map(_ :: Nil))
        case v =>
          filter1(next).map (r => v.map(_ ++ r))
      }
  }.map(_.map(identity[Any]))
}
def filter1(a: Any): Trampoline[Option[Any]] = a match {
  case 1 => Trampoline.done(Option.empty[Any])
  case l: List[Any] => Trampoline.defer(filterList(l))
  case t => Trampoline.done(Some(t))
}
def filter(l: List[Any]): List[Any] = {
  filterList(l).run match {
    case Some(l: List[Any]) => l
    case _ => Nil
  }
}

使用猫蹦床与原始代码

我试图使用您的原始代码做同样的事情，这是结果：

import cats.free._
import cats.implicits._
private def filterInner(list : List[Any], acc : List[Any] = Nil) : Trampoline[List[Any]] = {
  list match {
    case Nil => Trampoline.done(acc)
    case (l : List[_]) :: tail =>
      Trampoline.defer(filterInner(l)).flatMap {
        case Nil => Trampoline.defer(filterInner(tail, acc))
        case nested => Trampoline.defer(filterInner(tail, acc :+ nested))
      }
    case 1 :: tail =>     Trampoline.defer(filterInner(tail, acc))
    case other :: tail => Trampoline.defer(filterInner(tail, acc :+ other))
  }
}
def filter(list : List[Any]): List[Any] = filterInner(list).run

请注意，每次递归filterInner的递归调用都包裹在Trampoline.defer上，这是为了消除递归。您可以通过删除case (l : List[_]) :: tail零件中的包装并在我的测试示例中进行测试。