Advantages of F-bounded polymorphism over typeclass for return-current-type problem

Question

Returning the current type questions are often asked on StackOverflow. Here is one such example. The usual answers seem to be either F-bounded polymorphism or typeclass pattern solution. Odersky suggests in Is F-bound polymorphism useful?

F-bounds do indeed add significant complexity. I would love to be able to get rid of them, and replace them with higher-kinded subtyping

whilst tpolecat (the author of linked post) suggests

A better strategy is to use a typeclass, which solves the problem neatly and leaves little room for worry. In fact it’s worth considering abandoning subtype polymorphism altogether in these situations.

where the following disadvantage is identified

F-bounded polymorphism parameterizes a type over its own subtypes, which is a weaker constraint than what the user usually wants, which is a way to say “my type”, which you can’t express precisely via subtyping. However typeclasses can express this idea directly, so that’s what I would teach beginners

My question is, in light of the above suggestions, can someone demonstrate a situation where F-bounded polymorphism is favorable, or should we point to typeclass solution as the canonical answer for solving the return-current-type problem?

F-bound polymorphism by type parameter

trait Semigroup[A <: Semigroup[A]] { this: A =>
  def combine(that: A): A
}

final case class Foo(v: Int) extends Semigroup[Foo] {
  override def combine(that: Foo): Foo = Foo(this.v + that.v)
}

final case class Bar(v: String) extends Semigroup[Bar] {
  override def combine(that: Bar): Bar = Bar(this.v concat that.v)
}

def reduce[A <: Semigroup[A]](as: List[A]): A = as.reduce(_ combine _)

reduce(List(Foo(1), Foo(41)))        // res0: Foo = Foo(42)
reduce(List(Bar("Sca"), Bar("la")))  // res1: Bar = Bar(Scala)

F-bounded polymorphism by type member

trait Semigroup {
  type A <: Semigroup
  def combine(that: A): A
}

final case class Foo(v: Int) extends Semigroup {
  override type A = Foo
  override def combine(that: Foo): Foo = Foo(this.v + that.v)
}

final case class Bar(v: String) extends Semigroup {
  override type A = Bar
  override def combine(that: Bar): Bar = Bar(this.v concat that.v)
}

def reduce[B <: Semigroup { type A = B }](as: List[B]) =
  as.reduce(_ combine _)

reduce(List(Foo(1), Foo(41)))        // res0: Foo = Foo(42)
reduce(List(Bar("Sca"), Bar("la")))  // res1: Bar = Bar(Scala)

Typeclass

trait Semigroup[A] {
  def combine(x: A, y: A): A
}

final case class Foo(v: Int)
object Foo {
  implicit final val FooSemigroup: Semigroup[Foo] = 
    new Semigroup[Foo] {
      override def combine(x: Foo, y: Foo): Foo = Foo(x.v + y.v)
    }
}

final case class Bar(v: String)
object Bar {
  implicit final val BarSemigroup: Semigroup[Bar] = 
    new Semigroup[Bar] {
      override def combine(x: Bar, y: Bar): Bar = Bar(x.v concat y.v)
    }
}

def reduce[A](as: List[A])(implicit ev: Semigroup[A]): A = as.reduce(ev.combine)

reduce(List(Foo(1), Foo(41)))        // res0: Foo = Foo(42)
reduce(List(Bar("Sca"), Bar("la")))  // res1: Bar = Bar(Scala)

Answer 1

Yes, F-bounded polymorphysm is different from 'self' member type in the returned type. If you have a type hierarchy and invoke a method returning 'the same type' for some abstract class a :A, in F-bounded polymorphysm the result is A. In bound type member approach, the result is a.Self.

Compare:

   trait Base1[+Self <: FBound[Self]] {
      def copy :Self
   }
   trait Sub1 extends Base1[Sub1]
   class Impl1 extends Sub1 with Base1[Impl1] {
      def copy = this
   }

   trait Base2 {
      type Self <: Base
      copy :Self 
   }
   trait Sub2 extends Base2 { type Self <: Sub2 }
   class Impl2 extends Sub2 {
      type Self = Impl2
      def copy = this
   }

   def copy1[T <: Base1[T]](x :T) = x.self
   def copy2(x :Base2) = x.self
   
   val proto1 = new Impl1 :Sub1
   val proto2 = new Impl2 :Sub2
   val a = copy1(proto1)
   val b = copy2(proto2)

The type of a is Sub1, but the type of b is proto2.Self <: Sub2. This can be an advantage of member types: method copy2 is simpler, and no matter how specific an object you pass in, you'll get a value of the exact same type.

It is however a huge pain when applied recursively:

   class Ev1[T <: Base1[T]] 
   implicit val sub1Ev = new Ev1

   class Ev2[T <: Base2] 
   val sub2Ev = new Ev2

   class Foo
   implicit def foo1[T <: Base1[T]](x :T)(implicit ev :Ev1[T]) = new Foo
   implicit def foo2[T <: Base2](x :T)(implicit ev :Ev2[T]) = new Foo

   foo1(proto1.self) //compiles
   foo2(proto2.self) //does not compile
   def foo[T](x :T)(implicit ev:T => Foo) = ev(x)
  
   foo1(proto1.self) //compiles
   foo2(proto2.self) //does not compile

   foo(proto1.self) //ok
   foo(proto2.self)  //implicit not found

The implicit case is a pain, because now always possibility to specify the type arguments manually. Depending on complexity of the actual case, it is often possible to do some tricks in order to guide the compiler, but it takes quite a bit of experience, time, and method signatures are much more complicated.

Type classes are great in Haskel, or if you work with unrelated type, but the worst when you deal with type hierarchies, as they can only operate on the type they know.If you were to implement some modifications on a T <: Sub1/T <: Sub2 you'd have only implicits for Sub1, which might not return an Impl1. You can't always propagate the need for type classes up until the full type you operate is known, as that could result in dozen implicit parameters to a method, the signature of which would change with implementation.

Answer 2

From my experience

1 Don't use F-Bound type parameters.

2 You do need type classes.

3 Direct inheritance is still a very useful complement to type-classes.

Consider 3 examples that I happen to be familiar with.

Show[T]: producing a string representation from an object / data value.

Unshow[T]: producing an object / data value from a String representation.

Shear[T]: Performing a Shear geometric transformation on an object.

So Unshow[T] is straightforward, we have to use type classes and only type classes. We have no object of type T to work with until we have produced it. Direct inheritance is out. I say direct inheritance, because we may still want to use inheritance within the type class implementations. And we may want to use inheritance within a type class hierarchy, but lets ignore that complication and from now on assume, that is not what I'm referring to when I say inheritance. However note that implementation of algebraic sum types for Unshow[T] is very straightforward. Unshow[T] where T is an algebraic sum type, is essentially a find operation, you traverse the list of subtypes of T until you find one that successfully returns a value of the sub type. For example for UnShow[Option[A]], you try Unshow[Some[A]], if that fails you try Unshow[None]. Although simple to implement, the big limitation is that you must know all the subtypes of T when you create your Unshow[T] instance.

So for Show[T], being just a glorified, or re-envisioned toString method, we don't actually need to narrow the return type of our method or methods. But I wanted to talk about it because its conceptually simple and illustrates the advantages of inheritance. Now you are not going to get very far with Show[T] without the use of a type class, if we want a Show[List[A]], a Show[Array[A]] or a Show[Option[A]], we are going to have use a type class. However inheritance is still vitally useful for the implementation of instances for algebraic sum types. If the Show[T] type class instance for Type[T] delegates to an inherited method, then the instance for type T can be implemented even though all the sub types of T are not known at implementation. And even if all the sub types of the algebraic sum type are known at the time of instance creation, even if type T is effectively sealed, delegating to the inherited method is cleaner in my opinion than using a match statement.

So Shear operations we want to be able to perform a Shear operation on a Shape. And we want the shear operation to give us back a Shape. We do not want to seal our Shape trait, so we need to use inheritance to implement this. Of course we still need a type class if want to Shear a List[shape], an Array[Shape] or an Option[Shape]. so for simplicity let say we have:

trait Shape {
  def xShear(operand: Double): Shape
}

then we can simply narrow the return type even while keeping it abstract

trait Polygon extends Shape {
  override def xShear(operand: Double): Polygon
}

trait Triangle extends Polygon {
  override def xShear(operand: Double): Triangle = { implementation }
}

object Triangle {
  /** This allows us to create Triangles as if it was a class while keeping it a trait. */
  def apply(stuff): Trangle = { blah blah}
  def unapply(inp: Any): [(Pt, Pt, Pt)] = { blah, blah }
}

class EquilateralTriangle(stuff) extends Triangle {
  //Doesn't override xShear as can not fulfil the interface
}

Final suggestions.

If you have multiple method return types that you want to keep in lock step then use a type member not a type parameter. Its said that 3 people fully learned to use F bound type parameters safely. One died, one went mad, the other forgot.

Keep the number of methods in the inherited objects and in the type class instances to a minimum. Put all helper methods that can piggy back off the other instance implemented methods into the extension class for the type class.

Tend to avoid non final classes, if you use a trait with an apply and unapply method in its companion object, you get a lot of the advantages of of a class while avoiding the problems of non final classes.

Answer 3

F-Bounded is a great example of what a type system is capable of express, even simpler ones, like the Java one. But, a typeclass would always be safer and better alternative.

What do we mean with safer? Simply, that we can not break the contract of returning exactly the same type. Which can be done for the two forms of F-Bounded polymorphism (quite easily).

F-bounded polymorphism by type member

This one is pretty easy to break, since we only need to lie about the type member.

trait Pet {
  type P <: Pet
  def name: String 
  def renamed(newName: String): P
}

final case class Dog(name: String) extends Pet {
  override type P = Dog
  override def renamed(newName: String): Dog = Dog(newName)
}

final case class Cat(name: String) extends Pet {
  override type P = Dog // Here we break it.
  override def renamed(newName: String): Dog = Dog(newName)
}

Cat("Luis").renamed(newName = "Mario")
// res: Dog = Dog("Mario")

F-bounded polymorphism by type parameter

This one is a little bit harder to break, since the this: A enforces that the extending class is the same. However, we only need to add an additional layer of inheritance.

trait Pet[P <: Pet[P]] { this: P =>
  def name: String 
  def renamed(newName: String): P
}

class Dog(override val name: String) extends Pet[Dog] {
  override def renamed(newName: String): Dog = new Dog(newName)

  override def toString: String = s"Dog(${name})"
}

class Cat(name: String) extends Dog(name) // Here we break it.

new Cat("Luis").renamed(newName = "Mario")
// res: Dog = Dog(Mario)

Nevertheless, it is clear that the typeclass approach is more complex and has more boilerplate; Also, one can argue that to break F-Bounded, you have to do it intentionally. Thus, if you are OK with the problems of F-Bounded and do not like to deal with the complexity of a typeclass then it is still a valid solution.

Also, we should note that even the typeclass approach can be broken by using things like asInstanceOf or reflection.

---

BTW, it is worth mentioning that if instead of returning a modified copy, you want to modify the current object and return itself to allow chaining of calls (like a traditional Java builder), you can (should) use this.type.

trait Pet {
  def name: String

  def renamed(newName: String): this.type
}

final class Dog(private var _name: String) extends Pet {
  override def name: String = _name

  override def renamed(newName: String): this.type = {
    this._name = newName
    this
  }

  override def toString: String = s"Dog(${name})"
}

val d1 = Dog("Luis")
// d1: Dog = Dog(Luis)

val d2 = d1.renamed(newName = "Mario")
// d2: Dog = Dog(Mario)

d1 eq d2
// true

d1
// d1: Dog = Dog(Mario)

Answer 4

I would suggest that typeclasses are indeed the superior pattern, and any F-bound polymorphic solution to a question of 'return the current type' has an equally good if not better typeclass parallel.

The F-bound polymorphic approach doesn't actually express the 'current type' concept very well, whereas a typeclass can. Typeclasses also make for generally good code under the principle that composition is better than inheritance. This answer offers similar logic, with reference to scala typeclasses in particular.

Note: I'm not an authority; it just seems that this is probably the right answer (as hinted in the question), and needs to be represented.