5 ms·

> But idiomatic Lisp code really does use linked lists extensively, Idiomatic python code uses lists extensively. In my (somewhat limited) experience, they're

> But idiomatic Lisp code really does use linked lists extensively, Idiomatic python code uses lists extensively. In my (somewhat limited) experience, they're the default data structure to use for a lot of algorithms. Slightly more accurately, a lot of stuff in python uses sequences extensively, which are implemented by a number of types - but the default sequence is a list. And strings are lists. Yeah, if a list doesn't cut it then try sets or tuples or generators or coroutines or something else that implements a sequence. But for your initial prototype? List. And python's pretty popular.

edflsafoiewq 3y ago
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.
LeoPanthera 3y ago
I love Python's list comprehensions. When I first discovered them I had a kind of "mind blown" moment. They look like this, for anyone who doesn't know: squared_div_by_3 = [i**2 for i in range(10) if i % 3 == 0] Without using a list comprehension, this is equivalent to: squared_div_by_3 = [] for i in range(10): if i % 3 == 0: squared_div_by_3.append(i**2)
- pierrebai 3y ago
  Of course, Python would have been way more awesome if they did not reject the much more reader-friendly and idiomatic: squared_div_by_3 = [ for i in range(10): if i % 3 == 0: i**2 ] That is, just transforming the normal for loop and if into a list comprehension by surrounding it with brackets. It would even preserve the friendly forced blocking and indentation. Can you imagine?
  - esafak 3y ago
    It's inspired by set-builder notation: https://en.wikipedia.org/wiki/Set-builder_notation https://en.wikipedia.org/wiki/Set-builder_notation
  - xigoi 3y ago
    Nim has a `collect` macro which works exactly like this.
- thaumasiotes 3y ago
  There seems to have been a design emphasis in C# on providing something similar under the name LINQ. It would look like this: var squared_div_by_3 = from i in Enumerable.Range(0,10) where i % 3 == 0 select i*i; or alternatively: var squared_div_by_3 = Enumerable.Range(0,10).Where(i => i % 3 == 0).Select(i => i*i); In that second syntax, `Where` is exactly equivalent to Python's `filter` (or lisp's `remove-if-not`) and `Select` is of course equivalent to `map`; I assume the odd choice of names for C# is meant to appear similar to SQL. They're introducing Range objects with syntactic sugar so you can say `0..10` instead of `Enumerable.Range(0,10)`, and you'd think there would be LINQ implementations for those objects, but there aren't.
m463 3y ago
I like python significantly more than lisp. There are so many ways to express yourself in python that are troublesome in lisp. I actually think list manipulation is easier in python than lisp. I don't know, is there a lisp dialect that makes common data structures available in a multitude of ways? I seem to be able to manipulate lists quite easily in python, and switch back and forth to sets or hashes. but in lisp you have to dig in to find (for example): - how to prepend to a list - how to append to a list - how to remove an element from a lisp - how to do slices of lists it seems to me like a lot of operations in lisp are needlessly efficient too. Like instead of copying a list, you have to modify the list in place. if my list will only have 10 elements, and my machine does millions of instructions per second, can't I copy it around a few times if I want?
- samatman 3y ago
  > is there a lisp dialect that makes common data structures available in a multitude of ways? Clojure. The language is built around immutable data structures with the expected interface for maps and vectors, and the idiomatic list-churning we're both referring to is unified through the sequence abstraction. So switching from a vector to a map can often be as simple as switching constructors. Because they're immutable, every operation makes a "copy" but does so efficiently. I don't have a lot of use for Clojure these days but I enjoyed working with it. Rich Hickey is a smart fella.
  - rpd9803 3y ago
    this is a controversial take, but IMHO, the immutable data structures make Clojurescript (+ Reagent) a very, very nice way to build SPAs.
- bsdpufferfish 3y ago
  You only have to dig because you are less familiar with the language. > copy list Almost all functions have a copying and destructive variant.
- djaouen 3y ago
  Look into Hylang.
richie_adler 3y ago
> And strings are lists Eh, not really. Lists are mutable, strings are not. Strings are iterable and sliceable, which makes them usable in many similar ways to lists, but they're not lists.
- deleted 3y ago
  [deleted]
- volemo 3y ago
  Afaik, in Clojure lists are immutable by default, and strings (not literal ones) are mutable in Common Lisp. So I'd say depends on the flavour of your Lisp.
jshaqaw 3y ago
People confuse code at the exploratory phase with final production code. Linked lists are a massively flexible data structure which can be great when you are still feeling your way around a problem domain. Once you have a good sense for the shape of your data it is relatively trivial to go back and update the codebase with performance optimized structures.
- samatman 3y ago
  That may or may not be the case (that they're great for exploratory code, I have actually mixed feelings about that), but it in fact points directly at the problem I was referring to: using Common Lisp in the idiomatic and expected way involves reading and writing a whole bunch of list processing code. It's not so much that it's a foreign language in the syntactic sense (although it is) but the idiomatic semantics are also pretty foreign to the modern developer. That's a barrier whether or not the promised land is on the far side of the hill.
  - hajile 3y ago
    How is the idiom of linked lists foreign to modern devs? You create a list of items. You can add/remove elements to the start, end, and even the middle and even indexing is just as easy with the `nth` function. From a programmer perspective linked lists are universally better. That is to say that if a computer could perform operations on a linked list as quickly and with as little memory as it could for an array, nobody would ever choose to use arrays. We only use arrays because the computer forces us to.
    - gmfawcett 3y ago
      > if a computer could perform operations on a linked list as quickly and with as little memory as it could for an array, nobody would ever choose to use arrays You can start from a false premise, and draw any conclusion you like. If a computer could perform operations on a linked list as quickly and with as little memory as it could for an array, purple unicorns would be grazing on my lawn right now. :)

edflsafoiewq 3y ago

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.

LeoPanthera 3y ago

I love Python's list comprehensions. When I first discovered them I had a kind of "mind blown" moment. They look like this, for anyone who doesn't know: squared_div_by_3 = [i**2 for i in range(10) if i % 3 == 0] Without using a list comprehension, this is equivalent to: squared_div_by_3 = [] for i in range(10): if i % 3 == 0: squared_div_by_3.append(i**2)

pierrebai 3y ago
Of course, Python would have been way more awesome if they did not reject the much more reader-friendly and idiomatic: squared_div_by_3 = [ for i in range(10): if i % 3 == 0: i**2 ] That is, just transforming the normal for loop and if into a list comprehension by surrounding it with brackets. It would even preserve the friendly forced blocking and indentation. Can you imagine?
- esafak 3y ago
  It's inspired by set-builder notation: https://en.wikipedia.org/wiki/Set-builder_notation https://en.wikipedia.org/wiki/Set-builder_notation
- xigoi 3y ago
  Nim has a `collect` macro which works exactly like this.
thaumasiotes 3y ago
There seems to have been a design emphasis in C# on providing something similar under the name LINQ. It would look like this: var squared_div_by_3 = from i in Enumerable.Range(0,10) where i % 3 == 0 select i*i; or alternatively: var squared_div_by_3 = Enumerable.Range(0,10).Where(i => i % 3 == 0).Select(i => i*i); In that second syntax, `Where` is exactly equivalent to Python's `filter` (or lisp's `remove-if-not`) and `Select` is of course equivalent to `map`; I assume the odd choice of names for C# is meant to appear similar to SQL. They're introducing Range objects with syntactic sugar so you can say `0..10` instead of `Enumerable.Range(0,10)`, and you'd think there would be LINQ implementations for those objects, but there aren't.

m463 3y ago

I like python significantly more than lisp. There are so many ways to express yourself in python that are troublesome in lisp. I actually think list manipulation is easier in python than lisp. I don't know, is there a lisp dialect that makes common data structures available in a multitude of ways? I seem to be able to manipulate lists quite easily in python, and switch back and forth to sets or hashes. but in lisp you have to dig in to find (for example): - how to prepend to a list - how to append to a list - how to remove an element from a lisp - how to do slices of lists it seems to me like a lot of operations in lisp are needlessly efficient too. Like instead of copying a list, you have to modify the list in place. if my list will only have 10 elements, and my machine does millions of instructions per second, can't I copy it around a few times if I want?

samatman 3y ago
> is there a lisp dialect that makes common data structures available in a multitude of ways? Clojure. The language is built around immutable data structures with the expected interface for maps and vectors, and the idiomatic list-churning we're both referring to is unified through the sequence abstraction. So switching from a vector to a map can often be as simple as switching constructors. Because they're immutable, every operation makes a "copy" but does so efficiently. I don't have a lot of use for Clojure these days but I enjoyed working with it. Rich Hickey is a smart fella.
- rpd9803 3y ago
  this is a controversial take, but IMHO, the immutable data structures make Clojurescript (+ Reagent) a very, very nice way to build SPAs.
bsdpufferfish 3y ago
You only have to dig because you are less familiar with the language. > copy list Almost all functions have a copying and destructive variant.
djaouen 3y ago
Look into Hylang.

richie_adler 3y ago

> And strings are lists Eh, not really. Lists are mutable, strings are not. Strings are iterable and sliceable, which makes them usable in many similar ways to lists, but they're not lists.

deleted 3y ago
[deleted]
volemo 3y ago
Afaik, in Clojure lists are immutable by default, and strings (not literal ones) are mutable in Common Lisp. So I'd say depends on the flavour of your Lisp.

jshaqaw 3y ago

People confuse code at the exploratory phase with final production code. Linked lists are a massively flexible data structure which can be great when you are still feeling your way around a problem domain. Once you have a good sense for the shape of your data it is relatively trivial to go back and update the codebase with performance optimized structures.

samatman 3y ago
That may or may not be the case (that they're great for exploratory code, I have actually mixed feelings about that), but it in fact points directly at the problem I was referring to: using Common Lisp in the idiomatic and expected way involves reading and writing a whole bunch of list processing code. It's not so much that it's a foreign language in the syntactic sense (although it is) but the idiomatic semantics are also pretty foreign to the modern developer. That's a barrier whether or not the promised land is on the far side of the hill.
- hajile 3y ago
  How is the idiom of linked lists foreign to modern devs? You create a list of items. You can add/remove elements to the start, end, and even the middle and even indexing is just as easy with the `nth` function. From a programmer perspective linked lists are universally better. That is to say that if a computer could perform operations on a linked list as quickly and with as little memory as it could for an array, nobody would ever choose to use arrays. We only use arrays because the computer forces us to.
  - gmfawcett 3y ago
    > if a computer could perform operations on a linked list as quickly and with as little memory as it could for an array, nobody would ever choose to use arrays You can start from a false premise, and draw any conclusion you like. If a computer could perform operations on a linked list as quickly and with as little memory as it could for an array, purple unicorns would be grazing on my lawn right now. :)