Functional iteration F #: performance and preferred functional style

Question

I get an excellent book "Functional Programming of the Real World" by Tomasz Petricek and John Skeet (two SO gurus, by the way, thanks to both of them). The following function on page 277 presents a method for calculating a three-point average value in an array, taking into account lateral values ​​as special ones:

let blurArray (arr:float[]) = let res = Array.create arr.Length 0.0 res.[0] <- (arr.[0] + arr.[1]) / 2.0 res.[arr.Length-1] <- (arr.[arr.Length - 2] + arr.[arr.Length -1 ] )/2.0 for i in 1 .. arr.Length - 2 do res.[i] <- (arr.[i-1] + arr.[i] + arr.[i+1]) / 3.0 res 

I understand that this function is unchanged for the outside world, even if it internally accepts mutation and purpose. In addition, although it is really necessary, he can compose and accept me, while maintaining a declarative style. Without difficulty, I tried to come up with a functional solution, as an exercise, in order to get to know better the functions of a higher order, etc. I will communicate my decision, and then I will send my questions. First I define a helper function

 let computeElementsAverage (myArray:float[]) myIndex (myElement:float) = match myIndex with | 0 -> (myArray.[0..1] |> Array.average ) | lastInd when lastInd = (myArray.Length -1 ) -> (myArray.[lastInd-1..lastInd] |> Array.average ) | anIndex -> (myArray.[anIndex -1 .. anIndex + 1 ] |> Array.average ) 

(I could abstract away (indeces → float list), which is a template in match clauses, but I thought it was superfluous).

Then the blurArray equivalent becomes:

 let blurArray' (arr:float[]) = let mappingFcn = arr |> computeElementsAverage arr |> (Array.mapi mappingFcn) 

Finally, my questions are:

First of all, what will be the most recommended functional way? I especially dislike the fact that I am forced to declare a finite element of type element (float) in computeElementsAverage due to the requirements of Array.mapi. Are there any better methods for doing this, avoiding an argument that won't be used?

Secondly: in terms of performance, my code is much slower, as expected; but it works 1/10 faster than the source code; any other solution that will still rely on high-order functions without getting such a big hit on performance?

Finally, what is the general preferred way to perform calculations on a data structure (for example: arrays), which depends on several multiple indices? The way I came up with, as you can see, uses the mapi scan function and uses a closure that contains the structure itself; What is your preferred method?

PS: (the original version of blurArray uses int [] as input, I just changed it to float [] to use List.average in my version)

Answer 1

I think a good and more functional alternative would be to use Array.init . This function allows you to create an array by specifying the function that is used to calculate the element for each location.

This is still very similar to the source code, but now it does not need any explicit mutation (it is now hidden in Array.init ). In fact, I would probably use this in a revised version of the book :-).

 let blurArray (arr:float[]) = Array.init arr.Length (fun i -> if i = 0 then (arr.[0] + arr.[1]) / 2.0 elif i = arr.Length - 1 then (arr.[arr.Length - 2] + arr.[arr.Length - 1] )/2.0 else (arr.[i-1] + arr.[i] + arr.[i+1]) / 3.0 ) 

Then you can decide that there are more functions that you want to write, where you do something with the neighborhood of each point in the array - and you can specify the size of the neighborhood. You could write something like:

 let fillArray offset f (arr:float[]) = Array.init arr.Length (fun i -> f arr.[max 0 (i-offset) .. min (arr.Length-1) (i+offset)]) 

Here the function f is called with a submatrix of neighbors of each point with no more offset neighbors left and right (this does not go beyond the scope thanks to max and min checks). Now you can write a blur like:

 arr |> fillArray 1 Seq.average 

In fillArray creating a sub-array would be a bit inefficient - you could do it faster with ArraySegment or by copying the corresponding parts of the array to a local mutable array. But it looks very nice and functional!