Yesterday I wrote a block of scala code to calculate the (integer) Loday coordinates of the convex polytopes that model associahedra. I wrote the code with the help of a local LLM (codellama) but I wasn’t really happy about it. The code was bloated, had unnecessary bits, and not precise at all. Today, I am going to rewrite it in Common Lisp. This is completely unadulterated.
Let us start with our ground function that generates all parenthesizations of \(n+1\)-terms. This is almost verbatim translation of the scala code, but then again, this is the only sensible solution.
(defun parenthesizations (n)
(if (= n 1)
(list 0)
(loop for i from 1 below n
append (mapcar #'cons
(parenthesizations i)
(parenthesizations (- n i))))))
(parenthesizations 4)PARENTHESIZATIONS
((0 0 0 . 0) (0 (0 . 0) . 0) ((0 . 0) 0 . 0) ((0 0 . 0) . 0)
(((0 . 0) . 0) . 0))Now, both of the functions I wrote yesterday for labeling and counting leaves can be combined into a single function that traverses over a tree:
(defun traverse (tree base fn)
(if (atom tree)
(funcall base tree)
(funcall fn (traverse (car tree) base fn)
(traverse (cdr tree) base fn))))TRAVERSEFor counting we do
(traverse '(0 (0 . 0) . 0) (lambda (x) 1) #'+)4For flattening we do
(traverse '(0 (0 . 0) . 0) #'list #'append)(0 0 0 0)For relabelling we do
(mapcar (lambda (tree)
(let ((counter (let ((n 0)) (lambda (x) (incf n)))))
(traverse tree counter #'cons)))
(parenthesizations 4))((1 2 3 . 4) (1 (2 . 3) . 4) ((1 . 2) 3 . 4) ((1 2 . 3) . 4)
(((1 . 2) . 3) . 4))Next, I’ll implement the function that returns the size of the minimal subtree that contains a collection of elements. This is slight generalization of yesterday’s code where the code checked only a pair:
(defun min-subtree (tree pair)
(let ((elts (traverse tree #'list #'append)))
(if (atom tree)
most-positive-fixnum
(let ((left (min-subtree (car tree) pair))
(right (min-subtree (cdr tree) pair)))
(if (subsetp pair elts)
(min left right (1- (length elts)))
(min left right))))))
(min-subtree '((1 . 2) ((3 . 4) . 5) . 6) '(1 2 3))MIN-SUBTREE
5Next, the Loday coordinates for a given tree:
(defun loday-coordinates (tree n)
(loop for i from 1 below n
collect (min-subtree tree (list i (1+ i)))))
(loday-coordinates '((1 . 2) ((3 . 4) . 5) . 6) 6)LODAY-COORDINATES
(1 5 1 2 3)And finally, the coordinates of the extremal points for the convex polytope that models an associahedron \(K_n\):
(defun associahedra-coordinates (n)
(labels ((counter ()
(let ((n 0)) (lambda (x) (incf n))))
(label-tree (tree)
(let ((c (counter)))
(traverse tree c #'cons))))
(mapcar (lambda (x) (loday-coordinates (label-tree x) n))
(parenthesizations n))))
(associahedra-coordinates 4)
(associahedra-coordinates 5)ASSOCIAHEDRA-COORDINATES
((3 2 1) (3 1 2) (1 3 1) (2 1 3) (1 2 3))
((4 3 2 1) (4 3 1 2) (4 1 3 1) (4 2 1 3) (4 1 2 3) (1 4 2 1) (1 4 1 2)
(2 1 4 1) (1 2 4 1) (3 2 1 4) (3 1 2 4) (1 3 1 4) (2 1 3 4) (1 2 3 4))In my experience of playing with LLMs (both local and hosted) in
generating code, LLMs do well with imperative languages in relatively
simple problems. For some reason, all of the LLMs I tried generated junk
lisp code for the problems I am interested in. I tend to write
recursive, generalized/abstracted lisp code (think of
count-leaves or flatten or
label-leaves below and traverse function
above). LLMs can’t get even close to write something similar.
(defun count-leaves (tree)
(if (atom tree)
1
(+ (count-leaves (car tree))
(count-leaves (cdr tree)))))
(count-leaves '((1 . 2) ((3 . 4) . 5) . 6))
(defun flatten (tree)
(if (atom tree)
(list tree)
(append (flatten (car tree))
(flatten (cdr tree)))))
(flatten '((1 . 2) ((3 . 4) . 5) . 6))
(defun label-leaves (tree counter)
(if (atom tree)
(funcall counter)
(cons (label-leaves (car tree) counter)
(label-leaves (cdr tree) counter))))
(let ((c (let ((n 0)) (lambda () (incf n)))))
(label-leaves '((0 . 0) ((0 . 0) . 0) . 0) c))COUNT-LEAVES
6
FLATTEN
(1 2 3 4 5 6)
LABEL-LEAVES
((1 . 2) ((3 . 4) . 5) . 6)