F# Recursive function using match to create a Fibonacci sequence

Question

I have attempted to make a recursive function that utilizes match to create a Fibonacci sequence. I got Euler2 to work, but in Euler2a I'm trying to have the entire function self-contained except for the iteration constraint, j.

How must Euler2a change in order for it to provide the sequence?

Any pointers are most appreciated. :)

The results from Euler2

val Euler2 : list:int list -> i:int -> j:int -> int list

val z : int list = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89]

The results from Euler2a

val Euler2a : j:int -> (int list -> int -> int -> int list)

val z2 : (int list -> int -> int -> int list)

Euler2

let rec Euler2 (list: int list) i j =
    match i with
    | 1 | 2         ->  Euler2 list (i+1) j
    | _ when (i<=j) ->  let newList = list @ [list.[list.Length - 1] + list.[list.Length - 2]]
                        Euler2 newList (i+1) j
    | _             ->  list

let z = Euler2 [1;2] 1 10

Euler2

let rec Euler2a (j:int) =
    let i = 1
    let list = [1;2]
    let rec Euler2b (list: int list) i j =
        match i with
        | 1 | 2         ->  Euler2b list (i+1) j
        | _ when (i<=j) ->  let newList = list @ [list.[list.Length - 1] + list.[list.Length - 2]]
                            Euler2b newList (i+1) j
        | _             ->  list
    Euler2b

let z2 = Euler2a 10

Answer 1

Your Euler2a returns the value Euler2b which is a function that takes a list and 2 integer arguments. You need to actually supply the arguments by changing the line from

Euler2b

to

Euler2b list i j

so that the arguments are supplied to the function. Then everything works.

Answer 2

Besides the immediate problem with format of recursive call to inner function Euler2b from the body of Euler2a that John's answer addresses there are less obvious problems related to the taken approach.

• Your implementation uses F# list as base data structure. Although it allows to solve Project Euler Problem 2, it is used more like an array, than an idiomatic F# list. Expression list @ [list.[list.Length - 1] + list.[list.Length - 2]] is very computationally expensive not only from use of indexers list.[i], but also from append operator @ which completely trashes the current list on each iteration and recreates new, one element longer, creating unnecessary pressure on garbage collection. An idiomatic F# use of list would be growing it from left and reversing on the final step, like below:

  let euler2c len =
      let rec inner (list: int list) i len =
          match list with
          | l::p::tail when (i < len) -> inner ((l + p)::l::p::tail) (i+1) len
          | _  ->  List.rev list
      inner [2;1] 2 len
  

• Having list of Fibonacci numbers of some length is not convenient for solving the original problem as solution should be based on the value of last element, which would likely require extra parameter/condition. Much more idiomatic would be switching from list to F# sequence to lazily represent Fibonacci sequence of any arbitrary length. Using library function Seq.unfold allows for the following succinct one liner implementation of such:

  let fibnums = Seq.unfold (fun(curr,next) -> Some(curr,(next,curr+next)))(1,2)
  

  Now fibnums having type of seq<int> allows to be manipulated idiomatically using library functions and combinators. Particularly, making a sequence with last element not exceeding 4000000 can be expressed as trivial as fibs |> Seq.takeWhile ((>=) 4000000).