Co-prime values in F#

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 1

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

---

From @Henrik Hansen's answer here is an updated version figuring an active pattern to ease readability and extract common behaviour

let (|LT|EQ|GT|) (x, y) =
  if x < y then LT
  elif x = y then EQ
  else GT

let areCoPrimes x y =
  let rec aux (x, y) =
    match x, y with
    | 0, _ | _, 0 -> false
    | LT          -> aux (x, y - x)
    | EQ          -> x = 1
    | GT          -> aux (x - y, y)
  aux (abs x, abs y)