Talk:List (abstract data type)

Changes

Changes I made:

• Lists are not necessary allowed to be of heterogenous type, though the traditional Lisp lists of course are. Lists in Standard ML, for example, must be of a specific type (e.g. int list, or string list).
• The traditional way of implementing lists, originating with Lisp, is using cons cells: each list element has a "car" field containing the value, and a "cdr" field pointing to the next element (or NULL/null/nil/etc. for the last element). This turns into a linked list for non-nested lists, or a tree for nested lists. Lists can be implemented with arrays, but this isn't standard (or common, afaik).

--Delirium 03:47 6 Jul 2003 (UTC)

Cleanup

I removed the October 2005 cleanup tag as there is no discussion here of what needs improvement. Hyacinth 11:20, 10 February 2006 (UTC)

page should be renamed to say "List (Lisp)" not "List (computing)

This is the structure for lists used by the Lisp programming language. Also, while easy to build in RAM, it's not the greatest structure, due to its asymmetry and more (I could argue Lisp speaks lists with a lisp). Other programming languages generally represent & construct lists differently, and often more symmetrically, as via arrays. Even (X)HTML (a very popular part of computing) doesn't use such structures (cons-cells) externally to construct its lists (OL & UL plus the other XML attributes), nor I really doubt uses them internally in any implementation. So rename the title of this page. In its present form, it gives a mis-impression that Computer Science represents Lists this way and THINKS of lists this way, when, more often than not, it doesn't. --MBParker (talk) 01:15, 4 January 2008 (UTC) (MIT CS grad)

I agree that the page should be renamed to just List (data type): what is described is not exactly one abstract data type. I do not agree that this page describes Lisp lists (linked lists) only: those have their own page. Rp (talk) 11:04, 19 March 2012 (UTC)

I agree with List (data type). I recommend that at least python be referenced for its built-in list and list-comprehension as described in [5. Data Structures — Python 3.7.6 documentation](https://docs.python.org/3.7/tutorial/datastructures.html) dating back at least to 1996's version 1.4 [Python Tutorial](https://docs.python.org/release/1.4/tut/). Python's version is described as an ADT. DavidLeasure —Preceding undated comment added 18:50, 24 January 2020 (UTC)

Misleading lead claimng that a string is a tuple

User:Jorge Stolfi, a given string is indeed a tuple. But a string as a variable can have any length, not a fixed one, like tuple does! A list is a string, not a tuple. Pcap ping 12:25, 17 August 2009 (UTC)

A list, string, or uple value has fixed length, as you say. In some programming languages, a tuple (or list) variable can be assigned values of different lengths; Python is an example. In other programming languages, a tuple (or list) variable can only be assigned values of the declared length; Pascal is an example. Therefore that criterion does not distinguish strings from tuples or tuples from lists. Moreover, the concepts of "variable" and "assignment" do not exist in formal language theory. All the best, --Jorge Stolfi (talk) 18:54, 17 August 2009 (UTC)

The confusion you have with tuples is because you do not consider polymorphic lists. I'll expand on this later; (see chapter 29 in B.C. Pierce (2002) Types and Programming Languages, if you're inclined to write the stuff yourself). Insofar I've fixed the article on tuple to explain the difference between an n-tuple in set theory and a (typed) tuple in type theory, i.e. an element of a product type. Clearly a product type is not the same as a polymorphic list type. Pcap ping 00:41, 18 August 2009 (UTC)

Pcap is right. In type theory, lists are defined by an inductive definition such as A^* = μ α. 1 + A × α . So an instance of a list type is indeed isomorphic to a tuple of the form A × ... × A, but the concepts are quite distinct. --Classicalecon (talk) 09:14, 18 August 2009 (UTC)

The point is that lists (or tuples, or any other data structure) are intuitive concepts that can be (and were, and are) defined, used, and studied — in fully rigorous and precise terms — independently of any type theory. Type theory (or theories) may be nice and useful, but they are not the truth: they are attempts to formalize what programmers and compiler writers do. Sometimes a formal theory helps, but sometimes it only makes things harder to understand. Presenting the theoretical definition of a list as if it were the definition, or even a more "correct" defintion, is historically, pedagogically, and practically misleading. All the best, --Jorge Stolfi (talk) 21:47, 18 August 2009 (UTC)

Yes, you can do a lot in untyped lambda calculus, and a Turing machine works on untyped data. It's okay to be pragmatic, and the way the body of this article is structured follows the "concrete to abstract" path, except the lead start with the abstract notion. To fully follow your approach, you'd need to change it to focus on the concrete, which is more inconvenient because there are (several) other articles on concrete implementations of lists. So, you need to abstract away the implementation details at some point for this article to be more than a survey of list implementations.

Just like the word aaa is an element of many formal languages (in particular a*, but also words of length three over any alphabet including a), so a tuple is a an instance of a list type, but also of a product type. But that does not make a product type coincide with the list type, just like aaa being part of many languages does not make those languages coincide. So, it's not okay to identify the ADT list (of which there are at least two typed flavors in widespread use: monomorphic and polymorphic) with the notion of tuple. I've fixed the article in this respect. Pcap ping 22:47, 18 August 2009 (UTC)

Monad section issues

That section needs some integration with the definition above it. To start, the notation needs to be changed. Also, I don't see why you need the stuff besides return and append to give the monad. The rest appears to be superfluous for that purpose. Pcap ping 00:41, 18 August 2009 (UTC)

Original research, and a proposal to clean it up

While I believe most of this article to be true and if necessary verifiable by reliable sources, I have still tagged it as original research, because I think its lede suffers from original synthesis of ideas. Citing parts the lede:

In computer science, a list or sequence is an abstract data type that implements a finite ordered collection of values

Very well. This is the mathematical idea of a string (yes, that's mathematical idea, I've encountered it outside computer science in the context of pure logic), or a finite sequence. However, this could as well be an informal definition of arrays.

Some languages may allow list types to be indexed or sliced like array types, in which case the data type is more accurately described as an array.

True, but then they provide support for very different data types called lists: something prepend-only linked lists, as is common in functional and logic programming. Sometimes, as in Python, for dynamic arrays called "lists" due to historic accident (?).

What I think should be done is that we make a stricter distinction between lists and arrays. A Haskell/Lisp/Prolog list is a list. A Python list is not, but it gets a hatnote. As for "sequence" being a synonym of list, both Lisp and Python programmers will disagree on that one. QVVERTYVS (hm?) 21:08, 30 May 2014 (UTC)

Sorry, but you're splitting hairs over fine lexigraphical usages, not the sense of the meanings. I fail to see where that constitutes a violation of OR. The mission is to impart educational information, not, and especially NOT, in the lede confuse the poor sod who happens by to check a term's general meaning. I haven't seen Lisp in two decades and never wrote in it, nor do I use Python and other such languages as a computer engineer... they don't do a very good job talking to hardware!

If you think something it the lede is in violation of "Do not combine material from multiple sources to reach or imply a conclusion not explicitly stated by any of the sources", then by all means change it. But it seems a stretch to disable the sense of what the class is, to obfuscate the general understanding by being overly picky at sentence construct. Edit it as you can to retain that for the ignorant masses, or perhaps better yet, add a note (see {{notelist}} etc.) that explains the distinction (or claim or vice versa) is not solid and why.

I removed the OR tag as I saw nothing which was controversial or new to me (I first coded in 1976!) and seems plenty solid. I'm simply not going to get drawn into hashing it out over such a fine split hair. If you are an academic and find my understanding to be short of yours... well, I hope so! But is it worth an in-your-face tag that diminishes and makes the wiki look like a bunch of clowns? Not to me. Hang a {{questionable}} or {{citation-needed}} or some such IN-LINE tag on the offending sentences or phrasing would be my approach. I'd have to revisit which are available now, the template coders alway build a better mousetrap and break old tried and true tools. (But one reason I hardly bother to contribute here anymore! It's far too often a hostile environment. Hope my BALDERDASH! didn't make it more so for YOU! It wasn't personal, but all too often some kid comes along and starts tagging everything in sight... you know what I mean?) No way to pass along years of experience and discretion in exercising judgement! Do consider the in-line option. I see the tag is back!

Best regards, FrankB 17:25, 19 August 2014 (UTC)

Re: splitting hairs, check out what I excised from the article: "The items in a list can be sorted for the purpose of fast search (binary search)." This is true for one of the two meanings of "list" that are being conflated, not for the other. So it's not "fine lexigraphical usages", it's the difference between fast code and slow code that we're dealing with here.

(Maybe you're right that a big tag isn't as helpful as a lot of small ones, but I didn't find the time to sort through the article systematically; otherwise I'd probably have fixed it instead.) QVVERTYVS (hm?) 18:11, 19 August 2014 (UTC)

So let's fix it! My intuition is the following: there are roughly two types of things called "lists", indexed sequences which are array-like things; examples of which are the python list, java list, C# list, etc. etc. and the nil/cons pair as found in OCaml, Scala, Lisp, etc. The lazy behavior of the Haskell list currently links to Stream (computing), but I'm not sure if that's ideal either - that lumps things like the standard input stream together with a lazily evaluated sequence, which IMO are quite different beasts - so let's put that one aside for a moment.
These two are quite different beasts, but I wouldn't agree to calling either of these concepts a "real" list - implying that the other is not. The article is problematic in that it claims some things that go for one of these but not for the other as universal, and splitting that up sounds like a good idea. I'm going to make an edit to the first paragraph to try and define the subject matter. Lets see if we can work from there. Martijn Hoekstra (talk) 09:19, 11 November 2014 (UTC)

list vs array

Lists may be many things so the context needs to be explained. Assuming (abstract data type) is what we are discussing.

From experience implementing list objects in various projects. The difference between a list and an array is blurred by the fact that a list may be implemented as an array.

1. Arrays contain a set number of elements of the same type.
2. A list contains some indefinite number of elements, including 0 elements(an empty list), of any type. A list element may be a list.
3. Lists may infact be implemented as an array(under laying structure). In lisp 2 they were dynamic arrays containing pointers to typed objects. That is each element of the array was a pointer to a typed element. In this case the array still contains only like elements. A pointer to an object. The list is it's self an object containing it's size(number of elements) and the array of pointers.

Example of lisp 2 like object in C++ structures. In implementation the pointer points at the data (last field in the object). The data type is contained at a negative (-2 BYTEs offset on a PC) offset from the pointer, hiding the implementation data. A negative type value is a list. Positive values are atomic data elements. LISP 2 indexed list elements.

struct LispTwoObject {

   ...         // data type dependent data. (integer fraction digits, object attribute data)

  short type;  // type>0 atomic element type, type== 0 nil(empty list), type<0 negative list length
  union data {   // An object pointer points here. -size short is type.
    void* elm[]; // list array of pointers
    BYTE  val[]; // numeric object type, integer, floating etc.
    char  str[]; // character object type: character, ASCIIZ string, symbol etc
    char* name;  // types having a string display name
}};

The most defining difference between arrays and lists is that an array contains elements of the same type. A list may contain elements of different types. — Preceding unsigned comment added by Steamerandy (talk • contribs) 19:26, 6 October 2014 (UTC)

In Haskell, lists are of homogeneous type, just like arrays. In Scheme, both lists and arrays ("vectors") are of heterogeneous type. QVVERTYVS (hm?) 21:36, 6 October 2014 (UTC)

Flat list listed at Redirects for discussion

An editor has asked for a discussion to address the redirect Flat list. Please participate in the redirect discussion if you wish to do so. Hildeoc (talk) 19:46, 8 June 2019 (UTC)

Move discussion in progress

There is a move discussion in progress on Talk:Associative array which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 00:32, 27 January 2022 (UTC)