?

Log in

No account? Create an account
patrickwonders
patrickwonders

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.

Details about a class-based implementationCollapse ) Details about a functional implementationCollapse )

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.