Search code examples
arraysf#slicefoldaccumulator

How to calculate the "sliding sliced" fold of an array of int arrays in F#?


I have a function called calcArr_ArrOfArr in F# with the signature int [] -> int [][] -> int, i.e. calcArr_ArrOfArr takes two arguments, an int array and an array of int arrays, and returns an int.

I want to create the function calcArrOfArr with the signature int [][] -> int, which does the following:

let calcArrOfArr (arrOfArr : int [][]) =
    Array.fold (fun acc e -> acc + (calcArr_ArrOfArr e arrOfArr.[?..])) 0 arrOfArr

where ? would be the index of e + 1.
In other words, in calcArrOfArr I want to apply calcArr_ArrOfArr to every element e of arrOfArr plus the "remaining portion" of arrOfArr, i.e. the slice of arrOfArr starting from after element e. Of course, for the last element of arrOfArr, nothing would be added to the accumulator, nor would an exception be thrown.
Is there a way to create calcArrOfArr in a functional way? An Array.foldi function would come handy...


Solution

  • If you feel you need Array.foldi, write one! The following snippet will extend the built-in Array module with a foldi:

    module Array =
        let foldi f z a = 
            a |> Array.fold (fun (i,a) x -> i+1, f i a x) (0,z) |> snd
    

    Slicing from past-the-end gives you the empty array (i.e., [|0;1|].[2..] = [||]), so now your original suggestion works:

    let calcArrOfArr (arrOfArr : int [][]) = 
        Array.foldi (fun i acc e -> acc + (calcArr_ArrOfArr e arrOfArr.[i+1..])) 0 arrOfArr 
    

    However, the slice arrOfArr.[i+1..] copies the array slice; this might be unfortunate for efficiency.