Monday, February 28, 2011

Generic number functions in F#

I’ve been learning f# recently, it is a very powerful and elegant language and hopefully we will be using it for real development in the future. One of the first things I tried was writing a version of the classic Fizz-Buzz interview question (for integers from 1 to 100 print Fizz-Buzz if divisible by 15, Fizz if divisible by 3 and Buzz if divisible by 5).

In an effort to massively overcomplicate a trivial question I ended up defining a set of rules that could be applied to arbitrary inputs. The definition of a rule was:

  1. //a rule evaluates something to true of false
  2. type Rule<'a> = 'a -> bool

I then set about implementing the mod 3 and mod 5 rules and hit a problem. Ideally we should be able to apply our rules to any integer type, but because of the well known problem of .Net lacking an INumeric/IIntegral interface or equivalent this wasn’t possible and I ended up with separate rules for each integer type:

  1. let inline ModThreeInt() = fun n -> n % 3 = 0
  2. let inline ModThreeLong() = fun n -> n % 3L = 0L
  3. let inline ModThreeBigInt() = fun n -> n % 3I = 0I

Not very satisfactory! I really wanted a generic ModThree function that can be applied to any number that supports the mod operator. In fact we can get this behaviour using some Peano style arithmetic:

  1. let inline Mod (d : 'a) (n : 'b)
  2. = let inline zero x = x - x
  3. let inline one x = x / x
  4. let mutable cb = zero n
  5. for _ in [one d..d] do
  6. cb <- cb + (one n)
  7. n % cb = zero n

(Note we must make the function inline so it is not given a concrete type signature on first use)

The key here is are the generic zero and one functions defined in the first two lines. These give a one and a zero of type of the value they are called with. With these defined we can then increment a variable of type ‘b until it is equal to the value passed in of type ‘a. Then we can mod our value of type ‘b. Of course this is hopelessly inefficient if we are modding by a large number.

  1. //yay, we can call either of our mod functions with either a BigInt or an int
  2. //and they take either bigints or ints, no explicit casting
  3. let inline ModThree() = Mod 3
  4. let inline ModFive() = ModG 5I

After writing this I actually discovered that F# has some built in GenericOne and GenericZero functions so we could rewrite our generic mod function as:

  1. let inline ModG (d : 'a) (n : 'b)
  2. = let mutable c = GenericZero<'b>
  3. for i in [GenericOne<'a>..d] do
  4. c <- c + GenericOne<'b>
  5. n % c = GenericZero<'b>

So there we have it, a small part of a hideously overcomplicated and inefficient FizzBuzz solution, interesting though.

  1. let inline buzzFuzzRules _ =
  2. [ (Some BuzzFuzz, ModThree() &&& ModFive());
  3. (Some Buzz, ModThree());
  4. (Some Fuzz, ModFive());
  5. (None, Default)
  6. ]

No comments:

Post a Comment