What is a list?

Question

The PPCG community seems to be moving towards more general I/O formats. Then, we could generalize our notion of a "list" so that it is not restricted to the built-in list or array constructs.

For instance, for a challenge asking for a list output, should we be able to write a program that outputs a lambda expression that behaves like a list? That is, the lambda expression would take an index and return the corresponding value, as if it were a list.

It is a "list" in a sense that you can access any element given an index. The "list" wouldn't allow any modification to the elements, but the scope of challenges on PPCG doesn't involve with messing with the outputs after they are returned, as long as the program is reusable.

This is closely related to sequence challenges, some of which give the user an option between "make a program that gives the first n elements" and "make a program that gives the n-th element."

How should we define a list? Built-in lists only? General objects that behave like a list?

Answer 1

A list is a container in which the elements are in order

"In order" means, that there's a first element, which has a successor element, which also has a successor element and so on. If the list is finite, there's a last element without a successor. If the list empty, there isn't even a first element. Every element e together with it's successors is a list of it's own, with e as the first element. It must be possible to define two operations for the container:

• accessing the first element
• extracting the tail (if any). The tail of a list is the (sub-)list where the first element is the successor of the original first element.

Both operations can be arbitrary complex but must be consistent for all lists. Examples for accessing the first element: indexing at [0], using functions like Lisp's car. Examples for extracting the tail of a list l: python: tail=l[1:], pointer to arrays in C: tail=l+1, Lisp: function cdr.

Indexing at i is not an inherent feature of a list (but of an array), but can be trivially achieved by starting at the first element and taking i times the tail and then the head thereof.

Lists can be implemented with functions that map integers i to the ith element, but only if the language supports higher order functions, because when extracting the tail you have to create a new list-function out of the original list-function. Example (using Haskell syntax): l = join(*) is the (infinite) list of all square numbers. l 1 is the first element and tail = (.succ) l is the tail. Both operations (providing 1 as an argument and using (.succ)) are consistent for all list-functions.

List can be implemented via dictionaries with integers as keys. In Perl, %l = (1 => 1, 2 => 4, 3 => 9) is a list of the first three square numbers. The first element is accessed via lookup of key 1 and the tail via removing key 1 and re-mapping all remaining key/value pairs accordingly.

Some notes:

• lists as defined above have basically the same features as singly linked lists
• function/dictionaries don't have to use integers as arguments/keys, any ordered type will do, e.g. characters.
• yes, you can also implement finite lists with functions. The list of the first 4 square numbers is (again, using Haskell syntax): f x|x>0,x<5=x*x|otherwise=undefined
• usually a list requires some method to check for the empty list. For functions you can use a pair (list-function, length) just like C arrays also need a separate length variable or you can introduce a special element nil to mark the end of the list.

Answer 2

Lists are indexed, have a length, and a start index

First, I'd like to mention the length aspect. Lists have a non-negative integer length, even if that length isn't accessible via a function/operator.

The start index doesn't need to be accessible either. It is commonly 0 or 1 but can be any integer.

Now, lists need an indexing operation/function:

1. It must take an integer.
2. If the integer passed in is less than the start index, it must error (see below).
3. If the integer passed in is greater than or equal to startIndex + length, it must error.
4. Otherwise, it must return a value (which should match the value expected by the OP)

Erroring means one of the following:

1. An exception (printing to STDERR or terminating the program)
2. Returning an undefined value (think C). The key here is that you cannot know what the value will be before running the program, and changes each time you run it.
3. Returning an error value. This is a None, false, or any other consistent value. This value returned must be the same no matter the index passed.

Instead of erroring, lists may modulate the index: ((index - startIndex) % length) + startIndex. This effectively means that values wrap around.

(This is largely similar to ETHProduction's answer. I'm simply trying to tighten up the definitions)

Answer 3

If it indexes like a list, it's a list

What I mean by this is, a "list" structure returned from a function could be considered valid if

1. the structure can be "indexed", like what you would expect from any list;
2. "indexing" an item within the length of the "list" gives the correct value; and
3. "indexing" an item outside of the length produces a falsy result.

To expand on these points:

1. This is rather loose; there are several basic options:

   • It can be indexed directly with array access, as in the case of JavaScript's Objects (list = {1:1, 2:3, 3:6, 4:10} can be indexed with list[2]).
   • It can be accessed with a function call (so that list = lambda i:i*(i+1)/2 would be considered an "infinite list" of triangular numbers, indexing like list(2)).
   • It can be accessed via a built-in function or method for accessing such structures (such as the dict.get method in Python: list.get(2)).

2. This is fairly straightforward. Any index within the range of the "list", when accessed as specified above, should give the item that would be expected at that index in a true list structure. This can be 0-indexed, 1-indexed, or more generally n-indexed, where n is the first integer (or float, if you really need it) in a successive group that makes up the indices (suggested by Mego). Basically, the initial index can be any finite real number, but successive indices must each increase by 1 over the previous.

3. This is a little more vague. The default behavior for indexing outside of a list varies from language to language:

   • Python (and many other languages) throw an error.
   • JavaScript gives undefined, indicating no value.
   • In C, this is undefined behavior, meaning behavior may vary from compiler to compiler.
   • Many golfing languages wrap indices, i.e. list[list.length] == list[0].

   I think any of these behaviors is fine, as long as the "list" does not include unexpected values beyond its expected length. I would also allow returning any falsy value (0, False, null, etc.) for any index past the length.

   Note that only valid indices (non-negative integers for 0-indexed, positive integers for 1-indexed, etc.) need to be handled, as these would be the only candidates for indexes in the (theoretical) list.

---

Say the challenge was "given an integer n, output a list of the first n triangular numbers":

f=lambda n:lambda i:i*(i+1)/2 is not a valid entry; while it satisfies points 1 and 2 (after list = f(5), items can be accessed with e.g. list(3)), it does not satisfy point 3, as it keeps giving the correct result for inputs of 5 and beyond.

f=lambda n:lambda i:i<n and(i+1)*i/2, on the other hand, is a valid entry; if n = 5, then returned lambda fails for i ≥ 5, giving False instead of the triangular numbers.

I would not consider the ability to determine length an important element in determining a list, as DJMcMayhem suggested in the comments; as Mego pointed out, this ideology fails in languages like C, where an array consists of just a pointer to the first item and there is no way to get its length. However, the list must inherently have a length to comply with point 3.