Scala: How to write a f function inside the currying function?

user_13387383 0
Viewed 84

This sum function working fine, but I am having trouble to write the version that swap x and f:(Int=>Int)

Works fine:

def sum(f:Int=>Int):Int=>Int = {
    def ret_fun(x:Int):Int =
        if (x==1) f(1)
        else f(x)+ret_fun(x-1)
    ret_fun
}

Did not work:

def sum(x:Int):Int=>Int = {
    def ret_fun(f:Int=>Int):Int =
        if (x==1) f(1)
        else f(x)+ret_fun(x-1)
    ret_fun
}

Did anyone know how to solve this?

currying scala
2 Answers

First of all, the return type of the second sum should be (Int => Int) => Int, because it's supposed to return a function that accepts an Int => Int function, not an Int number.

Unfortunately you can't iterate over x using recursion of ret_fun, because x is not its argument. However you could use an indirect recursion of sum

def sum(x: Int): (Int => Int) => Int = {
  def ret_fun(f: Int => Int): Int =
    if (x == 1) f(1)
    else f(x) + sum(x - 1)(f)
  ret_fun
}

I imagine it may defeat the purpose of your exercise, because it's essentially the same as saying:

def sum(x: Int)(f: Int => Int): Int =
  if (x == 1) f(1)
  else f(x) + sum(x - 1)(f)

If your idea was to implement ret_fun using direct recursion and achieve the full analogy with the first example, let me comment on why it's problematic.

The reason is that the stop condition x == 1 is defined in terms of x and not in terms of f(x), so it's hard to determine which invocation should recurse and which shouldn't without changing the logic of the algorithm

def sum(x: Int): (Int => Int) => Int = {
  def ret_fun(f: Int => Int): Int =
    if (???) f(1)
    else f(x) + ret_fun(x => f(x - 1))
  ret_fun
}

We can, for instance, try if (f(x) == 0) 0, but as I said it will pretty much break the algorithm and will calculate f(x) + f(x - 1) + ... + 0 instead of f(x) + f(x - 1) + ... + f(1)

user_18865100

If you are fine with your second function depending on the first one, you just define it as this:

def sum(x: Int): (Int=>Int) => Int = f => sum(f)(x)

Otherwise you can do this:

def sum(x: Int): (Int => Int) => Int = f => f(x) + (if (x == 1) 0 else sum(x - 1)(f))

There's no need to define ret_fun separately.

If you absolutely want ret_fun, though, you can add x as a parameter to ret_fun, like this:

def sum(x: Int): (Int => Int) => Int = {
  def ret_fun(x: Int)(f: Int => Int): Int =
    if (x == 1) f(1)
    else f(x) + ret_fun(x - 1)(f)
  ret_fun(x)
}

If you want the function to be the first parameter, then you can do this, which is basically the same:

def sum(x: Int): (Int => Int) => Int = {
  def ret_fun(f: Int => Int)(x: Int): Int =
    if (x == 1) f(1)
    else f(x) + ret_fun(f)(x - 1)
  ret_fun(_)(x)
}
user_118820020
Related