LanguagePrimitives and Generic Math

Over the past few days I’ve been exploring ways to organize and reuse common functions which repeat across Euler problems.  Something I’ve been focusing on is leveraging F#’s structural typing feature to generalized implementations as much as possible (e.g. implement isPrime once so that it can be reused for int, long and bigint).  The following design has flowed out of this discussion: http://stackoverflow.com/questions/2840714/f-static-member-type-constraints.

The following is an extension of the LanguagePrimitives module which includes a set of functions, types, and values that help us leverage F#’s ability to statically inferred structural type constraints.

namespace Microsoft.FSharp.Core

module LanguagePrimitives =

    let inline zero_of (target:'a) : 'a = LanguagePrimitives.GenericZero<'a>
    let inline one_of (target:'a) : 'a = LanguagePrimitives.GenericOne<'a>
    let inline two_of (target:'a) : 'a = one_of(target) + one_of(target)
    let inline three_of (target:'a) : 'a = two_of(target) + one_of(target)
    let inline negone_of (target:'a) : 'a = zero_of(target) - one_of(target)
    
    let inline any_of (target:'a) (x:int) : 'a = 
        let one:'a = one_of target
        let zero:'a = zero_of target
        let xu = if x > 0 then 1 else -1
        let gu:'a = if x > 0 then one else zero-one

        let rec get i g = 
            if i = x then g
            else get (i+xu) (g+gu)
        get 0 zero 
        
    type G<'a> = {
        negone:'a
        zero:'a
        one:'a
        two:'a
        three:'a
        any: int -> 'a
    }    

    let inline G_of (target:'a) : (G<'a>) = {
        zero = zero_of target
        one = one_of target
        two = two_of target
        three = three_of target
        negone = negone_of target
        any = any_of target
    }

    let gn = G_of 1   //int32
    let gL = G_of 1L  //int64
    let gI = G_of 1I  //bigint
    let gF = G_of 1.0 //float 
    let gM = G_of 1.0M//decimal

And a new module Numerics, together with nested module Generic with the help of our LanguagePrimitives extensions, allows us to implement generic numeric algorithms, and then expose specific (more efficient) partial applications of them.

module Numerics =
    open Microsoft.FSharp.Core.LanguagePrimitives

    module Generic =
        //prime factorization, from greatest to least
        let inline factorize (g:G<'a>) n = 
            let rec factorize n j flist =  
                if n = g.one then flist 
                elif n % j = g.zero then factorize (n/j) j (j::flist) 
                else factorize n (j + g.one) (flist) 
            factorize n g.two []    
        //...

    open Generic

    let inline factorizeG n = factorize (G_of n) n
    let factorizeL = factorize gL
    let factorizeI = factorize gI
    let factorize = factorize gn

    //... 

Here is an example of the kind of types signatures we get using this strategy.

val inline factorizeG :
   ^a ->  ^a list
    when  ^a : (static member get_Zero : ->  ^a) and
          ^a : (static member get_One : ->  ^a) and
          ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( - ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( / ) :  ^a *  ^a ->  ^a) and
          ^a : (static member ( % ) :  ^a *  ^a ->  ^a) and  ^a : equality