F# 中的递归加法使用

Question

我正在尝试在 F#

m + 0 := m

m + (n + 1) := (m + n) + 1

中实现以下加法的递归定义我似乎无法获得正确的语法，最接近的我've come is

let rec plus x y =                        
 match y with                     
 | 0 -> x;                        
 | succ(y) -> succ( plus(x y) );

其中 succ n = n + 1。它会在 succ 的模式匹配上引发错误。

Answer 1

我不确定 succ 在您的示例中意味着什么，但它不是标准 F# 库中定义的模式。仅使用基本功能，您需要使用匹配任何数字的模式，然后减一（并在主体中加一）：

let rec plus x y =                         
 match y with                      
 | 0 -> x                     
 | y -> 1 + (plus x (y - 1))

在 F# 中（与 Prolog 等不同），您不能在模式中使用自己的函数。但是，您可以定义活动模式来指定如何将输入分解为各种情况。下面的代码接受一个整数，并返回 Zero（零）或 Succ y 值 y + 1：

let (|Zero|Succ|) n = 
  if n < 0 then failwith "Unexpected!"
  if n = 0 then Zero else Succ(n - 1)

然后您可以编写以下代码 ：更接近您的原始版本：

let rec plus x y =
  match y with
  | Zero -> x
  | Succ y -> 1 + (plus x y)

Answer 2

正如 Tomas 所说，如果不声明它，就不能像这样使用 succ 。您可以做的是创建一个代表数字的可区分联合：

type Number = 
| Zero
| Succ of Number

然后在 plus 函数中使用它：

let rec plus x y =
 match y with
 | Zero -> x
 | Succ(y1) -> Succ (plus x y1)

或者您可以将其声明为 + 运算符：

let rec (+) x y =
 match y with
 | Zero -> x
 | Succ(y1) -> Succ (x + y1)

如果您将 y 保留在我的 y1 位置，该代码可以工作，因为第二个 y 会隐藏第一个。但我认为这样做会使代码变得混乱。

Answer 3

type N = Zero | Succ of N

let rec NtoInt n =
  match n with
  | Zero -> 0
  | Succ x -> 1 + NtoInt x

let rec plus x y =
  match x with
  | Zero -> y
  | Succ n -> Succ (plus n y)

演示：

> plus (Succ (Succ Zero)) Zero |> NtoInt ;;
val it : int = 2
> plus (Succ (Succ Zero)) (Succ Zero) |> NtoInt ;;
val it : int = 3

Answer 4

let rec plus x y =
    match y with
    | 0 -> x
    | _ -> plus (x+1) (y-1)