Step-by-step cons reversing

cons-reverse.clj

;; (rev '()) => '()
;;
;; (rev '(1)) => (cons 1 '()) => '(1)
;;
;; (rev '(1 2)) => '(2 1) => (cons 2 (cons 1 '()))
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;
;; (rev '(1 2 3)) => '(3 2 1) => (cons 3               (cons 2 (cons 1 '()))   ) 
;;                            => (cons 3               (rev '(1 2))            )
;;                            => (cons (last '(1 2 3)) (rev '(1 2))            )
;;                            => (cons (last '(1 2 3)) (rev (butlast '(1 2 3))))
;;
;; (rev '(1 2)) => '(2 1) => (cons 2 (cons 1 '()))
;;                        => (cons (last '(1 2)) (rev (butlast '(1 2))))
;;
;; (rev xs) => (cons (last xs) (rev (butlast xs)))
;;
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;
;; (last '(1 2)) => 2 => (first (rev '(1 2))))
;;                       (first '(2 1))
;;                       2
;;
;; (last '(1 2 3)) => 3 => (first (rev '(1 2 3))
;;                         (first '(3 2 1))
;;                         3
;;
;; (last xs) => (first (rev xs)) ?
;;
;; Oh-oh. (rev '(1 2 3)) => (... (last '(1 2 3)         ) ...) 
;;                       => (... (... (rev '(1 2 3)) ...) ...)
;;
;;
;; (last '(1 2)) => 2 => (first (rev (rest '(1 2))))
;;                    => (first (rev '(2)))
;;                    => (first '(2))
;;                    => 2
;;
;; (last '(1 2 3)) => 3 => (first (rev (rest '(1 2 3))))
;;                      => (first (rev '(2 3)))
;;                      => (first '(3 2))
;;                      => 3
;;
;; (last xs) => (first (rev (rest xs)))
;;
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; 
;; (butlast '(1 2)) => '(1) => (rev (rest (rev '(1 2))))
;;                          => (rev (rest '(2 1))
;;                          => (rev '(1))
;;                          => '(1)
;;
;; (butlast '(1 2 3)) => '(1 2) => (rev (rest (rev '(1 2 3))))
;;                              => (rev (rest '(3 2 1))
;;                              => (rev '(2 1))
;;                              => '(1 2)
;;
;; (butlast xs) => (rev (rest (rev xs)) ?
;;
;; Oh-oh. (rev '(1 2 3)) => (... (butlast '(1 2 3)      ) ...) 
;;                       => (... (... (rev '(1 2 3)) ...) ...)
;;
;; (butlast '(1 2 3)) => '(1 2) => (cons 1                (butlast '(2 3)))
;;                              => (cons (first '(1 2 3)) (butlast '(2 3)))
;;                              => (cons (first '(1 2 3)) (rev (rest (rev (rest '(1 2 3))))))
;;                              => (cons 1 (rev (rest (rev '(2 3)))))
;;                              => (cons 1 (rev (rest '(3 2))))
;;                              => (cons 1 (rev '(2)))
;;                              => (cons 1 '(2))
;;                              => '(1 2)
;;  
;; (butlast '(1 2)) => '(1) => (cons 1              (butlast '(2)))
;;                          => (cons (first '(1 2)) (butlast '(2)))
;;                          => (cons (first '(1 2)) (rev (rest (rev (rest '(1 2))))))
;;                          => (cons 1 (rev (rest (rev '(2)))))
;;                          => (cons 1 (rev (rest '(2))))
;;                          => (cons 1 (rev '()))
;;                          => (cons 1 '())
;;                          => '(1)
;;
;; (butlast xs) => (cons (first xs) (butlast (rest xs)))
;;              => (cons (first xs) (rev (rest (rev (rest xs))))) 
;;
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;
;; (rev xs)     => (cons (last xs) 
;;                       (rev (butlast xs)))
;;
;; (last xs)    => (first (rev (rest xs)))
;; (butlast xs) => (cons (first xs) (rev (rest (rev (rest xs))))) 
;;
;; (rev xs) => (cons (first (rev (rest xs))) 
;;                   (rev (cons (first xs) (rev (rest (rev (rest xs)))))))
;;
;;

(defn rev [xs]
  (cond  
    (empty? xs) xs 
    (empty? (rest xs)) xs
    :else (cons (first (rev (rest xs)))
                (rev (cons (first xs) (rev (rest (rev (rest xs))))))))) 



(println (rev '()))
(println (rev '(1)))
(println (rev '(1 2)))
(println (rev '(1 2 3)))
(println (rev '(1 2 3 4)))