Hacker News Reader

Comment by johnhattan | Hacker News Reader

As someone who hasn't dealt with Lisp since the 1980's, help me out here. Immutable structures and Lisp seems to be incompatible, as Lisp's lists are about the most mutable things you'll ever see.

If, for example, I want to put a value into the middle of a list, would I be doing something akin to. . .

MyList = MyList.firstHalf + NewValue + MyList.secondHalf?

And how doesn't this become a horrible bottleneck?

View on HN

You can represent the list as a zipper data structure[1]. The idea is to represent a "cursor" pointing to some point in the list as a triple: (list of points before, point at current position, list of points after). So a zipper for an arbitrary list "xs" pointing to the beginning would be (() (car xs) (cdr xs)). There are some things you can do to handle the case with empty lists, which I'll leave to the reader :).

Given a zipper (as x bs) you can move the cursor right (rather, compute the zipper with the cursor one step further to the right, since we're purely functional) as ((cons x as) (car bs) (cdr bs)). You can insert a new element "y" into you current position by computing (as y (cons x bs)). If you discard the old version of the zipper every time you move or insert, this will use the same amount of memory as just storing the list, and you get insertions in O(N) time and O(1) memory. There's a whole field devoted to making data structures like this for purely functional languages, and this zipper concept extends itself rather naturally to trees.

[1]https://en.wikipedia.org/wiki/Zipper_%28data_structure%29

They are not necessarily incompatible. Historically, Lisp pairs are mutable, but that doesn't have to be the case. See Clojure, it is Lisp-like, with most data structures immutable.

Your example is not possible in an immutable list. Also note that this reassigning of variables is a red flag even in standard Lisps. In fact, variables are not that common. The most common way of referencing something for later usage is the let form, which already creates new "variables" anyway. Just eliminate ways to reassign them (setf?).

What you would do is to create a new list containing the elements you want. You may or may not want to give it a new name afterwards. Most likely, you'll use as it is and pass on to some other function.

I can't comment on this particular implementation. But it does not necessarily have to be a bottleneck. In fact, by having immutable data structures, that means that you can share data like crazy, without fear of anything being replaced where it should not. All sorts of optimizations are enabled that wouldn't be possible otherwise. If this implementation uses them, it's another matter entirely. No idea.

Generally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. So, immutability is preserved. Any existing references will not see their values changed. And the new references will share some memory with the old ones (how much depends on where in the list the value was inserted).

You can learn more in Okasaki's great book: http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

Actually Common Lisp and Scheme have a clear distinction between mutating and non-mutating list functions. They even have a naming schema to distinguish between, and most books focus on the non-mutating, in Common Lisp speak "nondestructive" list functions. Functions like append, remove do not mutate the input list, but (partially) new lists, which can share sublists with the input lists. For example (append a b) returns a list which contains a copy of a and the original b.

I wonder if you could use ropes[0].

[0] https://en.wikipedia.org/wiki/Rope_%28data_structure%29

I may be misreading this, but isn't that an example of lists being immutable rather than pervasive mutability?

Do not put a value into a middle of a list.

Read Chris Okasaki, "Purely functional data structures" for better options.

structural sharing is what clojure does. But you can have immutable data structures in old lisps if you only use cons, car and cdr, avoiding set-car and set-cdr.

Reply on news.ycombinator.com