Секвенце

Секвенца је уређена колекција вредности. Секвенца је снажна, основна апстракција у рачунарству. Секвенце нису инстанце одређеног уграђеног типа или апстрактне представе податка, већ скуп понашања која су заједничка за неколико различитих типова података. То јест, постоји много врста секвенци, али све оне имају заједничко понашање. Нарочито,

• Дужина: секвенца има коначну дужину, а дужина празне секвенце је 0.

• Избор чланова: секвенца поседује чланове који одговарају ненегативним целобројним индексима мањим од њене дужине, где је са 0 означен први члан.

Пајтон обухвата неколико изворних типова података који су секвенце од којих је вероватно најважнији низ.

Низови

Низ је секвенца која може имати произвољну дужину. Низови имају широк скуп уграђених понашања, заједно са специфичном синтаксом за изражавање тих понашања. Већ су виђени литерал низа који се вреднује у инстанцу низа, као и израз за одабир чланова који се вреднује у вредност унутар низа. Уграђена функција len враћа дужину секвенце. У наставку, цифре су низ од четири члана. Члан на индексу 3 је 8.

>>> цифре = [1, 8, 2, 8]
>>> len(цифре)
4
>>> цифре[3]
8

Поред тога, низови се могу међусобно сабирати и множити целим бројевима. За низове, сабирање и множење не сабирају и не множе чланове, већ уместо тога спајају и умножавају саме секвенце. То јест, функција add из модула operator (као и + оператор) даје низ који је спој сабраних аргумената. Функција mul из модула operator (као и * оператор) узимају низ и цео број k, а враћају низ који се састоји из k понављања улазног низа.

>>> [2, 7] + цифре * 2
[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]

Било које вредности могу бити стављене у низ, укључујући ту и друге низове. Одабир чланова се може применити више пута како би се у низу низова одабрали дубље угнежђени чланови.

>>> парови = [[10, 20], [30, 40]]
>>> парови[1]
[30, 40]
>>> парови[1][0]
30

Пролазак кроз секвенце

У многим случајевима, корисно би било пролазити кроз чланове неке секвенце и извршити неко рачунање за сваки члан. Овај шаблон се до те мере често среће да Пајтон поседује додатну управљачку наредбу за обраду секвенцијалних података: for наредбу.

Размотрити задатак бројања колико пута се нека вредност појављује у секвенци. Могуће је имплементирати функцију за рачунање овог броја користећи while петљу.

>>> def бројПојављивања(секвенца, вредност):
...     """Враћа број појављивања вредности унутар секвенце."""
...     укупно, индекс = 0, 0
...     while индекс < len(секвенца):
...         if секвенца[индекс] == вредност:
...             укупно = укупно + 1
...         индекс = индекс + 1
...     return укупно

>>> бројПојављивања(цифре, 8)
2

Наредба for у Пајтону може поједноставити тело ове функције тако што ће директно пролазити кроз вредности чланова, а да не уводи име индекс уопште.

>>> def бројПојављивања(секвенца, вредност):
...     """Враћа број појављивања вредности унутар секвенце."""
...     укупно = 0
...     for члан in секвенца:
...         if члан == вредност:
...             укупно = укупно + 1
...     return укупно

>>> бројПојављивања(цифре, 8)
2

Наредба for састоји се из једне клаузуле у облику:

for <име> in <израз>:
    <пакет>

Наредба for се извршава пратећи следећи поступак:

1. Вредновати заглавље <израз> које мора давати итерирајућу вредност.

2. За сваку вредност члана те итерирајуће вредности, редоследом:

   1. Повезати <име> на ту вредност у тренутном оквиру.

   2. Извршити <пакет>.

Овај поступак извршења помиње итерирајуће вредности. Низови су врста секвенце, а секвенце су итерирајуће вредности. Њихови чланови се разматрају по редоследу. Пајтон укључује и друге итерирајуће типове, али засад ће секвенце бити у жижи, док ће општа дефиниција појма „итерирајући” бити разматрана у одељку о итераторима у оквиру последњег поглавља.

Важна последица претходног поступка вредновања је да ће <име> остати повезано на последњи члан секвенце након што је for наредба извршена. Додатно, for петља уводи још један начин ажурирања окружења кроз ову наредбу.

Распакивање секвенце

Уобичајени шаблон у програмима је да постоји секвенца чланова који су и сами секвенце, али сви тачно одређене дужине. Наредба for може укључити више имена у своје заглавље како би „распаковала” сваку подсеквенцу у њој одговарајуће чланове. Примера ради, можемо имати низ двочланих низова:

>>> парови = [[1, 2], [2, 2], [2, 3], [4, 4]]

и жељу да се изброје сви парови код којих су први и други члан међусобно једнаки.

>>> бројЈеднаких = 0

Следећа for наредба која садржи два имена у свом заглављу ће повезати свако од имена x и y на први и други члан сваког пара, респективно.

>>> for x, y in парови:
...     if x == y:
...         бројЈеднаких = бројЈеднаких + 1

>>> бројЈеднаких
2

Овај шаблон повезивања више имена на више вредности у секвенцама тачно одређене дужине се назива распакивање секвенце и заправо је потпуно исти шаблон који је већ виђен код наредбе доделе која повезује вишеструка имена на вишеструке вредности.

Распони

Распон, односно range је још један уграђени тип секвенце у Пајтону који представља распон целих бројева. Распони се стварају помоћу range који прима два целобројна аргумента: први број и један након последњег броја у жељеном распону.

>>> range(1, 10)  # Укључује 1, али не и 10.
range(1, 10)

Позивање конструктора низа list над распоном вреднује се у низ са истим члановима као и распон, тако да је могућ лак преглед свих чланова.

>>> list(range(5, 8))
[5, 6, 7]

Уколико је задат само један аргумент, он се тумачи као један изнад последње вредности у распону који почиње нулом.

>>> list(range(4))
[0, 1, 2, 3]

Распони се обично појављују као израз у for заглављима како би се одредио број извршавања пакета наредби који следи. Уобичајени договор је да се користи један знак за подвлачење (односно, доња црта) за име у заглављу ако се то име не појављује у пакету наредби који следи:

>>> for _ in range(3):
...     print('Напред, Звездо!')
Напред, Звездо!
Напред, Звездо!
Напред, Звездо!

Што се тиче интерпретатора, подвлака, то јест доња црта, је само још једно од имена у окружењу, али према договору међу програмерима означава име које се неће појавити у будућим изразима који следе.

Обрада секвенци

Секвенце су до те мере чест облик сложених података да су понекад цели програми организовани око ове једне апстракције. Модуларни делови програма који имају секвенце као своје улазе и излазе могу бити мешани и упаривани како би се извршила нека обрада података. Сложени делови могу бити дефинисани међусобним уланчавањем операција обраде секвенци од којих је свака једноставна и усредсређена, односно има јасну намену.

Низовна убрајања

Многе операције обраде секвенци могу се изразити кроз вредновање, односно интерпретацију израза за сваки члан секвенце, и потоње прикупљање добијених вредности у резултујућу секвенцу. У Пајтону, низовно убрајање је израз који изводи једно такво израчунавање.

>>> непарни = [1, 3, 5, 7, 9]
>>> [x+1 for x in непарни]
[2, 4, 6, 8, 10]

Из разлога што се налази унутар угластих заграда, кључна реч for није део for наредбе већ уместо тога део такозваног низовног убрајања . Подизраз x+1 се вреднује, то јест интерпретира са x повезаним на сваки члан низа непарни и тако добијене вредности се прикупљају у низ.

Друга уобичајена операција обраде секвенци јесте избор подскупа вредности које задовољавају неки услов. Убрајања низа такође могу изразити овај шаблон, на пример бирање свих чланова из низа непарни који су делиоци броја 25.

>>> [x for x in непарни if 25 % x == 0]
[1, 5]

Општи облик низовног убрајања је:

[<израз пресликавања> for <име> in <израз секвенце> if <израз филтера>]

Да би се вредновало низовно убрајање, Пајтон најпре вреднује <израз секвенце> који мора да враћа итерирајућу вредност. Затим, пратећи редослед, вредност сваког члана се везује на <име>, вреднује се израз филтера и ако даје вредност тачно, вреднује се израз пресликавања. Најзад, вредности израза пресликавања се прикупљају у низ.

Агрегација

Трећи уобичајени шаблон у обради секвенци је агрегација односно здруживање или обједињавање свих вредности из секвенце у једну вредност. Уграђене функције sum, min, и max су само неки од примера агрегационих функција.

Комбиновањем шаблона вредновања израза за сваки члан, одабиром подскупа чланова, и обједињавањем чланова, могуће је решавање задатака и проблема користећи се приступом обраде секвенци.

Савршен број је природан број који је једнак збиру својих правих делилаца (укључујући и јединицу). Прави делиоци броја \(n\) су природни бројеви мањи од \(n\) који деле \(n\) без остатка. Списак делиоца броја \(n\) може се изразити преко убрајања низа.

>>> def делиоци(n):
...     return [1] + [x for x in range(2, n) if n % x == 0]

>>> делиоци(4)
[1, 2]
>>> делиоци(12)
[1, 2, 3, 4, 6]

Користећи функцију делиоци могу се пронаћи сви савршени бројеви до хиљаду помоћу другог низовног убрајања. Понекада се и број 1 рачуна у савршене бројеве, али ипак не задовољава горњу дефиницију правих делиоца. На овом месту ће бити ипак урачунат као савршени број због следећег примера.

>>> [n for n in range(1, 1000) if sum(делиоци(n)) == n]
[1, 6, 28, 496]

Може се поново искористити дефиниција делиоци за решавање другог задатка у коме се тражи минималан обим правоугаоника са целобројним дужинама страница, уколико је задата његова површина. Површина правоугаоника једнака је производу његове висине и ширине. Отуда, ако је задата површина и висина правоугаоника,, могуће је израчунати ширину. Може се извршити провера да и ширина и висина деле површину без остатка како би се осигурало да су странице правоугаоника целобројне.

>>> def ширина(површина, висина):
...     assert површина % висина == 0
...     return површина // висина

Обим правоугаоника једнак је збиру дужина његових страница.

>>> def обим(ширина, висина):
...     return 2 * ширина + 2 * висина

Висина правоугаоника са целобројним дужинама страница мора бити делилац његове површине. Минимални обим може се израчунати узимајући у обзир све целобројне висине.

>>> def минималниОбим(површина):
...     висине = делиоци(површина)
...     обими = [обим(ширина(површина, висина), висина) for висина in висине]
...     return min(обими)

>>> површина = 80
>>> ширина(површина, 5)
16
>>> обим(16, 5)
42
>>> обим(10, 8)
36
>>> минималниОбим(површина)
36
>>> [минималниОбим(n) for n in range(1, 10)]
[4, 6, 8, 8, 12, 10, 16, 12, 12]

Функције вишег реда

Уобичајени шаблони посматрани у оквиру обраде секвенци могу се изразити преко функција вишег реда. Прво, вредновање израза за сваки члан у секвенци може се изразити применом функције на сваки члан.

>>> def примениНаСве(функцијаПресликавања, секвенца):
...     return [функцијаПресликавања(x) for x in секвенца]

Избор чланова за које је неки израз истинит може се изразити применом функције на сваки члан секвенце.

>>> def задржиПодУсловом(функцијаФилтрирања, секвенца):
...     return [x for x in секвенца if функцијаФилтрирања(x)]

Коначно, многи облици агрегације, то јест здруживања могу се изразити кроз узастопну примену двоаргументне функције на већ донекле сведену вредност и сваки следећи члан по редоследу.

>>> def reduce(функцијаЗдруживања, секвенца, почетнаВредност):
...     вредност = почетнаВредност
...     for x in секвенца:
...         вредност = функцијаЗдруживања(вредност, x)
...     return вредност

Примера ради, претходна функција се може користити за множење свих чланова секвенце. Користећи mul као функцијаЗдруживања и 1 као почетнаВредност, функција reduce множи све бројеве из секвенце.

>>> from operator import mul
>>> reduce(mul, [2, 4, 8], 1)
64

Савршени бројеви могу се пронаћи такође и помоћу ових функција вишег реда.

>>> def делитељи(n):
...     делитељ = lambda x: n % x == 0
...     return [1] + задржиПодУсловом(делитељ, range(2, n))

>>> делитељи(12)
[1, 2, 3, 4, 6]
>>> from operator import add
>>> def збирДелилаца(n):
...     return reduce(add, делитељи(n), 0)

>>> def савршенБрој(n):
...     return збирДелилаца(n) == n

>>> задржиПодУсловом(савршенБрој, range(1, 1000))
[1, 6, 28, 496]

Уобичајени називи

У рачунарској заједници, чешћи назив за примениНаСве је map, а чешћи назив за задржиПодУсловом је filter. У Пајтону, уграђене функције map и filter су уопштења ових функција која не враћају низове. Више речи о овим функцијама биће у оквиру последњег поглавља. Горе наведене дефиниције су еквивалентне примени list конструктора на резултат позива уграђених map и filter функција.

>>> примениНаСве = lambda функцијаПресликавања, с: list(map(функцијаПресликавања, с))
>>> задржиПодУсловом = lambda функцијаФилтрирања, с: list(filter(функцијаФилтрирања, с))

Функција reduce је уграђена у functools модул из Пајтонове стандардне библиотеке. У тој верзији, аргумент почетнаВредност није обавезан.

>>> from functools import reduce
>>> def производ(секвенца):
...     return reduce(mul, секвенца)

>>> производ([1, 2, 3, 4, 5])
120

У Пајтон програмима, чешће се срећу непосредна низовна убрајања него функције вишег реда, али се може слободно рећи да су оба приступа обради секвенци широко распрострањена.

Апстракција секвенце

Представљена су два изворна типа података која задовољавају апстракцију секвенце: низови и распони. Оба задовољавају услове којима је започет овај одељак: дужину и избор чланова. Пајтон укључује још два понашања секвентних типова која обогаћују и проширују апстракцију секвенце.

Чланство

Може се извршити провера одређене вредности на чланство у секвенци. Пајтон поседује два оператора in и not in који се вреднују у True или False у зависности од тога да ли се члан појављује у секвенци или не.

>>> цифре
[1, 8, 2, 8]
>>> 2 in цифре
True
>>> 1828 not in цифре
True

Одсецање

Унутар себе, секвенце садрже краће подсеквенце. Такозвани одрезак секвенце је ма који исечак суседних чланова изворне секвенце, означен паром целих бројева. Баш као и код range конструктора, први цео број означава почетни индекс одреска, док други означава један индекс након завршетка истог.

У Пајтону, одсецање секвенци је изражено на сличан начин као и избор елемената, користећи угласте заграде. Почетни и крајњи индекс раздвојени су двотачком. По претпоставци, за сваку изостављену границу узима се крајња вредност, односно, 0 за почетни индекс, а дужина секвенце за крајњи индекс.

>>> цифре[0:2]
[1, 8]
>>> цифре[1:]
[8, 2, 8]

Набрајање ових додатних понашања апстракција секвенци у Пајтону даје прилику за осврт на тему из чега се све састоје корисне апстракције података. Богатство апстракције (то јест, колико понашања укључује) има и своје последице. За кориснике апстракције, додатна понашања свакако могу бити корисна. С друге стране, задовољавање свих захтева богатих апстракција неким новим типом података може бити изазовно. Још једна негативна последица богатих апстракција може бити и та да је корисницима потребно више времена да их науче и савладају.

Секвенце имају богату апстракцију зато што су до те мере распрострањене и свеприсутне у израчунавањима да је учење неколико сложених понашања више него оправдано и, на дужи рок, увек исплативо. Међутим, уопштено говорећи, за велику већину кориснички дефинисаних апстракција важи да треба да буду што је могуће једноставније.

Додатна литература: нотација одсецања прихвата разноразне случајеве као што су негативне почетне или крајње вредности, као и величине корака. Потпун опис се појављује у одељку интернет књиге Dive Into Python 3 о изворним типовима података. У овом поглављу ће бити коришћене само претходно описане основне функције.

Ниске

Текстуалне вредности су можда фундаменталније у рачунарству чак и од самих бројева. Као пример претходне тврдње, рачунарски програми су обично пишу и чувају у текстуалном облику. Изворни тип података за текст у Пајтону назива се ниска, а str му је припадајући конструктор.

Много је појединости о томе како су ниске представљене, изражене и манипулисане у Пајтону. Ниске су још један пример богатих апстракција које захтевају значајнију посвећеност од стране програмера да би се савладале и како би њима у потпуности овладало. Овај одељак служи као сажети увод у основна понашања ниски.

Литерали ниске могу изражавати произвољни текст који се налази или између једноструких или између двоструких наводника.

>>> 'Ја сам ниска.'
'Ја сам ниска.'
>>> "А ја сам Д'Артањан и садржим апостроф!"
"А ја сам Д'Артањан и садржим апостроф!"
>>> '您好'
'您好'

Ниске су се већ појављивале у досадашњим изворним кодовима, као докниске, унутар print позива, и као поруке о грешци у assert наредбама провере.

Ниске задовољавају два основна услова секвенце која су уведена на почетку овог одељка: имају своју дужину и подржавају избор чланова.

>>> град = 'Крагујевац'
>>> len(град)
10
>>> град[7]
'в'

Чланови ниске су и сами ниске које садрже само један знак. Знак представља било које слово неког алфабета (односно азбуке, абецеде, и других писама), интерпункцијски знак или други симбол. За разлику од многих других програмских језика, Пајтон нема посебан знаковни тип податка: било који текст је ниска, а ниске које представљају појединачне знакове имају јединичну дужину.

Као и низови, ниске се такође могу комбиновати сабирањем и множењем.

>>> 'Крагујевац' + ', Шумадија'
'Крагујевац, Шумадија'
>>> 'кус' * 2
'кускус'

Чланство

Понашање ниски разликује се од осталих секвентних типова у Пајтону. Апстракција ниске не одговара пуној апстракцији секвенце која је описана за низове и распоне. Конкретно, оператор чланства in применљив је и на ниске, али има потпуно другачије понашање од оног када се примењује на друге секвенце. Заправо овај оператор врши проверу присуства подниске, уместо појединачних чланова.

>>> 'де је' in "Где је Гиле?"
True

Вишередни литерали

Ниске нису ограничене на само један ред. Троструки знакови навода обухватају литерале ниске који се протежу у више редова. Ови троструки наводници су већ обимно коришћени у докнискама.

>>> """The Zen of Python
... claims, "Readability counts."
... Read more: import this."""
'The Zen of Python\nclaims, "Readability counts."\nRead more: import this.'

У горњем испису \n је један члан ниске који представља симбол за нови ред. Иако се појављује као двознак (обрнута коса црта и мало латинично слово n), ипак се рачуна као један за потребе одређивања дужине ниске и избора њених чланова.

Претварање у ниску

Ниска се може створити из било ког другог објекта у Пајтону позивањем str конструкторске функције са вредношћу објекта као аргументом. Ова одлика ниски корисна је за прављење описних ниски полазећи од објеката различитих типова.

>>> str(2) + ' је један од чланова низа ' + str(цифре)
'2 је један од чланова низа [1, 8, 2, 8]'

Додатна литература: кодирање текста у рачунарима је сложена тема. У овом поглављу, детаљи о представи ниски ће бити изапстраковани. Међутим, за многе примене, од изузетне су важности све појединости о томе како се ниске кодирају унутар самог рачунара. Поглавље о нискама у интернет књизи Dive Into Python 3 даје ближи опис кодирања знакова.

Стабла

Могућност да се низови користе као чланови других низова пружа ново средство за комбиновање у програмском језику. Ова способност обично се зове својство затворења типа података. Уопштено говорећи, метода комбиновања вредности има својство затворења ако резултат комбиновања може и сам бити комбинован помоћу исте методе. Затворење је извор снаге у било ком начину комбинације јер омогућава стварање хијерархијских структура – структура састављених из делова који су и сами састављени из делова и тако даље.

У дијаграмима окружења низови се могу визуализовати помоћу нотације са кућицама и показивачима. Низ је приказан преко узастопних правоугаоних поља, односно кућица које садрже чланове низа. Примитивне вредности као што су бројеви, ниске, логичке вредности, и None појављују се као чланови уоквирени кућицом. Сложене вредности, као што су вредности функција и други низови, означене су стрелицом, то јест показивачем.

Угнежђивање низова унутар других низова може унети неке сложености. Такозвано стабло је основна апстракција података која намеће правилност у хијерархијском структуирању и манипулисању вредностима.

Стабло има корен и секвенцу грана. Свака грана стабла је и сама стабло. Стабло без грана назива се лист. Свако стабло које се налази унутар стабла зове се подстабло датог стабла (као на пример, грана гране). Корен сваког подстабла неког стабла назива се чвором у том стаблу.

Апстракција података за стабло састоји се из конструктора стабло и селектора ознака и гране. Почећемо с поједностављеном верзијом.

>>> def стабло(корен, гране=[]):
...     for грана in гране:
...         assert даЛиЈеСтабло(грана), 'гране морају бити стабла'
...     return [корен] + list(гране)

>>> def ознака(стабло):
...     return стабло[0]

>>> def гране(стабло):
...     return стабло[1:]

Стабло је добро формирано само ако има ознаку корена и све гране које су такође стабла. Функција даЛиЈеСтабло се примењује у конструктору стабло како би се извршила провера јесу ли и све гране стабла добро формиране.

>>> def даЛиЈеСтабло(стабло):
...     if type(стабло) != list or len(стабло) < 1:
...         return False
...     for грана in гране(стабло):
...         if not даЛиЈеСтабло(грана):
...             return False
...     return True

Функција даЛиЈеЛист проверава да ли стабло има гране или не.

>>> def даЛиЈеЛист(стабло):
...     return not гране(стабло)

Стабла могу бити направљена угнежђеним изразима. Следеће стабло с има ознаку корена 3 и две гране.

>>> с = стабло(3, [стабло(1), стабло(2, [стабло(1), стабло(1)])])
>>> с
[3, [1], [2, [1], [1]]]
>>> ознака(с)
3
>>> гране(с)
[[1], [2, [1], [1]]]
>>> ознака(гране(с)[1])
2
>>> даЛиЈеЛист(с)
False
>>> даЛиЈеЛист(гране(с)[0])
True

Рекурзивна стабла се као функције могу користити за изградњу стабала. Примера ради, \(n\)-ти Фибоначијев број има ознаку корена \(n\)-тог Фибоначијевог броја и, за \(n > 1\), две гране које су такође Фибоначијева стабла. Фибоначијево стабло илуструје рекурзивно стабло израчунавања Фибоначијевог броја.

>>> def фибСтабло(n):
...     if n == 0 or n == 1:
...         return стабло(n)
...     else:
...         лева, десна = фибСтабло(n-2), фибСтабло(n-1)
...         фиб_n = ознака(лева) + ознака(десна)
...         return стабло(фиб_n, [лева, десна])
>>> фибСтабло(5)
[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]

Функције стабла рекурзије се такође користе за обраду стабала. На пример, функција избројЛистове броји и враћа колико стабло има листова.

>>> def избројЛистове(стабло):
...     if даЛиЈеЛист(стабло):
...         return 1
...     else:
...         бројЛистоваПоГранама = [избројЛистове(b) for b in гране(стабло)]
...         return sum(бројЛистоваПоГранама)
>>> избројЛистове(фибСтабло(5))
8

Стабла партиција

Стабла се такође могу користити за представљање партиција природног броја. Стабло партиција природног броја \(n\) користећи се бројевима не већим од \(m\) је бинарно (двограно) стабло које представља изборе начињене током рачунања. У стаблу партиција:

• лева грана (индекс 0) садржи све начине партиционисања броја \(n\) користећи најмање једно \(m\),

• десна грана (индекс 1) садржи све партиције које користе делове до \(m-1\), и

• ознака корена је \(m\).

Ознаке листова стабла партиција изражавају да ли путања од корена до листа представља успешну поделу природног броја \(n\).

>>> def стаблоПартиција(n, m):
...     """Враћа стабло партиција за n користећи делове не веће од m."""
...     if n == 0:
...         return стабло(True)
...     elif n < 0 or m == 0:
...         return стабло(False)
...     else:
...         лева = стаблоПартиција(n-m, m)
...         десна = стаблоПартиција(n, m-1)
...         return стабло(m, [лева, десна])

>>> стаблоПартиција(2, 2)
[2, [True], [1, [1, [True], [False]], [False]]]

Испис партиција из стабла партиција је још један рекурзивни процес којим се обилази стабло, градећи сваку партицију у виду низа. Кад год се дође до листа True партиција се исписује.

>>> def исписПартиција(tree, партиција=[]):
...     if даЛиЈеЛист(tree):
...         if ознака(tree):
...             print(' + '.join(партиција))
...     else:
...         лева, десна = гране(tree)
...         m = str(ознака(tree))
...         исписПартиција(лева, партиција + [m])
...         исписПартиција(десна, партиција)

>>> исписПартиција(стаблоПартиција(6, 4))
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

Одсецање се такође може користити на гранама стабла. На пример, могуће је да се пожели постављања ограничења на број грана у стаблу. Бинарна стабла имају највише две гране. Уобичајена трансформација стабла под именом бинаризација проналази бинарно стабло са истим ознакама као и оригинално стабло груписањем грана.

>>> def деснаБинаризација(с):
...     """Прави десно-разгранато бинарно стабло."""
...     return стабло(ознака(с), бинаризацијаГрана(гране(с)))

>>> def бинаризацијаГрана(низГрана):
...     """Бинаризација низа грана."""
...     if len(низГрана) > 2:
...         прва, остале = низГрана[0], низГрана[1:]
...         return [деснаБинаризација(прва), бинаризацијаГрана(остале)]
...     else:
...         return [деснаБинаризација(грана) for грана in низГрана]

>>> деснаБинаризација(стабло(0, [стабло(x) for x in [1, 2, 3, 4, 5, 6, 7]]))
[0, [1], [[2], [[3], [[4], [[5], [[6], [7]]]]]]]

Уланчане листе

До сада су само изворни типови коришћени за представљање секвенци. Међутим, такође се могу развити представе секвенци које нису уграђене у Пајтон. Уобичајена представа секвенце изграђене од угнежђених парова назива се уланчана листа. Дијаграм оркужења у наставку илуструје представу преко уланчане листе четворочлане секвенце која садржи 1, 2, 3 и 4.

>>> четири = [1, [2, [3, [4, 'празно']]]]

Уланчана листа је пар који садржи први члан секвенце (у овом случају 1) и остатак секвенце (у овом случају представа 2, 3, 4). Други члан је такође уланчана листа. Остатак најугнежђеније уланчане листе која садржи само 4 је празно, вредност која представља празну уланчану листу.

Уланчане листе имају рекурзивну структуру: остатак уланчане листе је уланчана листа или 'празно'. Може се дефинисати апстрактна представа података за валидацију, конкструкцију и избор компоненти уланчаних листа.

>>> празно = 'празно'
>>> def даЛиЈеУланчанаЛиста(с):
...     """с је уланчана листа ако је празна или ако је уређени пар (први, остатак)."""
...     return с == празно or (len(с) == 2 and даЛиЈеУланчанаЛиста(с[1]))

>>> def уланчанаЛиста(први, остатак):
...     """Направи уланчану листу од првог члана и остатка."""
...     assert даЛиЈеУланчанаЛиста(остатак), "остатак мора бити уланчана листа."
...     return [први, остатак]

>>> def први(с):
...     """Враћа први члан уланчане листе с."""
...     assert даЛиЈеУланчанаЛиста(с), "први је применљив само на уланчане листе."
...     assert с != празно, "празна уланчана листа нема први члан."
...     return с[0]

>>> def остатак(с):
...     """Враћа остатак чланова уланчане листе с."""
...     assert даЛиЈеУланчанаЛиста(с), "остатак је применљив само на уланчане листе."
...     assert с != празно, "празна уланчана листа нема остатак."
...     return с[1]

Горе, уланчанаЛиста је конструктор, а први и остатак су селектори за апстрактну представу податка уланчаних листа. Услов понашања за уланчане листе јесте да и за њих, попут пара, важи да су конструктор и селектори инверзне функције.

• Ако је уланчана листа с направљена из првог члана п и уланчане листе о, тада први(с) враћа п, а остатак(с) враћа о.

Конструктор и селектори се могу користити за манипулацију уланчаним листама.

>>> четири = уланчанаЛиста(1, уланчанаЛиста(2, уланчанаЛиста(3, уланчанаЛиста(4, празно))))
>>> први(четири)
1
>>> остатак(четири)
[2, [3, [4, 'празно']]]

Претходна имплементација ове врсте апстрактних података користи парове који су заправо двочлани низови. Вреди напоменути да је такође било могуће имплементирати парове користећи функције, а како је имплементација уланчаних листа могућа коришћењем било каквих парова, следи да је било изводљиво имплементирати уланчане листе користећи се само функцијама.

Уланчана листа може да смешта секвенцу вредности у редуследу, али још увек није показано да задовољава услове апстракције секвенци. Користећи апстрактну представу података која је дефинисана, могу се имплементирати два понашања која карактеришу секвенце: дужина и избор чланова.

>>> def дужинаУланчанеЛисте(с):
...     """Враћа дужину уланчане листе с."""
...     дужина = 0
...     while с != празно:
...         с, дужина = остатак(с), дужина + 1
...     return дужина

>>> def вратиЧланУланчанеЛисте(с, и):
...     """Враћа члан под индексом и уланчане листе с."""
...     while и > 0:
...         с, и = остатак(с), и - 1
...     return први(с)

Сада се може оперисати уланчаним листама као секвенцама користећи ове функције. (Још увек није дозвољено коришћење уграђене len функције, синтаксе за одабир чланова, или for наредбе, али ће ускоро и то бити омогућено.)

>>> дужинаУланчанеЛисте(четири)
4
>>> вратиЧланУланчанеЛисте(четири, 1)
2

Низ дијаграма окружења у наставку илуструје итеративни процес којим вратиЧланУланчанеЛисте проналази члан 2 на идексу 1 унутар уланчане листе. .. Испод је уланчана листа четири дефинисана користећи Пајтон примитиве како би се поједноставили дијаграми. Овај избор имплементације крши апстракцијске баријере, али омогућава лакши увид у процес израчунавања за овај пример. Најпре је функција вратиЧланУланчанеЛисте позвана, стварајући локални оквир. Израз у заглављу while наредбе вреднује се као тачан, што узрокује извршавање наредбе доделе из увученог while пакета. Функција остатак враћа уланчану подлисту која почиње са 2.

Затим, локални назив с ће бити ажуриран како би се односио на уланчану подлисту која почиње другим чланом оригиналне уланчане листе. Вредновање израза из while заглавља сада даје нетачну вредност па Пајтон интерпретира израз с десне стране return наредбе у последњој линији вратиЧланУланчанеЛисте функције.

Крајњи дијаграм окружења приказује локални оквир за позив функције први, који садржи име с повезано на исту уланчану подлисту. Функција први селектује вредност 2 и враћа је, а иста вредност ће бити враћена и од стране вратиЧланУланчанеЛисте.

Овај пример показује уобичајени шаблон израчунавања са уланчаним листама, где сваки следећи корак у итерацији обрађује све краће суфиксе оригиналне уланчане листе. Ова постепена обрада ради проналажења дужине и чланова уланчаних листа изискује неко време израчунавања. Пајтонови уграђени типови секвенци су имплементирани на другачији начин у коме за израчунавање дужине секвенце и за дохватање њених чланова сложеност и цена израчунавања нису тако високи. Појединости те представе су ван оквира овог текста.

Рекурзивна обрада

Обе функције, и дужинаУланчанеЛисте и вратиЧланУланчанеЛисте су итеративне. Оне скидају сваки слој угнежђеног пара све док се не дође до краја (у дужинаУланчанеЛисте) или жељеног члана (у вратиЧланУланчанеЛисте) уланчане листе. Дужина и избор чланова се такође могу имплементирати користећи се рекурзијом.

>>> def дужинаУланчанеЛистеРекурзивно(с):
...     """Враћа дужину уланчане листе с."""
...     if с == празно:
...         return 0
...     return 1 + дужинаУланчанеЛистеРекурзивно(остатак(с))

>>> def вратиЧланУланчанеЛистеРекурзивно(с, и):
...     """Враћа члан под индексом и уланчане листе с."""
...     if и == 0:
...         return први(с)
...     return вратиЧланУланчанеЛистеРекурзивно(остатак(с), и - 1)

>>> дужинаУланчанеЛистеРекурзивно(четири)
4
>>> вратиЧланУланчанеЛистеРекурзивно(четири, 1)
2

Ове рекурзивне имплементације прате ланац парова све док се не дође до краја (у дужинаУланчанеЛистеРекурзивно) или жељеног члана (у вратиЧланУланчанеЛистеРекурзивно) уланчане листе.

Рекурзија је такође корисна за трансформисање и комбиновање уланчаних листа.

>>> def продужиУланчануЛисту(с, т):
...     """Враћа уланчану листу са члановима с праћеним члановима т."""
...     assert даЛиЈеУланчанаЛиста(с) and даЛиЈеУланчанаЛиста(т)
...     if с == празно:
...         return т
...     else:
...         return уланчанаЛиста(први(с), продужиУланчануЛисту(остатак(с), т))

>>> продужиУланчануЛисту(четири, четири)
[1, [2, [3, [4, [1, [2, [3, [4, 'празно']]]]]]]]

>>> def примениНаСвакиЧланУланчанеЛисте(f, с):
...     """Примени функцију f на сваки члан уланчане листе с."""
...     assert даЛиЈеУланчанаЛиста(с)
...     if с == празно:
...         return с
...     else:
...         return уланчанаЛиста(f(први(с)), примениНаСвакиЧланУланчанеЛисте(f, остатак(с)))

>>> примениНаСвакиЧланУланчанеЛисте(lambda x: x*x, четири)
[1, [4, [9, [16, 'празно']]]]

>>> def условноЗадржавањеЧлановаУланчанеЛисте(f, с):
...     """Враћа уланчану листу чланова с за које важи да је f(ч) тачно."""
...     assert даЛиЈеУланчанаЛиста(с)
...     if с == празно:
...         return с
...     else:
...         задржани = условноЗадржавањеЧлановаУланчанеЛисте(f, остатак(с))
...         if f(први(с)):
...             return уланчанаЛиста(први(с), задржани)
...         else:
...             return задржани

>>> условноЗадржавањеЧлановаУланчанеЛисте(lambda x: x%2 == 0, четири)
[2, [4, 'празно']]

>>> def спојУланчануЛисту(с, раздвојник):
...     """Враћа ниску свих чланова уланчане листе с раздвојених раздвојник-ом."""
...     if с == празно:
...         return ""
...     elif остатак(с) == празно:
...         return str(први(с))
...     else:
...         return str(први(с)) + раздвојник + спојУланчануЛисту(остатак(с), раздвојник)

>>> спојУланчануЛисту(четири, ", ")
'1, 2, 3, 4'

Рекурзивна конструкција

Уланчане листе се посебно користе приликом поступне изграње секвенци, што је ситуација која се често појављује код рекурзивних израчунавања.

Функција бројПартиција са самог краја претходног поглавља враћала је број начина на који је могуће партиционисати природан број \(n\) користећи бројеве мање или једнаке \(m\) преко рекурзивног стабла. Преко секвенци, могуће је такође пребројити све партиције експлицитно користећи сличан поступак.

Треба пратити исту рекурзивну анализу проблема као и код пребројавања: партиционисање броја \(n\) користећи бројеве не веће од \(m\) укључује или

1. партиционисање \(n-m\) користећи природне бројеве не веће од \(m\), или

2. партиционисање \(n\) користећи природне бројеве не веће од \(m-1\).

За основне случајеве узима се да 0 има празну партицију, док је партиционисање негативнних бројева или партиционисање коришћењем делова мањих од 1 немогуће.

>>> def партиције(n, m):
...     """Враћа уланчану листу партиција n користећи делове не веће од m.
...        Свака од партиција представљена је такође уланчаном листом."""
...     if n == 0:
...         return уланчанаЛиста(празно, празно) # Уланчана листа с празном партицијом
...     elif n < 0 or m == 0:
...         return празно
...     else:
...         користећи_m = партиције(n-m, m)
...         са_m = примениНаСвакиЧланУланчанеЛисте(lambda s: уланчанаЛиста(m, s), користећи_m)
...         без_m = партиције(n, m-1)
...         return продужиУланчануЛисту(са_m, без_m)

У рекурзивном случају, праве се две уланчане подлисте партиција. Прва користећи \(m\), па се због тога \(m\) умеће на почетак сваког члана резултата користећи_m да би се добило са_m.

Резултат функције партиције је изузетно угнежђен: уланчана листа уланчаних листа, а свака уланчана листа је представљена преко угнежђених парова који су заправо низови. Користећи функцију спојУланчануЛисту са одговарајућим раздвојницима, могу се приказати партиције на читак начин.

>>> def испишиПартиције(n, m):
...     улисте = партиције(n, m)
...     ниске = примениНаСвакиЧланУланчанеЛисте(lambda с: спојУланчануЛисту(с, " + "), улисте)
...     print(спојУланчануЛисту(ниске, "\n"))

>>> испишиПартиције(6, 4)
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1