Списъци

Днес ще си говорим за това, което отличава Lisp/Scheme от нефункционалните езици за програмиране.

Цялостната философия на Lisp

Погледни предишните статии. Има ли нещо, което да ги обединява? Ще ти подскажа - всичките са много кратки. Функционалните езици имат като основна цел и философия опростеността1. А лесен не е същото като елементарен. Днес ще става дума за основната и, до голяма степен, единствена структура от данни в Lisp/Scheme.

Списъкът

Какво е списък от данни? Това е последователност от елементи. Нищо особено. В Lisp списъците са едносвързани. Това означава, че всеки елемент има указател към следващия. Първият сочи към втория, вторият към третия - мисли си за метална верига. Оставяш тази верига да виси за единия край. Тя си е свързана, не се разпада. Но всеки елемент виси само на този точно над него. Ето това е едносвързан списък. Какво ще ни попречи по средата на тази верига, за една от халките2 да закачим друга верига? Абсолютно нищо. Точно така и се прави, в Lisp. Ако си от по-образованите читатели на нашето скромно уики, в главата ти вероятно вече се въртят термини като "ацикличен граф", "дърво", "рекурентна дефиниция". Да, ще стигнем и до тези. Ако ли не - спокойно, така и така никой не харесва ония всезнайковци - направо се радвам, че не си от тях :)
Та, основният градивен елемент в Lisp е cons. В Scheme се казва pair, а в нашата верига се казва халка.
Всеки cons има точно два елемента: car и cdr3. Едното показва какво се държи тук, другото към кой друг елемент е вързан текущият. Ето как би изглеждал кодът за cons на C++:

template <class T>
struct cons
{
    T * data;        //car
    cons * next;    //cdr
}

Всеки списък е едно от две неща:

  • Празен списък. Това е () или още nil. Малко специална стойност за езика, но в момента това не е важно.
  • Списък с първи елемент в car и някакъв друг списък в cdr (там се съдържат всички останали елементи) Първият елемент може да е някакъв атом, т.е. най-малката градивна част на Lisp. Например число, символен низ, nil - стандартните неща. Може да бъде и цял друг списък.

Това е. Нищо повече. Вече знаеш цялата структура на Lisp. Няма дълги обяснения къде можеш или не можеш да декларираш функции, няма типове от данни, нищо. Вече имаш всичко, вече можеш да разбиеш основите на програмисткия свят. Готов ли си? Спокойно, нито пък аз. Днес ще навлизаме с малки, малки стъпки в материала. Но, в общи линии, оттук нататък ще вземаме учудващо хитри техники, които се използват и до днес, в Lisp и в по-модерни езици и правят живота на програмистите лесен и светъл.

Конструиране на списъци

Сега ще се поупражняваме, за да видиш за какво става въпрос и да ти дойдат малко идеи.
Първият, и най-елементарен, начин да се създават списъци е с процедурата cons. На нея се подават два аргумента и тя връща списък с car - първия елемент и cdr - втория. Cdr трябва да е списък (може и празен), car може да е кажи-речи всичко. Тоест, cdr също може да не е списък, но тогава cons няма да създаде списък, а някаква друга глупост.
Cons всъщност връща двойка car/cdr. Което е почти същото като списък. В общи линии разликата е единствено в начина, по който се отпечатва на екрана. Ето примери:

(cons 3 5)
;Това е двойка (car . cdr).
> (3 . 5)
(cons 3 (cons 2 (cons 4 5) ) )
; Печата всички поредни car елементи и към какво cdr сочи последният.
> (3 2 4 . 5)
(cons 3 '() ) )
;Това беше празният списък
> (3)
(cons (cons 3 2) (cons 2 (cons 5 4 ) ) )
> ( (3 . 2) 2  5 . 4 )
(cons (cons 3 '()) (cons 2 (cons 5 '() ) ) )
> ( (3) 2 5)

Когато за cdr се даде някакъв същински списък(proper list), интерпретаторът решава, че вече няма да печата (… . cdr) конструкцията. Основно, защото последният cdr не сочи към нищо. Което е и дефиницията на списък. Пише я горе.

Това е полезно, по принцип, но реално имаме и по-удобна процедура за създаване на списък. Тя е подобаващо именована list. На list се подават произволен брой аргументи и връща списък от тях. Точно толкова елементарно е, колкото звучи.

(list 4)
> (4)
(list 3 5 6 8 9 1337 9001)
> (3 5 6 8 9 1337 9001)
(list (list 1 1) (list 2 3) (list 5 8) (list 13 21) )
> ((1 1) (2 3) (5 8) (13 21))

Освен това, елементите на списък може да се достъпват поотделно. Ето как.

Всички възможни начини да се извика елемент на списък

Ако за нещо ни трябва, можем да вземем само car или само cdr елемента на списък. Това става с процедурите car и cdr4.

; За примерите ще използваме списъка l
; Процедурата display печата първия си аргумент на екрана
(let ((l (list 1 2 3 4 5)))
(display (car l) )    ; Връща първия елемент
> 1
(display (cdr l) )    ; Връща всички останали елементи
> (2 3 4 5)
(display (car (cdr l)) )    ; Връща втория елемент
> 2
)

Освен car и cdr, има няколко помощни функции, дефинирани за удобство. Ако в някой момент ни трябва вторият елемент на списък, тоест (car (cdr l)), може просто да се използва cadr. По същия начин, вместо (cdr (car l )) - (cdar l).
До 3 букви могат да се използват.
car, cdr,
caar, cdar, cadr, cddr,
caaar, caadr, cadar, caddr, cdaar, cdadr, cddar, cdddr
Са все валидни функции в Lisp. Измислени са, за да може да полудееш по-бързо и ефективно. Пък и, трябва да признаеш, едно е да получиш грешка "bad argument 1 for function ‘isprime(int)’" в C++. Съвсем друго е "cdadr: expects argument of type <cdadrable value>". Не можеш да биеш cdadrable value.

Последното нещо, което имам да ти кажа днес е как да си променяш съществуващ списък в движение. set-car! и set-cdr!. Имат удивителни накрая. Работят точно както се очаква. За тях няма set-caddr!, и слава Богу.

(let ((l (list 1 2 3 4 5)))
(set-car! l '())
(display l)
> (() 2 3 4 5)
(set-car! (cddr l) '())
(display l)
> (() 2 () 4 5)
(set-cdr! (cddr l) '())
(display l)
> (() 2 ())
)

Упражнения

  • Създай процедура, която по дадено число N връща списък от първите N прости числа.
  • Напиши процедура, която по даден списък с числа връща нов списък, състоящ се само от простите числа в предишния.

За запознатите с теорията на графите.

  • Двоично дърво се моделира в Scheme сравнително елементарно.

( ((2) (3)) (4) ) е един пример. Това е дърво с листа 2, 3 и 4, като 4 директно следва корена, а 2 и 3 са едно ниво по-ниско. За двоично дърво с листа, които са числа, напиши процедура, която да намира сумата на листата.

  • Или, ако си оптимист, да извършва предварително подадена операция върху листата (в частност - сума).
  • Или, ако си голям оптимист, да връща списък от листата на дървото, върху който да може да се извършват операции, в частност - сума.
  • Или, ако просто нямаш какво друго да правиш - да работи за произволно дърво, не само за двоично.

Ако задачите са трудни - спокойно. Следващия път ще се занимаваме с точно такива неща.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License