In F#, is there a functional way to converting a flat array of items into an array of a group of items?

Question

In F#, imagine we have an array of bytes representing pixel data with three bytes per pixel in RGB order:

[| 255; 0;   0; //Solid red
   0;   255; 0; //Solid green
   0;   0;   255; //Solid blue
   1;   72;  9; 
   34;  15;  155
... |]

I'm having a hard time knowing how to functionally operate on this data as-is, since a single item is really a consecutive block of three elements in the array.

So, I need to first group the triples in the array into something like this:

[| 
   [| 255; 0;   0   |];
   [| 0;   255; 0   |];
   [| 0;   0;   255 |];
   [| 1;   72;  9   |];
   [| 34;  15;  155 |]
... |]

Now, gathering up the triples into sub-arrays is easy enough to do with a for loop, but I'm curious--is there a functional way to gather up groups of array elements in F#? My ultimate goal is not simply to convert the data as illustrated above, but to solve the problem in a more declarative and functional manner. But I have yet to find an example of how to do this without an imperative loop.

Answer 1

kvb's answer may not give you what you want. Seq.windowed returns a sliding window of values, e.g., [1; 2; 3; 4] becomes [[1; 2; 3]; [2; 3; 4]]. It seems like you want it split into contiguous chunks. The following function takes a list and returns a list of triples ('T list -> ('T * 'T * 'T) list).

let toTriples list = 
  let rec aux f = function
    | a :: b :: c :: rest -> aux (fun acc -> f ((a, b, c) :: acc)) rest
    | _ -> f []
  aux id list

Here's the inverse:

let ofTriples triples =
  let rec aux f = function
    | (a, b, c) :: rest -> aux (fun acc -> f (a :: b :: c :: acc)) rest
    | [] -> f []
  aux id triples

EDIT

If you're dealing with huge amounts of data, here's a sequence-based approach with constant memory use (all the options and tuples it creates have a negative impact on GC--see below for a better version):

let (|Next|_|) (e:IEnumerator<_>) =
  if e.MoveNext() then Some e.Current
  else None

let (|Triple|_|) = function
  | Next a & Next b & Next c -> Some (a, b, c) //change to [|a;b;c|] if you like
  | _ -> None

let toSeqTriples (items:seq<_>) =
  use e = items.GetEnumerator()
  let rec loop() =
    seq {
      match e with
      | Triple (a, b, c) -> 
        yield a, b, c
        yield! loop()
      | _ -> ()
    }
  loop()

EDIT 2

ebb's question about memory use prompted me to test and I found toSeqTriples to be slow and cause surprisingly frequent GCs. The following version fixes those issues and is almost 4x faster than the list-based version.

let toSeqTriplesFast (items:seq<_>) =
  use e = items.GetEnumerator()
  let rec loop() =
    seq {
      if e.MoveNext() then
        let a = e.Current
        if e.MoveNext() then 
          let b = e.Current
          if e.MoveNext() then
            let c = e.Current
            yield (a, b, c)
            yield! loop()
    }
  loop()

This has relatively constant memory usage vs a list or array-based approach because a) if you have a seq to start with the entire sequence doesn't have to be slurped into a list/array; and b) it also returns a sequence, making it lazy, and avoiding allocating yet another list/array.

Answer 2

I need to first group the triples in the array into something like this:

If you know they will always be triples then representing then as a tuple int * int * int is more "typeful" than using an array because it conveys the fact that there are only ever exactly three elements.

Other people have described various ways to massage the data but I would actually recommend not bothering (unless there is more to this than you have described). I would opt for a function to destructure your array as-is instead:

let get i = a.[3*i], a.[3*i+1], a.[3*i+2]

If you really want to change the representation then you can now do:

let b = Array.init (a.Length/3) get

The answer really depends upon what you want to do next though...

Answer 3

(Hat tip: Scott Wlaschin) As of F# 4.0, you can use Array.chunkBySize(). It does exactly what you want:

let bs = [| 255;   0;   0; //Solid red
              0; 255;   0; //Solid green
              0;   0; 255; //Solid blue
              1;  72;   9; 
             34;  15; 155 |]
let grouped = bs |> Array.chunkBySize 3
// [| [|255;   0;   0|]
//    [|  0; 255;   0|]
//    [|  0;   0; 255|]
//    [|  1;  72;   9|]
//    [| 34;  15; 155|] |]

The List and Seq modules also have chunkBySize() in F# 4.0. As of this writing, the docs at MSDN don't show chunkBySize() anywhere, but it's there if you're using F# 4.0.

Answer 4

UPDATE: As pointed out by Daniel, this answer is wrong because it creates a sliding window.

You can use the Seq.windowed function from the library. E.g.

let rgbPix = rawValues |> Seq.windowed 3

This returns a sequence rather than an array, so if you need random access, you could follow that with a call to Seq.toArray.

Answer 5

Another approach, that takes and yields arrays directly:

let splitArrays n arr =
    match Array.length arr with
    | 0 ->
        invalidArg "arr" "array is empty"
    | x when x % n <> 0 ->
        invalidArg "arr" "array length is not evenly divisible by n"
    | arrLen ->
        let ret = arrLen / n |> Array.zeroCreate
        let rec loop idx =
            ret.[idx] <- Array.sub arr (idx * n) n
            match idx + 1 with
            | idx' when idx' <> ret.Length -> loop idx'
            | _                            -> ret
        loop 0

Or, yet another:

let splitArray n arr =
    match Array.length arr with
    | 0 ->
        invalidArg "arr" "array is empty"
    | x when x % n <> 0 ->
        invalidArg "arr" "array length is not evenly divisible by n"
    | arrLen ->
        let rec loop idx = seq {
            yield Array.sub arr idx n
            let idx' = idx + n
            if idx' <> arrLen then
                yield! loop idx' }
        loop 0 |> Seq.toArray