CODEWITHSUNDEEP
f#
user2233088
user2233088

Reputation: 1

F# arrays and match pattern

I'm trying yo learn F# and arrays with recursion. I have solved summarizing an array with recursion now I'm trying to do the same thing except this time with match pattern but I can't get it to work help.

let myArray = Array.create 5 0

myArray.[0] <- 0
myArray.[1] <- 1
myArray.[2] <- 2
myArray.[3] <- 3
myArray.[4] <- 4

let rec sum (arr : int array) counter =
    if counter = 0 then 0
    else arr.[counter] + sum arr (counter - 1)

////////////////////////////////////////////////
// Can't get this to work.

let rec sum1 (arr : int array) counter =
    match arr with
    | [||] -> printfn "0"
    | arr -> arr.[counter] + sum arr (counter - 1)

Upvotes: 0

Views: 3606

Answers (1)

Gene Belitski
Gene Belitski

Reputation: 10350

The problem with your implementation is that you expect immutable arr somehow changing from call to call to sum1. It does not change, so your implementation for anything, but empty array will be throwing System.IndexOutOfRangeExceptionwhen counter gets negative!

Continue sticking to manipulation with the index:

let rec sum1 (arr : int array) counter =
    match counter with
    | 0 -> 0
    | _ -> arr.[counter - 1] + sum1 arr (counter - 1)

And sum1 myarray (myarray.Length) returns 10 as expected.

This implementation is not perfect as well as your first one sum with if-then-else. To understand why just try running it with something like let myarray = Array.init 100000 id - it will likely throw System.Stackoverflow exception. Cause of exception - it is not tail-recursive.

Making it tail-recursive is not difficult - just add an accumulator sum that fully unties subsequent calls stack-wise:

let rec sum1TR sum counter (arr: int[]) =
    match counter with
    | 0 -> sum
    | _ -> sum1TR (sum + arr.[counter - 1]) (counter - 1) arr

Now sum1TR 0 1000000 (Array.init 1000000 id) works even for an array of a million items.

Finally, as you want to get a sum of array's elements it make sense to expose to end user only single parameter - the array per se, moving recursive summator inside the external function:

let sum (as: int[]) =
    let rec summator s l =
        match l with
        | 0 -> s
        | _ -> summator (s + as.[l - 1]) (l - 1)
    summator 0 as.Length

Upvotes: 4

Related Questions