Scala中的匿名递归函数

zhte4eai  于 2023-04-12  发布在  Scala
关注(0)|答案(7)|浏览(237)

有没有一种方法可以在Scala中编写一个递归的匿名函数?我正在考虑这样的事情:

((t: Tree) => {
    print(t.value);
    for (c <- t.children)
        thisMethod(c)
})(root)

(相关问题:Which languages support recursive function literals / anonymous functions?

elcex8rz

elcex8rz1#

如您发布的链接中所述。您可以使用Y-组合器。下面是示例:

scala> def fix[A,B](f: (A=>B)=>(A=>B)): A=>B = f(fix(f))(_)
fix: [A,B](f: ((A) => B) => (A) => B)(A) => B

scala> val fact = fix[Int,Int](f => a => if(a<=0) 1 else f(a-1) * a)
fact: (Int) => Int = <function1>

scala> fact(12)
res0: Int = 479001600

注意它不适用于大的数字。小心尾部调用优化。

uz75evzq

uz75evzq2#

如果你不想达到“惊人的数学”,你可以回到scala的对象方面。

val fact = new Function1[Int,Int]{
    def apply(x:Int):Int = if(x==1) x else x * apply(x-1)
}
uajslkp6

uajslkp63#

为了让它看起来更极客,你也可以使用这种代码风格:

val fact = new ((Int) => Int){
  def apply(x:Int):Int = if(x==1) x else x * apply(x-1)
}
vwoqyblh

vwoqyblh4#

除了这个线程中的许多好的响应之外,Scala没有给我们提供尾部调用优化的定点组合子这个事实一直困扰着我,以至于我决定写一个宏来将类似Y组合子的调用转换为普通的、惯用的递归调用(当然有尾部调用优化)。

fix[Int,Int]((next) => (y) => ...body...)

很容易被翻译成

({(input) =>
  object next {
    def apply(y:Int):Int = ...body...
  }
  next(input)
})

我已经把针对Scala 2.11的宏实现(稍微调整一下也可以在2.10中工作)放到了this gist中。
有了这个宏,我们可以以匿名的方式执行普通的递归任务,而不用担心堆栈溢出。

import asia.blip.ymacro.YMacro._
(y[BigInt,BigInt]((xx) => (y) => if(y==1) 1 else y * xx(y-1)))(2000)

给予

res0: BigInt = 33162750924506332411753933805763240382811...
kmynzznz

kmynzznz5#

Scala上的递归调用。让我以N个数的和为例进行递归

var sumIt:(Int => Int) = (x: Int) => {if(x<=1) 1 else sumIt(x-1)+x}

 scala> sumIt(10) 
val res141: Int = 55

你可以看到sumIt的类型是Int,Int作为输入,返回值是。sumIt lambda函数的参数是一个Integer,它递归调用sumIt。
我只是这个例子,以便于理解递归调用。你可以直接公式为这个逻辑像…

sumValue = (N*(N+1)) /2
bfrts1fy

bfrts1fy6#

添加到@in-ho-yi的answer上。为了简单起见,你可以直接在匿名函数中定义一个局部函数,并使用它进行递归。在局部函数之前使用@tailrec,你可以确保它会应用尾部递归,这是你不能用Y组合子来做的。
这是一个比Y-combinator更好的方法,因为它只向堆栈添加2帧,每次调用函数只添加1帧(如果不是尾递归,如果是尾递归,则总共只添加1帧,因此最多将使用3帧),而不是Y-combinator使用的每次调用6帧

import scala.annotation.tailrec

val fact = {(input: BigInt)=>
  @tailrec
  def f(x:BigInt, acc: BigInt = 1):BigInt = {
    if(x<=1) acc
    else f(x-1, x*acc)
  }
  f(input)
}

print(fact(1024))
von4xj4u

von4xj4u7#

一个非常简单的方法:

val fact = { (x: Int) =>
  def f(x: Int): Int = if (x == 0) 1 else x * f(x-1)
  f(x)
}

// Use as anonymous function below
(1 to 5).map { (x: Int) =>
  def f(x: Int): Int = if (x == 0) 1 else x * f(x-1)
  f(x)
}

// res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 6, 24, 120)

相关问题