14rec, Common Lisp

Language: Layout:

#|
Используя стандартное представление списков, запрограммировать следующий предикаты для работы со списками. 
Каждый предикат должен вычислять сложность (число шагов, необходимых для вычисления) для  самого себя.
    1. Конкатенация двух упорядоченных по возрастанию списков так, чтобы полученный список также был упорядочен по возрастанию. 
    2. Инверсия списка.
    3. Вывод на экран элементов списка.
    4. Сформировать для заданного списка список, элементами которого являются числа, задающие число вхождений каждого элемента исходного списка в этот список.
    5. Проверка, является ли один список подсписком другого списка, причем таким, что все его элементы являются последними элементами исходного списка.
    6. Выделение подсписка, первым элементом которого будет заданный элемент
    7. Удаление повторяющихся элементов списка с сохренением порядка.
|#

;Конкатенация двух упорядоченных по возрастанию списков так, чтобы полученный список также был упорядочен по возрастанию.

(defun concat (l1 l2 &optional (compl 0))
 
   (cond
       ;((and (null l1) (null l2)) (list (+ compl 5)))
       ((null l1) (append l2  (list (list (+ compl 4))))); (concat nil nil (+ compl 4))))
       ((null l2) (append l1  (list (list (+ compl 4)))));(concat nil nil (+ compl 4))))
       ((< (first l1) (first l2)) (cons (first l1) (concat (rest l1) l2 (+ compl 8))))
       (t (cons (first l1) (concat l1 (rest l2) (+ compl 4))))
    )
    )

;Инверсия списка.
(defun inverse (list &optional (compl 0) (i (- (length list) 1)))
    (cond
        ((null list) (list (list (+ compl 3))))
        (t (cons (nth i list) (inverse (butlast list) (+ compl 4) (- i 1))))
        )
    )

;Вывод на экран элементов списка.
(defun print-list (list &optional (compl 0))
 (mapcar #'(lambda (x) (format t "~a " x)) list)
    )

;Сформировать для заданного списка список, элементами которого являются числа, задающие число вхождений каждого элемента исходного списка в этот список.
(defun counts (list)
    (mapcar #'(lambda (x) (count x list)) list)
    )

;Проверка, является ли один список подсписком другого списка, причем таким, что все его элементы являются последними элементами исходного списка.
(defun is-sublist (l1 l2 &optional (compl 0) (i (- (length l1) 1)) (j (- (length l2) 1)))
    (print i) (print j)   
    (cond
           ((< i j) nil)
           ((< j 0) t)
           ((equal (nth i l1) (nth j l2)) (is-sublist l1 l2 (+ compl 5) (- i 1) (- j 1)))
           (t nil)
           )
    )

;Выделение подсписка, первым элементом которого будет заданный элемент
(defun sublist (list el)
    (let(pos)) (setf pos 0)
    (let (complexity)) (setf complexity 0)
    (loop for x in list
          if (eql x el)
              return pos
          else 
              do (incf pos)
          do (setf complexity (+ 2 complexity))
          )
    (let (len)) (setf len (length list))
    (when (eql pos len) (return-from sublist (list nil (+ complexity 2)))) 
    (decf len)
    (loop for i from pos to len
          collect (nth i list) into sublist
          do (incf complexity)
          finally (return (list sublist complexity))
          )
    )

;Удаление повторяющихся элементов списка с сохренением порядка
(defun remove-repeats (list)
    (let (complexity)) (setf complexity 0)
    (loop while (not (null list))
          collecting (first list) into l
          do (setf list (remove (first list) list))
          do (setf complexity (+ 6 complexity))
          finally (return (list l complexity))
          )
    )

(let (l1)) (setf l1 (list 0 1 2 2 3 3 3))
(let (l2)) (setf l2 (list 3 3 3 ))
(print (- (length l1) 1))
;(print (equal (nth 6 l1) (nth 2 l2)))
(print "Список 1")
(print l1)
;(print-list l1)
(print "_____________________________________")
(print "Список 2")
(print l2)
(print "_____________________________________")
(print "Конкатенация двух упорядоченных по возрастанию списков так, чтобы полученный список также был упорядочен по возрастанию.")
(print (concat l1 l2))
(print "_____________________________________")
;(print "Инверсия списка 1")
;(print (inverse l1))

(print "_____________________________________")
(print "Сформировать для списка 1 список, элементами которого являются числа, задающие число вхождений каждого элемента исходного списка в этот список.")
(print (counts l1))
(print "_____________________________________")
(print "Проверка, является ли один список подсписком другого списка, причем таким, что все его элементы являются последними элементами исходного списка.")
(print (is-sublist l1 l2))
(print "_____________________________________")
(let (num)) (setf num 7)
(print "Выделение подсписка списка 1, первым элементом которого будет заданный элемент")
(princ "Заданный элемент: ") (print num)
(print (sublist l1 num))
(print "_____________________________________")
(print "Удаление повторяющихся элементов списка 1 с сохренением порядка")
(print (remove-repeats  l1 ))

[ + ] Show input
Absolute running time: 0.17 sec, cpu time: 0.03 sec, memory peak: 9 Mb, absolute service time: 0,28 sec