Is this the definition for a list using cons?

Question

In a paper I see a definition for a list (T is any type you want):

listof T ::= Nil | Cons T (listof T)

I think this says:

List of type T is defined as either Nil or the result of the function cons applied to a list of type T, where cons links the list with another list (the remainder - which could be nil).

Is this an accurate description?

Answer 1

Yes. This is how Lisp lists were constructed.

This is the linked list. Since a Nil or Cons is an object in memory, we thus have an object for every element in the list. That object has - given it is a Cons - two references: one to the element the list holds at that position, and one to the next node in the linked list.

So if you store a list (1,4,2,5), then internally, it is stored as:

+---+---+   +---+---+   +---+---+   +---+---+
| o | o---->| o | o---->| o | o---->| o | o----> Nil
+-|-+---+   +-|-+---+   +-|-+---+   +-|-+---+
  v           v           v           v
  1           4           2           5

Or you can construct it like Cons 1 (Cons 4 (Cons 2 (cons 4 Nil))).

The concept of a Lisp list is quite popular in both functional and logic programming languages.

Working with linked lists usually requires to write different algorithms than working with arrays and arraylists. Obtaining the k-th element will require O(k) time, so usually one aims to prevent that. Therefore one usually iterates through the list and for instance emits certain elements (given these for instance satisfy a given predicate).