4 ms·

A Python list is an ArrayList/vector, not a linked list. CL lists are linked lists of cons cells.

samatman 3y ago
Correct. There's no such thing as a python a-list, or p-list, and they can't share structure. There's overlap between programming in Python with lists, and programming in Lisp with lists, but not as much as it appears. In idiomatic Lisp, it's rather common to search a list for a value, cdr it, and cons that cdr to the collection you're building up. Python has nothing like that, because what I said makes no sense in terms of Python lists.
- o11c 3y ago
  What do a-list/p-list have to do with sharing structure? If you want shared structure of lists in Python, use `itertools.chain`. If you want key-value mappings, use a dict. Order is preserved by default nowadays, and conversion to/from an iterable of 2-tuples is trivial.
  - thaumasiotes 3y ago
    > If you want shared structure of lists in Python, use `itertools.chain`. That would involve zero shared structure. itertools.chain is just an iterator that iterates one iterable and then, instead of declaring that it's done, goes on to iterate another one. Shared structure between lists means that two lists refer to some of the same regions of memory.
    - o11c 3y ago
      And multiple `itertools.chain` instances pointing to the same list chunk(s) also use sharing.
      - thaumasiotes 3y ago
        OK, that is true, but that approach would have the significant downside that you can't pass over a list more than once.
- d0mine 3y ago
  Iterators can be shared in Python e.g., here's a well-known grouper recipe (traverse `it` iterator in chunks of `N` items each): zip(*[it]*N) Example: >>> L = [1, 2, 3, 4] >>> *zip(*[iter(L)]*2), ((1, 2), (3, 4)) Here's the single result of the iter() call is shared. The purpose is to show that iterator can be shared in principle (ignore other aspects of the code).
hajile 3y ago
Does the CL spec require the implementation to use linked lists or merely to behave as if it were a linked list? I believe it is the latter and that makes a world of difference when it comes to optimization. A great mainstream example of this are JavaScript Arrays. They are defined to behave as hashtables. They inherit from Object. Their "indices" are actually strings instead of numbers (all object keys are strings and numbers get converted to strings before the lookup happens). Despite that spec model, JS arrays have used a very different representation in practice for decades. Even in the dark ages, arrays were implemented as linked lists. Today, they might be hashtables, linked lists, boxed objects, or even unboxed primitives all while still pretending to be hashtables. Cons doesn't have to return a linked list element.
- gmfawcett 3y ago
  > Does the CL spec require the implementation to use linked lists or merely to behave as if it were a linked list? "list: a chain of conses in which the car of each cons is an element of the list, and the cdr of each cons is either the next link in the chain or a terminating atom." -- https://www.lispworks.com/documentation/HyperSpec/Body/26_glo_l.htm#list https://www.lispworks.com/documentation/HyperSpec/Body/26_gl... Interpret that as you will. But what "world of difference" optimizations are you suggesting here? Give an example of a significant optimization at the implementation level that preserves cons semantics.

Correct. There's no such thing as a python a-list, or p-list, and they can't share structure. There's overlap between programming in Python with lists, and programming in Lisp with lists, but not as much as it appears. In idiomatic Lisp, it's rather common to search a list for a value, cdr it, and cons that cdr to the collection you're building up. Python has nothing like that, because what I said makes no sense in terms of Python lists.

o11c 3y ago
What do a-list/p-list have to do with sharing structure? If you want shared structure of lists in Python, use `itertools.chain`. If you want key-value mappings, use a dict. Order is preserved by default nowadays, and conversion to/from an iterable of 2-tuples is trivial.
- thaumasiotes 3y ago
  > If you want shared structure of lists in Python, use `itertools.chain`. That would involve zero shared structure. itertools.chain is just an iterator that iterates one iterable and then, instead of declaring that it's done, goes on to iterate another one. Shared structure between lists means that two lists refer to some of the same regions of memory.
  - o11c 3y ago
    And multiple `itertools.chain` instances pointing to the same list chunk(s) also use sharing.
    - thaumasiotes 3y ago
      OK, that is true, but that approach would have the significant downside that you can't pass over a list more than once.
d0mine 3y ago
Iterators can be shared in Python e.g., here's a well-known grouper recipe (traverse `it` iterator in chunks of `N` items each): zip(*[it]*N) Example: >>> L = [1, 2, 3, 4] >>> *zip(*[iter(L)]*2), ((1, 2), (3, 4)) Here's the single result of the iter() call is shared. The purpose is to show that iterator can be shared in principle (ignore other aspects of the code).

hajile 3y ago

Does the CL spec require the implementation to use linked lists or merely to behave as if it were a linked list? I believe it is the latter and that makes a world of difference when it comes to optimization. A great mainstream example of this are JavaScript Arrays. They are defined to behave as hashtables. They inherit from Object. Their "indices" are actually strings instead of numbers (all object keys are strings and numbers get converted to strings before the lookup happens). Despite that spec model, JS arrays have used a very different representation in practice for decades. Even in the dark ages, arrays were implemented as linked lists. Today, they might be hashtables, linked lists, boxed objects, or even unboxed primitives all while still pretending to be hashtables. Cons doesn't have to return a linked list element.

gmfawcett 3y ago
> Does the CL spec require the implementation to use linked lists or merely to behave as if it were a linked list? "list: a chain of conses in which the car of each cons is an element of the list, and the cdr of each cons is either the next link in the chain or a terminating atom." -- https://www.lispworks.com/documentation/HyperSpec/Body/26_glo_l.htm#list https://www.lispworks.com/documentation/HyperSpec/Body/26_gl... Interpret that as you will. But what "world of difference" optimizations are you suggesting here? Give an example of a significant optimization at the implementation level that preserves cons semantics.