基于Flatmap的Scala尾部递归
基于Flatmap的Scala尾部递归
提问于 2021-04-02 13:37:04
我有一个递归调用，定义如下：
def getElems[A](a: A)(f: A => List[A]): List[A] = {
f(a)
}
def parse[A](depth: Int, elems: List[A], f: A => List[A]): List[A] = {
elems.flatMap(elem => {
if (depth > 0) {
parse(depth - 1, getElems(elem)(f), f)
} else elems
})
}可以看到，对于elems中的每个元素，我运行一个函数，该函数反过来返回另一个列表。我一直这样做，直到我达到深度0。例如，我从某个元素和某个深度开始，如下所示：
parse(depth = 2, elems = List("1", "2"), someFnThatGivesBackAListOfString)我对上面的代码所做的是，对于elems中的每个元素，我检查深度值，如果深度> 0，我对该elem运行函数，并重复相同的过程，直到深度达到0。这可以像预期的那样工作，但可以看出它不是堆栈安全的，我想得到一个尾部递归实现。据我所知，尾递归是关于缩减的，但这里不是这样的。那么我如何让它堆栈安全，或者我如何在这里做一个尾递归逻辑呢？
我从类似这样的东西开始，但这并不完全正确：
def firstAttempt[A](ls: List[A], depthOrig: Int)(f: (A => List[A])): List[A] = {
@annotation.tailrec
def helper(acc: List[A], ls: List[A], depth: Int): List[A] =
ls match {
case Nil => acc
case sublist @ (head :: tail) =>
// Check if the entry is available in the bloom filter
if (depth > 0)
helper(acc ::: f(head), tail, depth - 1)
else
helper(acc.appended(head), tail, depthOrig)
}
helper(Nil, ls, depthOrig)
}回答 1
Stack Overflow用户
回答已采纳
发布于 2021-04-02 17:51:38
我通过将当前深度附加到每个元素来实现这一点。
def parse[A](depth:Int, elems:List[A], f:A => List[A]): List[A] = {
@annotation.tailrec
def loop(todo:List[(A,Int)], acc:List[A]): List[A] = todo match {
case Nil => acc
case (_,dpth)::_ if dpth < 1 =>
val (zs, td) = todo.span(_._2 < 1)
loop(td, acc ++ zs.flatMap(_ => zs.map(_._1)))
case (elm,dpth)::tl =>
loop(f(elm).map(_ -> (dpth-1)) ++ tl, acc)
}
loop(elems.map(_ -> depth), Nil)
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66914910
复制相关文章
相似问题
腾讯云开发者
