The difference between lists and sequences

Question

I'm trying to understand the difference between sequences and lists.

In F# there is a clear distinction between the two. However in C# I have seen programmers refer to IEnumerable collections as a sequence. Is what makes IEnumerable a sequence the fact that it returns an object to iterate through the collection?

Perhaps the real distinction is purely found in functional languages?

Answer 1

Not really - you tend to have random access to a list, as well as being able to get its count quickly etc. Admittedly linked lists don't have the random access nature... but then they don't implement IList<T>. There's a grey area between the facilities provided by a particular platform and the general concepts.

Sequences (as represented by IEnumerable<T>) are read-only, forward-only, one item at a time, and potentially infinite. Of course any one implementation of a sequence may also be a list (e.g. List<T>) but when you're treating it as a sequence, you can basically iterate over it (repeatedly) and that's it.

Answer 2

I think that the confusion may arise from the fact that collections like List<T> implement the interface IEnumerable<T>. If you have a subtype relationship in general (e.g. supertype Shape with two subtypes Rectangle and Circle), you can interpret the relation as an "is-a" hierarchy.

This means that it is perfectly fine to say that "Circle is a Shape" and similarly, people would say that "List<T> is an IEnumerable<T>" that is, "list is a sequence". This makes some sense, because a list is a special type of a sequence. In general, sequences can be also lazily generated and infinite (and these types cannot also be lists). An example of a (perfectly valid) sequence that cannot be generated by a list would look like this:

// C# version                           // F# version
IEnumerable<int> Numbers() {            let rec loop n = seq {
  int i = 0;                               yield n
  while (true) yield return i++;           yield! loop(n + 1) }
}                                       let numbers = loop(0)

This would be also true for F#, because F# list type also implements IEnumerable<T>, but functional programming doesn't put that strong emphasis on object oriented point of view (and implicit conversions that enable the "is a" interpretation are used less frequently in F#).

Answer 3

Sequence content is calculated on demand so you can implement for example infinite sequence without affecting your memory. So in C# you can write a sequence, for example

IEnumerable<int> Null() {
  yield return 0;
}

It will return infinite sequence of zeros. You can write

int[] array = Null().Take(10).ToArray()

And it will take 10*4 bytes of memory despite sequence is infinite. So as you see, C# does have distinction between sequence and collection