Hacker News new | ask | show | jobs
by kazinator 1856 days ago
How about we do that in Lisp, and then apply the invert function to its own source code?

  1> (defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree)))))
  invert
  2> (invert '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
  ((((nil (((nil ((nil (nil (nil . tree) . car) . invert) (nil (nil . tree) . cdr) . invert) . cons) . tree)
           (nil . tree) . atom) . if)
     nil . tree) . invert) . defun)
A Lisp tree structure can be regarded not as a binary tree, but as an n-ary tree; under which we can come up with a different semantics for inverting:

  3> (defun invert2 (tree)
       (if (listp tree)
          [mapcar invert2 (reverse tree)]
          tree))
  invert2
Now for comparison, we apply that to the original invert:

  4> (invert2 '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
  (((((tree car) invert) ((tree cdr) invert) cons) tree (tree atom)
    if)
   (tree) invert defun)
That's actually halfway readable.

Okay, now let's crank up the stupid knob to about 7.5.

  5> (defun invert3 (tree)
        (cond ((listp tree)
               [mapcar invert3 (reverse tree)])
              ((symbolp tree) (intern (reverse (symbol-name tree))))
              (t tree)))
        
  invert3
  6> (invert3 '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
  (((((eert rac) trevni) ((eert rdc) trevni) snoc) eert (eert mota)
    fi)
   (eert) trevni nufed)
and finally to 11:

  12> (defun invert4 (tree)
        (let ((tree-picture (with-out-strlist-stream (s)
                              (print tree s))))
          (each ((line tree-picture))
            (let* ((rl (reverse line))
                   (sb (mapcar (relate "()" ")(") rl)))
              (put-line `@{sb -78}`)))))
  invert4
  13> (invert4 '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
                                                                   trevni nufed)
                                                        (eert mota) fi) (eert)  
                                       ((eert rdc) trevni) snoc) eert           
                                    (((((eert rac) trevni)                      
  nil
Look, text-wise left-right mirror image of the printed version of the tree!