Patrick (patrickwonders) wrote,
Patrick
patrickwonders

  • 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
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 14 comments