Talk:List (abstract data type)
|WikiProject Computer science||(Rated Start-class, High-importance)|
|WikiProject Computing / Software||(Rated Start-class, Mid-importance)|
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)
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)
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)
- 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)