Vypracujte úlohu

Súbor obsahuje tieto funkcie:

append(list1, list2)
concat(lists)
filter(function, list)
length(list)
map(function, list)
foldl(function, list, initial)
foldr(function, list, initial)
reverse(list)

Každá funkcia má vrátiť výsledok tak aby vyvhovoval automatickým testom, nemá vypisovať nič pomocou print.

Návod k cvičeniu: operácie so zoznamami

V tomto cvičení napíšete vlastné implementácie základných operácií so zoznamami. Cieľom nie je použiť hotové funkcie Pythonu, ale precvičiť si prechádzanie zoznamu, tvorbu nového zoznamu a prácu s akumulátorom.

Čo je zoznam v Pythone

Zoznam (list) je usporiadaná a meniteľná kolekcia hodnôt. Hodnoty sú uložené v určitom poradí, môžu sa opakovať a nemusia byť všetky rovnakého typu.

numbers = [10, 20, 20, 30]
mixed = ["Python", 2026, True, [1, 2]]
empty = []

Každý prvok má index. Indexovanie začína od nuly:

numbers[0]   # 10
numbers[2]   # 20
numbers[-1]  # 30, posledný prvok

Zoznam je meniteľný, takže prvok možno nahradiť alebo pridať ďalšie prvky:

numbers[0] = 99
numbers.append(40)

V prvom riadku je dôležité rozumieť tomu, že priradenie mení prvý prvok zoznamu. V cvičení však vstupné zoznamy neupravujte; vytvárajte nové výsledné zoznamy.

Zoznam môže obsahovať aj ďalšie zoznamy. Takýto zoznam nazývame vnorený zoznam:

matrix = [[1, 2], [3, 4]]
matrix[0][1]  # 2

Viac informácií nájdete v oficiálnej dokumentácii:

• Úvod do dátových štruktúr – zoznamy
• Oficiálna dokumentácia typu list

Základné operácie so zoznamami

Prechádzanie zoznamu

Najčastejšie potrebujeme spracovať každý prvok. Na to slúži cyklus for:

for item in numbers:
    print(item)

Ak potrebujeme aj index, môžeme použiť enumerate:

for index, item in enumerate(numbers):
    print(index, item)

Dĺžka a test členstva

Vstavaná funkcia len vráti počet prvkov. Operátor in overí, či sa hodnota v zozname nachádza:

len([10, 20, 30])  # 3
20 in [10, 20, 30] # True
99 in [10, 20, 30] # False

V tomto cvičení implementujete vlastnú funkciu length, preto v jej tele nepoužívajte len.

Pridanie a odstránenie prvkov

Metóda append pridá jeden prvok na koniec zoznamu a zmení pôvodný zoznam:

items = [1, 2]
items.append(3)       # items je teraz [1, 2, 3]
items.append([4, 5])  # items je teraz [1, 2, 3, [4, 5]]

Ak chceme pridať všetky prvky iného zoznamu, použijeme extend:

items = [1, 2]
items.extend([3, 4])  # items je teraz [1, 2, 3, 4]

remove(value) odstráni prvý výskyt hodnoty a pop(index) odstráni prvok na danom indexe a zároveň ho vráti:

items = [10, 20, 30]
items.remove(20)  # [10, 30]
last = items.pop() # last je 30, items je [10]

Tieto metódy menia zoznam priamo. V tomto cvičení ich nepoužívajte na vstupné argumenty.

Spájanie, opakovanie a výber časti zoznamu

Operátor + spojí dva zoznamy a * zopakuje ich obsah:

[1, 2] + [3, 4]  # [1, 2, 3, 4]
[1, 2] * 2       # [1, 2, 1, 2]

Výrez (slice) vyberie časť zoznamu. Horná hranica sa nezapočítava:

values = [0, 1, 2, 3, 4]
values[1:4]  # [1, 2, 3]
values[:2]   # [0, 1]
values[::2]  # [0, 2, 4]

Výrez vytvára nový zoznam, čo môže byť užitočné pri práci s poradím prvkov. Pri tomto cvičení si však vždy skontrolujte, či riešenie nepoužíva práve hotovú operáciu, ktorú máte implementovať.

Zoradenie a obrátenie poradia

sort() zoradí zoznam priamo, zatiaľ čo sorted() vytvorí zoradený výsledok. reverse() obráti zoznam priamo:

values = [3, 1, 2]
sorted(values)  # [1, 2, 3]
values.reverse()

Metódy, ktoré menia zoznam priamo, zvyčajne vracajú None. Preto si treba dávať pozor na rozdiel medzi:

values.reverse()       # zmení values
reversed_values = values[::-1]  # vytvorí nový zoznam

Prehľad bežných operácií sekvencií a metód meniteľných sekvencií je v časti Common Sequence Operations a Mutable Sequence Types.

Čo treba implementovať

V súbore list_ops.py doplňte funkcie:

Funkcia	Význam
append(list1, list2)	pridá všetky prvky druhého zoznamu za prvky prvého zoznamu
concat(lists)	spojí zoznam zoznamov do jedného zoznamu
filter(function, list)	ponechá iba prvky, pre ktoré funkcia vráti True
length(list)	spočíta počet prvkov
map(function, list)	pre každý prvok vytvorí transformovanú hodnotu
foldl(function, list, initial)	postupne spracuje prvky zľava doprava
foldr(function, list, initial)	postupne spracuje prvky sprava doľava
reverse(list)	vráti prvky v opačnom poradí

Funkcie majú vracať nový výsledok. Vstupné zoznamy neupravujte pomocou append, extend, sort alebo reverse s bodkou.

Odporúčaný postup

Začnite jednoduchšími funkciami a postupne využívajte už vytvorené operácie:

1. length
2. append
3. concat
4. filter a map
5. reverse
6. foldl a foldr

Pri väčšine funkcií si pripravte prázdny výsledný zoznam a prejdite vstup pomocou for. Počas prechodu pridajte do výsledku iba to, čo podľa zadania treba.

Ako premýšľať o jednotlivých funkciách

length

Použite počítadlo. Na začiatku je 0 a pri každom prvku ho zvýšte o 1. Prázdny zoznam musí mať dĺžku 0.

append

Výsledok má obsahovať najprv všetky prvky z list1 a potom všetky prvky z list2.

Príklad:

append([1, 2], [2, 3, 4]) -> [1, 2, 2, 3, 4]

Neodstraňujte duplicitné hodnoty a nevnárajte druhý zoznam ako jeden prvok.

concat

Argumentom je zoznam zoznamov. Prejdite vonkajší zoznam a potom postupne prvky každého vnútorného zoznamu. Ide o sploštenie iba jednej úrovne.

concat([[1, 2], [3], [], [4, 5]]) -> [1, 2, 3, 4, 5]
concat([[[1], [2]], [[3]]]) -> [[1], [2], [3]]

Druhý príklad je dôležitý: vnorené zoznamy sa rekurzívne nesplošťujú.

filter

Pre každý prvok zavolajte predanú funkciu. Do výsledku ho vložte iba vtedy, keď je výsledok volania pravdivý.

filter(lambda x: x % 2 == 1, [1, 2, 3, 5]) -> [1, 3, 5]

Predikát môže byť ľubovoľná funkcia, preto nepredpokladajte, že pracuje iba s číslami.

map

Každý prvok musí byť vo výsledku zastúpený práve raz, ale po použití predanej funkcie.

map(lambda x: x + 1, [1, 3, 5]) -> [2, 4, 6]

map prvky nevynecháva. Ak transformačná funkcia vráti None, aj None patrí do výsledku.

Najdôležitejšia časť: foldl a foldr

Obe funkcie používajú akumulátor. Pri každom kroku zavoláte predanú funkciu a jej výsledok sa stane novým akumulátorom. Ak je zoznam prázdny, výsledkom je pôvodná hodnota initial.

Pozor na poradie argumentov: testované funkcie majú tvar function(accumulator, element).

foldl: zľava doprava

Pri zozname [1, 2, 3] a počiatočnej hodnote 0 prebehne výpočet takto:

acc = 0
acc = function(acc, 1)
acc = function(acc, 2)
acc = function(acc, 3)

Ekvivalentný zápis je:

function(function(function(0, 1), 2), 3)

foldr: sprava doľava

Pri rovnakom zozname sa prvky spracujú v opačnom poradí:

acc = 0
acc = function(acc, 3)
acc = function(acc, 2)
acc = function(acc, 1)

Ekvivalentný zápis je:

function(function(function(0, 3), 2), 1)

Pri sčítaní môže byť rozdiel neviditeľný, pretože sčítanie je komutatívne. Testy používajú aj delenie, kde sa rozdiel prejaví. Ak si nie ste istí, rozpíšte si konkrétny výpočet na papier.

reverse

Výsledok má obsahovať tie isté objekty v opačnom poradí. Zoznamy vo vnútri prvkov sa nemajú meniť ani splošťovať:

reverse([[1, 2], [3], [], [4, 5]])
-> [[4, 5], [], [3], [1, 2]]

Môžete využiť prechod od posledného indexu po prvý alebo postupne vkladať prvky na začiatok nového zoznamu. Vstupný zoznam nechajte nedotknutý.

Čomu sa vyhnúť

• Nepoužívajte priamo vstavané operácie, ktoré cvičenie napodobňuje, napríklad len, map, filter, sum alebo list.reverse().
• Nezamieňajte append s pridaním celého zoznamu ako jedného prvku.
• Pri concat nesplošťujte vnorené zoznamy viac než o jednu úroveň.
• V filter volajte predikát a kontrolujte jeho výsledok; nekopírujte všetky prvky automaticky.
• V map nezabudnite zavolať funkciu na každý prvok.
• Pri foldl a foldr nezmeňte poradie argumentov na function(element, accumulator).
• Nezapisujte riešenie tak, aby menilo vstupné zoznamy.

Overenie riešenia

Testy spustíte v priečinku cvičenia príkazom:

python -m unittest list_ops_test.py

Ak test zlyhá, prečítajte si jeho názov. Ten zvyčajne napovie, či je problém v prázdnom zozname, poradí prvkov, vnorení alebo v smere skladania.

Pred odovzdaním si vlastným príkladom overte najmä:

append([], [1, 2])
concat([[], [1], [2, 3]])
filter(lambda x: x > 2, [1, 3, 2, 4])
map(lambda x: x * 2, [1, 2, 3])
foldl(lambda acc, x: x / acc, [1, 2, 3], 6)
foldr(lambda acc, x: x / acc, [1, 2, 3], 6)
reverse(["a", 2, [3]])

Najlepší ďalší krok je implementovať jednu funkciu, spustiť testy a až potom pokračovať ďalšou. Tak ľahšie zistíte, ktorá zmena spôsobila prípadný problém.

Previous Post Next Post