Lisp 反转所有连续的元素序列
Lisp reversing all continuous sequences of elements
我只想反转连续序列，而不是原始列表中的所有元素。
Ex:
(reverseC '( 1 2 ( 4 5 ) 5 ) ) => ( 2 1 ( 5 4 ) 5 )
(reverseC '(1 4 2 (3 4) 9 6 (7 8)))) => (2 4 1 (4 3) 6 9 (8 7))
我正在考虑将其拆分为 2 个函数：一个用于反转简单列表 ( 1 2 3 ) -> ( 3 2 1 ) 和一个函数
（主要）确定连续序列，从中制作一个列表，对该列表应用反向并重新制作整个反向列表。
(defun reverse-list ( lista )
(if (eql lista () )
()
(append (reverse-list (cdr lista )) (list ( car lista)))
)
)
这是反向函数，但我不知道如何做另一个。我是 Lisp 的新手，我来自 Prolog，所以这是一个相当大的变化。欢迎任何想法。
(defun reverse-more (L)
(if (eql L nil)
nil
(let ( el (car L)) (aux (cdr L)))
(if (eql (listp el) nil)
...No idea on the rest of the code ...
您可以使用单个递归函数一次执行所有操作，通常会警告您应该优先使用循环构造而不是递归方法（见下文）：
(defun reverse-consecutive (list &optional acc)
(etypecase list
;; BASE CASE
;; return accumulated list
(null acc)
;; GENERAL CASE
(cons (destructuring-bind (head . tail) list
(typecase head
(list
;; HEAD is a list:
;;
;; - stop accumulating values
;; - reverse HEAD recursively (LH)
;; - reverse TAIL recursively (LT)
;;
;; Result is `(,@ACC ,LH ,@LT)
;;
(nconc acc
(list (reverse-consecutive head))
(reverse-consecutive tail)))
;; HEAD is not a list
;;
;; - recurse for the result on TAIL with HEAD
;; in front of ACC
;;
(t (reverse-consecutive tail (cons head acc))))))))
例子
(reverse-consecutive '(1 2 (3 4) 5 6 (7 8)))
=> (2 1 (4 3) 6 5 (8 7))
(mapcar #'reverse-consecutive
'((1 3 (8 3) 2 )
(1 4 2 (3 4) 9 6 (7 8))
(1 2 (4 5) 5)))
=> ((3 1 (3 8) 2)
(2 4 1 (4 3) 6 9 (8 7))
(2 1 (5 4) 5))
备注
@Melye77 destructuring-bind 表达式与 Prolog 中的 [Head|Tail] = List 做同样的事情。我本可以这样写的
(let ((head (first list))
(tail (rest list)))
...)
同样，我更喜欢尽可能使用 (e)typecase over the generic cond 表达式，因为我认为它更精确。
我本可以写成：
(if acc
(if (listp (first list))
(nconc ...)
(reverse-consecutive ...))
acc)
...不过我觉得不太清楚，教初学者也不是什么好事。
相反，我认为介绍各种可用结构很有用，甚至（尤其是）对于初学者来说。
例如，实际上不建议过度使用递归函数：有大量现有的序列迭代结构不依赖于尾调用优化的可用性（不能保证实现，尽管它通常通过适当的声明可用） .
迭代版本
这是一个使用标准 reverse 和 nreverse 函数的迭代版本。与上述方法相反，内部列表只是简单地反转（仅在第一级深度检测到连续块）：
(defun reverse-consecutive (list)
(let (stack result)
(dolist (e list (nreverse result))
(typecase e
(list
(dolist (s stack)
(push s result))
(push (reverse e) result)
(setf stack nil))
(t (push e stack))))))
已经有 ，但这似乎是一个有趣的挑战。我试图抽象出一些细节，并生成了一个 map-contig 函数，该函数使用输入列表的每个连续子列表调用一个函数，并确定什么是连续列表通过传入的谓词。
(defun map-contig (function predicate list)
"Returns a new list obtained by calling FUNCTION on each sublist of
LIST consisting of monotonically non-decreasing elements, as determined
by PREDICATE. FUNCTION should return a list."
;; Initialize an empty RESULT, loop until LIST is empty (we'll be
;; popping elements off of it), and finally return the reversed RESULT
;; (since we'll build it in reverse order).
(do ((result '())) ((endp list) (nreverse result))
(if (listp (first list))
;; If the first element is a list, then call MAP-CONTIG on it
;; and push the result into RESULTS.
(push (map-contig function predicate (pop list)) result)
;; Otherwise, build up sublist (in reverse order) of contiguous
;; elements. The sublist is finished when either: (i) LIST is
;; empty; (ii) another list is encountered; or (iii) the next
;; element in LIST is non-contiguous. Once the sublist is
;; complete, reverse it (since it's in reverse order), call
;; FUNCTION on it, and add the resulting elements, in reverse
;; order, to RESULTS.
(do ((sub (list (pop list)) (list* (pop list) sub)))
((or (endp list)
(listp (first list))
(not (funcall predicate (first sub) (first list))))
(setf result (nreconc (funcall function (nreverse sub)) result)))))))
这是您的原始示例：
(map-contig 'reverse '< '(1 2 (4 5) 5))
;=> (2 1 (5 4) 5)
值得注意的是，这将检测单个子列表中的不连续性。例如，如果我们只想要连续的整数序列（例如，每个连续的差为 1），我们可以用一个特殊的谓词来做到这一点：
(map-contig 'reverse (lambda (x y) (eql y (1+ x))) '(1 2 3 5 6 8 9 10))
;=> (3 2 1 6 5 10 9 8)
如果您只想在子列表出现时中断，您可以只使用始终 returns true 的谓词：
(map-contig 'reverse (constantly t) '(1 2 5 (4 5) 6 8 9 10))
;=> (5 2 1 (5 4) 10 9 8 6)
这里是另一个例子，其中 "contiguous" 表示 "has the same sign"，我们不颠倒连续的序列，而是对它们进行排序：
;; Contiguous elements are those with the same sign (-1, 0, 1),
;; and the function to apply is SORT (with predicate <).
(map-contig (lambda (l) (sort l '<))
(lambda (x y)
(eql (signum x)
(signum y)))
'(-1 -4 -2 5 7 2 (-6 7) -2 -5))
;=> (-4 -2 -1 2 5 7 (-6 7) -5 -2)
更像 Prolog 的方法
(defun reverse-contig (list)
(labels ((reverse-until (list accumulator)
"Returns a list of two elements. The first element is the reversed
portion of the first section of the list. The second element is the
tail of the list after the initial portion of the list. For example:
(reverse-until '(1 2 3 (4 5) 6 7 8))
;=> ((3 2 1) ((4 5) 6 7 8))"
(if (or (endp list) (listp (first list)))
(list accumulator list)
(reverse-until (rest list) (list* (first list) accumulator)))))
(cond
;; If LIST is empty, return the empty list.
((endp list) '())
;; If the first element of LIST is a list, then REVERSE-CONTIG it,
;; REVERSE-CONTIG the rest of LIST, and put them back together.
((listp (first list))
(list* (reverse-contig (first list))
(reverse-contig (rest list))))
;; Otherwise, call REVERSE-UNTIL on LIST to get the reversed
;; initial portion and the tail after it. Combine the initial
;; portion with the REVERSE-CONTIG of the tail.
(t (let* ((parts (reverse-until list '()))
(head (first parts))
(tail (second parts)))
(nconc head (reverse-contig tail)))))))
(reverse-contig '(1 2 3 (4 5) 6 7 8))
;=> (3 2 1 (5 4) 8 7 6)
(reverse-contig '(1 3 (4) 6 7 nil 8 9))
;=> (3 1 (4) 7 6 nil 9 8)
关于此的两点注意事项。首先，list* 非常像 cons，因为 (list* 'a '(b c d)) returns (a b c d)。 list** 虽然可以接受更多参数（例如，**(list* 'a 'b '(c d e)) returns (a b c d e) )，并且在我看来，它使列表的意图（与任意的cons-cells相反）更加清晰。其次，另一个答案解释了 destructuring-bind 的使用；如果
，这种方法可能会更短一些
(let* ((parts (reverse-until list '()))
(head (first parts))
(tail (second parts)))
被替换为
(destructuring-bind (head tail) (reverse-until list '())
我只想反转连续序列，而不是原始列表中的所有元素。
Ex:
(reverseC '( 1 2 ( 4 5 ) 5 ) ) => ( 2 1 ( 5 4 ) 5 )
(reverseC '(1 4 2 (3 4) 9 6 (7 8)))) => (2 4 1 (4 3) 6 9 (8 7))
我正在考虑将其拆分为 2 个函数：一个用于反转简单列表 ( 1 2 3 ) -> ( 3 2 1 ) 和一个函数 （主要）确定连续序列，从中制作一个列表，对该列表应用反向并重新制作整个反向列表。
(defun reverse-list ( lista )
(if (eql lista () )
()
(append (reverse-list (cdr lista )) (list ( car lista)))
)
)
这是反向函数，但我不知道如何做另一个。我是 Lisp 的新手，我来自 Prolog，所以这是一个相当大的变化。欢迎任何想法。
(defun reverse-more (L)
(if (eql L nil)
nil
(let ( el (car L)) (aux (cdr L)))
(if (eql (listp el) nil)
...No idea on the rest of the code ...
您可以使用单个递归函数一次执行所有操作，通常会警告您应该优先使用循环构造而不是递归方法（见下文）：
(defun reverse-consecutive (list &optional acc)
(etypecase list
;; BASE CASE
;; return accumulated list
(null acc)
;; GENERAL CASE
(cons (destructuring-bind (head . tail) list
(typecase head
(list
;; HEAD is a list:
;;
;; - stop accumulating values
;; - reverse HEAD recursively (LH)
;; - reverse TAIL recursively (LT)
;;
;; Result is `(,@ACC ,LH ,@LT)
;;
(nconc acc
(list (reverse-consecutive head))
(reverse-consecutive tail)))
;; HEAD is not a list
;;
;; - recurse for the result on TAIL with HEAD
;; in front of ACC
;;
(t (reverse-consecutive tail (cons head acc))))))))
例子
(reverse-consecutive '(1 2 (3 4) 5 6 (7 8)))
=> (2 1 (4 3) 6 5 (8 7))
(mapcar #'reverse-consecutive
'((1 3 (8 3) 2 )
(1 4 2 (3 4) 9 6 (7 8))
(1 2 (4 5) 5)))
=> ((3 1 (3 8) 2)
(2 4 1 (4 3) 6 9 (8 7))
(2 1 (5 4) 5))
备注
@Melye77 destructuring-bind 表达式与 Prolog 中的 [Head|Tail] = List 做同样的事情。我本可以这样写的
(let ((head (first list))
(tail (rest list)))
...)
同样，我更喜欢尽可能使用 (e)typecase over the generic cond 表达式，因为我认为它更精确。
我本可以写成：
(if acc
(if (listp (first list))
(nconc ...)
(reverse-consecutive ...))
acc)
...不过我觉得不太清楚，教初学者也不是什么好事。 相反，我认为介绍各种可用结构很有用，甚至（尤其是）对于初学者来说。 例如，实际上不建议过度使用递归函数：有大量现有的序列迭代结构不依赖于尾调用优化的可用性（不能保证实现，尽管它通常通过适当的声明可用） .
迭代版本
这是一个使用标准 reverse 和 nreverse 函数的迭代版本。与上述方法相反，内部列表只是简单地反转（仅在第一级深度检测到连续块）：
(defun reverse-consecutive (list)
(let (stack result)
(dolist (e list (nreverse result))
(typecase e
(list
(dolist (s stack)
(push s result))
(push (reverse e) result)
(setf stack nil))
(t (push e stack))))))
已经有
(defun map-contig (function predicate list)
"Returns a new list obtained by calling FUNCTION on each sublist of
LIST consisting of monotonically non-decreasing elements, as determined
by PREDICATE. FUNCTION should return a list."
;; Initialize an empty RESULT, loop until LIST is empty (we'll be
;; popping elements off of it), and finally return the reversed RESULT
;; (since we'll build it in reverse order).
(do ((result '())) ((endp list) (nreverse result))
(if (listp (first list))
;; If the first element is a list, then call MAP-CONTIG on it
;; and push the result into RESULTS.
(push (map-contig function predicate (pop list)) result)
;; Otherwise, build up sublist (in reverse order) of contiguous
;; elements. The sublist is finished when either: (i) LIST is
;; empty; (ii) another list is encountered; or (iii) the next
;; element in LIST is non-contiguous. Once the sublist is
;; complete, reverse it (since it's in reverse order), call
;; FUNCTION on it, and add the resulting elements, in reverse
;; order, to RESULTS.
(do ((sub (list (pop list)) (list* (pop list) sub)))
((or (endp list)
(listp (first list))
(not (funcall predicate (first sub) (first list))))
(setf result (nreconc (funcall function (nreverse sub)) result)))))))
这是您的原始示例：
(map-contig 'reverse '< '(1 2 (4 5) 5))
;=> (2 1 (5 4) 5)
值得注意的是，这将检测单个子列表中的不连续性。例如，如果我们只想要连续的整数序列（例如，每个连续的差为 1），我们可以用一个特殊的谓词来做到这一点：
(map-contig 'reverse (lambda (x y) (eql y (1+ x))) '(1 2 3 5 6 8 9 10))
;=> (3 2 1 6 5 10 9 8)
如果您只想在子列表出现时中断，您可以只使用始终 returns true 的谓词：
(map-contig 'reverse (constantly t) '(1 2 5 (4 5) 6 8 9 10))
;=> (5 2 1 (5 4) 10 9 8 6)
这里是另一个例子，其中 "contiguous" 表示 "has the same sign"，我们不颠倒连续的序列，而是对它们进行排序：
;; Contiguous elements are those with the same sign (-1, 0, 1),
;; and the function to apply is SORT (with predicate <).
(map-contig (lambda (l) (sort l '<))
(lambda (x y)
(eql (signum x)
(signum y)))
'(-1 -4 -2 5 7 2 (-6 7) -2 -5))
;=> (-4 -2 -1 2 5 7 (-6 7) -5 -2)
更像 Prolog 的方法
(defun reverse-contig (list)
(labels ((reverse-until (list accumulator)
"Returns a list of two elements. The first element is the reversed
portion of the first section of the list. The second element is the
tail of the list after the initial portion of the list. For example:
(reverse-until '(1 2 3 (4 5) 6 7 8))
;=> ((3 2 1) ((4 5) 6 7 8))"
(if (or (endp list) (listp (first list)))
(list accumulator list)
(reverse-until (rest list) (list* (first list) accumulator)))))
(cond
;; If LIST is empty, return the empty list.
((endp list) '())
;; If the first element of LIST is a list, then REVERSE-CONTIG it,
;; REVERSE-CONTIG the rest of LIST, and put them back together.
((listp (first list))
(list* (reverse-contig (first list))
(reverse-contig (rest list))))
;; Otherwise, call REVERSE-UNTIL on LIST to get the reversed
;; initial portion and the tail after it. Combine the initial
;; portion with the REVERSE-CONTIG of the tail.
(t (let* ((parts (reverse-until list '()))
(head (first parts))
(tail (second parts)))
(nconc head (reverse-contig tail)))))))
(reverse-contig '(1 2 3 (4 5) 6 7 8))
;=> (3 2 1 (5 4) 8 7 6)
(reverse-contig '(1 3 (4) 6 7 nil 8 9))
;=> (3 1 (4) 7 6 nil 9 8)
关于此的两点注意事项。首先，list* 非常像 cons，因为 (list* 'a '(b c d)) returns (a b c d)。 list** 虽然可以接受更多参数（例如，**(list* 'a 'b '(c d e)) returns (a b c d e) )，并且在我看来，它使列表的意图（与任意的cons-cells相反）更加清晰。其次，另一个答案解释了 destructuring-bind 的使用；如果
，这种方法可能会更短一些(let* ((parts (reverse-until list '()))
(head (first parts))
(tail (second parts)))
被替换为
(destructuring-bind (head tail) (reverse-until list '())