A good way to look back arbitrary number of items in the Array.Fold in F#

Question

In the folder function of the Array.Fold operation, i want to look back arbitrary number of items.

The only way i can figure out is like this.

let aFolder (dataArray, curIdx, result) (dataItem) =
      let N = numItemsToLookBack(result, dataItem) 
      let recentNitems =  dataArray.[curIdx - N .. curIdx - 1]
      let result = aCalc(result, dataItem, recentNitems )

      dataArray, curIdx + 1, result

myDataArray |> Array.fold aFolder (myDataArray, 0, initResult)

As you can see, I passed the whole dataArray and index to the folder function to get the "recentNitems". But this way allows the folder function to access not only preceding data, but also the following data.

Is there a way to prevent this looking forward thing? Or, is there a better (more functional or more efficient) way regardless of this looking forward problem?

Answer 1

If numItermToLookBack is fixed, then you could use Seq.windowed:

let arr = [|1;2;3;4;5;6;7;|]
let warr = arr |> Seq.windowed 3 |> Seq.toArray

and you get:

val warr : int [] array =
  [|[|1; 2; 3|]; [|2; 3; 4|]; [|3; 4; 5|]; [|4; 5; 6|]; [|5; 6; 7|]|]

If the number is not fixed, I don't know a way to do it more easily than yours.

BTW, in your code

  let recentNitems =  dataArray.[curIdx - n .. curIdx - 1]

and also in my method, a new small array is created every time, which might hurt performance a little.

Answer 2

If you need to look back at arbitrary number of elements, then using Array.fold directly maybe isn't the best option as the function is designed for scenarios where you can process elements one by one.

There is nothing wrong with using direct access to arrays in F# - as long as you don't mutate them, you're still writing functional code (so maybe recursion + direct access using indices would work in your scenario).

As Yin Zhu points out, you could generate array of portions of array (using Seq.windowed), but creating a O(n) number of small arrays may be quite an overhead. Here is a more sophisticated trick you could also use:

I see you need to call the aCalc function with only the relevant part of the array as an argument. You could create a simple wrapper for the array that provides access only to the relevant part of the array like this:

type ArraySlice<'a>(arr:'a[], from, max) = 
  member x.Item
    with get(index) =
      let index = index + from
      if index > max || index < from then failwith "out of range"
      arr.[index]

As far as I understand your code, you need to generate the number of lookback items based on the result, so you'll probably need to write this using single fold, which could be done roughly like this:

// If you write this using lambdas or local 'let' binding, the 
// 'dataArray' value will be in scope, so you don't need to keep it as
// part of the state...
(dataArray, (0, initResult)) ||> Array.fold (fun (i, result) item -> 
   let n = numItemsToLookBack (result, item)  
   let recent =  new ArraySlice<_>(dataArray, max 0 (i - n), i - 1)
   // Note: modify aCalc, so that it takes 'ArraySlice'
   let result = aCalc(result, item, recent) 
   i + 1, result)