CODEWITHSUNDEEP
scalagenerics
Phil
Phil

Reputation: 3562

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

Upvotes: 0

Views: 537

Answers (2)

jwvh
jwvh

Reputation: 51271

There are a few things going wrong here.

This f + selfIter(f, n-1) says that f (type T) must have a + method that takes another T as an argument. But you don't want to add these things, you want to compose them.

Here's a simpler way to get the result you're after.

Stream.iterate(2.0)(compose(double, inc, _))(2)  // res0: Double = 14.0

If you're intent on a recursive method, this appears to achieve your goal.

def selfIter[T](start:T, n:Int)(f:T=>T): T = {
  if (n < 2) f(start)
  else f(selfIter(start, n-1)(f))
}
selfIter(2.0, 2)(compose(double, inc, _))  // res0: Double = 14.0

Upvotes: 2

Mikel San Vicente
Mikel San Vicente

Reputation: 3863

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

Upvotes: 3

Related Questions