Scala Generics With Recursion

Question

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

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

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

Scala Generics With Recursion

Sign up