How do you call the following recursive lists of lists. Only “nested lists” is a name which comes to my mind. I want to give a better name for these favorite data structure of mine.
[],
[a, b]
[[a, b], [[b,c], d, []]
These nested lists are handy for delete/insert operations, compared with those on the standard flattened lists.
Note that lists including the empty list [] are not considered to be a member of the flattened list, which matches the policy of SWI-prolog that [] is not an atom.
I might have tried to look for what doesn’t exist. Now I think I should use “list” including nested list. I was pulled strongly by analogy to parens (…) for associativjity of ‘comma’ for goals that ((a,b),c) is equivalent to '(a, (b, c))`, while bracket […] not the case.
S-expression of Lisp is internally represented as a binary tree with binary cells as nodes with a car-link and a cdr-one for two successor nodes. Is this not the answer to your question.
EDIT
Prolog term, for example, t(r(e), e) as a tree is written in a lisp S-expression '(t (r e) e), (list (quote t) (list (quote r) (quote e) ) (quote e)),
and so on, I believe.
I was making a bad joke - Lisp cons-cells are the equivalent of Prolog [A|B], which can be used to construct trees, but it’s rather tedious. (I’m ignoring DEFSTRUCT, which is somewhat similar to Prolog’s record/1)
Anyway, a list in Prolog can contain anything in its nodes, including other lists, so “list” seems to be sufficient – or (if you’re talking to people with a Python background) “nested list”.
I have to agree. I just wanted to have name which puts emphasis on that they are intermediate structure which are finally flattened ones as output, like
(1 + 2) + 3 = (1 + (2 + 3)) for 6 in associative arithmetic.
BTW, I have little knowledge with other programming language like Python. I know only query 1 + 2 for Python returns 3, though for Python I daily keep it updated via homebrew
because of dependencies unknown to me. I am not joking on this. But I will check later on “nested list” of Python.
Python’s “list” allows appending (front or back), indexing, and decomposition (e.g., you can write x,*y=[1,2,3], which assigns 1 to x and [2,3] to y). Because it allows indexing, in many ways, this “list” is more similar to a vector in C++ than to a Prolog or Lisp list. The Python list can contain any values, so [1,[2,3]] is allowed (and [1,[2,3]][1][0]==2). But people often say things like “list of int” for homogenous lists; “list of lists” is rather limited (it allows [[1,2],[3,4]] but doesn’t allow [1,[2,3]]), so “nested list” emphasizes that the elements may be lists but can be something else, and “nested list” also emphasizes that the elements aren’t all the same type.
For the pedantic, a Python list is a container that has pointers (or references) to the elements; this is a rich source of beginner errors because list contents are mutable and therefore passing a list to a function allows modifying the list’s contents:
>>> def foo(a_list):
... a_list[0] = 'xyz'
...
>>> x = [1,2,3]
>>> x
[1, 2, 3]
>>> foo(x)
>>> x
['xyz', 2, 3]
Thank you for striking lecture for me on Python’s list. To me, Python seems more serious
on list processing than Prolog/Lisp. I must learn Python.
So far I am against Python for a personal and silly reason that it took easy way of use of the period ‘.’ in Prolog from me. I might be making a bad joking. I have to change my narrow attitude. In fact, it may be the case that I must respect Python.
As Richard O’Keefe has demonstrated, Prolog’s (and Lisp’s) simpler lists can be just as expressive and efficient, and also much easier to reason about (e.g., using RB-trees instead of mutable arrays).
I have very mixed feelings about Python - it’s nice for beginners but has its own set of complexities. (I was on the Python support team at Google for 5 years.)
If you have questions about Python, send me a message off-list.
The recently added Prolog-Python interface opens up some interesting possibilities, using Python as a “glue layer”; I think that this avoids many of Python’s surprises.
