Lisp как устроены списки: Лекция 4. Списки | [ИУ9] Основы информатики

Лекция 4. Списки | [ИУ9] Основы информатики

LISP — List processing, обработка списков. Список — основная структура данных языка Scheme.

(1 2 3 4) — список из четырёх чисел.

Создание списка

(list <элементы>)
(list 1 2 3 4)    →    (1 2 3 4)
(list)            →    ()

Операции над списками:

(cons <голова> <хвост>) → <список>

Создаёт новый список из некоторого значения («головы») и другого списка («хвоста»). Первым элементом нового списка будет «голова», последующими — хвост.

(cons 1 (list 2 3 4))   →   (1 2 3 4)

(car <список>) → <голова списка>
(cdr <список>) → <хвост списка>
(null? <список>) → <bool>

Это селекторы, запрашивают голову и хвост списка, список должен быть непустым.

(car (list 1 2 3 4)) → 1
(cdr (list 1 2 3 4)) → (2 3 4)
(null? (list 1 2 3 4)) → #f
(null? (list)) → #t

Пустой список, запись списка через цитирование

'() — пустой список

Запись списка при помощи цитирования:

'(1 (2 3 4) 5 6)

Вложенные списки:

(list (list 1 2 3) (list 4 5 6)) → ((1 2 3) (4 5 6))
'((1 2 3) (4 5 6))               → ((1 2 3) (4 5 6))

Список можно связать с переменной:

(define L '(1 2 3))
(define x 1)
(define (f y)
  (list x y))
(define (f y)
  (cons x (cons y '())))
'(x y)

Встроенная функция length

(length '(1 1 2 1)) → 4

Встроенная функция append — конкатенация списков:

(append '(1 2 3) '(4 5 6)) → (1 2 3 4 5 6)
(append '(1 2) '(3 4) '(5 6)) → (1 2 3 4 5 6)

Объект, который строится функцией cons — т. н. cons-ячейка или пара. Аргументами функции cons могут быть любые объекты.

Правильный список — это или пустой список, или cons-пара, вторым элементом которой является правильный список.

(cons 1 2)            → (1 . 2)   ;; неправильный список
(cons 1 (cons 2 '())) → (1 2)     ;; правильный список
(cons 1 (cons 2 (cons 3 4))) → (1 2 3 . 4)  ;; тоже неправильный список

Пример. Как могла бы быть определена встроенная функция length:

(define (length xs)
  (if (null? xs)
      0
      (+ 1 (length (cdr xs)))))
(define (length xs)
  (define (loop len xs)
    (if (null? xs)
        len
        (loop (+ len 1) (cdr xs))))
  (loop 0 xs))

Функция pair? возвращает истину, если аргумент — cons-ячейка.

Используется для того, чтобы единообразно преобразовать все элементы списка, принимает процедуру и исходный список, строит новый список той же длины, что и исходный, каждый элемент этого списка является результатом применения процедуры к элементу исходного списка.

(define (square x) (* x x))
(map square '(1 2 3 4 5))  →  '(1 4 9 16 25)

Расширенный вариант использования

(map
  (lambda (x y) (+ (* 2 x) (* 3 y)))
  '(1 2 1 2)
  '(2 3 2 3 2)
) →
  '(8 13 8 13)

Функцию map («простой вариант») можно описать как:

(define (map f xs)
  (if (null? xs)
      '()
      (cons (f (car xs)) (map f (cdr xs)))))

Безымянная процедура, принимающая произвольное число аргументов:

(lambda xs …)

xs — список аргументов

((lambda xs xs) 1 2 3 4) → (1 2 3 4)

Безымянная процедура, принимающая n+ аргументов:

(lambda (a b c . xs) …)
((lambda (a b c . xs)
   (list (+ a b c) xs))
 1 2 3 4 5) →
   (6 (4 5))

Именованная процедура:

(define (f <фиксированные параметры> . <список параметров>)
  …)
(define (f a b c . xs)
  (list (+ a b c) xs))
(f 1 2 3 4 5) → (6 (4 5))
(define (f . xs)
  (list xs xs))
(f 1 2 3) → ((1 2 3) (1 2 3))

Функцию list можно описать так:

(define (list .
  xs) xs)

Пример:

((lambda x x)) → ()

Вычислительная сложность — асимптотическая оценка времени работы программы. Асимптотическая, значит, нас интересует не конкретное время, а поведение.

T(<данные>) — функция, возвращающая точное значение времени работы программы на конкретных входных данных.

Асимптотическая оценка O(f(<данные>)) показывает, что функция T(•) при росте входных данных ведёт себя как функция f(•) с точностью до некоторого постоянного сомножителя.

Т.е. существует такое k, что

T(data) <= k×f(data)

при росте аргумента data.

Оценку вычислительной сложности для некоторого алгоритма и некоторого абстрактного вычислителя обычно оценивают в числе элементарных команд этого абстрактного вычислителя.

Для Scheme элементарными операциями считаются вызов функции, cons,

Встроенные функции могут иметь разную сложность!

Например,

• (map f xs) — O(len(xs)×T(f)), где T(f) — среднее время работы (f x).
• (length xs) — O(len(xs)).
• (append xs ys) — O(len(xs)).

.

(define (append xs ys)
  (if (null? xs)
      ys
      (cons (car xs) (append (cdr xs) ys))))

(define (f x)
  (lambda (y) (+ x y))
(define f1 (f 1))
(define f7 (f 7))
(f1 10) → 11
(f7 10) → 17

• eqv? — атомы сравнивает по значению, сложные типы данных (списки, векторы, lambda) — по ссылке.
• eq? — может и атомы сравнивать по ссылке.
• equal? — сравнивает аргументы по значению.
• = — равенство чисел. Может сравнивать числа разных типов.
• Функции сравнения отдельных типов вроде string=?…

Функция equal? медленная, т. к. сравнивает аргументы по значению, в частности, для списков сравнивает их содержимое. Но она наиболее предсказуемая.

Функции eq? и eqv? работают быстро, но могут давать неожиданные результаты.

(define x …)
(define y x)
(eq? x y)     → #t
(eqv? x y)    → #t
(equal? x y)  → #t

LISP — Списки — CoderLessons.com

Списки были самой важной и основной составной структурой данных в традиционном LISP. На сегодняшний день Common LISP предоставляет другие структуры данных, такие как вектор, хеш-таблица, классы или структуры.

Списки – это отдельные связанные списки. В LISP списки строятся в виде цепочки простой структуры записей с именем cons, связанной вместе.

Минусы Запись Структура

Минусы – это структура записи, содержащая два компонента, которые называются car и cdr.

Минусы ячейки или минусы – это объекты значений пар, которые создаются с помощью функции cons.

Функция cons принимает два аргумента и возвращает новую cons-ячейку, содержащую два значения. Эти значения могут быть ссылками на любой тип объекта.

Если второе значение не равно nil или другой cons-ячейке, то значения печатаются в виде пунктирной пары, заключенной в скобки.

Два значения в ячейке cons называются car и cdr. Функция car используется для доступа к первому значению, а функция cdr – для доступа ко второму значению.

пример

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo

(write (cons 1 2))
(terpri)
(write (cons 'a 'b))
(terpri)
(write (cons 1 nil))
(terpri)
(write (cons 1 (cons 2 nil)))
(terpri)
(write (cons 1 (cons 2 (cons 3 nil))))
(terpri)
(write (cons 'a (cons 'b (cons 'c nil))))
(terpri)
(write ( car (cons 'a (cons 'b (cons 'c nil)))))
(terpri)
(write ( cdr (cons 'a (cons 'b (cons 'c nil)))))

Когда вы выполняете код, он возвращает следующий результат –

(1 . 2)
(A . B)
(1)
(1 2)
(1 2 3)
(A B C)
A
(B C)

Вышеприведенный пример показывает, как структуры cons могут использоваться для создания единого связанного списка, например, список (ABC) состоит из трех cons-ячеек, связанных друг с другом их cdrs .

Схематически это можно выразить как –

Списки в LISP

Хотя cons-ячейки могут использоваться для создания списков, построение списка из вложенных вызовов функции cons не может быть лучшим решением. Функция списка скорее используется для создания списков в LISP.

Функция list может принимать любое количество аргументов и, поскольку она является функцией, она оценивает свои аргументы.

Первая и остальные функции дают первый элемент и остальную часть списка. Следующие примеры демонстрируют концепции.

Пример 1

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo

(write (list 1 2))
(terpri)
(write (list 'a 'b))
(terpri)
(write (list 1 nil))
(terpri)
(write (list 1 2 3))
(terpri)
(write (list 'a 'b 'c))
(terpri)
(write (list 3 4 'a (car '(b . c)) (* 4 -2)))
(terpri)
(write (list (list 'a 'b) (list 'c 'd 'e)))

Когда вы выполняете код, он возвращает следующий результат –

(1 2)
(A B)
(1 NIL)
(1 2 3)
(A B C)
(3 4 A B -8)
((A B) (C D E))

Пример 2

Создайте новый файл исходного кода с именем main. lisp и введите в него следующий код.

Live Demo

(defun my-library (title author rating availability)
   (list :title title :author author :rating rating :availabilty availability)
)
(write (getf (my-library "Hunger Game" "Collins" 9 t) :title))

"Hunger Game"

Функции управления списком

В следующей таблице приведены некоторые часто используемые функции управления списками.

автомобиль

Он принимает список в качестве аргумента и возвращает свой первый элемент.

корд

Он принимает список в качестве аргумента и возвращает список без первого элемента

минусы

Он принимает два аргумента, элемент и список, и возвращает список с элементом, вставленным на первое место.

список

Он принимает любое количество аргументов и возвращает список с аргументами в качестве элементов-членов списка.

присоединять

Он объединяет два или более списка в один.

прошлой

Он берет список и возвращает список, содержащий последний элемент.

член

Он принимает два аргумента, второй из которых должен быть списком, если первый аргумент является членом второго аргумента, а затем возвращает остаток списка, начинающийся с первого аргумента.

задний ход

Он берет список и возвращает список с верхними элементами в обратном порядке.

Обратите внимание, что все функции последовательности применимы к спискам.

Пример 3

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo

(write (car '(a b c d e f)))
(terpri)
(write (cdr '(a b c d e f)))
(terpri)
(write (cons 'a '(b c)))
(terpri)
(write (list 'a '(b c) '(e f)))
(terpri)
(write (append '(b c) '(e f) '(p q) '() '(g)))
(terpri)
(write (last '(a b c d (e f))))
(terpri)
(write (reverse '(a b c d (e f))))

Когда вы выполняете код, он возвращает следующий результат –

A
(B C D E F)
(A B C)
(A (B C) (E F))
(B C E F P Q G)
((E F))
((E F) D C B A)

Конкатенация автомобилей и CDR Функции

Функции car и cdr и их комбинация позволяют извлечь любой конкретный элемент / элемент списка.

Однако последовательности функций car и cdr можно сократить, объединив букву a для car и d для cdr внутри букв c и r.

Например, мы можем написать cadadr для сокращения последовательности вызовов функций – car cdr car cdr.

Таким образом, (cadadr ‘(a (cd) (efg))) вернет d

Пример 4

Создайте новый файл исходного кода с именем main.lisp и введите в него следующий код.

Live Demo

(write (cadadr '(a (c d) (e f g))))
(terpri)
(write (caar (list (list 'a 'b) 'c)))   
(terpri)
(write (cadr (list (list 1 2) (list 3 4))))
(terpri)

Когда вы выполняете код, он возвращает следующий результат –

списков в LISP — GeeksforGeeks

Улучшить статью

Сохранить статью

• Последнее обновление: 12 окт, 2021

Улучшить статью

Сохранить статью

Списки в обычном LISP — это просто одиночный связанный список. В LISP списки представляют собой цепочки записей. Говоря о структурах записей в LISP, очень важна концепция Cons. Cons в LISP представляет собой структуру записи с двумя основными компонентами. Функция cons принимает 2 аргумента и возвращает новую ячейку cons с car и dir.

1. car: Используется для доступа к первому значению в функции cons.
2. cdr: Используется для доступа ко второму значению в функции cons.

Примечание: Если второе значение не равно нулю или представляет собой просто другую ячейку cons, то значения печатаются в виде пары точек, заключенных в круглые скобки.

Пример:

Lisp

 (GEEKSFORG)
(999)
(А Б)
(A B C) 

 запись(список значение1 значение 2 ...) 

 (1 2)
(Г Е Е К С)
(ГЕКСФОРГЕКС НИЛЬ)
(3 4 GEEKS G 7722)
((GEEKSFORGEEKS IS) (ЛУЧШИЙ РЕСУРС ДЛЯ DSA)) 

 ЛУЧШИЙ
ГИКИ
(C D) 

 CL-USER> (список 1 2 3)
(1 2 3)
 

 CL-USER> (первый (список 1 2 3))
1
CL-USER> (второй (список 1 2 3))
2
 

 CL-USER> (defparameter my-list (list 1 2 3))
МОЙ СПИСОК
CL-USER> (setf (второй мой список) 7)
7
CL-USER> мой список
(1 7 3)
 

 CL-USER> (nth 1 (список 1 2 3))
2
 

 CL-USER> (defparameter my-list (список 1 2 3))
МОЙ СПИСОК
CL-USER> (setf (nth 1 my-list) 65)
65
CL-USER> мой список
(1 65 3)
 

 CL-USER> (mapcar #'evenp (список 1 2 3 4 5 6))
(НОЛЬ Т НИЛ Т НОЛЬ Т)
 

 CL-USER> (list (evenp 1) (evenp 2) (evenp 3) (evenp 4) (evenp 5) (evenp 6))
(НОЛЬ Т НИЛ Т НОЛЬ Т)
 

 CL-USER> (mapcar #'string-upcase (list "Hello" "world!"))
("ПРИВЕТ МИР!")
 

 CL-USER> (defun my-map (список функций)
           (если список
               (минусы (функция funcall (первый список))
                     (функция my-map (список остальных)))
               ноль))
МОЯ КАРТА
CL-USER> (my-map #'string-upcase (список "a" "b" "c"))
("А" "Б" "В")