Worice - 3 months ago 54

Python Question

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.

Answer

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
```