F-Bounded polymorphism with abstract types in Scala

Question

I have read several articles expressing that abstract types should be used to achieve f-bounded polymorphism in Scala. This is primarily to alleviate type inference issues, but also to remove the quadratic growth that type parameters seem to introduce when defining recursive types.

These are defined as so:

trait EventSourced[E] {
  self =>

  type FBound <: EventSourced[E] { type FBound <: self.FBound }

  def apply(event: E): FBound
}

However, this appears to introduce two issues:

1) Each time a user wants to reference an object of this type, they must also refer to the FBound type parameter. This feels like a code smell:

def mapToSomething[ES <: EventSourced[E], E](eventSourced: ES#FBound): Something[ES, E] = ...

2) The compiler is now unable to infer type parameters for methods such as the above, failing with the message:

Type mismatch, expected: NotInferredES#FBound, actual: MyImpl#FBound

Is anyone out there using a successful implementation of f-bounded polymorphism in their solution, whereby the compiler is still able to infer types?

Wideawake

The Scala collections library uses F-bounded polymorphism successfully without problems. It uses type parameters rather than type members, you may want to try a solution based on that. – Catt

Please can you give me an example to look at, i.e. which parts of the library do this? – Wideawake

See List in the standard library. Note the F-bounded polymorphism used in its inheritance of GenericTraversableTemplate and LinearSeqOptimized. – Catt

Thank you, I will investigate Martin's use of f-bounded polymorphism here and see if the compiler has the same type inference issues that it did when my code was using type parameters :D – Wideawake

Can you tell us what you want this code to do exactly? What is mapToSomething supposed to return? – Catt

This example references the f-bounded trait only in the definition of a subtype (e.g. List). The Scala library never actually references the f-bounded traits directly within a method signature, therefore avoiding the problems associated with the type inferencer. It's interesting, but doesn't provide any solution in my case, as I need to reference the f-bounded type in a method signature. Maybe I need to re-jig my design. – Wideawake

Answer 1

I've since realised that f-bounded polymorphism should be avoided in most cases - or rather - there's usually an alternative design that you should opt for. To understand how to avoid it, we first need to know what makes us require it:

F-bounded polymorphism occurs when a type expects important interface changes to be introduced in derived types.

This is avoided by composing the expected areas of change instead of attempting to support them via inheritance. This actually comes back to Gang of Four design patterns:

Favor 'object composition' over 'class inheritance'

-- (Gang of Four, 1995)

For example:

trait Vehicle[V <: Vehicle[V, W], W] {
    def replaceWheels(wheels: W): V
}

becomes:

trait Vehicle[T, W] {
    val vehicleType: T
    def replaceWheels(wheels: W): Vehicle[T, W]
}

Here, the 'expected change' is the vehicle type (e.g Bike, Car, Lorry). The previous example assumed this would be added through inheritance, requiring an f-bounded type that made inference of W impossible for any function using Vehicle. The new method, which uses composition, does not exhibit this problem.

See: https://github.com/ljwagerfield/scala-type-inference/blob/master/README.md#avoiding-f-bounded-polymorphism

Wideawake

> The new method, which uses composition, does not exhibit this problem Not quite true. If you would like to preserve type-level checks you would need it eventually, like VehicleType[V <: VehicleType] – Cardsharp

Answer 2

See the discussion of F-bounded polymorphism in Twitter's Scala School.

Catt

This example uses type parameters, and therefore causes inference problems. In my example, the types for the following method definition cannot be inferred at the call-site: def doSomething[ES <: EventSourced[ES, E], E](that: ES) – Wideawake

In the examples from Twitter or the Scala library, the F-bound type parameter is on the class itself, not the methods. F-bounded polymorphism lets methods refer to the type of this, the exact type it ends up being in subclasses. Take for example the definition of map in TraversableLike inherited in List, def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That. Repr is the F-Bound type parameter, and is List[A] inside List, but the code in TraversableLike can be written without any knowledge of List. – Catt

Yes, I think ultimately I need to re-think some of my design. It seems to me like f-bounded polymorphism should only be used at type definition level, when inheriting from an f-bounded supertype. However, in my code, there are several instances where it is used at method level... I feel this needs to change. – Wideawake

I followed the link but there is only type parameter implementation and not a single hint about abstract type implementation for f-bound polymorphism – Cardsharp

@Cardsharp Abstract inner types and type parameters are equivalent in Scala. Given that type parameters are more succinct, there is no reason to write an example using abstract types. – Catt

they are not strictly equivalent. They differs when it comes to automatic type inference. And also they differs in how they look in code. I perfectly know how to define F-Bound polymorphism in terms of type parameters, but like the original author curious how that should be done in terms of abstract types. – Cardsharp

Answer 3

I am probably missing something with the following implementation.

trait EventSourced[E] {
  self =>

  type FBound <: EventSourced[E] { type FBound <: self.FBound }

  def apply(event: E): FBound
}

trait Something[ES, E]

def mapToSomething[E](
  eventSourced: ES forSome {
    type ES <: EventSourced[E]
  }): Something[eventSourced.type, E] = ???

class Test extends EventSourced[Boolean] {
  type FBound = Test
  def apply(event:Boolean):FBound = ???
}

val x:Test  = ???

mapToSomething(x)

Barque