cumulative sum using array.fold in F#

Question

I have an array of the following type

let myarray = [| 1 .. 5 |]

I would like to get another array where each element is a cumulative sum of elements that come before it:

let mycumarray = [| 1 3 6.. 15 |]

What I tried to do is:

let sumArray array = Array.fold (fun acc elem -> acc + elem) 0.0 array
let mycumarray = sumArray myarray

However it does not work. Does anybody have any suggestions to obtain a cumulative sum?

Answer 1

I think you're looking for Array.scan, which is very similar to Array.fold, but returns all the state values instead of just the final one:

(Array.scan (+) 0 myArray).[1..]

The .[1..] is array slicer notation (see the MSDN on arrays in F#) to drop the first element, which is necessary because scan includes the initial state in the output.

Answer 2

Array.scan is surely the best solution but you can use your fold if you want like this:

let cumList xs = 
    List.ofSeq xs 
    |> List.fold (fun (acc, ys) elem -> 
                      let acc' = acc + elem 
                      in (acc', ys @ [acc'])) 
       (0, []) 
    |> snd 
    |> List.toArray

here is your example:

> cumList [|1..5|];;                                                                                                                               
val it : int [] = [|1; 3; 6; 10; 15|]

Note that the @ is not optimal but it shows nicely what is done (if performance is important you can use List.foldBack or do :: in there and a final List.rev to get the right ordering.

Also you could use Array.append directly instead of @

making the example generic on numbers:

let inline cumList xs = 
    List.ofSeq xs 
    |> List.fold (fun (acc, ys) elem -> 
                      let acc' = acc + elem 
                      in (acc', ys @ [acc'])) 
       (LanguagePrimitives.GenericZero, []) 
    |> snd 
    |> List.toArray

you see you just have to make the function inline and use GenericZero instead of 0 (which is assumed to be an int)

btw: this works too with the Array.scan approach:

let inline cumList2 xs =
    Array.scan (+) LanguagePrimitives.GenericOne xs

remark the array-slice is unnecessary in this case if you just start with 1 instead of 0!