CODEWITHSUNDEEP
syntaxf#
Arran McCabe
Arran McCabe

Reputation: 117

Recursive addition in F# using

I'm trying to implement the following recursive definition for addition in F#

m + 0 := m

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

I can't seem to get the syntax correct, The closest I've come is 

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

Where succ n = n + 1. It throws an error on pattern matching for succ.

Upvotes: 1

Views: 374

Answers (4)

BLUEPIXY
BLUEPIXY

Reputation: 40145

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

Upvotes: 1

svick
svick

Reputation: 244807

As Tomas said, you can't use succ like this without declaring it. What you can do is to create a discriminated union that represents a number:

type Number = 
| Zero
| Succ of Number

And then use that in the plus function:

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

Or you could declare it as the + operator:

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

If you kept y where I have y1, the code would work, because the second y would hide the first one. But I think doing so makes the code confusing.

Upvotes: 2

kongo2002
kongo2002

Reputation: 1024

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

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243051

I'm not sure what succ means in your example, but it is not a pattern defined in the standard F# library. Using just the basic functionality, you'll need to use a pattern that matches any number and then subtract one (and add one in the body):

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

In F# (unlike e.g. in Prolog), you can't use your own functions inside patterns. However, you can define active patterns that specify how to decompose input into various cases. The following takes an integer and returns either Zero (for zero) or Succ y for value y + 1:

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

Then you can write code that is closer to your original version:

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

Upvotes: 3

Related Questions