Функции от по-висок ред със списъци

Тази лекция е малко по-дълга от повечето. Хайде, предишните бяха за по пет минути. Ще издържиш и една по-голяма, Вярвам в теб!

Преговор

В трета лекция ставаше дума за генератори на функции. Там имаше хубави идеи, но темата все още не е изчерпана. Да погледнем кода от миналия път:

(define (aggregate oper term n step min_n null_value)
    (if (<= n min_n)
        null_value
        (oper
            (term n)
            (aggregate oper term (- n step) step min_n null_value)
        )
    )
)

Процедурата aggregate се извиква по веднъж за всяко от числата от n до min_n, като на всяко от тях съпоставя term, зависещо от n, и накрая извършва операцията oper върху всички получени стойности.
Например, ако ни трябва сумата на числата от 1 до 10, кодът ще изглежда така:
(aggregate + (lambda (x) x) 10 1 0 0)
> 55

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

Така, да започваме

Генератори на списъци

Горният код работи. Освен това, ако смея сам да кажа, е елегантно написан и дава сравнително голяма свобода на програмиста.
Какъв, тогава, е фундаменталният му проблем?
Горният код приема числа и връща числа. Не че с числа може да се правят малко неща, де. Но все пак, за да може да се очаква от програмата да прави нещо различно от прости математически операции, трябва да я направим по-качествена. Само тогава светът отново ще стане ярък и красив.

Връщане на списък

По-наблюдаделните читатели1 ще обединят знанията от предишните няколко лекции и ще се сетят, че term и oper могат да бъдат процедурите car и cons. Тоест, вместо да събираме, умножаваме или каквото там правехме резултатите до момента - можем да си ги направим на списъче. Ето как:

(define (map n step min_n)
    (aggregate cons (lambda x (car x)) n step min_n '())
)

По този начин се получава списък, в който на всяко число от n до min_n през стъпка step се съпоставя (term n).

Функционални инструменти за програмиране

Процедурата неслучайно се казва map. В почти всички езици има такава. Съпоставянето между нещо и нещо друго е много базова част в програмирането въобще. Май е на второ място само след сортирането.

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

Тези функции обикновено се наричат съответно map, filter и reduce2. В по-новите езици се наричат инструменти на функционалното програмиране. В Лисп се наричат инструменти, защото Лисп е толкова стар, че за него Бийтълс не са Ретро3.

Когато става дума за подобни функции, друг често използван термин е list comprehension. Тоест, обработка на списъци4.
Пример, на Python:

[item*2 for item in [1,2,3,4]]
> [2, 4, 6, 8]

И на Ruby:
[1, 2, 3, 4].map { |item| item*2 }
> [2, 4, 6, 8]

Чу ли това, Lisp? Какво правят другите езици? Нима ще ги оставиш да им се размине? Нито пък аз.
Време е да си напишем качествена map процедура. Тя ще приема списък и процедура, ще съпоставя на всеки от елементите му резултата от процедурата извикана с този елемент и ще връща списък от тези резултати.

Приемане на списък

Този път вече няма да ни се размине - ще трябва да модифицираме вече написания код.
Как може да се направи така, че да работи програмата със списък, вместо с интервала $[min_n, n]$?
Това наистина е интересен въпрос и ако държиш да се развиваш самостоятелно в ученията си, бих ти препоръчал в този момент да спреш да четеш и да се върнеш когато в главата ти се е оформила идеята. Иначе, на следващия ред просто ще го кажа, няма проблем.

В момента прехода от един елемент към следващия се изчислява по възможно най-елементарния начин - от текущия елемент се изважда стъпката. Това, което искаме, е на текущия елемент да му се взема cdr-то. Тоест, да се взема следващия елемент в списъка, с който работим. Ще предефинираме стъпката, значи:

(define (map lst term)
    (if (null? lst)
        '()
        (cons
            (term (car lst))
            (map (cdr lst) term)
        )
    )
)

Това принципно работи и може да се извика с:
(map (list 1 2 3 4) (lambda (x) (* x 2)))
> (2 4 6 8)

Забележи, че се казва lambda (x). Това означава, че ламбдата приема точно един аргумент.
Обърни внимание, че това няма да работи за:
(map (list 1 2 3 4) (lambda x (* x 2)))
> *: expects type <number> as 1st argument, given: (1); other arguments were: 2

Ако беше казано lambda x, Scheme щеше да реши не че се подава един аргумент, а един списък с всичките аргументи на функцията. Такава функция може да се извика с произволен брой аргументи (оставям на теб да решиш дали това е хубаво или лошо нещо).

Така де, map все още не е достатъчно добре написано. След малко ще си напишем filter и reduce функции - ако и те са като тази, всичко ще го има написано по три пъти. Ако някъде, някога, нещо трябва да се промени, ще трябва да се променя три пъти.
Какво ще стане, когато това се наложи? Ще забравиш. Или въобще няма да го променяш ти и горкото същество, на което се пада честта, ще изгуби часове, може би дни, в дебъгване на глупав проблем, когато се окаже, че подобни функции не се държат…подобно.
Точно затова трябва да се спазва DRY принципът - "Don't Repeat Yourself". Да не говорим, че като го спазваш, реално се напъваш по-малко. Йей, програмиране! :)

Още веднъж, този път с чувство

Сега заедно ще напишем map, filter и reduce процедурите, използвайки една базова процедура, към която трите ще се обръщат. Впрочем, ако очакваш домашно в тази лекция - няма да има. Ако вече се чувстваш като джедай, първо напиши тези три функции и после ела да ги сравниш с моите.

Преди няколко лекции си направихме добре изглеждаща и обмислена aggregate процедура. Съвсем малко работа е нужна там, за да я накараме да работи за списъци. Ще я вземем назаем като прототип за процедура accumulate.
Забележка: Не си мисли, че този стил на работа говори за мързел. На мен в началото така ми се струваше. Това е правилният начин. Ако нещо те съмнява - пробвай се да напишеш всичко без да ползваш готов код, започвайки от нулата. Виж колко време ще ти отнеме. И виж дали няма да има бъгове. След това сравни с този метод :)

Първо, махаме n и min_n полетата. На тяхно място има един списък - lst. Не го кръщаваме list, защото вече има такава процедура. null_value си остава, защото май ще му намеря приложение.

(define (accumulate term oper null_value lst)
    (if (null? lst)
        null_value
        (oper
            (term (car lst))
            (accumulate term oper null_value (cdr lst))
        )
    )
)

Оттук вече Reduce се пише лесно. Това е функция, приемаща следните аргументи:

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

Тя връща едно нещо, което е резултатът от операцията върху всички елементи на списъка.
Ще си дефинирам една процедурка identity, която ще връща единствения си аргумент непроменен. За по-лесно тестване.

(define (identity x) x)
(define (reduce oper base lst)
  (accumulate identity oper base lst)
)

;Удвоеният сбор на числата в (1 2 3 4):
(reduce + 0
    (map (lambda (x) (* x 2)) (list 1 2 3 4))
)
> 20
(reduce identity * 1 (list 1 2 3 4))
> 24

Няма да е зле да се погрижим за някакви стойности по подразбиране на term, oper, и base, но за момента това не ни е приоритет. Освен това, когато ни стане приоритет, ще трябва да го сменяме само на едно място. Кой е шефа, а?

Сега вече можем да си викаме map само по списък и операция за всеки елемент:

(define (map term lst)
  (accumulate term cons '() lst)
)

(map (lambda (x) (+ (* x 2) 4)) (list 1 2 3 4))
> (6 8 10 12)

А как се прави филтър?

(define (filter pred lst)
    (accumulate identity
        (lambda (x y) (if (pred x) (cons x y) y))
        '() lst
    )
)

(filter (lambda (x) (not (= x 3))) (list 1 2 3 4))
> (1 2 4)

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

Функции от по-висок ред със списъци

Може, ако ни мързи, да си направим процедури, които връщат процедура със съответната операция върху списъци. Те ще приемат всички нужни аргументи, освен списък. Списъкът ще се подава на получената процедура. Така, ако по някаква причина три пъти подред ни трябва да вземем квадратите на числа в списък, няма да е трудно:

(define (reduce_proc oper base)
  (lambda (lst) (reduce oper base lst))
)
(define (map_proc term)
  (lambda (lst) (map term lst))
)
(define (filter_proc pred)
  (lambda (lst) (filter pred lst))
)

(let ((map_square (map_proc (lambda (x) (* x x)))))
  (map_square (map_square (map_square (list 1 2 3 4))))
)
> (1 256 6561 65536)

Задача

Промених си мнението, все пак ще има и нещо за упражнение.
Естествено, това включва написването на map, filter, reduce процедурите, ако още не ти се е получило да се накараш да ги напишеш.
Преправи процедурата accumulate така, че да може да се използва както от днешните три процедури, така и от предишната aggregate, която не работеше със списък, а с n, min_n и step.
За да стане това ще трябва да:


Напиши си и процедури all? и any?. И двете получават като аргументи предикат и списък. Първата връща #t когато предикатът е изпълнен за всеки елемент на списъка, втората - когато е изпълнен поне за един елемент. Иначе връщат #f. Не е нужно да правят каквото и да е ако списъкът е празен.

Ето сорс за това, което беше изписано днес.

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