Using F#'s static type parameters and encoding numeric constants

Question

I'm writing a library¹ in F# that provides some bitwise operations, and I want to make sure as many of my functions as possible are inline let bindings with static type parameters (this allows me to write one function and use it for int16, int32, and maybe even bignum with little overhead). This route will certainly fail to work at some point. Some of the functionality provided by said library is somewhat complicated.

¹Note: I'm aware of the issues of exposing inline let bindings via a public interface.

However, I want to stretch this to the furthest extent it can go. Right now, I'm trying to write the population count algorithm in this form, and I'm facing a problem. I'm not sure how to encode the masks, e.g. 0x3333..., that appear in these algorithms. I can get around shift constants and similar using some extra bit trickery.

Is there any trick I can use, whether via F#'s type inference and static type parameters, or via bit-twiddling, to write the algorithm the way I want? Is there any way I can encode these sorts of constants in the statically generic function?

A more vague question: are there some specific things I can rely on to utilize static type parameters to their fullest, especially in the context of numerics? For example, I heavily use GenericOne and GenericZero. Are there more things like this, that I might have missed?

Answer 1

First, you can use numeric literals to avoid ugly uses of GenericOne and GenericZero. Here is a brief example:

module NumericLiteralG = begin
  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 
end

// Usage
let inline ten() = 10G
ten() + 1
ten() + 2L

Second, F# doesn't seem to support generic hexa numeric literals. One trick is to use double backticks so that you have indicative names:

let inline shift x = 
    let ``0x33333333G`` = 858993459G
    ((x >>> 2) &&& ``0x33333333G``) + (x &&& ``0x33333333G``)

// Usage
shift 20
shift 20L
shift 20uy

There are a few nice questions on SO about numeric literals. I give some references in case you go that route:

• F# Static Member Type Constraints
• Complete, efficient NumericLiteral module implementation
• How to write a function for generic numbers?