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?

I fear not, at least not from the .NET side, since .NET doesn't have a common subtype for all numeric types (it simply cannot, actually, since all value types must derive directly from System.ValueType). That being said, I don't know F#, so it might be that they work around it somehow – but don't keep your hopes too high. — Joey, Jan 19 '11 at 07:21

score 26 · Accepted Answer · edited May 23 '17 at 12:00

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.

Notice the insane inferred type signature of `crossfoot` here using the Numeric Literal technique without adding sufficient type annotations. — Stephen Swensen, Jan 19 '11 at 17:31
Yep, this is when type inference shines. I'm glad we don't have to specify those constraints explicitly. — Daniel, Jan 19 '11 at 17:35
Well, that's not what I'm getting at actually: the inferred signature is way too general here and we can actually tighten it significantly by 1) adding some type annotations, 2) using the technique I developed. See: http://stackoverflow.com/questions/2840714/f-static-member-type-constraints/2840826#2840826 — Stephen Swensen, Jan 19 '11 at 17:41
I don't fully understand the code you linked to (or your technique--but I haven't had much time to look). I'd be glad for you to optimize my code and post an improved answer. — Daniel, Jan 19 '11 at 17:49
@Stephen: It finally clicked. I updated the code (hopefully) according to your suggestions. — Daniel, Jan 19 '11 at 17:58
I love F#, but having to write such code for generic numeric operations will likely turn off some newcomers. — Daniel, Jan 19 '11 at 18:03
@Daniel, indeed! I updated my answer with an overview of the different techniques and the inferred type signatures they yield. I think newcomers may have an easier time stomaching the "Record Type Technique". — Stephen Swensen, Jan 19 '11 at 18:28
I think, I'll mark this one as the answer being a combination of previous versions. Not to forget that is short, readable *and* I can understand it; although I did not fully grasp the thing with `inline` and `^a`, yet. — primfaktor, Jan 21 '11 at 08:07

score 16 · Answer 2 · edited May 23 '17 at 12:01

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)

Wow, thanks for dedicating so much of your time to my newbie question. I'll have to invest a lot more to even understand all this. — primfaktor, Jan 21 '11 at 07:51
Am I correct that `NumericLiteralG.FromInt32(int)` constructs a generic number from its input by means of the [Peano axioms](http://en.wikipedia.org/wiki/Natural_number#Peano_axioms "Wikipedia on Peano axioms")? Isn't that quite slow? — primfaktor, Jan 21 '11 at 08:18
The Peano axioms are too restrictive here, but the concept is close. And yes, it is slow. Though @kvb has a faster implementation at the end of this answer: http://stackoverflow.com/questions/4740857/complete-efficient-numericliteral-module-implementation/4741799#4741799. — Stephen Swensen, Jan 21 '11 at 13:28
We use similar techniques to compile fast FFT code over arrays, vectors, matrices and so on for the F# for Numerics library. — J D, Jan 23 '11 at 19:43

kvb · Answer 3 · 2011-01-19T19:10:06.227

14

Since the question of how to make the type signatures less hairy when using the generalized numeric literals has come up, I thought I'd put in my two cents. The main issue is that F#'s operators can be asymmetric so that you can do stuff like System.DateTime.Now + System.TimeSpan.FromHours(1.0), which means that F#'s type inference adds intermediary type variables whenever arithmetic operations are being performed.

In the case of numerical algorithms, this potential asymmetry isn't typically useful and the resulting explosion in the type signatures is quite ugly (although it generally doesn't affect F#'s ability to apply the functions correctly when given concrete arguments). One potential solution to this problem is to restrict the types of the arithmetic operators within the scope that you care about. For instance, if you define this module:

module SymmetricOps =
  let inline (+) (x:'a) (y:'a) : 'a = x + y
  let inline (-) (x:'a) (y:'a) : 'a = x - y
  let inline (*) (x:'a) (y:'a) : 'a = x * y
  let inline (/) (x:'a) (y:'a) : 'a = x / y
  let inline (%) (x:'a) (y:'a) : 'a = x % y
  ...

then you can just open the SymmetricOps module whenever you want have the operators apply only to two arguments of the same type. So now we can define:

module NumericLiteralG = 
  open SymmetricOps
  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

and

open SymmetricOps
let inline crossfoot x =
  let rec compute n =
      if n = 0G then 0G
      else n % 10G + compute (n / 10G)
  compute x

and the inferred type is the relatively clean

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

while we still get the benefit of a nice, readable definition for crossfoot.

edited Jan 19 '11 at 19:10

answered Jan 19 '11 at 18:57

kvb

54,864
2
91
133

1

This should probably be marked as the answer since it provides straightforward usage (the function reads as you would expect) and the best implementation (type inference is clean). – Daniel Jan 19 '11 at 20:13
@Daniel, I wouldn't go that far ;) There is a notable performance hit using this technique which I find unacceptable. – Stephen Swensen Jan 19 '11 at 20:17
I'm curious to see benchmarks of this versus your technique. It's been so long since I wrote something where sub-seconds mattered that I generally favor readability over performance. – Daniel Jan 19 '11 at 20:21
@Stephen - note that if you're worried about performance, it's not too hard to define a more efficient (but less elegant) `NumericLiteralG.FromInt32` method. – kvb Jan 19 '11 at 20:31
@kvb - Could you perhaps update your answer with such? My imagination is failing me. – Daniel Jan 19 '11 at 20:38
@kvb, yes, that is part of my worry, and I do remember seeing you post a more efficient version somewhere before, but is it so efficient it can really eliminate notable drag? I'm also worried about the implementations of GenericZero/One (line 2304, prim-types.fs) which are statically optimized for the "primitive" numeric types, but use reflection for bigint and bignum (I think), for example. – Stephen Swensen Jan 19 '11 at 20:38
@kvb, regarding GenericZero/One implementation. Are bigint and bignum statically optimized by the `when ^T : ^T = (^T : (static member Zero : ^T) ())` case? When is `GenericOneDynamicImplTable` ever used? By consumers from non-F# code? – Stephen Swensen Jan 19 '11 at 20:51
@kvb - If you want to beef up `FromInt32` for reps, feel free to answer this question: http://stackoverflow.com/questions/4740857/complete-efficient-numericliteral-module-implementation – Daniel Jan 19 '11 at 21:16
1

@Stephen - Yes, uses of GenericZero (and GenericOne) should not result in the use of reflection - the call to `bigint.Zero` should be inlined directly. I'm not 100% sure why the dynamic implementation exists, but it does allow the functions to be called by other languages (or reflectively from F#) - however, note that for some operators (such as `(-)`), there is no dynamic version... – kvb Jan 19 '11 at 23:18

score 2 · Answer 4 · edited Sep 28 '16 at 11:44

I stumbled upon this topic when I was looking for a solution and I am posting my answer, because I found a way to express generic numeral without the less than optimal implementation of building up the number by hand.

open System.Numerics
// optional
open MathNet.Numerics

module NumericLiteralG = 
    type GenericNumber = GenericNumber with
        static member instance (GenericNumber, x:int32, _:int8) = fun () -> int8 x
        static member instance (GenericNumber, x:int32, _:uint8) = fun () -> uint8 x
        static member instance (GenericNumber, x:int32, _:int16) = fun () -> int16 x
        static member instance (GenericNumber, x:int32, _:uint16) = fun () -> uint16 x
        static member instance (GenericNumber, x:int32, _:int32) = fun () -> x
        static member instance (GenericNumber, x:int32, _:uint32) = fun () -> uint32 x
        static member instance (GenericNumber, x:int32, _:int64) = fun () -> int64 x
        static member instance (GenericNumber, x:int32, _:uint64) = fun () -> uint64 x
        static member instance (GenericNumber, x:int32, _:float32) = fun () -> float32 x
        static member instance (GenericNumber, x:int32, _:float) = fun () -> float x
        static member instance (GenericNumber, x:int32, _:bigint) = fun () -> bigint x
        static member instance (GenericNumber, x:int32, _:decimal) = fun () -> decimal x
        static member instance (GenericNumber, x:int32, _:Complex) = fun () -> Complex.op_Implicit x
        static member instance (GenericNumber, x:int64, _:int64) = fun () -> int64 x
        static member instance (GenericNumber, x:int64, _:uint64) = fun () -> uint64 x
        static member instance (GenericNumber, x:int64, _:float32) = fun () -> float32 x
        static member instance (GenericNumber, x:int64, _:float) = fun () -> float x
        static member instance (GenericNumber, x:int64, _:bigint) = fun () -> bigint x
        static member instance (GenericNumber, x:int64, _:decimal) = fun () -> decimal x
        static member instance (GenericNumber, x:int64, _:Complex) = fun () -> Complex.op_Implicit x
        static member instance (GenericNumber, x:string, _:float32) = fun () -> float32 x
        static member instance (GenericNumber, x:string, _:float) = fun () -> float x
        static member instance (GenericNumber, x:string, _:bigint) = fun () -> bigint.Parse x
        static member instance (GenericNumber, x:string, _:decimal) = fun () -> decimal x
        static member instance (GenericNumber, x:string, _:Complex) = fun () -> Complex(float x, 0.0)
        // MathNet.Numerics
        static member instance (GenericNumber, x:int32, _:Complex32) = fun () -> Complex32.op_Implicit x
        static member instance (GenericNumber, x:int32, _:bignum) = fun () -> bignum.FromInt x
        static member instance (GenericNumber, x:int64, _:Complex32) = fun () -> Complex32.op_Implicit x
        static member instance (GenericNumber, x:int64, _:bignum) = fun () -> bignum.FromBigInt (bigint x)
        static member instance (GenericNumber, x:string, _:Complex32) = fun () -> Complex32(float32 x, 0.0f)
        static member instance (GenericNumber, x:string, _:bignum) = fun () -> bignum.FromBigInt (bigint.Parse x)

    let inline genericNumber num = Inline.instance (GenericNumber, num) ()

    let inline FromZero () = LanguagePrimitives.GenericZero
    let inline FromOne () = LanguagePrimitives.GenericOne
    let inline FromInt32 n = genericNumber n
    let inline FromInt64 n = genericNumber n
    let inline FromString n = genericNumber n

this implementation comes by without complicated iteration during the cast. It uses FsControl for the Instance module.

http://www.fssnip.net/mv

cdonlan · Answer 5 · 2012-08-18T23:43:11.973

Is crossfoot exactly what you want to do, or is it just summing the digits of a long number?

because if you just want to sum the digits, then:

let crossfoot (x:'a) = x.ToString().ToCharArray()
                       |> (Array.fold(fun acc x' -> if x' <> '.' 
                                                    then acc + (int x')
                                                    else acc) 0)

... And you are done.

Anyways, Can you convert stuff to a string, drop the decimal point, remember where the decimal point is, interpret it as an int, run crossfoot?

Here is my solution. I am not sure exactly how you want "crossfoot" to work when you have a decimal point added.

For instance, do you want: crossfoot(123.1) = 7 or crossfoot(123.1) = 6.1? (I'm assuming you want the latter)

Anyways, the code does allow you to work with numbers as generics.

let crossfoot (n:'a) = // Completely generic input

    let rec crossfoot' (a:int) =       // Standard integer crossfoot
        if a = 0 then 0 
        else a%10 + crossfoot' (a / 10)

    let nstr = n.ToString()

    let nn   = nstr.Split([|'.'|])    // Assuming your main constraint is float/int

    let n',n_ = if nn.Length > 1 then nn.[0],nn.[1] 
                else nn.[0],"0"

    let n'',n_' = crossfoot'(int n'),crossfoot'(int n_)

    match n_' with
    | 0 -> string n''
    | _ -> (string n'')+"."+(string n_')

If you need to input big integers or int64 stuff, the way crossfoot works, you can just split the big number into bitesize chunks (strings) and feed them into this function, and add them together.

Yes, that's also a possibility. I was just talking about integer crossfoot. But using a string would mean it gets less type safe. I would not want to be able to say `crossfoot "no number"`. I think I like member constraints with `inline` most. — primfaktor, Aug 20 '12 at 07:37

How to write a function for generic numbers?

5 Answers5

UPDATE: Simple Answer

NumericLiteralG Technique

Record Type Technique

Linked

Related