Списки

У Scheme список — це фундаментальна структура даних для групування значень. Списки — це впорядковані набори елементів, де кожен елемент може бути будь-якого типу, включно з іншим списком. Списки широко використовують у Scheme як для зберігання даних, так і для структури програми.

Приклад 1: простий список

(list 1 2 3)

• Створює список із трьох елементів: 1, 2 та 3.

Результат: (1 2 3)

Доступ до елементів списку

Доступ до елементів у списку здійснюється за допомогою процедур car і cdr:

• car отримує перший елемент списку.
• cdr отримує решту списку (все, крім першого елемента).

Приклади

(define my-list (list 1 2 3))
(car my-list)  ; Отримати перший елемент
(cdr my-list)  ; Отримати решту списку

Результат:

• (car my-list) повертає 1
• (cdr my-list) повертає (2 3)

Проста рекурсія: перебір списку

Рекурсивно викликаючи car для cdr списку, можна обробляти кожен елемент по одному, доки список не буде пройдено. Це лежить в основі багатьох алгоритмів обробки списків.

Приклад: друк кожного елемента списку

Ось проста рекурсивна функція для друку кожного елемента в списку:

(define (print-elements lst)
  (if (null? lst)
    (lumi-message "done")
    (begin
      (lumi-message (number->string (car lst))) ;; Вивести перший елемент
      (print-elements (cdr lst)))))             ;; Обробити решту списку

• Базовий випадок: якщо список порожній (null? lst), зупинити рекурсію.
• Рекурсивний випадок: вивести перший елемент (car lst), потім викликати функцію для решти списку (cdr lst).

Приклад використання

(print-elements (list 1 2 3))

Вивід:

• "1"
• "2"
• "3"

Результат: "done"

Як це працює

1. Функція отримує перший елемент списку за допомогою car і обробляє його.
2. Потім вона викликає себе з рештою списку (cdr).
3. Цей процес повторюється, доки список не стане порожнім (null? lst).

Приклад 2: змішані типи

Списки можуть містити елементи різних типів, включно з рядками, логічними значеннями, числами, іншими списками або навіть результатом виразів:

(list 42 "hello" #t (list 1 2) (+ 3 4))

• Це створює список із:
  • числа (42)
  • рядка ("hello")
  • логічного значення (#t)
  • іншого списку ((1 2))
  • результату виразу ((+ 3 4), який обчислюється як 7)

Результат: (42 "hello" #t (1 2) 7)

Ці приклади демонструють універсальність списків у Scheme — вони є потужним інструментом для організації та обробки даних.

Побудова списків

Процедура cons використовується для створення нового списку шляхом поєднання елемента з існуючим списком.

(cons new-element existing-list)

Приклад

(cons 0 (list 1 2 3))

• Додає 0 на початок списку (1 2 3).

Результат: (0 1 2 3)

Перевірка списків

Процедура list? перевіряє, чи дане значення є списком.

(list? value)

Приклад: list?

(list? (list 1 2 3))  ; Перевірити, чи (list 1 2 3) є списком
(list? 42)            ; Перевірити, чи 42 є списком

Результат:

• (list? (list 1 2 3)) повертає #t (істина)
• (list? 42) повертає #f (хибність)

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

Scheme надає кілька вбудованих процедур для роботи зі списками, зокрема:

• length: повертає кількість елементів у списку.
• append: об’єднує два або більше списків в один.
• reverse: повертає новий список з елементами у зворотному порядку.

(length (list 1 2 3))          ; Повертає 3
(append (list 1 2) (list 3 4)) ; Повертає (1 2 3 4)
(reverse (list 1 2 3))         ; Повертає (3 2 1)

Результат:

• (length (list 1 2 3)) повертає 3
• (append (list 1 2) (list 3 4)) повертає (1 2 3 4)
• (reverse (list 1 2 3)) повертає (3 2 1)

Використання list-ref

Процедура list-ref отримує елемент за вказаним індексом списку (індекс від нуля).

(list-ref lst index)

• lst: список, з якого потрібно отримати елемент.
• index: індекс від нуля, що вказує, який елемент повертати.

Приклад: list-ref

(list-ref (list 10 20 30 40) 2)  ; Отримати елемент з індексом 2

Результат: 30

Вкладені списки

Списки в Scheme можуть містити інші списки як елементи, створюючи вкладену структуру.

Приклад: створення вкладеного списку

(define nested-list (list (list 1 2) (list 3 4) (list 5)))

• Створює список із трьох елементів, кожен з яких сам по собі є списком.

Результат: ((1 2) (3 4) (5))

Доступ до вкладених даних

Щоб отримати доступ до елементів у вкладеному списку, можна використовувати комбінації car та cdr для навігації структурою.

Приклад: доступ до елементів

(car nested-list)              ; Отримати перший елемент: (1 2)
(car (car nested-list))        ; Отримати перший елемент першого підсписку: 1
(cdr (car nested-list))        ; Отримати решту першого підсписку: (2)
(car (cdr (car nested-list)))  ; Отримати другий елемент першого підсписку: 2

Пояснення

1. car nested-list:

   • отримує перший елемент nested-list, який є (1 2).

2. car (car nested-list):

   • отримує перший елемент (1 2), який є 1.

3. cdr (car nested-list):

   • отримує решту (1 2), тобто (2).

4. car (cdr (car nested-list)):

   • отримує перший елемент (2), який є 2.

Приклад: доступ до елементів інших підсписків

(car (cdr nested-list))        ; Отримати другий підсписок: (3 4)
(car (car (cdr nested-list)))  ; Отримати перший елемент другого підсписку: 3

Цей підхід дозволяє систематично переміщатися по вкладеному списку та отримувати доступ до конкретних елементів — це дає потужну гнучкість для роботи з ієрархічними даними.

Резюме

• Списки у Scheme — універсальні та важливі структури даних.
• Використовуйте list для створення списку, car та cdr для доступу до елементів і cons для побудови списків.
• Вбудовані процедури, такі як length, append, reverse та list-ref, роблять операції зі списками простими та ефективними.
• Списки можуть бути вкладеними, створюючи складні структури даних для розширених сценаріїв використання.