F#中的共同素数值

Question

我是一个处理琐碎问题的F#新手.如何检查两个整数是否是共同素数？我发现这种pythonic方法非常有趣,恕我直言,优雅.我试图用F#翻译它,没有财富.我想这主要是因为我缺乏经验.

无论如何,这是迄今为止我的"最佳"尝试:

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

它应该结果,即在

prime 23 13;;
- : bool = true

显然,它不起作用.在F#中解决这个问题的最佳方法是什么？我来自R编程,需要完全不同的心态.

Answer 1

几乎直接翻译了python代码链接.

首先,我们需要gcd使用递归定义一个函数作为"循环构造"而不是python而(FP更"面向递归")

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

这就是通过将前一个函数与1的部分应用程序组合在一起coprime来定义哪个函数可以轻松地以无点样式完成gcd

let coprime = gcd >> (=) 1

功能与以下相同:

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

除此之外,我们可以通过一些调整使代码更通用(关于数字类型),虽然我不确定它是否值得
(BigInteger.GreatestCommonDivisor例如,当操作bigint时可能更喜欢使用)

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

来自@Henrik Hansen这里的答案是一个更新版本,用于确定活动模式以简化可读性并提取常见行为

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)

Answer 2

仅适用于该运动:这是使用欧几里得算法的减法版本的版本.不像Sehnsuchts那样优雅地使用分裂风格,并且可能没那么高效:

let rec areCoPrimes a b =
    match a, b with
    | a, b when a < 0 -> areCoPrimes -a b
    | a, b when b < 0 -> areCoPrimes a -b
    | 0, b  -> false
    | a, 0 -> false
    | a, b when a = b -> a = 1
    | a, b when a > b -> areCoPrimes (a - b) b
    | a, b when a < b -> areCoPrimes a (b - a)

欧几里德肉是最后三个匹配,而前四个匹配小于或等于零的值.