How to write a function for generic numbers?

Question

I'm quite new to F# and find type inference really is a cool thing. But currently it seems that it also may lead to code duplication, which is not a cool thing. I want to sum the digits of a number like this:

let rec crossfoot n =   if n = 0 then 0   else n % 10 + crossfoot (n / 10)  crossfoot 123 

This correctly prints 6. But now my input number does not fit int 32 bits, so I have to transform it to.

let rec crossfoot n =   if n = 0L then 0L   else n % 10L + crossfoot (n / 10L)  crossfoot 123L 

Then, a BigInteger comes my way and guess what…

Of course, I could only have the bigint version and cast input parameters up and output parameters down as needed. But first I assume using BigInteger over int has some performance penalities. Second let cf = int (crossfoot (bigint 123)) does just not read nice.

Isn't there a generic way to write this?

Answer 1

Building on Brian's and Stephen's answers, here's some complete code:

module NumericLiteralG =      let inline FromZero() = LanguagePrimitives.GenericZero     let inline FromOne() = LanguagePrimitives.GenericOne     let inline FromInt32 (n:int) =         let one : ^a = FromOne()         let zero : ^a = FromZero()         let n_incr = if n > 0 then 1 else -1         let g_incr = if n > 0 then one else (zero - one)         let rec loop i g =              if i = n then g             else loop (i + n_incr) (g + g_incr)         loop 0 zero   let inline crossfoot (n:^a) : ^a =     let (zero:^a) = 0G     let (ten:^a) = 10G     let rec compute (n:^a) =         if n = zero then zero         else ((n % ten):^a) + compute (n / ten)     compute n  crossfoot 123 crossfoot 123I crossfoot 123L 

UPDATE: Simple Answer

Here's a standalone implementation, without the NumericLiteralG module, and a slightly less restrictive inferred type:

let inline crossfoot (n:^a) : ^a =     let zero:^a = LanguagePrimitives.GenericZero     let ten:^a = (Seq.init 10 (fun _ -> LanguagePrimitives.GenericOne)) |> Seq.sum     let rec compute (n:^a) =         if n = zero then zero         else ((n % ten):^a) + compute (n / ten)     compute n 

Explanation

There are effectively two types of generics in F#: 1) run-type polymorphism, via .NET interfaces/inheritance, and 2) compile time generics. Compile-time generics are needed to accommodate things like generic numerical operations and something like duck-typing (explicit member constraints). These features are integral to F# but unsupported in .NET, so therefore have to be handled by F# at compile time.

The caret (^) is used to differentiate statically resolved (compile-time) type parameters from ordinary ones (which use an apostrophe). In short, 'a is handled at run-time, ^a at compile-time–which is why the function must be marked inline.

I had never tried to write something like this before. It turned out clumsier than I expected. The biggest hurdle I see to writing generic numeric code in F# is: creating an instance of a generic number other than zero or one. See the implementation of FromInt32 in this answer to see what I mean. GenericZero and GenericOne are built-in, and they're implemented using techniques that aren't available in user code. In this function, since we only needed a small number (10), I created a sequence of 10 GenericOnes and summed them.

I can't explain as well why all the type annotations are needed, except to say that it appears each time the compiler encounters an operation on a generic type it seems to think it's dealing with a new type. So it ends up inferring some bizarre type with duplicated resitrictions (e.g. it may require (+) multiple times). Adding the type annotations lets it know we're dealing with the same type throughout. The code works fine without them, but adding them simplifies the inferred signature.

Answer 2

In addition to kvb's technique using Numeric Literals (Brian's link), I've had a lot of success using a different technique which can yield better inferred structural type signatures and may also be used to create precomputed type-specific functions for better performance as well as control over supported numeric types (since you will often want to support all integral types, but not rational types, for example): F# Static Member Type Constraints.

Following up on the discussion Daniel and I have been having about the inferred type signatures yielded by the different techniques, here is an overview:

NumericLiteralG Technique

module NumericLiteralG =      let inline FromZero() = LanguagePrimitives.GenericZero     let inline FromOne() = LanguagePrimitives.GenericOne     let inline FromInt32 (n:int) =         let one = FromOne()         let zero = FromZero()         let n_incr = if n > 0 then 1 else -1         let g_incr = if n > 0 then one else (zero - one)         let rec loop i g =              if i = n then g             else loop (i + n_incr) (g + g_incr)         loop 0 zero  

Crossfoot without adding any type annotations:

let inline crossfoot1 n =     let rec compute n =         if n = 0G then 0G         else n % 10G + compute (n / 10G)     compute n  val inline crossfoot1 :    ^a ->  ^e     when ( ^a or  ^b) : (static member ( % ) :  ^a *  ^b ->  ^d) and           ^a : (static member get_Zero : ->  ^a) and          ( ^a or  ^f) : (static member ( / ) :  ^a *  ^f ->  ^a) and           ^a : equality and  ^b : (static member get_Zero : ->  ^b) and          ( ^b or  ^c) : (static member ( - ) :  ^b *  ^c ->  ^c) and          ( ^b or  ^c) : (static member ( + ) :  ^b *  ^c ->  ^b) and           ^c : (static member get_One : ->  ^c) and          ( ^d or  ^e) : (static member ( + ) :  ^d *  ^e ->  ^e) and           ^e : (static member get_Zero : ->  ^e) and           ^f : (static member get_Zero : ->  ^f) and          ( ^f or  ^g) : (static member ( - ) :  ^f *  ^g ->  ^g) and          ( ^f or  ^g) : (static member ( + ) :  ^f *  ^g ->  ^f) and           ^g : (static member get_One : ->  ^g) 

Crossfoot adding some type annotations:

let inline crossfoot2 (n:^a) : ^a =     let (zero:^a) = 0G     let (ten:^a) = 10G     let rec compute (n:^a) =         if n = zero then zero         else ((n % ten):^a) + compute (n / ten)     compute n  val inline crossfoot2 :    ^a ->  ^a     when  ^a : (static member get_Zero : ->  ^a) and          ( ^a or  ^a0) : (static member ( - ) :  ^a *  ^a0 ->  ^a0) and          ( ^a or  ^a0) : (static member ( + ) :  ^a *  ^a0 ->  ^a) and           ^a : equality and  ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and           ^a : (static member ( % ) :  ^a *  ^a ->  ^a) and           ^a : (static member ( / ) :  ^a *  ^a ->  ^a) and           ^a0 : (static member get_One : ->  ^a0) 

Record Type Technique

module LP =     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     }  open LP 

Crossfoot, no annotations required for nice inferred signature:

let inline crossfoot3 n =     let g = G_of n     let ten = g.any 10     let rec compute n =         if n = g.zero then g.zero         else n % ten + compute (n / ten)     compute n  val inline crossfoot3 :    ^a ->  ^a     when  ^a : (static member ( % ) :  ^a *  ^a ->  ^b) and          ( ^b or  ^a) : (static member ( + ) :  ^b *  ^a ->  ^a) and           ^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 : equality and           ^a : (static member ( / ) :  ^a *  ^a ->  ^a) 

Crossfoot, no annotations, accepts precomputed instances of G:

let inline crossfootG g ten n =     let rec compute n =         if n = g.zero then g.zero         else n % ten + compute (n / ten)     compute n  val inline crossfootG :   G< ^a> ->  ^b ->  ^a ->  ^a     when ( ^a or  ^b) : (static member ( % ) :  ^a *  ^b ->  ^c) and          ( ^c or  ^a) : (static member ( + ) :  ^c *  ^a ->  ^a) and          ( ^a or  ^b) : (static member ( / ) :  ^a *  ^b ->  ^a) and           ^a : equality 

I use the above in practice since then I can make precomputed type specific versions which don't suffer from the performance cost of Generic LanguagePrimitives:

let gn = G_of 1  //int32 let gL = G_of 1L //int64 let gI = G_of 1I //bigint  let gD = G_of 1.0  //double let gS = G_of 1.0f //single let gM = G_of 1.0m //decimal  let crossfootn = crossfootG gn (gn.any 10) let crossfootL = crossfootG gL (gL.any 10) let crossfootI = crossfootG gI (gI.any 10) let crossfootD = crossfootG gD (gD.any 10) let crossfootS = crossfootG gS (gS.any 10) let crossfootM = crossfootG gM (gM.any 10)