CODEWITHSUNDEEP
scala
thlim
thlim

Reputation: 2982

Scala function with a recursive function parameter

I am curious if can implement a Scala function similar to this Javascript function. Obviously, I can do it easily with an inner function.

Knowing that Scala has to declare the parameter type and arity upfront, I just wonder if there is anything I could use to implement this JS function. Thanks.

function factorial(x) {
  if (x < 0) throw Error("Cannot calculate factorial of a negative number");
  return (function(f) {
    return f(f, x, 1);
  })(function(f, i, fact) {
    return i === 0 ? fact : f(f, i-1, i*fact);
  });
}

Upvotes: 1

Views: 345

Answers (1)

Hamish
Hamish

Reputation: 1015

If I have understood your question correctly, indeed you can do this and the best known approach is to use what's called a Y-combinator. In short a Y-combinator takes a function as a parameter and keeps applying it. The Y-combinator has no knowledge of the parameter types involved

Copying the example Y-combinator right from rosetta code:

def Y[A,B](f: (A=>B)=>(A=>B)) = {
  case class W(wf: W=>A=>B) {
    def apply(w: W) = wf(w)
  }
  val g: W=>A=>B = w => f(w(w))(_)
  g(W(g))
}

defines your combinator. You can then pass it your recursive function

val fac = Y[Int, Int](f => i => if (i <= 0) 1 else f(i - 1) * i)
fac: Int => Int = <function1>

And then give that something to evaluate

scala> fac(6)
res0: Int = 720

Upvotes: 6

Related Questions