(in-package :cl-user)

(declaim (optimize speed))

(defun maplist-nreverse (f list)
  (do ((sub list (cdr sub))
       (r nil (cons (funcall f sub) r)))
      ((null sub) (nreverse r))))

(defun maplist-rplacd (f list)
  (let ((r (cons nil nil)))
    (do ((sub list (cdr sub))
	 (end r (let ((x (cons (funcall f sub) nil)))
		  (rplacd end x)
		  x)))
	((null sub) (cdr r)))))

(defun collect-list (n)
  (loop repeat n collect nil))

(defun test-f (l f)
  (dotimes (i (expt 10 5))
    (funcall f #'identity l)))

(defun print-header (n f)
  (format *trace-output* "~A Conses: ~:D~%" f (* (expt 10 n) (expt 10 5))))

(defun do-tests ()
  (dotimes (i 5)
    (let ((l1 (collect-list (expt 10 i)))
	  (l2 (collect-list (expt 10 i))))
      (print-header i #'maplist-nreverse)
      (time (test-f l1 #'maplist-nreverse))
      (print-header i #'maplist-rplacd)
      (time (test-f l2 #'maplist-rplacd)))))