Custom type class

[vstastny]

I have recently seen a little example in Scala how write a generic "library" using type classes (http://danielwestheide.com/blog/2013/02/06/the-neophytes-guide-to-scala-part-12-type-classes.html). It consists of math (including the interface) and statistics module. The approach of course takes an advantage of high order types in Scala. Math module with the default implementations:

object Math {
  trait NumberLike[T] {
    def plus(x: T, y: T): T
    def divide(x: T, y: Int): T
    def minus(x: T, y: T): T
  }
  object NumberLike {
    implicit object NumberLikeDouble extends NumberLike[Double] {
      def plus(x: Double, y: Double): Double = x + y
      def divide(x: Double, y: Int): Double = x / y
      def minus(x: Double, y: Double): Double = x - y
    }
    implicit object NumberLikeInt extends NumberLike[Int] {
      def plus(x: Int, y: Int): Int = x + y
      def divide(x: Int, y: Int): Int = x / y
      def minus(x: Int, y: Int): Int = x - y
    }
  }
}

and the Statistics module:

object Statistics {
  import Math.NumberLike
  def mean[T](xs: Vector[T])(implicit ev: NumberLike[T]): T =
    ev.divide(xs.reduce(ev.plus(_, _)), xs.size)
}

At this point, the mean function is generic enough so that it can be used with int or double.

Trying to simulate this in F# inspiring by FsControl style, I end up writing each method as a type:

module Math =

    type Plus = Plus with
        static member instance (Plus, x:int, _:int) = fun y -> x + y
        static member instance (Plus, x:float, _:float) = fun y -> x + y 
    type Minus = Minus with
        static member instance (Minus, x:int, _:int) = fun y -> x - y
        static member instance (Minus, x:float, _:float) = fun y -> x - y 
    type Divide = Divide with
        static member instance (Divide, x:int, _:int) = fun y -> x / y
        static member instance (Divide, x:float, _:float) = fun y -> x / y
    type Length = Length with
        static member instance (Length, xs: int list, _: int) = fun () -> xs.Length
        static member instance (Length, xs: float list, _:float) = fun () -> xs.Length |> float

    let inline internal plus x y = Inline.instance (Plus, x) y
    let inline internal minus x y = Inline.instance (Minus, x) y
    let inline internal divide x y = Inline.instance (Divide, x) y
    let inline internal length xs = Inline.instance (Length, xs) ()   

And simple example:

open Math
let r1 = plus 12 34
let r2 = plus 12.0 34.0

That works well until you want to use it in the function which shall be generic:

module Statistics =
    let mean (xs : 'a list) =
        let sum = xs |> List.reduce (plus) in divide sum (length xs)

The issue is the restriction of the list element type. The compiler infers the type of the list elements by the first usage of the function, i.e in this case the type is float and using the function with different type will cause compilation error:

open Statistics
let r3 = mean [13.; 23.; 42.; 45.; 61.; 73.; 96.; 100.; 199.; 420.; 900.; 3839.]
//let r4 = mean [13; 23; 42; 45; 61; 73; 96; 100; 199; 420; 900; 3839] // This does not compile

So, I wonder whether this scala example might be written at all in any way using the FsControl style or does it require completely different approach? Thank you.

[gusty]

The function mean must be inline.

There is already a Generic math module in FsControl, see the Numeric examples in Haskell.fsx

[vstastny]

For the whole complexity I missed the essentials:-). Thank you.

[gusty]

True, the rest of your code looks fine. Also note there is a more native way to do that in F# directly, see the function Seq.average but I understand you did it as an excersise and it seems to me you get the idea of how to use the library.

[vstastny]

Exactly, this is only to play with hoping that I can use the mechanism later on to do something useful. To finish the example, I would like to include another type, e.g. Tree like this:

type Tree<'a> =
    | Empty
    | Node of ('a * Tree<'a> * Tree<'a>)

type Tree with
    static member inline instance (_:Plus, x:Tree<'a>, _:Tree<'a>) = fun (_ : Tree<'a>) -> x
    static member inline instance (_:Minus, x:Tree<'a>, _:Tree<'a>) = fun (_ : Tree<'a>) -> x
    static member inline instance (_:Divide, x:Tree<'a>, _:Tree<'a>) = fun (_ : Tree<'a>) -> x
    static member inline instance (_:Length, x:Tree<'a>, _:Tree<'a>) = fun () -> Empty : Tree<'a>

let testTree =
    let one = Node (1, Empty, Empty)
    let six = Node (6, Empty, Empty)
    let three = Node (3, one, six)
    let eight = Node (8, Empty, Empty)
    let ten = Node (10, Empty, Empty)
    let nine = Node (9, eight, ten)
    let five = Node (5, three, nine)
    five

This is not the most clever, but should serve to demonstration only. Now, this works well:

let r5 : Tree<int> = plus (testTree) (Empty)
let r6 : Tree<int> = divide (testTree) (Empty)
let r7 : Tree<int> = divide (testTree) (Empty)

but this does not:

let r8 : Tree<int> = length [testTree; Empty]
let r9 : Tree<int> = mean [testTree; testTree; Empty]

Does it relate to the fact that type T<'a> does not conform to 'a? If so, the only solution can be to provide specific type, e.g. Tree<int> or Tree<float>, resulting in loss of genericity, right?

My last question is whether in principal it is possible to provide implementation also for System types, e.g.

type System.String with
    static member instance (_:Plus, x:string, _:string) = fun y -> x + y
    static member instance (_:Minus, x:string, _:string) = fun y -> y + x
    static member instance (_:Divide, x:string, _:string) = fun (y : string) -> x
    static member instance (_:Length, xs:string list, _:string) = fun () -> List.length xs |> string

let r10 : string = plus ("a") ("b")

One might expect this to work, unfortunately it does not. Thank you for any comment or suggestion.

[gusty]

It is true that sometimes is a problem when you have a single overload of a specific kind and you solve it adding another (dummy if necessary) overload with the same kind, however this is not your case, again your problem is more basic: you don't have a list in your definition of length if you have a look at the way you defined it already, the instance for Tree should be something like

  static member instance (_:Length, x:List<Tree<'a>>, _:Tree<'a>) = fun () -> Empty: Tree<'a>

Now regarding the String instance, have a look at the end of the doc in the readme.md the orphan instance case, that's exactly what happens here, so you can only define it if you include it in the original definition of the Type Methods. As the doc says, if you define it later it will not work as extensions methods are not taken into account in overload resolution and if it was possible it is also a bad practice.

[vstastny]

I see. Again, thank you.