In other words, Sequence may not provide random access. Conceptually, it may be related to different types of iterators in C++: http://www.cplusplus.com/reference/iterator/

Conceptually, why can programs only access elements of a sequence through specific ops? Which common scenarios might an array work in, but not a scan?

I'm also a little confused as to the benefit of sequences, especially since I can't seem to find much info online about the differences between sequences and other data types like arrays. I'm mostly able to find info on sequential data structures, but this seems to be a bit different (https://en.wikipedia.org/wiki/Sequence_container_(C%2B%2B)#:~:text=In%20computing%2C%20sequence%20containers%20refer,as%20integers%20or%20custom%20classes.)

I will take a stab at trying to to justify this idea of a Sequence. One of the benefits of thinking in terms of sequences as opposed to arrays is that a sequence is a higher level abstraction. We can describe any structure that can be iterated over as a sequence, including arrays, linked lists, binary trees, graphs, and even infinite sets like the natural numbers! If we define our high level functions like map, filter, and fold in terms of a Sequence, then we only need to implement them once, as opposed to having a separate implementation for each data structure. This becomes even more powerful when you consider user-defined data structures because all you need to do is implement the Sequence interface for your new data structure and you gain access to all of these nice functions for free.

Could we think of this as similar to a parent class to ordered containers? All sequences are ordered containers with certain basic methods, so they can be generalized for many different types of variables, as @jonathan describes above, but they can also be extended by more specific container types?

I think another advantage of the Sequence abstraction is that data structures can be implemented in a thread safe manner. For example, a common "insert" function could always be guaranteed to lock and unlock the data structure it's operating on regardless of whether or not it's an array, vector, graph, etc.

Similar to what jonathan mentioned, using these higher level abstractions lets us think about these operations from a functional perspective, which is the basis for functional Church languages like Haskell or OCaml. More generally, if we can encode rules for whether operations or data can be parallelized, like we did for sequences and map, then we can design programming languages that can abstract away a lot of the messy parts of parallelism and make parallelism more accessible.

Is it ever the case that we actually lose performance due to constraining our expressibility like this? The value of creating general structures for abstraction is clear, but surely such rigid partitioning of conceptual pieces can sometimes restrict us?