How to return a specific list

Question

I am trying to code this in LISP and I am having a lot of troubles with it.

This is what I have at the moment:

(defun list_incr (x)
    (if (eq (first x) nil)
        x
        (if (< (first x) (first(rest x)))
            (append (list (first x) (first(rest x))) (list_incr (rest(rest x))))
            (list_incr (cons (first x) (rest(rest x)))))))

If given a list (1 3 2 4), it needs to return (1 3 4). At the moment, my code does it fine for 2 consecutive increasing numbers, but when it decreases it doesn't work anymore.

I need the code to return a list with increasing numbers from the give list.

Some Examples:

if given a list (1 2 4 6 5), it should return (1 2 4 6)

if given (3 1 4 5 2 6), it should return (3 4 5 6)

Thank you!

Answer 1

Here are two other approaches, one with the higher-order REDUCE function, and one with LOOP, with annotations. Both of them are a little more general that what is requested in your question, as they accept TEST and KEY arguments: TEST is the comparison predicate and represents the order by which the resulting list is sorted; the test function is called for values extracted by the KEY predicate from the original elements, and defaults to the identity function.

With REDUCE

Reducing (a.k.a. folding) is a way to build a value incrementally, based on values from a list. Here below, the intermediate state is a cons-cell with the result list built so far in its CAR and the latest (maximal) value taken by elements in the list in its CDR. In the anonymous lambda given to REDUCE, it is augmentend whenever the current value is greater that the latest one, otherwise it is kept as-is. REDUCE is called with an initial state value to avoid corner-cases with lists of zero or one elements: generally speaking, it makes sense to provide an :initial-value when the type of the state is different from the type of the list's elements. If instead they are of the same type, it is more natural to avoid it (e.g. (reduce #'+ '(0 1 2))).

(defun monotonic-subset (list &key (test #'<) (key #'identity))
  (flet ((key (object) (funcall key object)))
    (declare (inline key))
    ;; WHEN returns NIL when LIST is NIL
    (when list
      ;; Here we assume LIST is a cons cell; with more work, the
      ;; function could be made to handle vectors too.
      (destructuring-bind (head . tail) list
        (declare (type list list))
        ;; We need to reverse the result computed by REDUCE, which
        ;; pushes elements in front of an intermediate list. Here we
        ;; can use the destructive NREVERSE function instead of
        ;; REVERSE because we own the intermediate list and can mutate
        ;; it anyhow we want before returning a result.
        (nreverse
         ;; take the CAR of the state value computed by reduce
         (car
          ;; (reduce f (e1 .. en) :initial-value v)
          ;; == (f (f (f (f v e1) e2) ...) en)
          (reduce (lambda (state object &aux (key (key object)))
                    (destructuring-bind (objects . last) (print state)
                      (if (funcall test last key)
                          (cons (list* object objects) key)
                          state)))
                  tail
                  :initial-value (cons (list head) (key head)))))))))

With LOOP

Alternatively, you can use the <init> then <step> expression of LOOP:

(defun monotonic-subset (list &key (test #'<) (key #'identity))
  (loop
     ;; iterate over all objects in list
     for o in list
     ;; k is the key of o
     for k = (funcall key o)
     ;; initially, we keep the value
     ;; later, we keep it only if the comparison holds
     for keep = t then (funcall test last k)
     ;; the last value is either the current key, or the last one
     for last = (if keep k last)
     ;; collect only keys that where kept
     when keep collect o))

Answer 2

Here is an alternative, tail-recursive version. This has the advantage that on an implementation which optimises tail calls it will work on arbitrarily big lists, but the usual disadvantage that it returns things backwards, so you need a call to reverse.

It uses a local function as you need two extra arguments, and also uses destructuring-bind to avoid a lot of repeated calls to first and rest. It also slightly despicably checks for a list with zero or one element by (null (rest list)): this works in CL because (cdr '()) (aka (rest '())) is (): it would not work in Scheme, I think, which is fussier about these things.

(defun increasing-elements (list)
  (labels ((increasing-loop (tail current accumulator)
             (if (null tail)
                 (reverse accumulator)
               (destructuring-bind (first . rest) tail
                 (if (> first current)
                     (increasing-loop rest first (cons first accumulator))
                   (increasing-loop rest current accumulator))))))
    (if (null (rest list))
        list
      (destructuring-bind (head . tail) list
        (increasing-loop tail head (list head))))))

Answer 3

Here is a possible recursive definition to solve the problem:

(defun exercise-1d (x)
  (cond ((null x) nil)
        ((null (rest x)) x)
        ((> (second x) (first x)) (cons (first x) (exercise-1d (rest x))))
        (t (exercise-1d (cons (first x) (rest (rest x)))))))

The recursion has two terminal cases: when the list is empty or contains a single element. In both cases the current list is returned.

After the first two tests we are sure that the list has at least two elements, so we can start to check about the relation between the first two elements.

If the second element is greater than the first one, then the first is included and the recursion is applied to the rest of the list.

On the other hand, if the second element is not greater than the first, it is skipped, and the recursion is applied to the list constituted by the first element and all the elements following the second one.