Recursively iterating over an array in F#

问题:

This is a rather simple request, but I am having trouble with F#'s syntax. I need to create a function to iterate over a bidimensional array recursively, increasing a counter every time a condition is met. In this case, the function takes an ID as a parameter, then checks to see how many times that ID is present inside the inner arrays. I was thinking of something like this:

let runner array count =  
    match count with  
    |0 -> (exit loop)  
    |n -> (perform function)  
        runner array count-1

For the general structure of the recursive iteration function. However, there are several thing I'm not sure about. What are the conditions for exiting the recursive loop (ie, the base case) in F#? How do I structure this so it traverses both the main and sub-arrays to check for the ID? And how do I make it so that the counter increases with each run of the recursive loops, assuming I can't use mutable functions? Any help would be appreciated.

回答1:

There is a more generic way to do it. You want to fold over a 2d array. They don't have a fold defined in the Array2D module, but you can write one.

let fold f state (arr: 'a [,]) =
    Seq.cast<'a> arr
    |> Seq.fold f state

We "cheat" a little here, cast gives us a flat sequence of elements from the array, which we later pass to a regular fold. So now you can do:

 array |> fold (fun counter e -> if cond e then counter+1 else counter) 0

where cond is the condition you want to check.

回答2:

I find 2D arrays a bit awkward in F#, but here's how you could do it:

let recursivelyCountID ID (matr : 'T[,]) =
    let rec dim1 acc index0 index1 =
        if index1 > matr.GetUpperBound 1 then
            acc
        else
            let newAcc = if matr.[index0, index1] = ID then acc+1 else acc
            dim1 newAcc index0 (index1+1)

    let rec dim0 acc index0 =
        if index0 > matr.GetUpperBound 0
        then acc
        else dim0 (acc + (dim1 0 index0 0)) (index0+1)

    dim0 (matr.GetLowerBound 0) (matr.GetLowerBound 1)

If you would use an array of arrays instead, you could use the functions in F#'s standard Array module:

let IDsInInnerArray ID xs = xs |> Array.sumBy (fun i -> if i = ID then 1 else 0)
let totalIDs ID xss = xss |> Array.map (fun xs -> IDsInInnerArray ID xs) |> Array.sum

Edit: I embarrassed myself by missing the fact that 2D arrays implement IEnumerable, so instead of the previous code working with arrays of arrays, a straight forward function for 2D arrays would be:

let totalIDs ID (matr : 'T[,]) = 
    matr 
    |> Seq.cast<'T> 
    |> Seq.sumBy (fun i -> if i = ID then 1 else 0)

...using the Seq.cast function as scrwtp shows in his answer.

回答3:

It is a bit clunky:

 let count (x : 'a [,]) (e : 'a) =
    seq { for x in arr do yield x :?> 'a } |> Seq.where ((=) e) |> Seq.length

Arrays implement GetEnumerator so this should work for Array3D and 4D as well.