Back to Questions
1.2k
views7
comments
Automatic generalization not general enough?
f#

I've run into this problem numerous times now, but it seems really inconvenient writing generic functions to deal with numeric types. For example consider the following implementation of a function to factor integers:

1
2
3
4
5
6
7
8
9
10
11
12
13

let factor n fail_if = 
    let rec factor n factorization = 
        match n with
        | 0 | 1 -> factorization
        | _ -> 
            let p = smallest_prime_factor n
            match factorization with
            | (x,mult)::tl when (x=p) -> factor (n/p) ((x,mult+1)::tl)
            | prev::_  when (fail_if prev) -> []
            | l -> factor (n/p) ((p,1)::l)
        
    factor n []
    |> List.rev

Aside from the calling of function fail_if so that I can terminate the factorization early if some condition is met, this is a pretty boilerplate factorization method. But it works only for ints. It should work with int64s, or unsigned types, etc, but it seems I have to write another function to do that with basically the exact same code. Is there a method I'm missing to deal with this more generically?

.

Without the numeric types implementing a common interface, typeclass support, automatic interface support, or anything else like that, I'm afraid it is not very pretty. (At least, that I know of, and especially if you want full type checking.)

Here is a generic version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

let inline factor (n:^a) fail_if (one:^a) spf = 

    let rec factor n factorization = 

        match n with

        | _ when n = (one - one) || n = one -> factorization

        | _ -> 

            let p = spf n

            match factorization with

            | (x,mult)::tl when (x=p) -> factor (n/p) ((x,mult + one)::tl)

            | prev::_  when (fail_if prev) -> []

            | l -> factor (n/p) ((p,one)::l)

        

    factor n []

    |> List.rev

Which produces the lovely type signature:

1
2
3
4
5
6
7
8
9
10

val inline factor :

   ^a -> ( ^c *  ^a -> bool) ->  ^a -> ( ^a ->  ^c) -> ( ^c *  ^a) list

    when  ^a : (static member ( - ) :  ^a *  ^a ->  ^a) and

          ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and

         ( ^a or  ^c) : (static member ( / ) :  ^a *  ^c ->  ^a)

(The BCL number types don't appear to have static members for Zero or One.)

Alternatively, you could create a type to store the functions you need (add, div, zero, one) and add that to your function. Something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

type 'a NumOps = {

    Zero : 'a

    One : 'a

    Add : 'a -> 'a -> 'a

    Div : 'a -> 'a -> 'a }

let intops = {

    Zero = 0;

    One = 1;

    Add = (+);

    Div = (/); } 

    

let int64ops = {

    Zero = 0L;

    One = 1L;

    Add = (+);

    Div = (/); } 

let spf n ops = n

let factor n fail_if ops = 

    let rec factor n factorization = 

        match n with

        | _ when n = (ops.Zero) || n = ops.One -> factorization

        | _ -> 

            let p = spf n ops

            match factorization with

            | (x,mult)::tl when (x=p) -> factor (ops.Div n p) ((x,ops.Add mult ops.One)::tl)

            | prev::_  when (fail_if prev) -> []

            | l -> factor (ops.Div n p) ((p,ops.One)::l)

        

    factor n []

    |> List.rev

You could hide the ugly implementation and write a nice wrapper on top.

Now, if type extensions could figure into member constraints...

By on 3/5/2009 8:15 PM ()

Actually, the Microsoft.FSharp.Core.LanguagePrimitives module has built-in members GenericZero and GenericOne which work on both primitive types as well as any other types with get_Zero and get_One static methods, respectively. Thus, the following code ought to work:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

open Microsoft.FSharp.Core.LanguagePrimitives
  
let inline factor n fail_if smallest_prime_factor= 
    let one = GenericOne
    let zero = GenericZero
    let rec factor n factorization = 
        match n with
        | _ when n = zero || n = one -> factorization
        | _ -> 
            let p = smallest_prime_factor n
            match factorization with
            | (x,mult)::tl when (x=p) -> factor (n/p) ((x,mult+one)::tl)
            | prev::_  when (fail_if prev) -> []
            | l -> factor (n/p) ((p,one)::l)        
    factor n []
    |> List.rev
By on 3/6/2009 6:43 AM ()

That's awesome, thanks! I have to wonder though, if there's any technical reason why the compiler couldn't be smart enough to know that the only type specific operations you've used (1 and 0) have generic equivalents and to emit IL using the generic equivalents instead, even though technically your sourec code would still contain the numbers 1 and 0.

By on 3/6/2009 10:22 AM ()

If the int literals 0 and 1 were automatically coerced to whatever numeric type, then you run into the whole mess of numeric auto coercion and so on. For instance, 2.5 / 2 -- is that integer or floating division? (Right now it's a compiler error.)

It's definately inconvenient at times, but I feel that having implicit conversions ends up being more trouble than its worth. This is my personal experience dealing with C# and accidentally having things convert incorrectly. Perhaps there's a convenient-yet-unambiguous way to achieve this.

By on 3/6/2009 10:28 AM ()

I tried to apply this to a prime number sequence coded and came up with the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

let rec smallest_prime_factor n = 
    let limit = System.Math.Sqrt(float(n))
    let rec smallest_prime_factor primes = 
        match primes with
        | LazyList.Cons(p,_) when (GenericGreaterThan (float(p)) limit) -> n
        | LazyList.Cons(p,_) when (GenericEquality (n%p) GenericZero) -> p
        | LazyList.Cons(_,tail) -> smallest_prime_factor tail
        | _ -> failwith "Invalid prime sequence!"
    smallest_prime_factor primes
and is_prime n = (GenericEquality (smallest_prime_factor n) n)
and next_prime_after n = 
    let GenericTwo = GenericOne + GenericOne
    let candidate = n+GenericTwo
    if (is_prime candidate) then candidate
    else next_prime_after candidate
and all_primes_after n = 
    let next = next_prime_after n
    LazyList.consf next (fun () -> all_primes_after next)
and primes = 
    let GenericTwo = GenericOne + GenericOne
    let GenericThree = GenericTwo + GenericOne
    LazyList.consf GenericTwo (fun () -> LazyList.consf GenericThree ( fun() -> all_primes_after GenericThree ) )

It still constraints all the types to be of type integer. Is it because of the modulus operator? If so, is there a way to fix it?

By on 3/6/2009 8:39 PM ()

There are two issues: first of all, you need to mark your functions inline because of the type constraints that you need to express. Secondly, you'll get a warning that marking "primes" as 'inline' is deprecated because it's a value; this can be resolved by making it a function taking no arguments instead. With these two considerations in mind, here's what I get (edit: this won't actually work because "let rec inline" has some issues; you won't get any red squiggles in Visual Studio, but attempting to compile will give you an error):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

let rec inline smallest_prime_factor n = 
    let limit = System.Math.Sqrt(float(n))
    let rec smallest_prime_factor primes = 
        match primes with
        | LazyList.Cons(p,_) when (GenericGreaterThan (float(p)) limit) -> n
        | LazyList.Cons(p,_) when (GenericEquality (n%p) GenericZero) -> p
        | LazyList.Cons(_,tail) -> smallest_prime_factor tail
        | _ -> failwith "Invalid prime sequence!"
    smallest_prime_factor (primes())
and inline is_prime n = (GenericEquality (smallest_prime_factor n) n)
and inline next_prime_after n = 
    let GenericTwo = GenericOne + GenericOne
    let candidate = n+GenericTwo
    if (is_prime candidate) then candidate
    else next_prime_after candidate
and inline all_primes_after n = 
    let next = next_prime_after n
    LazyList.consf next (fun () -> all_primes_after next)
and inline primes() = 
    let GenericTwo = GenericOne + GenericOne
    let GenericThree = GenericTwo + GenericOne
    LazyList.consf GenericTwo (fun () -> LazyList.consf GenericThree ( fun() -> all_primes_after GenericThree ) )

If the only function that other code needs to use is the "primes" function, it may make sense to refactor your code so that the primes is defined as a non-recursive inline function, with several local recursive functions (which then would not need to be marked inline). This would give you:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

let inline primes() =
  let rec smallest_prime_factor n = 
    let limit = System.Math.Sqrt(float(n))
    let rec smallest_prime_factor primes = 
        match primes with
        | LazyList.Cons(p,_) when (GenericGreaterThan (float(p)) limit) -> n
        | LazyList.Cons(p,_) when (GenericEquality (n%p) GenericZero) -> p
        | LazyList.Cons(_,tail) -> smallest_prime_factor tail
        | _ -> failwith "Invalid prime sequence!"
    smallest_prime_factor primes
  and is_prime n = (GenericEquality (smallest_prime_factor n) n)
  and next_prime_after n = 
    let GenericTwo = GenericOne + GenericOne
    let candidate = n+GenericTwo
    if (is_prime candidate) then candidate
    else next_prime_after candidate
  and all_primes_after n = 
    let next = next_prime_after n
    LazyList.consf next (fun () -> all_primes_after next)
  and primes = 
    let GenericTwo = GenericOne + GenericOne
    let GenericThree = GenericTwo + GenericOne
    LazyList.consf GenericTwo (fun () -> LazyList.consf GenericThree ( fun() -> all_primes_after GenericThree ) )
  primes

This has the advantage that the inner definition of primes doesn't need to be converted into a function, but can remain a lazy list. (edit: It also has the advantage that it actually works!)

By on 3/9/2009 7:08 AM ()

Well that certainly makes it easier. Thanks for the tip!

By on 3/6/2009 7:06 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper