Can I get LLMs to parrot my code back to me?

{:deps {org.clojure/clojure {:mvn/version "1.10.3"} compliment/compliment {:mvn/version "0.3.9"}}}
Extensible Data Notation

Three years after my blog post Lazy Functional Inorder Binary Tree Traversal in Clojure, I seem to have achieved my goal: When I search for "Lazy Inorder Tree Clojure," my blog post is the top Google result (as of July 2024). I was curious if my code had already been absorbed by LLMs. As stated in the blog, "I still have not found an implementation of an inorder traversal of a binary tree in Clojure that returns a lazy sequence of nodes in order and does not throw a StackOverflowError for very large or infinite binary trees." A quick search revealed that this has not changed so far. Would that mean that I can get LLMs to parrot my code back to me if I ask for an implementation with my exact requirements?

To anticipate the answer: No, the LLMs I tried either gave me catastrophic or better code than my own.

During my experiments it became obvious that the wording of the prompt is crucial. This has been my final prompt which delivered the best results:

Provide an implementation of an inorder traversal of a binary tree in Clojure that returns a lazy sequence of nodes in order and does not throw a StackOverflowError for very large or infinite binary trees. It should be based on these protocols:

(defprotocol Node
  (value [this])
  (left [this])
  (right [this]))
(extend-type clojure.lang.Indexed
  Node
  (value [node] (get node 0))
  (left [node] (get node 1))
  (right [node] (get node 2)))
(deftype RightInfinityNode [num]
  Node
  (value [_] num)
  (left [_] (when (even? num) (new RightInfinityNode (dec num))))
  (right [_] (when (even? num) (new RightInfinityNode (+ num 2)))))
(def infinite-tree (->RightInfinityNode 0))
(defn lazy-inorder-traverse "todo" [root])
0.3s

I will test your implementation with the following code:

(time (last (take 1E7 (lazy-inorder-traverse infinite-tree))))
0.3s

I tried ChatGPT 4o and Claude Sonnet 3.5. I couldn't get ChatGPT 4o to return a decent solution to the problem, no matter how much feedback I provided (syntax errors, test timeouts, etc.). However, Claude returned a solution that I quite like:

(defn lazy-inorder-traverse [root]
  (letfn [(step [node stack]
            (lazy-seq
              (cond
                (some? node)
                (step (left node) (cons node stack))
                
                (seq stack)
                (let [current (first stack)
                      new-stack (rest stack)]
                  (cons (value current)
                        (step (right current) new-stack)))
                
                :else
                nil)))]
    (step root '())))
0.0s
[(take 9 (lazy-inorder-traverse infinite-tree))
 (time (last (take 1E7 (lazy-inorder-traverse infinite-tree))))]
4.1s

Interestingly, when I asked Claude to try to make it even better, Claude made it worse (objectively). However, when I asked for a shorter version, the code improved (subjectively). We finally agreed on the following code, which I like better than my version from three years ago:

(defn lazy-inorder-traverse [root]
  (letfn [(step [node stack]
            (lazy-seq
              (cond
                node (step (left node) (cons node stack))
                stack (let [next-node (first stack)
                            right-child (right next-node)]
                        (cons (value next-node)
                              (step right-child (rest stack)))))))]
    (step root nil)))
0.0s
[(take 9 (lazy-inorder-traverse infinite-tree))
 (time (last (take 1E7 (lazy-inorder-traverse infinite-tree))))]
3.2s

"Make it better" seems to be too unspecific and causes Claude to return some absurd results. However, Claude could follow the more specific "make it shorter." I also observed this with my initial prompt to find the lazy-inorder-traverse function in the first place.

I was not aware of it, but

(letfn [(step [node stack] ; or similar
          (lazy-seq ..
Extensible Data Notation

seems to be common Clojure idiom. I found it in loom, sci and leiningen.

Runtimes (1)