Phillip R Phillip R - 3 years ago 99
Scala Question

Scala Generics With Recursion

So I have a generic compose combinator.

Recall that the composition of two functions—f and g-- is h(x) = f(g(x))

def inc(x: Double) = x + 1
def double(x: Double) = 2 * x

def compose[A,B,C](f: B => C, g: A => B, x: A): C = f(g(x))

//TEST
println(compose(double, inc, 2.0))
//OUTPUT
// 6.0


But now I want to implement the self-composition iterator combinator, recursively, using my compose function where:

def selfIter[T](f: T=>T, n: Int) = f composed with itself n times.


I tried doing this:

def selfIter[T](f: T, n: Int): T = {
if(n == 0) f
else f + selfIter(f, n-1)
}

//TEST
println(selfIter(compose(double, inc, 2.0), 2))


I get an error, I know I'm doing something fundamentally wrong, but I cant figure out what I need to do.

In this case, the output should be 14.0 because first call will be 2(2+1) = 6.0, and then second call will be 2(6.0 + 1) = 14.0

Question: How should I refactor my code so that selfIter will compose f with itself n times until we have n == 0, and returns the final value

Answer Source

The easiest way to solve this kind of problems is to use the combinators provided by Scala. Also you should first compose the function you want to use and then apply the input

def compose[A,B,C](f: B => C, g: A => B): A => C = g.andThen(f)
def selfIter[T](f: T=>T, n: Int): T => T = Function.chain(List.fill(n)(f))
println(selfIter(compose(double, inc), 2)(2.0))

If compose signature could not be changed then

def compose[A,B,C](f: B => C, g: A => B, x: A): C = f(g(x))
def selfIter[T](f: T=>T, n: Int): T => T = Function.chain(List.fill(n)(f))
println(selfIter[Double](compose(double, inc, _), 2)(2.0))

But it makes much more sense the first solution

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download