Scala pass a generic function into another generic function confusion

Question

I'm implementing the List type in Scala when following a book.

Here's the definition of my List type:

sealed trait List[+A]

case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

All the later mentioned functions are defined in the companion object List in the same file

object List

I wrote foldLeft and foldRight as the following

def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
    case Nil => z
    case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
}

def foldRight[A,B](l: List[A], z: B)(f: (A, B) => B): B = l match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
}

There's an exercise on the book, which is to implement foldLeft using foldRight. Here's my initial implementation

def foldLeftWithRight[A,B](l: List[A], z: B)(f: (B, A) => B): B = {
    foldRight(l, z)((a: A, b: B) => f(b, a))
}

Then I think I should write another function to do the reverse arguments if I'm to implement foldRight using foldLeft. As follows:

def reverseArgs[A,B](f: (A, B) => B): (B, A) => B = {
    (b: B, a: A) => f(a, b)
}

So I changed code of foldLeftWithRight to the following:

def foldLeftWithRight[A,B](l: List[A], z: B)(f: (B, A) => B): B = {
    foldRight(l, z)(reverseArgs(f))
}

And IntelliJ is complaining about reverseArgs(f):

Type mismatch: expected (A, B) => B, actual (B, B) => B

When I try to compile the code, the error is the following:

Error:(21, 37) type mismatch;
    found   : (B, A) => B
    required: (B, Any) => Any
        foldRight(l, z)(reverseArgs(f))

An interesting observation is that when I use the reverseArgs on foldRightWithLeft, there's no problem at all:

def foldRightWithLeft[A,B](l: List[A], z: B)(f: (A, B) => B): B = {
    foldLeft(l, z)(reverseArgs(f))
}

What is going on here?

Oleg Pyzhcov · Accepted Answer · 2017-07-20 08:51:51Z

2

If you rename type parameters of your reverseArgs function to X and Y, you'll get something like

def reverseArgs[X ,Y](f: (X, Y) => Y): (Y, X) => Y = ???

Type of f in foldLeftWithRight is (B, A) => B. Passing that to reverseArgs means that:

X = B
Y = A
Y = B

I guess Intellij infers from here that A = B and this is why it's complaining that (B, B) => B isn't (A, B) => B. Scalac decides that Y = Any instead, because it's the least upper bound of two potentially unrelated types.

Good solution here is to generalize more. Return type of reversed function does not have to be one of parameter types, so you can introduce another generic type for that:

def reverseArgs[X ,Y, Z](f: (X, Y) => Z): (Y, X) => Z = {
    (b: Y, a: X) => f(a, b)
}

answered Jul 20, 2017 at 8:51

Oleg Pyzhcov

7,3611 gold badge21 silver badges31 bronze badges

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

Collectives™ on Stack Overflow

Scala pass a generic function into another generic function confusion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related