F-Bounded Type Polymorphism Considered Tricky

This post is intended to address a question that I seem to see come up every few months on the Scala mailing
list or the #scala IRC channel on freenode. The question is often posed in terms of the phrase
"recursive type" and usually involves someone having some difficulty or other (and many arise) with
a construction like this:

trait Account[T <: Account[T]] {
  def addFunds(amount: BigDecimal): T
}

class BrokerageAccount(total: BigDecimal) extends Account[BrokerageAccount] {
  def addFunds(amount: BigDecimal) = new BrokerageAccount(total + amount)
}

class SavingsAccount(total: BigDecimal) extends Account[SavingsAccount] {
  def addFunds(amount: BigDecimal) = new SavingsAccount(total + amount)
}

This sort of self-referential type constraint is known formally as F-bounded type polymorphism and is usually attempted when someone is
trying to solve a common problem of abstraction in object-oriented languages; how to define a polymorphic
function that, though defined in terms of a supertype, will when passed a value of some subtype will always
return a value of the same subtype as its argument.

It's an interesting construct, but there are some subtleties that can trip up the unwary user, and which make
naive or incautious use of the pattern problematic. The first issue that must be dealt with is how to
properly refer to the abstract supertype, rather than some specific subtype. Let's begin with a simple
example; let's say that we need a function that, given an account, will apply a transaction fee for adding
funds below a certain threshold.

object Account {
  val feePercentage = BigDecimal("0.02")
  val feeThreshold = BigDecimal("10000.00")

  def deposit[T <: Account[T]](amount: BigDecimal, account: T): T = {
    if (amount < feeThreshold) account.addFunds(amount - (amount * feePercentage))
    else account.addFunds(amount)
  }
}

This is straightforward; the type bound is enforced via polymorphism at the call site. You'll notice that the
type ascribed to the "account" argument is T, and not Account[T] - the bound on T gives us all the constraints
that we want. This does what we want it to do when we're talking about working with one account at a time.
But, what if we want instead to perform some action with a collection of accounts of varying types; suppose
we need a method to debit all of a customer's accounts for a maintenance fee? We can expect our type bounds
to hold, but things begin to get a little complicated; we're forced to use bounded existential types.
Here is the correct way to do so:

object Account {
  def debitAll(amount: BigDecimal, accounts: List[T forSome { type T <: Account[T] }]): List[T forSome { type T <: Account[T] }] = {
    accounts map { _.addFunds(-amount) }
  }
}

The important thing to notice here is that the type of individual members of the list are existentially
bounded, rather than the list being existentially bounded as a whole. This is important, because it means
that the type of elements may vary, rather than something like "List[T] forSome { type T <: Account[T] }"
which states that the values of the list are of some consistent subtype of T.

So, this is a bit of an issue, but not a terrible one. The existential types clutter up our codebase and
sometimes give the type inferencer headaches, but it's not intractable. The ability to state these existential
type bounds does, however, showcase one advantage that Scala's existentials have over Java's wildcard types,
which cannot express this same construct accurately.

The most subtle point about F-bounded types that is important to grasp is that the type bound is *not*
as tight as one would ideally want it to be; instead of stating that a subtype must be eventually
parameterized by itself, it simply states that a subtype must be parameterized by some (potentially
other) subtype. Here's an example.

class MalignantAccount extends Account[SavingsAccount] {
  def addFunds(amount: BigDecimal) = new SavingsAccount(-amount)
}

This will compile without error, and presents a bit of a pitfall. Fortunately, the type bounds that we
were required to declare at the use sites will prevent many of the failure scenarios that we might be
concerned about:

object Test {
  def main(argv: Array[String]): Unit = {
    Account.deposit(BigDecimal("10.00"), new MalignantAccount)
  }
}

nuttycom@crash: ~/tmp/scala/f-bounds $ scalac Test.scala
Test.scala:27: error: inferred type arguments [MalignantAccount] do not conform to method deposit's type parameter bounds [T <: Account[T]]
    deposit(BigDecimal("10.00"), new MalignantAccount)
    ^
one error found

but it's a little disconcerting to realize that this level of strictness is *only* available at the use site,
and cannot be readily enforced (except perhaps by implicit type witness trickery, which I've not yet tried)
in the declaration of the supertype, which is what we were really trying to do in the
first place.

Finally, it's important to note that F-bounded type polymorphism in Scala falls on its face when you start
talking about higher-kinded types. Suppose that one desired to state a supertype for Scala's structurally
monadic types (those which can be used in for-comprehensions):

trait Monadic[M[+_] <: ({ type λ[+α] = Monadic[M, α] })#λ, +A] {
  def map[B](f: A => B): M[B]
  def flatMap[B](f: A => M[B]): M[B]
}

This fails to compile outright, complaining about cyclic references in the type constructor M.

In conclusion, my experience has been that F-bounded type polymorphism is tricky to get right and causes typing clutter in the codebase. That isn't to say that it's without value, but I think it's best to consider very carefully whether it is actually necessary to your particular application before you step into the rabbit hole. Most of the time, there's no wonderland at the bottom.

EDIT:

Heiko asks below why not use the following definition of debitAll:

object Account {                                                                                                   
  def debitAll2[T <: Account[T]](amount: BigDecimal, accounts: List[T]): List[T] = {                            
    accounts map { _.addFunds(-amount) }                                                                           
  } 
}

The problem here is that this has a subtly different meaning; this says that for debitAll2, all the members
of the list must be of the *same* subtype of Account. This becomes apparent when we actually try to use the
method with a list where the subtype varies. In both constructions, actually, you end up having to explicitly
ascribe the type of the list, but I've not been able to find a variant for the debitAll2 where the use site
will actually compile with such a variant-membered list.

object Test {
  def main(argv: Array[String]): Unit = {                                                                          
    // compiles, though requires type ascription of the list; this is where the inferencer breaks down. 
    Account.debitAll(BigDecimal("10.00"), List[T forSome { type T <: Account[T] }](new SavingsAccount(BigDecimal("0")), new BrokerageAccount(BigDecimal("0"))))

    // doesn't compile                                                                                             
    // Account.debitAll2(BigDecimal("10.00"), new SavingsAccount(BigDecimal("0")) :: new BrokerageAccount(BigDecimal("0")) :: Nil)
    
    // doesn't compile
    // Account.debitAll2(BigDecimal("10.00"), List[T forSome { type T <: Account[T] }](new SavingsAccount(BigDecimal("0")), new BrokerageAccount(BigDecimal("0"))))
  }                                                                                                                
}