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

Mikel San Vicente · Accepted Answer · 2017-09-29 22:03:35Z

3

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

edited Sep 29, 2017 at 22:03

answered Sep 29, 2017 at 21:50

Mikel San Vicente

3,8632 gold badges24 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Phil Over a year ago

What if Im not allowed to change anything in the compose function? How would I do it that way? And recursion is a must

Phil Over a year ago

Could to explain a bit about the third parameter in compose. Why you used _ and how that works with this function.chain and list.fill

Mikel San Vicente Over a year ago

if you look at selfIter method the first parameter is of type T => T, we could satisfy that by passing (v: Double) => compose(double, inc, v), this is equivalent to compose(double, inc, _)

jwvh · Accepted Answer · 2017-09-30 05:59:38Z

2

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

edited Sep 30, 2017 at 5:59

answered Sep 29, 2017 at 21:52

jwvh

51.3k7 gold badges42 silver badges70 bronze badges

Collectives™ on Stack Overflow

Scala Generics With Recursion

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related