Immutable Persistent Data Structures in Common Lisp (opens in new tab)

This is primarily a blog post about the FSet library for Common Lisp, available at http://common-lisp.net/project/fset/

> They can be useful for certain constructions, but they don’t really enable anything amazing that you can’t do otherwise, just with a slightly different algorithm.

One really nice property of laziness is dealing with data larger than RAM. A couple of months ago I wrote some ML processing of the wikipedia XML in Clojure. In about 5 lines, I had a lazy sequence of every <Article> tag from the XML. Then I can (map my-fn all-articles-from-wikipedia), without blowing the heap (the wikipedia XML was like ~10GB, zipped).

Yes, it's possible to do non-lazy, but this was cleaner and simpler.

One algorithmic advantage of lazy seqs is that (map foo (map bar (map baz my-big-seq))) makes only one pass over the data, as opposed to 3 when non-lazy.

Historical note: FSet was inspired by a language called Refine, which was in turn inspired by SETL, created in the late 1970s at NYU. As far as I know, SETL was the first language to have functional collection types (does anyone know for sure?).

Anyway, some of the operation names used in FSet -- 'with', 'less', and 'arb', for example -- can be traced back to SETL.

SETL also appears to have been the first language with what are now called "comprehensions" (it used the term "formers") to construct collections declaratively. For example,

  { x ** 2 : x in {1 .. 5} }

would produce a set of the squares of the integers from 1 through 5. (Does anyone know of an earlier language with these?)

A bit off topic, but I found the radioactive syntax highlighting and bold-everything in the code samples extremely distracting and hard to read. I would recommend sticking to dark-on-light code when it’s in the middle of dark-on-light text.

Could someone help me with the "thread" example at the end? Something in my shallow understanding seems wrong:

"Threads in Clojure give access to concurrent processing."

"Nothing in the recursive (defmacro -> ...) starts a parallel process."