n+k patterns in F#?

Question

Hi all,

I wrote the following in F#:

let fib x = 
  match x with
  | 0 -> 0
  | 1 -> 1
  | n+2 -> fib n + fib (n+1)

Unfortunately, I got a compiler error stating I had used an infix operator in an unexpected place. Other than using the wildcard character, is there a way I can express my intent in F#?

Answer 1

I would subtract -2 on both sides. And you have to add the rec keyword, because you are declaring a recursive function.

so you get:

let rec fib x =
    match x with
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n - 2) + fib (n - 1)

Answer 2

F# doesn't support n+k patterns, but you can rewrite it in terms of just n:

let rec fib x =
    match x with
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n - 2) + fib (n - 1)

Note that recursive functions in F# need the rec keyword, unlike in Haskell.

Answer 3

You can get that by definining an active pattern. I'm not exactly sure how n+k patterns work with Haskell (e.g. can they ever fail?), but the following should be a good start:

// Result of matching 'input' against 'add + k'
let (|PlusNum|) add input = 
  input - add

let rec fib = function
  | 0 -> 0 
  | 1 -> 1 
  | PlusNum 2 n -> fib n + fib (n+1)

EDIT: Based on the comment by sepp2k, here is an updated version that fails if "n" would be negative:

// Result of matching 'input' against 'add + k'
let (|PlusNum|_|) add input = 
  if input - add < 0 then None 
  else Some(input - add)