Why does F#'s Seq.windowed return seq of array

Question

Seq.windowed in F# returns a sequence where each window within is an array. Is there a reason why each window is returned as an array (a very concrete type) as opposed to say, another sequence or IList<'T>? An IList<'T>, for example, would be sufficient if the purpose was to communicate that the items of the window can be randomly accessed but an array says two things: elements are mutable and randomly accessible. If you can rationalise the choice of array, how is windowed different from Seq.groupBy? Why does that latter (or operators in the same vein) not also return the members of a group as an array?

I'm wondering if this is simply a design oversight or is there a deeper, contractual reason for an array?

Answer 1

I do not know what is the design principle behind this. I suppose it might just be an accidental aspect of the implementation - Seq.windowed can be quite easily implemented by storing items in arrays, while Seq.groupBy probably needs to use some more complicated structure.

In general, I think that F# APIs either use 'T[] if using array is the natural efficient implementation, or return seq<'T> when the data source may be infinite, lazy, or when the implementation would have to convert the data to an array explicitly (then this can be left to the caller).

For Seq.windowed, I think that array makes a good sense, because you know the length of the array and so you are likely to use indexing. For example, assuming that prices is a sequence of date-price tuples (seq<DateTime * float>) you can write:

prices
|> Seq.windowed 5
|> Seq.map (fun win -> fst (win.[2]), Seq.averageBy snd win)

The sample calculates floating average and uses indexing to get the date in the middle.

In summary, I do not really have a good explanation for the design rationale, but I'm quite happy with the choices made - they seem to work really well with the usual use cases for the functions.

Answer 2

A couple of thoughts.

First, know that in their current version, both Seq.windowed and Seq.groupBy use non-lazy collections in their implementation. windowed uses arrays and returns you arrays. groupBy builds up a Dictionary<'tkey, ResizeArray<'tvalue>>, but keeps that a secret and returns the group values back as a seq instead of ResizeArray.

Returning ResizeArrays from groupBy wouldn't fit with anything else, so that obviously needs to be hidden. The other alternative is to give back the ToArray() of the data. This would require another copy of the data to be created, which is a downside. And there isn't really much upside, since you don't know ahead of time how big your group will be anyways, so you aren't expecting to do random access or any of the other special stuff arrays enable. So simply wrapping in a seq seems like a good option.

For windowed, it's a different story. You want an array back in this case. Why? Because you already know how big that array is going to be, so you can safely do random access or, better yet, pattern matching. That's a big upside. The downside remains, though - the data needs to be re-copied into a newly-allocated array for every window.

seq{1 .. 100} |> Seq.windowed 3 |> Seq.map (fun [|x; _; y|] -> x + y)

There is still the open question - "but couldn't we avoid the array allocation/copy downside by internally only using true lazy seqs, and returning them as such? Isn't that more in the 'spirit of the seq'?" It would be kind of tricky (would need some fancy cloning of enumerators?), but sure, probably with some careful coding. There's a huge downside to this, though. You'd need to cache the entire unspooled seq in memory to make it work, which kind of negates the whole goal of doing things lazily. Unlike lists or arrays, enumerating a seq multiple times is not guaranteed to yield the same results (e.g. a seq that returns random numbers), so the backing data for these seq windows you are returning needs to be cached somewhere. When that window is eventually accessed, you can't just tap in and re-enumerate through the original source seq - you might get back different data, or the seq might end at a different place. This points to the other upside of using arrays in Seq.windowed - only windowSize elements need to be kept in memory at once.