# What is a list?

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 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?

• One problem with returning a lambda expression that behaves like a list: There's no way to get the length. – James Jun 13 '18 at 22:21
• Sidenote, this question is not restricted to lambda expressions. – JungHwan Min Jun 13 '18 at 22:22
• @DJMcMayhem That's no different from returning an "array" in C, which is really just a pointer to the first item. – user45941 Jun 13 '18 at 22:50
• Pari/GP has a built-in polynomial type. It has a length, can be indexed, and can be easily converted to the built-in list type and vice versa. But it cannot start with 0. Is that a list? – alephalpha Jun 19 '18 at 9:08
• Ideally, the definition should not exclude languages like sed or vim for which the only type is raw text. In such cases, an unambiguous text format, e.g. comma-separated fields, should count as a list. – Ray Jun 25 '18 at 22:13

# 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.
• I feel like the term "operation" is being stretched here for extracting the tail. For example, is list.sublist(1, list.length -1) allowed? list.reverse.pop.reverse? To go a little bit more extreme: mySet.sort().pop_front().toSet() – Nathan Merrill Jun 18 '18 at 18:27
• @NathanMerrill: if you don't have built-in lists, things can get complicated. If you come up with a custom list data type, accessing the tail can be indeed a sequence of several (primitive/built-in) functions. So yes, all your examples are allowed (although toSet sounds like "no duplicates" which list can have). I've used custom lists before, where the tail operation could look like tail l = case l of L(_:t) -> L t; _ -> error "no tail". – nimi Jun 18 '18 at 20:50
• Any integer-taking function would be a list, then no? – Nathan Merrill Jun 18 '18 at 21:13
• @NathanMerrill: yes, but only in languages that support higher-order functions, because the tail operation must return a list, i.e. also a function. And, as said in my 2nd note, all character-taking functions are lists, too. – nimi Jun 18 '18 at 21:35
• You don't necessarily need that: many languages don't have functions on objects. There only need to exist two functions that work as specified, right? – Nathan Merrill Jun 18 '18 at 22:06
• @NathanMerrill: the two functions that need to exist take functions (the lists) as arguments and return (in the case of tail) a function. That makes the two functions higher-order. The list-functions themselves don't have to be higher-order. If you claim that a function in language A is a list, it has to be handled by the two access functions also in language A -> A has to support higher-order functions. – nimi Jun 18 '18 at 22:24
• Oh, I understand what you were saying. Correct :) – Nathan Merrill Jun 19 '18 at 5:56
• One more question: If a question asked for the first N in sequence A### (in list format), does this answer allow an infinite list, as long as the first N are satisfied? Your haskell syntax seems to imply "no", but I want to be clear. – Nathan Merrill Jun 19 '18 at 6:00
• @NathanMerrill: Tricky. I tend to say "No". If a challenge asks for the first n elements, then the answer has to be a finite list. On the other hand and if I'm not mistaken, we accept a sole C pointer to an array as a valid solution. The first n elements are correct, but as C has no boundary checks the very same pointer can also be seen as a pointer to an infinite array (modulo memory size), because you can access elements beyond the intended size. Both should be treated the same way, but I'm not sure whether disallowing sole C pointers is better than allowing infinite list-functions. – nimi Jun 19 '18 at 16:06
• I agree with the header of this answer, but I've downvoted because the body seems to exclude some perfectly valid list implementations. – Peter Taylor Jun 20 '18 at 9:49
• @PeterTaylor: could you give an example of such an implementation? – nimi Jun 20 '18 at 15:21
• A built-in array which doesn't have a slice method. – Peter Taylor Jun 20 '18 at 15:28
• And @NathanMerrill thought that list.sublist(1, list.length -1) was stretching the word "operation"! I certainly don't think it's reasonable to expect everyone to interpret it as covering "It is possible to define a function which ..." – Peter Taylor Jun 20 '18 at 16:29
• @PeterTaylor: oh, I used (or wanted to use) the word "operation" with an abstract meaning. Sorry if I wasn't clear enough. I've edited my post. – nimi Jun 20 '18 at 17:15
• What does "but must be consistent for all lists" mean? That I have to be consistent with the built-in list in my language? If so, that's a terrible requirement. A linked list and an array-list often have different apis to support different use cases – Nathan Merrill Jun 21 '18 at 14:46

# 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)

• If the integer passed in is greater than or equal to startIndex + length, it must error. This definition poses problems to Husk (and probably other golfing langs as well), where indexing never returns an error but wraps around. – Laikoni Jun 15 '18 at 16:58
• @Laikoni that's a good point. I'll add an exception. – Nathan Merrill Jun 15 '18 at 22:39
• I'd like to note that my definition doesn't exclude functions from imitating a list. With Laikoni's suggestion, this is especially true if the sequence is periodic. – Nathan Merrill Jun 15 '18 at 22:45
• Does your answer disqualify infinite lists? I think infinite lists should still count. – cole Jun 16 '18 at 3:57
• Yes it does, because it is impossible to distinguish between infinite lists and functions. (Unless the infinite list is periodic) – Nathan Merrill Jun 16 '18 at 14:14
• I'd love feedback as to why this is being downvoted? Laikoni's comment was a great one, but I already implemented it. – Nathan Merrill Jun 18 '18 at 18:20
• I downvoted because I disagree that lists must be finite. Infinite lists are a powerful feature of many languages (like Haskell), and disallowing them not only cripples certain languages, but makes several challenges impossible or otherwise absurdly difficult. – user45941 Jun 19 '18 at 0:20
• @Mego fair enough. In this regard, however, both ETH's answer and mine are equivalent. – Nathan Merrill Jun 19 '18 at 5:57
• I do not read them as being equivalent, because you make an explicit statement that lists must be finite. ETH's answer makes no such provision. – user45941 Jun 19 '18 at 12:32
• "as long as the "list" does not include unexpected values beyond its expected length" – Nathan Merrill Jun 19 '18 at 14:10
• @NathanMerrill That does still allow the list to be infinite, if the challenge allows or expects it to be so. – ETHproductions Jun 19 '18 at 20:29
• @ETHproductions ah, I understand. Yeah, explicitly allowing infinite lists was definitely an oversight I missed :) – Nathan Merrill Jun 20 '18 at 1:20

## 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.

• Regarding your argument against more freedom with indexing: so long as the indices are successive integral values (or float values with delta 1, for insane languages), I think it should be fine. Where you start isn't all that important - the key is that you can add 1 to an index to get the next index. – user45941 Jun 14 '18 at 4:31
• I don't think #3 is a very good requirement. Why do we care if my custom list performs similarly to the language I'm operating in? I do understand the need for a maximum length, but I'm still thinking how we define it. – Nathan Merrill Jun 15 '18 at 14:32
• @Mego Thanks, I've modified point 2 to match your suggestion. – ETHproductions Jun 15 '18 at 23:56
• @NathanMerrill Yeah, "similarly to built-in lists" was a bad choice of language--I changed my perspective a bit midway through writing the expanded point, without changing the TL;DR version. Revised now. – ETHproductions Jun 15 '18 at 23:57
• @CatWizard The bit about infinite lists made more sense in the original version of the answer, especially now with the mention of wrapping lists. I've removed it now. – ETHproductions Jun 16 '18 at 0:56
• IMO function calling isn't "indexing", it's function calling. I think it's a bit absurd to submit a function for challenges which ask for a list, even if the list asked for is infinite. Functions aren't infinite lists, I don't see why we should label them as such. – Conor O'Brien Jun 17 '18 at 19:18
• @ConorO'Brien it is quite trivial to convert such function to an indexed list by simply iterating through a bunch of indices using some loop. That step is not likely going to add anything interesting to the challenge other than force users to use a loop. – JungHwan Min Jun 17 '18 at 21:25
• One could argue that a list in C does not have an "inherent" length, because there's no reason you have to use the entire area of allocated memory. Unless you would consider f(n){return"foobar"+n;} an invalid submission to "return a list of the characters in foobar without the first n characters." (This isn't just theoretical -- if there's an upper bound to the list's length, malloc(999) could save a lot of bytes.) And this gets even fuzzier in languages like brainfuck. I don't think requirement 3 is necessary. – Doorknob Jun 19 '18 at 17:07
• @Doorknob the length isn't related to the implementation of the list, its related to the challenge. When a challenge specifies that it wants a list of something, the length of that something should be specified as well. – Nathan Merrill Jun 20 '18 at 1:25
• @Doorknob BF doesn't have functions anyway. It can't "return a list", just "print a list", which is (hopefully) more well defined. – user202729 Jun 23 '18 at 15:14