Hacker News Reader

Comment by Karellen | Hacker News Reader

> 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.

View on HN

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

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.

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.

> 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.

And multiple `itertools.chain` instances pointing to the same list chunk(s) also use sharing.

OK, that is true, but that approach would have the significant downside that you can't pass over a list more than once.

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).

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.

> 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_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.

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.

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.

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.

> 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. :)

My assertion is that linked lists map BETTER to the human and WORSE to the computer. The thought experiment is simply a way to prove that fact and is not a premise let alone a false one.

If arrays and linked lists had the same performance characteristics, we'd pick linked lists every time because they map better to how humans think about problems while arrays map better to how computers think about problems.

Thus we can conclude the exact opposite of the assertion I was responding to. People naturally gravitate toward linked lists then get forcibly re-educated to use arrays because that's what makes the computer happy.

My assertion is that linked lists map BETTER to the human

That's your assertion, but you didn't back it up by anything other than saying you can insert into the middle of a list (which is rare to need and can be done with a sorted map).

Thus we can conclude the exact opposite of the assertion I was responding to

You can't conclude anything from someone making the same assertion with no evidence over and over.

Pragmatically what people use over and over are arrays and hash maps. There's a reason perl, python, lua and javascript all thrived by having arrays and hash maps built in to the core of the language.

If you want to loop through something or index by an offset you use an array. If you want to access by key, you use a hash map. In the rare scenario you need to insert into the middle of a specific order, use a sorted map. Modern programming has no place for basic linked lists of granular data and they aren't missed in any sort of real scenario.

If can back up what you're saying with any sort of evidence or a specific scenario, go ahead.

Linked lists in their basic form are essentially obsolete. Having small items linked by pointers on a modern computer means following the pointer, allocation and deallocation are all more expensive than using data.

This sounds like a backwards rationalization without a technical explanation. Why would a linked list be any better for 'exploratory' programming? The vast majority of data structures are arrays, hash maps and occasionally a sorted map for the times where you need to insert something in a specific place.

What scenario is a linked list valuable in 'exploratory' programming where it wouldn't make more sense to use a different basic data structure?

I've felt my way around a new problem domains many times, and my experience is that a vector and a map will do just fine.

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)

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?

It's inspired by set-builder notation: https://en.wikipedia.org/wiki/Set-builder_notation

Nim has a `collect` macro which works exactly like this.

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.

I've not used python much but is that not the same/similar to the unfold function in functional languages?

Reads less like Perl in Lisp:

    (loop for i below 10 when (zerop (mod i 3)) collect (* i i))

Are you joking?

With iterate, for comparison:

  (iter (for i below 10) (if (zerop (mod i 3)) (collect (* i i))))

In racket:

    (for/list ([i (in-range 10)
               #:when (zero? (remainder i 3))])
       (pow i 2))

there’s also for/vector for/and for/or for/first for/last, most likely for/set. Hashes. can add your own, etc…

In Haskell:

let xs = [x*x | x <- [0..], x `mod` 3 == 0]

You can decide later how many you actually want.

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?

> 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.

this is a controversial take, but IMHO, the immutable data structures make Clojurescript (+ Reagent) a very, very nice way to build SPAs.

You only have to dig because you are less familiar with the language.

> copy list

Almost all functions have a copying and destructive variant.

Look into Hylang.

I don’t think you know Common Lisp very well, or are talking about some super limited Lisp dialect I’ve never heard of.

99% emacs lisp

hmm... maybe I need to look at the packages that use common lisp.

see here: https://lispcookbook.github.io/cl-cookbook/data-structures.h...

This is all "I don't know the language" type stuff.

If you don't know Python, slicing syntax is also strange.

Common Lisp was VERY forward-thinking and has all kinds of these features that only became mainstream decades later.

> 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.

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.

Reply on news.ycombinator.com