How to improve readability of a big lisp function

Question

My main method (remove-random-edge) looks quite difficult to read. I'm new to list, so would appreciate any advice on how to improve the code.

(defun find-node (node graph)
 (find-if #'(lambda (i) (eql node (first i))) graph))
;; Input, graph, is in form ((from-1 to-1 to-2 to-3 ...)
;; (from-2 to-4 to-5 to-6 ...) ...)
;; where from-n and to-n are integers.
(defun remove-random-edge (graph)
 "Remove one random edge from a graph given as adjacency list."
 (let* ((node-list-1 (elt graph (random (length graph))))
 (node-1 (first node-list-1))
 (destinations (remove-duplicates (rest node-list-1)))
 (node-2 (elt destinations (random (length destinations))))
 (node-list-2 (find-node node-2 graph)))
 (flet ((replace-tail-for-head (node) (if (eql node node-2) node-1 node))
 (is-head-p (node) (eql node-1 node))
 (is-tail-p (node) (eql node-2 node))
 (starts-with-tail-p (nodes) (eql node-2 (first nodes))))
 (setf (rest node-list-1) (concatenate 'list 
 (rest node-list-1)
 (remove-if #'is-head-p (rest node-list-2)))) 
 (loop for node in (remove-duplicates (rest node-list-2))
 with match
 with repcd 
 do (setf match (find-node node graph))
 do (setf repcd (if (eql node node-1)
 (remove-if #'is-tail-p (rest match))
 (map 'list #'replace-tail-for-head (rest match))))
 do (setf (rest match) (sort repcd #'<))) 
 (remove-if #'starts-with-tail-p graph))))

UPD: With review comments applied:

(defun remove-random-edge (graph)
 "Remove one random edge from a graph given as adjacency list."
 (let* ((head-list (elt graph (random (length graph))))
 (head (first head-list))
 (destinations (remove-duplicates (rest head-list)))
 (tail (elt destinations (random (length destinations))))
 (tail-list (assoc tail graph)))
 (flet ((replace-tail-for-head (node) (if (eql node tail) head node)))
 (setf (rest head-list) (concatenate 'list 
 (rest head-list)
 (remove head (rest tail-list)))) 
 (loop for node in (remove-duplicates (rest tail-list))
 for match = (assoc node graph)
 do (setf (rest match) (if (eql node head)
 (remove tail (rest match))
 (mapcar #'replace-tail-for-head (rest match)))))
 (remove tail graph :key #'first))))

Before:

15.109 seconds of real time
50,245,719,578 processor cycles
767,039,256 bytes consed

After:

2.312 seconds of real time
7,665,669,728 processor cycles
778,172,816 bytes consed

Answer 1

Superficial

Your find-node is actually (almost) assoc or, if you prefer, (find node graph :key #'first).

Use mapcar instead of map 'list because it makes the intent clearer (the difference is that mapcar takes only lists and map any sequence).

You need just one do in loop; you can even fold all your setfs into one (setf a b c d e f).

In loop, with should (stylistically) come before for.

Deep

Your code looks too complicated for what it does.

None of your flet local functions is really necessary. E.g., (remove-if #'is-head-p ...) should be (remove node-1 ...), and (remove-if #'starts-with-tail-p ...) should be (remove node-2 ... :key #'first); this would make the code both faster and cleaner.

Your loop should be

(loop for node in (remove-duplicates (rest node-list-2))
 for match = (find-node node graph)
 for repcd = (if (eql node node-1)
 (remove-if #'is-tail-p (rest match))
 (map 'list #'replace-tail-for-head (rest match))))
 do (setf (rest match) (sort repcd #'<))) 

General

Usually it is better to use the most specific function you need. E.g., use setq on simple variables (instead of setf which also supports general references). Use mapcar instead of map 'list when working with lists (as opposed to vectors).

• zzandy: Thank you, very informative. I missed the fact that setf can be folded, and the fact that flet is redundant is totally clear now, after you pointed that out. Why is mapcar preferable over map here, also, is with before for a stylistic preference?
• sds: @zzandy: with before for is stylistic. mapcar make your intent clearer. See edits