Рекурсивное добавление в F # с использованием

Question

Я пытаюсь реализовать следующее рекурсивное определение для добавления в F #

м + 0: = м

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

Кажется, я не могу понять правильный синтаксис. Самое близкое, что я получил, это

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 # (в отличие, например, от Пролога) вы не можете использовать свои собственные функции внутри шаблонов. Однако вы можете определить активных шаблонов , которые определяют, как разбить входные данные на различные случаи. Следующее принимает целое число и возвращает либо 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

Как сказал Томас, вы не можете использовать 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)

DEMO:

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