Patrick (patrickwonders) wrote,

  • Mood:

Programming paradigms

To get a more-than-theoretical handle on Lisp, I have started playing with enumerating the partitions of a set. I found a nice algorithm summary online. Coming from a Python mindset, my natural inclination was to make a set partition iterator.

Beginning there, I created a Lisp class for a set partition iterator. The class maintains three pieces of state information: a copy of the original set we are to partition, a vector called κ that keeps a running counter of where we are in the iteration, and a vector M where the i-th element is the maximum of all the first i elements of κ.

With the class, you can do something like this to enumerate the 15 different partitions of the set { a, b, c, d }.:

(let ((my-set '(:a :b :c :d)))
    (let ((iter (make-instance 'set-partition-iterator :list my-set)))
	(do ((pp (get-partition iter) (next-partition iter)))
	    ((not pp))
	    (format t "~a~%" pp)))

This first cut was very poor Lisp. I directly followed the pseudo code in the article. As such, there is a great deal of indexing into vectors and walking backwards through lists and such.

For my second approach, I just used a list for my data structure. I kept the copy of the original set as the first element of the list. The rest of the list was just the κ state. And, I calculated the M information every time I needed it.

My goal in this phase was to make it much more Lisp-y. For starters, I reversed the order of the κ information so that I could walk through the list forward instead of backward and so that I could use Lisp built-ins to calculate the M list:

(let ((MM (maplist #'(lambda (lst) (reduce #'max lst)) kappa)))

Note: this is elegant to look at, but it is O(n2) for an operation that only needs to be O(n).

I had intended to make the iterator using closures so that you never got to handle the list containing the state. But, I wasn't too keen on that because one of the things that I wanted to do in moving to the list instead of the class was make it easy for you to fork the iterator. I went so far as to make it entirely functional.

In the class version, the next-partition method returned a partition. In this functional version, the next-partition returns a new iterator that begins at the partition after where the given iterator is. So, now you need to call get-partition explicitly, but looping makes more sense.

(let ((my-set '(:a :b :c :d)))
    (do ((ii (make-set-partition-iterator my-set) (next-partition ii)))
        ((not ii))
        (format t "~a~%" (get-partition ii))))

Because it's functional, you could nest another do in there to run through all of the partitions you have left at any given point:

(let ((my-set '(:a :b :c :d)))
    (do ((ii (make-set-partition-iterator my-set) (next-partition ii)))
        ((not ii))
	(do ((jj ii (next-partition jj)))
	    ((not jj))
	    (some-operation (get-partition jj)))))

I could rewrite the class version to keep κ in a better order. It would be annoying to make the class version functional yet it seems very anti-Lisp to give it a copy constructor to allow the forking.

The number of partitions in a set grows very rapidly. There are 2 partitions of a two-element set, 5 partitions of a three-element set, 15 partitions of a 4-element set, 51 partitions of a 5-element set, and 72697 partitions of a 10-element set. I'm most always going to be using sets with more than 20 elements.

I really, really believe that functional stuff is easier to understand, to debug, and to re-use. But, it feels wrong to rebuild two 20+ element lists a few hundred thousand times even if the body of the loop is going to be doing much more work than my little iterator. So, I'm caught in the middle ground. I have a non-trivial amount of state which I need to copy a bazillion times, or I have a non-trivial amount of state that morphs behind my back.

Maxims, analogies, and/or dogma welcomed.

Tags: lisp, programming
  • Post a new comment


    default userpic

    Your reply will be screened