heterogeneous lists through flexible types

Question

I am trying to stick heterogeneous types in a list making use of flexible types

type IFilter<'a> = 
    abstract member Filter: 'a -> 'a

type Cap<'a when 'a: comparison> (cap) = 
    interface IFilter<'a> with
        member this.Filter x = 
            if x < cap
            then x
            else cap

type Floor<'a when 'a: comparison> (floor) = 
     interface IFilter<'a> with
        member this.Filter x = 
            if x > floor
            then x
            else floor

type Calculator<'a, 'b when 'b:> IFilter<'a>> (aFilter: 'b, operation: 'a -> 'a) = 
    member this.Calculate x = 
        let y = x |> operation
        aFilter.Filter y

type TowerControl<'a> () = 
    let mutable calculationStack = List.empty
    member this.addCalculation (x: Calculator<'a, #IFilter<'a>> ) =
        let newList = x::calculationStack
        calculationStack <- newList

let floor10 = Floor<int> 10
let calc1 = Calculator<int, Floor<int>> (floor10, ((+) 10))

let cap10 = Cap 10
let calc2 = Calculator (cap10, ((-) 5))

let tower = TowerControl<int> ()
tower.addCalculation calc1
tower.addCalculation calc2

In the example above

member this.addCalculation (x: Calculator<'a, #IFiler<'a>> ) =  

produces the error

error FS0670: This code is not sufficiently generic. The type variable 'a could not be generalized because it would escape its scope.

Apologies if a similar question has already been posted. Thank you.

Answer 1

There's no easy way to do this. It looks like you really want calculationStack to have type:

(∃('t:>IFilter<'a>).Calculator<'a, 't>) list

but F# doesn't provide existential types. You can use the "double-negation encoding" ∃'t.f<'t> = ∀'x.(∀'t.f<'t>->'x)->'x to come up with the following workaround:

// helper type representing ∀'t.Calculator<'t>->'x
type AnyCalc<'x,'a> = abstract Apply<'t when 't :> IFilter<'a>> : Calculator<'a,'t> -> 'x

// type representing ∃('t:>IFilter<'a>).Calculator<'a, 't>
type ExCalc<'a> = abstract Apply : AnyCalc<'x,'a> -> 'x

// packs a particular Calculator<'a,'t> into an ExCalc<'a>
let pack f = { new ExCalc<'a> with member this.Apply(i) = i.Apply f }

// all packing and unpacking hidden here
type TowerControl<'a> () = 
    let mutable calculationStack = List.empty

    // note: type inferred correctly!
    member this.addCalculation x =
        let newList = (pack x)::calculationStack
        calculationStack <- newList

    // added this to show how to unpack the calculations for application
    member this.SequenceCalculations (v:'a) =
        calculationStack |> List.fold (fun v i -> i.Apply { new AnyCalc<_,_> with member this.Apply c = c.Calculate v }) v

// the remaining code is untouched

let floor10 = Floor<int> 10
let calc1 = Calculator<int, Floor<int>> (floor10, ((+) 10))

let cap10 = Cap 10
let calc2 = Calculator (cap10, ((-) 5))

let tower = TowerControl<int> ()
tower.addCalculation calc1
tower.addCalculation calc2

This has the big advantage that it works without modifying the Calculator<_,_> type, and that the semantics are exactly what you want, but the following disadvantages:

1. It's hard to follow if you're unfamiliar with this way of encoding existentials.

2. Even if you are familiar, there's a lot of ugly boilerplate (the two helper types) since F# doesn't allow anonymous universal qualification either. That is, even given that F# doesn't directly support existential types, it would be much easier to read if you could write something like:

   type ExCalc<'a> = ∀'x.(∀('t:>IFilter<'a>).Calculator<'a,'t>->'x)->'x
   let pack (c:Calculator<'a,'t>) : ExCalc<'a> = fun f -> f c
   
   type TowerControl<'a>() =
       ...
       member this.SequenceCalcualtions (v:'a) =
           calculationStack |> List.fold (fun v i -> i (fun c -> c.Calculate v)) v
   

   But instead we've got to come up with names for both helper types and their single methods. This ends up making the code hard to follow, even for someone already familiar with the general technique.

On the off chance that you own the Calculator<_,_> class, there's a much simpler solution that might work (it may also depend on the signatures of the methods of the real Calcuator<,> class, if it's more complex than what you've presented here): introduce an ICalculator<'a> interface, have Calculator<_,_> implement that, and make calculationStack a list of values of that interface type. This will be much more straightforward and easier for people to understand, but is only possible if you own Calculator<_,_> (or if there's already an existing interface you can piggy back on). You can even make the interface private, so that only your code is aware of its existence. Here's how that would look:

type private ICalculator<'a> = abstract Calculate : 'a -> 'a

type Calculator<'a, 'b when 'b:> IFilter<'a>> (aFilter: 'b, operation: 'a -> 'a) = 
    member this.Calculate x = 
        let y = x |> operation
        aFilter.Filter y
    interface ICalculator<'a> with
        member this.Calculate x = this.Calculate x

type TowerControl<'a> () = 
    let mutable calculationStack = List.empty
    member this.addCalculation (x: Calculator<'a, #IFilter<'a>> ) =
        let newList = (x :> ICalculator<'a>)::calculationStack
        calculationStack <- newList

    member this.SequenceCalculations (v:'a) =
        calculationStack |> List.fold (fun v c -> c.Calculate v) v