 Worice - 3 years ago 167
Python Question

# Co-prime values in F#

I am an F# newbie dealing with a trivial problem. How do I check if two integers are co-prime? I found this pythonic approach really interesting and, IMHO, elegant. I am trying to translate it in F#, without fortune. It is mainly due to my inexperience, I suppose.

In any case, this is my "best" attempt so far:

``````let prime (x, y) =
if y <> 0 then
(x, y) <| (y, x % y)
else
x;;
``````

It should result, i.e., in

``````prime 23 13;;
- : bool = true
``````

Clearly, it does not work. What is the best way to approach such a problem in F#? I come from R programming, that requires a totally different mindform. Sehnsucht

Almost a direct translation of the python code linked.

First we need to define a `gcd` function using recursion as "looping construct" instead of the python while (FP is more "recursion oriented")

``````let rec gcd = function
| x, 0 -> x
| x, y -> gcd (y, x % y)
``````

That just leaves the `coprime` function to define which can be easily done in pointfree style by composing the previous `gcd` function with the partial application of equality with 1

``````let coprime = gcd >> (=) 1
``````

which is functionaly the same as :

``````let coprime (x, y) = gcd (x, y) = 1
``````

Aside from that we can make with a few tweaks the code more general (regarding numeric types) though I'm not sure it's worth it
(as one could prefer to use `BigInteger.GreatestCommonDivisor` when manipulating bigint for example)

``````open LanguagePrimitives

let inline gcd (x, y) =
// we need an helper because inline and rec don't mix well
let rec aux (x, y) =
if y = GenericZero
then x
else aux (y, x % y)
aux (x, y)

// no pointfree style, only function can be inlined not values
let inline coprime (x, y) = gcd (x, y) = GenericOne
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download