Lisp reversing all continuous sequences of elements

Question

I want to reverse only the continuous sequences, not all the elements of my original 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))

I was thinking of splitting it into 2 functions: one to reverse a simple list ( 1 2 3 ) -> ( 3 2 1 ) and one function (main) to determine the continuous sequences, make a list out of them, apply reverse on that list and the remake the whole reversed list.

(defun reverse-list ( lista ) 
    (if (eql lista () )
        ()
        (append (reverse-list (cdr lista )) (list ( car lista)))
    )
)

This is the reverse function but I have no idea how to do the other one. I'm new to Lisp and I come from Prolog so it's a pretty big change of scenery. Any idea is welcome.

(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 ...

Woodprint

See this, this and also this question about reverse. Now, when you are reversing a list, if the current element you are visiting is a list, you want to reverse it recursively first. – Calaboose

None of the links really helped me much. I already said I have the function to reverse a simple list. Look at my example, it hastoreverse only the continuous sequences. I dont know how to stop my function, reverse what I already read and the keep going – Woodprint

Please elaborate on what you mean with "continuous"? I'd understand this as '(1 2 4) would become '(2 1 4), which the accepted answers doesn't satisfy. Perhaps contiguous/consecutive is the better term here? – Mizzenmast

By continuous, I meant on the same level, not intrerrupted by another sublist. It was my mistake for giving such an example. It could've well been (1 3 (8 3) 2 ) => (3 1 (3 8) 2). – Woodprint

Answer 1

You can perform all at once with a single recursive function, with the usual warning that you should favor looping constructs over recursive approaches (see below):

(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))))))))

Exemples

(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))

Remarks

@Melye77 The destructuring-bind expression does the same thing as [Head|Tail] = List in Prolog. I could have written this instead

(let ((head (first list)) 
      (tail (rest list)))
 ...)

Likewise, I prefer to use (e)typecase over the generic cond expression whenever possible, because I think it is more precise.

I could have written:

(if acc
    (if (listp (first list))
      (nconc ...)
      (reverse-consecutive ...))
    acc)

... but I think it is less clear and not a good thing to teach beginners. On the contrary, I think it is useful, even (especially) for beginners, to introduce the full range of available constructs. For example, overusing recursive functions is actually not recommended: there are plenty of existing iteration constructs for sequences that do not depend on the availability of tail-call optimizations (which are not guaranteed to be implemented, though it is generally available with appropriate declarations).

Iterative version

Here is an iterative version which uses of the standard reverse and nreverse functions. Contrary to the above method, inner lists are simply reversed (contiguous chunks are only detected at the first level of depth):

(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))))))

Calaboose

As I understand only continuous sequences should be reversed, but your code reverse all sequences? – Grater

By continuous, I meant on the same level, not intrerrupted by another sublist. It was my mistake for giving such an example. It could've well been (1 3 (8 3) 2 ) => (3 1 (3 8) 2). – Woodprint

@Melye77 Please see additional test cases to confirm the function does what it should. Thanks. – Calaboose

Yes that was indeed what I was looking for. Thank you for the explanations as well, makes sense now – Woodprint

Answer 2

There's already an accepted answer, but this seems like a fun challenge. I've tried to abstract some of the details away a bit, and produced a map-contig function that calls a function with each contiguous sublist of the input list, and determines what's a contiguous list via a predicate that's passed in.

(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)))))))

Here's your original example:

(map-contig 'reverse '< '(1 2 (4 5) 5))
;=> (2 1 (5 4) 5)

It's worth noting that this will detect discontinuities within a single sublist. For instance, if we only want continuous sequences of integers (e.g., where each successive difference is one), we can do that with a special predicate:

(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)

If you only want to break when a sublist occurs, you can just use a predicate that always 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)

Here's another example where "contiguous" means "has the same sign", and instead of reversing the contiguous sequences, we sort them:

;; 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)

A more Prolog-ish approach

(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)

Just two notes about this. First, list* is very much like cons, in that (list* 'a '(b c d)) returns (a b c d). list** can take more arguments though (e.g., **(list* 'a 'b '(c d e)) returns (a b c d e)), and, in my opinion, it makes the intent of lists (as opposed to arbitrary cons-cells) a bit clearer. Second, the other answer explained the use of destructuring-bind; this approach could be a little bit shorter if

(let* ((parts (reverse-until list '()))
       (head (first parts))
       (tail (second parts)))

were replaced with

(destructuring-bind (head tail) (reverse-until list '())

Exarch

As I understand the question (or its wording) only your answer solves the question. +1 – Mizzenmast

@DanielJour I think it's got the potential to, but I'm still not sure exactly what's meant by continuous/contiguous either. In a comment, you mentioned 1 2 4 becoming 2 1 4 since 1 2 gets reversed, and then 4 gets reversed. The example I showed would still produce 4 2 1 when called with '<`, but it'd be easy enough to pass in a predicate that checks for immediately adjacent numbers. – Exarch

Sorry for the misunderstanding. By continuous, I meant on the same level, not intrerrupted by another sublist. It was my mistake for giving such an example. It could've well been (1 3 (8 3) 2 ) => (3 1 (3 8) 2). I'm a begginer in Lisp, coming from Prolog and even the accepted answer doesn't solve it for me cause I have no idea how --typecase-- and --destructuring-bind-- work. I needed something more for beginners but I felt it was the closest thing. Though you found a great challenge in this xD – Woodprint

@melye77 even the accepted answer doesn't solve it for me cause I have no idea how --typecase-- and --destructuring-bind-- work. even though it does what you want, you might want to un accept that answer for the time being. There's no obligation to accept am answer at any point, and accepting too early may discourage others from posting answers (which might actually suit your needs better). – Exarch

Ok, I unaccepted it. I want a more... basic so to speak, recursive way of doing this. I'm struggling for the moment to understand what destructuring-bind is... it's confusing. Who knows, maybe you're right and I'll get more offers. I thought that if it works, I should accept it – Woodprint

@Melye77 I added some explanations about destructuring-bind. – Calaboose

@Melye77 I've updated my answer with a more prolog-ish approach as well. The main difference is an auxiliary local function introduced with labels that computes the initial reversed segment, and returns a list of it and the tail. – Exarch