7 ms·

Immutable Persistent Data Structures in Common Lisp

48 points by postfuturist 14y ago

arohner 14y ago
> 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.
- mark_l_watson 14y ago
  +1 Allen, great example! I also have a side project where I am making multiple sweeps thought the wikipedia XML data. I did this in Ruby using a streaming XML parser, but I am going to try your approach.
enduser 14y ago
This is primarily a blog post about the FSet library for Common Lisp, available at http://common-lisp.net/project/fset/ http://common-lisp.net/project/fset/
- gruseom 14y ago
  FSet was written by HN member http://news.ycombinator.com/user?id=ScottBurson http://news.ycombinator.com/user?id=ScottBurson.
- postfuturist 14y ago
  It is also about using plain linked lists as immutable ordered sequences, sets, or maps.
deleted 14y ago
[deleted]
ScottBurson 14y ago
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?)
- andrewcooke 14y ago
  you could argue that apl (1964) had a similar idea, although a different syntax?
jacobolus 14y ago
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.
- postfuturist 14y ago
  Fixed that, thanks.
thyrsus 14y ago
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."
- postfuturist 14y ago
  It's nothing to do with process threads. http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/-%3E http://clojure.github.com/clojure/clojure.core-api.html#cloj...

48 points by postfuturist 14y ago

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

mark_l_watson 14y ago
+1 Allen, great example! I also have a side project where I am making multiple sweeps thought the wikipedia XML data. I did this in Ruby using a streaming XML parser, but I am going to try your approach.

enduser 14y ago

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

gruseom 14y ago
FSet was written by HN member http://news.ycombinator.com/user?id=ScottBurson http://news.ycombinator.com/user?id=ScottBurson.
postfuturist 14y ago
It is also about using plain linked lists as immutable ordered sequences, sets, or maps.

deleted 14y ago

[deleted]

ScottBurson 14y ago

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

andrewcooke 14y ago
you could argue that apl (1964) had a similar idea, although a different syntax?

jacobolus 14y ago

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.

postfuturist 14y ago
Fixed that, thanks.

thyrsus 14y ago

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

postfuturist 14y ago
It's nothing to do with process threads. http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/-%3E http://clojure.github.com/clojure/clojure.core-api.html#cloj...