Hlavní navigace

Knihovny pro zpracování posloupností (sekvencí) v Pythonu

Pavel Tišnovský

Sekvence, a to včetně sekvencí nekonečných, jsou velmi užitečnou datovou abstrakcí, s níž jsme se již nesčetněkrát setkali při popisu jazyka Clojure. Podobný koncept ovšem můžeme využít i v Pythonu, a to mj. i díky existenci knihovny clj.

Doba čtení: 27 minut

11. Přístup k prvkům nekonečné sekvence

12. Funkce nth a take v Pythonu

13. Použití funkce flatten

14. Funkce shuffle

15. Rozdělení sekvence do podskupin s využitím funkce group-by

16. Funkce group_by v Pythonu

17. Sloučení několika sekvencí funkcí interleave

18. Funkce interleave v Pythonu

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Knihovny pro zpracování posloupností (sekvencí) v Pythonu

V seriálu o programovacím jazyce Clojure jsme se již mnohokrát setkali s pojmem sekvence, popř. nekonečné sekvence nebo dokonce lazy sekvence. Jedná se o datovou abstrakci, která je sice velmi jednoduchá, ale o to užitečnější v praxi – ostatně velká část standardní knihovny Clojure je na sekvencích založena. Pro ty programátory, kteří programovací jazyk Clojure znají a současně používají i Python, je určena minimalisticky pojatá knihovna nazvaná clj. V této knihovně nalezneme implementaci všech základních funkcí, které jsou v Clojure určeny pro práci se sekvencemi. Tyto funkce je možné použít i pro klasické seznamy a iterátory, jak ostatně uvidíme v dalším textu.

Na tomto místě pro jistotu upozorním na dvojici velmi užitečných knihoven, o jejichž existenci by měl, alespoň podle mého skromného názoru, vědět každý Pythonista. Jedná se o knihovny functools a itertools. Mnoho dále popsaných funkcí totiž v těchto knihovnách naleznete, i když pod jiným názvem (obě knihovny si taktéž zaslouží samostatný článek). Knihovna clj je určena skutečně pro skalní clojuristy :-)

Abychom pochopili, jaké funkce a generátory nalezneme v knihovně clj, popišme si nejprve ve stručnosti sekvence a lazy sekvence tak, jak jsou implementovány přímo v programovacím jazyce Clojure. Posléze se podíváme na to, do jaké míry byl úspěšný převod tohoto konceptu do Pythonu.

2. Sekvence a lazy sekvence v programovacím jazyku Clojure

Mnoho funkcí a maker, které nalezneme ve standardní knihovně programovacího jazyka Clojure, souvisí s takzvanými sekvencemi. Tímto termínem se označuje programové rozhraní, které svými základními možnostmi zhruba odpovídá iterátorům známým z programovacího jazyka Java. V Clojure existuje velké množství funkcí, které dokážou pracovat se sekvencemi, ať již se jedná o běžné sekvence (jejichž prvky jsou přímo uloženy v operační paměti) nebo takzvané líné sekvence (lazy sekvence), které nové prvky vytváří či zjišťují až při konkrétním přístupu na tyto prvky. Mezi tyto funkce patří například sort, sort-by, take či flatten. Díky tomu, že všechny standardní kolekce (seznamy, vektory, …) jsou současně i sekvencemi, lze tyto funkce aplikovat i na kolekce, ovšem ve skutečnosti jsou sekvencemi i další typy objektů, zejména pak I/O proudy (tímto směrem se posunuly i standardní knihovny Javy), řetězce (což jsou sekvence znaků) atd.

Naprostý základ pro práci se sekvencemi tvoří trojice funkcí nazvaných first, rest a next. Funkce first vrací první prvek v sekvenci, popř. speciální hodnotu nil v případě, že je sekvence prázdná. Funkce restnext vrací zbylé prvky v sekvenci, ovšem liší se tím, jaká hodnota se vrátí ve chvíli, kdy již v sekvenci nezbyly žádné prvky (kromě prvního). V tomto případě vrátí rest prázdnou sekvenci (například prázdný seznam), zatímco funkce next vrátí již zmíněnou speciální hodnotu nil. U běžných sekvencí, například seznamů, jsou tyto funkce implementovány přímočaře, ovšem v případě lazy sekvencí se prvky vrácené pomocí funkce first vyhodnocují až za běhu, například pomocí nějaké generátorové funkce. Tímto způsobem je možné pracovat i s nekonečnými sekvencemi, u nichž už z principu nelze dopředu znát celkový počet prvků atd.

Velmi dobrým příkladem lazy sekvence je funkce range, která dokonce existuje v několika podobách, jež se od sebe z hlediska programátora-uživatele liší především různým počtem parametrů. Pokud se této funkci nepředá žádný parametr, vrátí funkce range sekvenci celých čísel od nuly do nekonečna. Zde je patrné, proč se musí jednat o lazy sekvenci – nekonečnou řadu celých čísel by samozřejmě v případě normální sekvence nebylo možné uložit do operační paměti. Pokud se funkci range předá pouze jediný parametr (kterým musí být celé číslo – je kontrolováno v runtime), je vrácena sekvence celých čísel od 0 do zadané hodnoty-1. Opět se jedná o nefalšovanou lazy sekvenci, takže se nemusíte bát používat i velké n. Dále již následují v podstatě jen kosmetické úpravy – volání funkce range se dvěma parametry m, n vytvoří sekvenci celých čísel od m do n-1 a pokud je použit ještě třetí parametr, určuje se jím krok, který může být i záporný.

Takto navrženou funkci range nalezneme i v knihovně clj. Je přitom zachováno standardní chování range ze základní knihovny Pythonu, ovšem v případě potřeby může tato funkce (volaná bez parametrů) vytvořit nekonečnou lazy sekvenci!

3. Sekvence a lazy sekvence v Pythonu a knihovně clj

V Pythonu se chování skutečných sekvencí a lazy sekvencí může napodobit pomocí generátorů. Ty byly původně do Pythonu přidány mj. i z důvodu kratšího a přehlednějšího zápisu iterátorů. U generátorů se nemusí psát celá třída s metodami __iter__() a __next__() atd.) a celý zápis generátoru je většinou realizován jedinou funkcí, v níž se nová hodnota generuje příkazem yield (současně se předává řízení koprogramu, který generátor používá). Stav generátoru je typicky uložen právě v této funkci v lokálních proměnných (což je na druhou stranu odlišné od chování jazyka Clojure a vede k nepříjemným vedlejším efektům).

Příkladem použití generátoru může být funkce range, která sice vychází ze standardní pythonovské funkce téhož jména, ovšem přidává možnost tvorby nekonečné sekvence:

def range(*args):
    """
    Usage: range()
           range(end)
           range(start, end)
           range(start, end, step)
 
    Returns a generator of numbers from ``start`` (inclusive) to ``end``
    (exclusive), by ``step``, where ``start`` defaults to ``0``, ``step`` to
    ``1``, and ``end`` to infinity. When ``step`` is equal to ``0``, returns an
    infinite sequence of ``start``.
 
    Note that this delegates to Python’s built-in ``range`` (or ``xrange`` in
    Python 2) if there are arguments.
    """
    if args:
        for e in _range(*args):
            yield e
        return
 
    n = 0
    while True:
        yield n
        n += 1

Samotná implementace nekonečné sekvence je zapsána v posledních čtyřech řádcích.

Naproti tomu v programovacím jazyku Clojure je podobná sekvence interně vytvářena takto (což je do značné míry totožné s implementací iterátoru v Pythonu):

private class RangeIterator implements Iterator {
    private Object next;
 
    public RangeIterator() {
        this.next = start;
    }
 
    public boolean hasNext() {
        return(! boundsCheck.exceededBounds(next));
    }
 
    public Object next() {
        if (hasNext()) {
            Object ret = next;
            next = Numbers.addP(next, step);
            return ret;
        } else {
            throw new NoSuchElementException();
        }
    }
 
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Ve skutečnosti se chování sekvencí v Clojure a Pythonu odlišuje, a to ve chvíli, kdy nějaká funkce musí „zkonzumovat“ data z generátoru, například při přístupu k n-tému prvku. V Clojure získáme vždy stejný (desátý) prvek nekonečné sekvence:

(def s (range))
(def i1 (nth s 10))
(def i2 (nth s 10))
(def i3 (nth s 10))
(println i1 i2 i3)
 
10 10 10

V Pythonu se ovšem používá společný stav generátoru a dostame výsledky rozdílné:

from clj.seqs import range, nth
s = range()
i1 = nth(s, 10)
i2 = nth(s, 10)
i3 = nth(s, 10)
print(i1, i2, i3)
 
10 21 32

4. Instalace knihovny clj

Po krátkém úvodu nastal čas si vyzkoušet některé možnosti nabízené knihovnou clj. Samotná instalace této knihovny je velmi snadná, ostatně jedná se vlastně o pouhé dva zdrojové soubory. Vzhledem k tomu, že clj je dostupná na PyPi, můžeme pro instalaci použít nástroj pip:

$ pip3 install --user clj
Collecting clj
  Downloading https://files.pythonhosted.org/packages/46/de/6d06743f2327f070602eb1f6dff525c92397de17fb418e206b13945e8468/clj-0.1.0.tar.gz
Installing collected packages: clj
  Running setup.py install for clj ... done
Successfully installed clj-0.1.0

Od této chvíle by mělo být možné provést například:

from clj.seqs import range, first, rest
 
help("clj.seqs.first")
 
Help on function first in clj.seqs:
 
clj.seqs.first = first(coll)
    Returns the first item in the collection. If ``coll`` is ``None`` or empty,
    returns ``None``.
 
 
help("clj.seqs.range")
 
Help on function range in clj.seqs:
 
clj.seqs.range = range(*args)
    Usage: range()
           range(end)
           range(start, end)
           range(start, end, step)
 
    Returns a generator of numbers from ``start`` (inclusive) to ``end``
    (exclusive), by ``step``, where ``start`` defaults to ``0``, ``step`` to
    ``1``, and ``end`` to infinity. When ``step`` is equal to ``0``, returns an
    infinite sequence of ``start``.
 
    Note that this delegates to Python’s built-in ``range`` (or ``xrange`` in
    Python 2) if there are arguments.

5. Základní funkce pro práci se sekvencemi

Připomeňme si, že sekvence jsou v programovacím jazyce Clojure důležité především z toho důvodu, že ve standardní knihovně tohoto jazyka se nachází velké množství funkcí a maker pro práci s nimi. Tvůrci LISPu a z něho odvozeného jazyka Clojure totiž zastávají názor, že je lepší používat relativně malé množství datových typů a mít pro tyto typy k dispozici velké množství obecných funkcí, které je možné vzájemně kombinovat. Naproti tomu se v klasickém OOP spíše upřednostňuje mít větší počet specializovaných datových typů (tříd) s relativně malým množstvím specializovaných funkcí aplikovatelných na tyto typy (metody). Obecně asi nelze říci, který přístup je lepší, protože záleží na povaze řešené úlohy. Vraťme se však k jazyku Clojure a k jeho kolekcím. V následující tabulce jsou vypsány některé zcela základní funkce, které lze při práci s kolekcemi použít. Povšimněte si, že žádná z těchto funkcí nemění původní kolekci, maximálně vrátí jako svůj výsledek kolekci novou, která ve většině případů používá stejné prvky jako kolekce původní (tím se zamezuje zbytečným kopiím v paměti):

# Funkce Podpora v clj Stručný popis funkce
1 count ano vrátí počet prvků v sekvenci
2 cons ano vrátí novou kolekci s přidaným prvkem (odkaz jazyka LISP)
3 concat ano spojení dvou sekvencí (rozdílné od cons!)
4 first ano první prvek sekvence
5 second ano druhý prvek sekvence
6 rest ano sekvence bez prvního prvku
7 nth ano získání n-tého prvku sekvence
8 distinct ano vrátí se nová sekvence s unikátními prvky (bez duplicit)

6. První demonstrační příklad – použití základních funkcí pro konstrukci sekvencí a pro přístup k prvkům sekvence

V prvním demonstračním příkladu si popíšeme způsob použití většiny funkcí popsaných v předchozí kapitole. Nejprve si ukážeme původní tvar příkladu naprogramovaného v jazyce Clojure. Zde jsou sekvence základním abstraktním typem; konkrétním typem může být například vektor:

(def s [1 2 3 1 2 3])
 
(println "Count:")
(println (count s))
(println)
 
(println "Reversed:")
(println (reverse s))
 
(println "First:")
(println (first s))
(println "Second:")
(println (second s))
(println "Rest:")
(println (rest s))
 
(println "Distinct items:")
 
(println (distinct s))
 
(println "Cons 1:")
(def new_sequence (cons s ["A" "B" "C"]))
(println new_sequence)
 
(println "Cons 2:")
(def new_sequence_2 (cons ["A" "B" "C"] s))
(println new_sequence_2)
 
(println "Concat 1:")
(def new_sequence (concat s ["A" "B" "C"]))
(println new_sequence)
 
(println "Concat 2:")
(def new_sequence_2 (concat ["A" "B" "C"] s))
(println new_sequence_2)

Výsledky tohoto příkladu po jeho spuštění v REPLu:

Count:
6
 
Reversed:
(3 2 1 3 2 1)
 
First:
1
 
Second:
2
 
Rest:
(2 3 1 2 3)
 
Distinct items:
(1 2 3)
 
Cons 1:
([1 2 3 1 2 3] A B C)
 
Cons 2:
([A B C] 1 2 3 1 2 3)
 
Concat 1:
(1 2 3 1 2 3 A B C)
 
Concat 2:
(A B C 1 2 3 1 2 3)
Poznámka: povšimněte si, jak se odlišuje chování funkcí cons a concat. Pokud potřebujete k existující sekvenci přidat další prvek, použijte cons; pokud naopak potřebuje dvě sekvence spojit, využijete concat.

Nyní se pokusme tento příklad převést do Pythonu. Na začátku musíme naimportovat všechny používané funkce:

from clj.seqs import count, first, second, rest, cons, concat, distinct

Dále si vytvoříme pomocné funkce pro tisk sekvence na standardní výstup:

def hr():
    print(40*"-")
    print()
 
 
def print_sequence(sequence):
    for item in sequence:
        print(item)
    hr()

A můžeme začít s přepisováním. Povšimněte si například toho, že namísto reverse je nutné použít standardní funkci reversed:

sequence = [1, 2, 3, 1, 2, 3]
 
print("Original:")
print_sequence(sequence)
 
# puvodni funkce len() a nova funkce count()
print("Len and count:")
print(len(sequence))
print(count(sequence))
hr()
 
# puvodni (standardni) funkce reversed()
print("Reversed:")
print_sequence(reversed(sequence))
 
# funkce first(), second() a rest()
print("First:")
print(first(sequence))
print("Second:")
print(second(sequence))
print("Rest:")
print(rest(sequence))
print_sequence(rest(sequence))
 
# nova funkce distinct()
print("Distinct items:")
 
print(distinct(sequence))
print_sequence(distinct(sequence))
 
# prevod sekvence zpet na seznam
print(list(distinct(sequence)))
 
# funkce cons
print("Cons 1:")
new_sequence = cons(sequence, ["A", "B", "C"])
print_sequence(new_sequence)
 
print("Cons 2:")
new_sequence_2 = cons(["A", "B", "C"], sequence)
print_sequence(new_sequence_2)
 
# funkce concat
print("Concat 1:")
new_sequence = concat(sequence, ["A", "B", "C"])
print_sequence(new_sequence)
 
print("Concat 2:")
new_sequence_2 = concat(["A", "B", "C"], sequence)
print_sequence(new_sequence_2)

Výsledky by měly vypadat přesně takto:

Original:
1
2
3
1
2
3
----------------------------------------
 
Len and count:
6
6
----------------------------------------
 
Reversed:
3
2
1
3
2
1
----------------------------------------
 
First:
1
Second:
2
Rest:
<generator object drop at 0x7f255594b678>
2
3
1
2
3
----------------------------------------
 
Distinct items:
<generator object distinct at 0x7f255594b678>
1
2
3
----------------------------------------
 
[1, 2, 3]
Cons 1:
[1, 2, 3, 1, 2, 3]
A
B
C
----------------------------------------
 
Cons 2:
['A', 'B', 'C']
1
2
3
1
2
3
----------------------------------------
 
Concat 1:
1
2
3
1
2
3
A
B
C
----------------------------------------
 
Concat 2:
A
B
C
1
2
3
1
2
3
----------------------------------------
Poznámka: povšimněte si, že sekvenci nemůžeme přímo vytisknout funkcí print, ovšem můžeme ji převést na seznam, který již vytisknout umíme.

7. Funkce filter a remove

Velmi často se při zpracování sekvencí používají funkce nazvané filter a remove. Ve skutečnosti je funkce filter součástí standardní knihovny Pythonu, takže v knihovně clj musela být implementována pouze funkce remove. Obě funkce, tj. jak filter, tak i remove, jsou funkcemi vyššího řádu, což znamená, že jejich parametrem je další funkce (typicky funkce anonymní). Funkce filter se používá pro vytvoření nové sekvence, která bude obsahovat jen ty prvky ze sekvence původní, které odpovídají nějakému predikátu (predikát je obecně funkce vracející pro svůj jediný vstup pravdivostní hodnotu). Funkce remove pracuje přesně naopak, tj. odstraňuje ze sekvence ty prvky, které odpovídají predikátu.

Vzhledem k tomu, že knihovna clj realizuje sekvence formou generátorů, je implementace funkce remove značně strohá:

def remove(pred, coll):
    """
    Return a generator of the items in ``coll`` for which ``pred(item)``
    returns a falsy value.
    """
    for e in coll:
        if not pred(e):
            yield e

8. Druhý demonstrační příklad – použití funkcí filterremove

Ve druhém demonstračním příkladu si popíšeme chování funkcí filter a remove. Opět si nejprve uvedeme variantu určenou pro programovací jazyk Clojure. Ze sekvence s původně devíti prvky 1..9 nejprve vytvoříme sekvenci se všemi prvky dělitelnými třemi, posléze sekvenci se všemi prvky NEdělitelnými třemi, dále sekvenci získanou filtrací prvků, pro něž predikát vždy vrátí pravdivostní hodnotu True a konečně sekvenci získanou odstraněním prvků, pro něž predikát vždy vrací True:

(def s (range 1 10))
 
; kratky zapis anonymni funkce pomoci #()
(def filtered (filter #(zero? (mod % 3)) s))
(println filtered)
 
; kratky zapis anonymni funkce pomoci #()
(def removed (remove #(zero? (mod % 3)) s))
(println removed)
 
; zde nelze kratky zapis pouzit - musi se specifikovat argument
(def filtered (filter (fn [x] true) s))
(println filtered)
 
; zde nelze kratky zapis pouzit - musi se specifikovat argument
(def removed (remove (fn [x] true) s))
(println removed)

Výsledky postupně vypadají takto:

; prvky delitelne tremi
(3 6 9)
 
; prvky nedelitelne tremi
(1 2 4 5 7 8)
 
; prvky filtrovane s vyuzitim predikatu, ktery vraci True
(1 2 3 4 5 6 7 8 9)
 
; prvky odstranene s vyuzitim predikatu, ktery vraci True
()

Přepis do Pythonu je přímočarý a použijeme v něm anonymní funkce vytvářené pomocí konstrukce lambda:

from clj.seqs import remove
 
 
def hr():
    print(40*"-")
    print()
 
 
def print_sequence(sequence):
    for item in sequence:
        print(item)
    hr()
 
 
sequence = range(1, 10)
 
print("Original:")
print_sequence(sequence)
 
filtered = filter(lambda x: x % 3 == 0, sequence)
print("Filtered:")
print_sequence(filtered)
 
removed = remove(lambda x: x % 3 == 0, sequence)
print("Removed:")
print_sequence(removed)
 
filtered = filter(lambda _: True, sequence)
print("Filtered:")
print_sequence(filtered)
 
removed = remove(lambda _: True, sequence)
print("Removed:")
print_sequence(removed)

Výsledky odpovídají Clojure:

Original:
1
2
3
4
5
6
7
8
9
----------------------------------------
Filtered:
3
6
9
----------------------------------------
Removed:
1
2
4
5
7
8
----------------------------------------
Filtered:
1
2
3
4
5
6
7
8
9
----------------------------------------
Removed:
(zde nic není :-)
----------------------------------------

9. Funkce take-while

V některých případech nám bude užitečná i poněkud komplikovanější funkce, která je nazvaná take-while. Zatímco u funkce take popsané dále se přímo zadává počet prvků lazy sekvence, která se má vrátit, je v případě funkce take-while namísto konstantního počtu prvků výsledné sekvence předán predikát, tj. funkce s (v tomto případě) jedním parametrem, jejímž výsledkem by měla být pravdivostní hodnota true nebo false.

Návratovou hodnotou funkce take-while je (obecně) opět lazy sekvence získaná ze vstupní sekvence, ovšem vráceno je pouze prvních n prvků, pro něž predikát vrací hodnotu true. Nejedná se však o klasický filtr (viz též předchozí dvě kapitoly), protože ihned ve chvíli, kdy predikát poprvé vrátí hodnotu false, je lazy sekvence ukončena. Pokud vrátí predikát hodnotu false již při prvním volání, je výsledkem prázdná sekvence, pokud naopak vrací hodnotu true vždy, vrátí se potenciálně nekonečná lazy sekvence (což však někdy nemusí vadit, pokud se tedy nebudeme snažit o výpis všech prvků). Vzhledem k určitým omezením take-while je nutné, aby měl predikát pouze jeden parametr, což většinou znamená, že si musíme vypomoci novou funkcí (popř. anonymní funkcí).

Příklad použití funkce take-while v Clojure:

(def my-sequence (range))
 
; prvni pouziti nekonecne sekvence
(println (take-while #(< % 10) my-sequence))
 
; druhe pouziti nekonecne sekvence
(println (take-while #(< % 10) my-sequence))
 
; false se vrati ihned v prvnim volani
(println (take-while (fn [x] false) my-sequence))

10. Třetí příklad – kombinace remove a take-while pro nekonečné sekvence

Výše zmíněné funkce remove a take-while nyní použijeme v Pythonu, a to vlastně naprosto stejným způsobem, jako tomu bylo v programovacím jazyku Clojure:

from clj.seqs import count, range, take_while, remove
 
 
def hr():
    print(40*"-")
    print()
 
 
def print_sequence(sequence):
    for item in sequence:
        print(item)
    hr()
 
 
sequence = range()
 
# toto NE: print(count(sequence))
 
print("Vyber prvku mensich nez 10 ze vsech prirozenych cisel:")
 
new_sequence_1 = take_while(lambda x: x < 10, sequence)
print_sequence(new_sequence_1)
 
 
def podminka(x):
    return x < 10
 
 
sequence = range()
 
print("Vyber prvku mensich nez 10 ze vsech prirozenych cisel:")
 
new_sequence_2 = take_while(podminka, sequence)
print_sequence(new_sequence_2)
 
print("Vyber prvku delitelnych tremi a mensich nez 20 ze vsech prirozenych cisel:")
 
# nekonecna lazy sekvence
sequence = range()
 
# lze ji filtrovat
filtered = filter(lambda x: x % 3 == 0, sequence)
 
# a vybrat n prvku z nekonecneho poctu
new_sequence = take_while(lambda x: x < 20, filtered)
print_sequence(new_sequence)
 
 
print()
 
print("Kombinace remove() a take_while():")
 
# nekonecna lazy sekvence
sequence = range()
 
# lze ji filtrovat
removed = remove(lambda x: x % 3 != 0, sequence)
 
# a vybrat n prvku z nekonecneho poctu
new_sequence = take_while(lambda x: x < 30, removed)
print_sequence(new_sequence)
 
print()
 
print("Predikat vracejici vzdy False:")
 
# nekonecna lazy sekvence
sequence = range()
 
# predikat ktery vzdy vraci False
new_sequence = take_while(lambda _: False, sequence)
print_sequence(new_sequence)

Výsledky vygenerované předchozím příkladem:

Vyber prvku mensich nez 10 ze vsech prirozenych cisel:
0
1
2
3
4
5
6
7
8
9
----------------------------------------
Vyber prvku mensich nez 10 ze vsech prirozenych cisel:
0
1
2
3
4
5
6
7
8
9
----------------------------------------
Vyber prvku delitelnych tremi a mensich nez 20 ze vsech prirozenych cisel:
0
3
6
9
12
15
18
----------------------------------------
Kombinace remove() a take_while():
0
3
6
9
12
15
18
21
24
27
----------------------------------------
Predikat vracejici vzdy False:
----------------------------------------

11. Přístup k prvkům nekonečné sekvence

Při práci s lazy sekvencemi, které obsahují nekonečný počet prvků, si musíme dát pozor na to, aby se náhodou nespustilo vyhodnocení celé (nekonečné) sekvence. V reálných programech k tomuto problému v naprosté většině případů nedochází, už jen z toho důvodu, že například funkce map (tu jsme si nepopsali, ale je taktéž součástí knihovny) jako svůj parametr akceptuje lazy sekvenci a jejím výsledkem je taktéž lazy sekvence.

My ovšem v následujících příkladech budeme muset zjistit a vypsat hodnotu alespoň několika prvků nekonečných lazy sekvencí. K tomuto účelu nám velmi dobře poslouží funkce nth, take a někdy taktéž poněkud složitější funkce take-while zmíněna v textu výše. Nejjednodušší z této trojice funkcí je nepochybně funkce nth, jež – jak jste již pravděpodobně z jejího názvu uhodli – vrací n-tý prvek sekvence, což většinou znamená, že se vyhodnotí i předchozích n-1 prvků (ovšem ve skutečnosti se výsledky ukládají do vyrovnávací paměti, takže někdy k vyhodnocení nedochází, alespoň ne v Clojure).

Příklad napsaný v Clojure:

user=> (def s (range))
#'user/s
 
user=> (println (nth s 10))
10
 
user=> (println (nth s 10))
10
 
user=> (println (nth s 10))
10
Poznámka: povšimněte si, že se skutečně vždy vrátí desátý prvek původní sekvence.

Zatímco funkce nth vrátí konkrétní prvek z lazy sekvence, je další užitečná funkce nazvaná take nepatrně obecnější, neboť ta vrací prvních n prvků lazy sekvence. Ovšem výsledkem není vektor či seznam těchto prvků, ale taktéž lazy sekvence, což znamená, že k vyhodnocení (získání) prvků dochází později a někdy taktéž vůbec ne. My ovšem v našich příkladech budeme výsledek funkce take vypisovat pomocí REPL, takže k vyhodnocení dojde vždy:

(user=> (println (take 10 s))
(0 1 2 3 4 5 6 7 8 9)
 
user=> (println (take 5 (drop  10 s)))
(10 11 12 13 14)
 
user=> (->> (range) (drop 10) (take 5) println)
(10 11 12 13 14)

12. Funkce nth a take v Pythonu

Nyní se pokusíme použít funkce nth a take v Pythonu. Obě zmíněné funkce jsou v knihovně clj implementovány, takže by s jejich použitím neměl být – alespoň zdánlivě – žádný problém. Začátek skriptu je stejný, jako v předchozích příkladech:

from clj.seqs import nth, take, range
 
 
def hr():
    print(40*"-")
    print()
 
 
def print_sequence(sequence):
    for item in sequence:
        print(item)
    hr()

Vytvoříme nekonečnou sekvenci a třikrát po sobě se pokusíme přečíst její desátý prvek:

sequence = range()
 
item = nth(sequence, 10)
print(item)
 
# pozor na rozdilne chovani!
item = nth(sequence, 10)
print(item)
 
# pozor na rozdilne chovani!
item = nth(sequence, 10)
print(item)

Výsledek může být překvapující – pokaždé totiž dostaneme jiný prvek!:

10
21
32

Je tomu tak z toho důvodu, že v Pythonu nemáme skutečné lazy sekvence, ale „pouze“ generátory, které si pamatují svůj stav a funkce nth tento stav nenávratně změní.

Podobně je tomu při použití funkce take, která v Clojure vrátí prvních deset prvků (nekonečné) (lazy) sekvence:

sequence = range()
s1 = take(10, sequence)
s2 = take(10, sequence)
s3 = take(10, sequence)

Výsledek bude opět odlišný od očekávaného stavu:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
Kvůli tomu, že sekvence jsou v Pythonu realizovány přes generátory, nemusí všechny funkce pracovat stejně, jako je tomu v Clojure!

13. Použití funkce flatten

V komunitě vývojářů používajících programovací jazyk Python se poměrně často diskutuje o „správné“ implementaci funkce typu flatten, tj. funkce, která dostane na vstupu rekurzivní datovou strukturu (například seznam seznamů) a vytvoří z ní jednorozměrnou sekvenci. V knihovně clj samozřejmě tato funkce existuje a její chování do značné míry odpovídá stejnojmenné funkci implementované v programovacím jazyce Clojure. Podívejme se tedy nejdříve na to, jak se tato užitečná funkce používá v Clojure:

(def colors ["red", "blue", "green", "yellow", "cyan", "magenta", "black", "white"])
(def c1 [colors [1 [2 [3 [4 [5 6 7 8 9]]]]]])
(def c2 [[c1] c1])
 
(println (flatten colors))
(println (flatten c1))
(println (flatten c2))

Výsledek by měl vypadat následovně:

(red blue green yellow cyan magenta black white)
 
(red blue green yellow cyan magenta black white 1 2 3 4 5 6 7 8 9)
 
(red blue green yellow cyan magenta black white 1 2 3 4 5 6 7 8 9 red blue green yellow cyan magenta black white 1 2 3 4 5 6 7 8 9)

V Pythonu můžeme postupovat naprosto stejným způsobem, pouze nesmíme zapomenout naimportovat správnou funkci:

from clj.seqs import flatten
 
colors = ["red", "blue", "green", "yellow", "cyan", "magenta", "black", "white"]
c1 = [colors, [1, [2, [3, [4, [5, 6, 7, 8, 9]]]]]]
c2 = [[c1], c1]
 
print(list(colors))
print(list(flatten(colors)))
print()
 
print(list(c1))
print(list(flatten(c1)))
print()
 
print(list(c2))
print(list(flatten(c2)))

Výsledky budou vypadat podobně, i když samozřejmě reprezentace seznamů a sekvencí bude při tisku odlišná od programovacího jazyka Clojure:

['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white']
['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white']
 
[['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white'], [1, [2, [3, [4, [5, 6, 7, 8, 9]]]]]]
['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white', 1, 2, 3, 4, 5, 6, 7, 8, 9]
 
[[[['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white'], [1, [2, [3, [4, [5, 6, 7, 8, 9]]]]]]], [['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white'], [1, [2, [3, [4, [5, 6, 7, 8, 9]]]]]]]
['red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white', 1, 2, 3, 4, 5, 6, 7, 8, 9, 'red', 'blue', 'green', 'yellow', 'cyan', 'magenta', 'black', 'white', 1, 2, 3, 4, 5, 6, 7, 8, 9]

14. Funkce shuffle

V některých situacích (v mém případě například při psaní testů) je zapotřebí vzít vstupní sekvenci a náhodně v ní proházet jednotlivé prvky. Tuto operaci zajišťuje funkce nazvaná shuffle. Opět se nejdříve podívejme na to, jak se tato funkce používá v programovacím jazyce Clojure. Není to nic těžkého – pouze desetkrát vypíšeme sekvenci s náhodně proházenými prvky:

(def colors ["red", "blue", "green", "yellow", "cyan", "magenta", "black", "white"])
 
(dotimes [n 10]
    (println (shuffle colors)))

Výsledek bude vypadat například takto (pokaždé ovšem bude jiný):

[green cyan black white red magenta yellow blue]
[cyan white black green yellow red blue magenta]
[red green white black yellow blue cyan magenta]
[black magenta red yellow blue green white cyan]
[yellow blue white cyan magenta green red black]
[cyan black yellow white green magenta red blue]
[blue black magenta white yellow green red cyan]
[yellow blue cyan white magenta red black green]
[red cyan yellow black white blue green magenta]
[green cyan black blue magenta red yellow white]
Poznámka: ve skutečnosti se tato funkce poněkud odlišuje od ostatních funkcí, s nimiž jsme se prozatím seznámili. Je tomu tak z toho důvodu, že vyhodnocení této funkce není „líné“, ale výsledná sekvence je ihned takzvaně „realizována“, tj. jsou vypočteny její prvky, aniž by jazyk Clojure čekal, jestli někdo sekvenci či její prvky bude ve skutečnosti potřebovat.

Použití stejnojmenné funkce v Pythonu:

from clj.seqs import shuffle
 
colors = ["red", "blue", "green", "yellow", "magenta", "cyan", "white", "black"]
 
for i in range(1, 10):
    print(list(shuffle(colors)))

Výsledky budou vypadat následovně:

['yellow', 'green', 'cyan', 'magenta', 'blue', 'black', 'white', 'red']
['magenta', 'green', 'yellow', 'white', 'red', 'cyan', 'blue', 'black']
['blue', 'red', 'black', 'cyan', 'yellow', 'white', 'magenta', 'green']
['green', 'cyan', 'red', 'black', 'white', 'yellow', 'blue', 'magenta']
['black', 'yellow', 'white', 'cyan', 'green', 'blue', 'red', 'magenta']
['blue', 'cyan', 'white', 'black', 'magenta', 'red', 'green', 'yellow']
['magenta', 'white', 'blue', 'green', 'yellow', 'cyan', 'black', 'red']
['cyan', 'red', 'black', 'magenta', 'white', 'green', 'yellow', 'blue']
['green', 'yellow', 'blue', 'black', 'red', 'cyan', 'magenta', 'white']

15. Rozdělení sekvence do podskupin s využitím funkce group-by

Sekvenci je možné rozdělit do skupin s využitím funkce vyššího řádu pojmenované group-by. Této funkci se kromě rozdělované sekvence předává i další funkce, jejíž návratová hodnota je použita pro rozpoznání skupiny (může se jednat o libovolnou hodnotu kromě nil). Podívejme se například na způsob rozdělení sekvence přirozených čísel na tři skupiny:

  1. Čísla dělitelná třemi
  2. Čísla, u kterých po vydělení třemi dostaneme zbytek 1
  3. Čísla, u kterých po vydělení třemi dostaneme zbytek 2
(def s (range 1 100))
 
(def groups (group-by #(mod % 3) s))
 
(def k (sort (keys groups)))
 
(doseq [key k]
    (println key (get groups key)))

Výsledky:

0 [3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99]
1 [1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97]
2 [2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 77 80 83 86 89 92 95 98]

Podobně můžeme rozdělit názvy barev podle délky názvu:

(def colors ["red", "blue", "green", "yellow", "cyan", "magenta", "black", "white"])
 
(def groups (group-by #(count %) colors))
 
(println groups)

Výsledky:

{3 [red],
 4 [blue cyan],
 5 [green black white],
 6 [yellow],
 7 [magenta]}
Poznámka: tato funkce je zvláštní tím, že jejím výsledkem je slovník (dictionary), jehož klíče jsou získány z funkce předané do group-by a hodnoty jsou nově vypočtené podsekvence.

16. Funkce group_by v Pythonu

Naprosto stejným způsobem budeme postupovat v Pythonu, ovšem jméno funkce se pochopitelně muselo změnit z group-by na group_by:

from clj.seqs import group_by
 
sequence = range(1, 100)
 
print(group_by(lambda x: x % 3, sequence))
 
groups = group_by(lambda x: x % 3, sequence)
 
keys = sorted(groups.keys())
 
for key in keys:
    print(key, groups[key])

Výsledek rozdělení čísel do tří skupin:

0 [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99]
1 [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97]
2 [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98]

Rozdělení jmen barev podle délky jmen:

colors = ["red", "blue", "green", "yellow", "cyan", "magenta", "black", "white"]
 
groups = group_by(lambda color: len(color), colors)
print(groups)

Výsledkem je slovník s pěticí dvojic klíč-hodnota:

{3: ['red'],
 4: ['blue', 'cyan'],
 5: ['green', 'black', 'white'],
 6: ['yellow'],
 7: ['magenta']}

17. Sloučení několika sekvencí funkcí interleave

Dalo by se říci, že opakem funkce group-by je funkce pojmenovaná interleave. Ta slouží pro proložení prvků ze dvou či více sekvencí do sekvence nové. Nejprve se ze všech vstupních sekvencí získá stejný počet prvků určený nejkratší sekvencí. Následně se postupně vytvoří sekvence nová pravidelným prokládáním prvků všech (obecně zkrácených) vstupních sekvencí. Podívejme se na jednoduchý příklad, v němž nejprve vytvoříme sekvenci celých čísel a barev a posléze sekvenci celých čísel, barev a znaků hvězdičky:

(def s (range 1 10))
 
(def colors ["red", "blue", "green", "yellow", "cyan", "magenta", "black", "white"])
 
(println (interleave s colors))
 
(println)
 
(println (interleave s colors (repeat 10 "*")))

Výsledky:

(1 red 2 blue 3 green 4 yellow 5 cyan 6 magenta 7 black 8 white)
(1 red * 2 blue * 3 green * 4 yellow * 5 cyan * 6 magenta * 7 black * 8 white *)
Poznámka: povšimněte si, jak jsme elegantně vytvořili sekvenci s deseti hvězdičkami. Taktéž stojí za pošimnutí, že sekvence s celými čísly i hvězdičkami byly zkráceny na délku osmi prvků.

18. Funkce interleave v Pythonu

Použití funkce interleave v Pythonu je prakticky totožné s výše uvedeným příkladem určeným pro Clojure. Takže jen krátce:

from clj.seqs import interleave, repeat
 
def hr():
    print(40*"-")
    print()
 
 
def print_sequence(sequence):
    for item in sequence:
        print(item)
    hr()
 
 
sequence1 = range(1, 10)
sequence2 = ["red", "blue", "green", "yellow", "orange", "cyan", "white", "black"]
 
print("Two sequences interleaved:")
print_sequence(interleave(sequence1, sequence2))
 
print("Three sequences interleaved:")
print_sequence(interleave(sequence1, sequence2, repeat("*", 10)))

Výsledky (nyní jsou prvky sekvencí vypsané pod sebou):

Two sequences interleaved:
1
red
2
blue
3
green
4
yellow
5
orange
6
cyan
7
white
8
black
----------------------------------------
Three sequences interleaved:
1
red
*
2
blue
*
3
green
*
4
yellow
*
5
orange
*
6
cyan
*
7
white
*
8
black
*
----------------------------------------
Poznámka: ve skutečnosti nalezneme v knihovně clj ještě větší množství více či méně užitečných funkcí, ovšem ty nejdůležitější již byly popsány.

19. Repositář s demonstračními příklady

Zdrojové kódy všech dnes zmíněných demonstračních příkladů byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/lisps-for-python-vm. V případě, že nebudete chtít klonovat celý repositář (ten je ovšem stále velmi malý, stále doslova několik kilobajtů), můžete namísto toho použít odkazy na jednotlivé příklady, které naleznete v následující tabulce:

Alternativní (a přibližně ekvivalentní) příklady naprogramované přímo v Clojure:

20. Odkazy na Internetu

  1. clj – repositář s knihovnou
    https://github.com/bfontaine/clj
  2. clj 0.1.0 – stránka na PyPi
    https://pypi.python.org/py­pi/clj/0.1.0
  3. Clojure aneb jazyk umožňující tvorbu bezpečných vícevláknových aplikací pro JVM (4.část – kolekce, sekvence a lazy sekvence)
    https://www.root.cz/clanky/clojure-aneb-jazyk-umoznujici-tvorbu-bezpecnych-vicevlaknovych-aplikaci-pro-jvm-4-cast-kolekce-sekvence-a-lazy-sekvence/
  4. Clojure a bezpečné aplikace pro JVM: sekvence, lazy sekvence a paralelní programy
    https://www.root.cz/clanky/clojure-a-bezpecne-aplikace-pro-jvm-sekvence-lazy-sekvence-a-paralelni-programy/
  5. Python becomes a platform
    https://khinsen.wordpress­.com/2012/03/15/python-becomes-a-platform/
  6. Python becomes a platform. Thoughts on the release of clojure-py
    https://news.ycombinator.com/i­tem?id=3708974
  7. SchemePy
    https://pypi.org/project/SchemePy/
  8. lispy
    https://pypi.org/project/lispy/
  9. Lython
    https://pypi.org/project/Lython/
  10. Lizpop
    https://pypi.org/project/lizpop/
  11. Budoucnost programovacích jazyků
    http://www.knesl.com/budoucnost-programovacich-jazyku
  12. LISP Prolog and Evolution
    http://blog.samibadawi.com/2013/05/lisp-prolog-and-evolution.html
  13. List of Lisp-family programming languages
    https://en.wikipedia.org/wi­ki/List_of_Lisp-family_programming_languages
  14. clojure_py na indexu PyPi
    https://pypi.python.org/py­pi/clojure_py
  15. PyClojure
    https://github.com/eigenhom­bre/PyClojure
  16. Hy na GitHubu
    https://github.com/hylang/hy
  17. Hy: The survival guide
    https://notes.pault.ag/hy-survival-guide/
  18. Hy běžící na monitoru terminálu společnosti Symbolics
    http://try-hy.appspot.com/
  19. Welcome to Hy’s documentation!
    http://docs.hylang.org/en/stable/
  20. Hy na PyPi
    https://pypi.org/project/hy/#des­cription
  21. Getting Hy on Python
    https://lwn.net/Articles/596626/
  22. Programming Can Be Fun with Hy
    https://opensourceforu.com/2014/02/pro­gramming-can-fun-hy/
  23. Přednáška o projektu Hy (pětiminutový lighttalk)
    http://blog.pault.ag/day/2013/04/02
  24. Hy (Wikipedia)
    https://en.wikipedia.org/wiki/Hy
  25. Clojure home page
    http://clojure.org/
  26. Clojure Sequences
    http://clojure.org/sequences
  27. Making Clojure Lazier
    https://clojure.org/reference/lazy
  28. Clojure Data Structures
    http://clojure.org/data_structures
  29. Clojure
    https://en.wikipedia.org/wiki/Clojure
  30. Clojars
    https://clojars.org/
  31. Seznam knihoven na Clojars
    https://clojars.org/projects
  32. Clojure – Functional Programming for the JVM
    http://java.ociweb.com/mar­k/clojure/article.html
  33. Clojure quick reference
    http://faustus.webatu.com/clj-quick-ref.html
  34. 4Clojure
    http://www.4clojure.com/
  35. ClojureDoc (rozcestník s dokumentací jazyka Clojure)
    http://clojuredocs.org/
  36. SICP (The Structure and Interpretation of Computer Programs)
    http://mitpress.mit.edu/sicp/
  37. Pure function
    http://en.wikipedia.org/wi­ki/Pure_function
  38. Funkcionální programování
    http://cs.wikipedia.org/wi­ki/Funkcionální_programová­ní
  39. Čistě funkcionální (datové struktury, jazyky, programování)
    http://cs.wikipedia.org/wi­ki/Čistě_funkcionální
  40. Dynamic Languages Strike Back
    http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html
  41. Scripting: Higher Level Programming for the 21st Century
    http://www.tcl.tk/doc/scripting.html
  42. Threading macro (dokumentace k jazyku Clojure)
    https://clojure.github.io/clo­jure/clojure.core-api.html#clojure.core/->
  43. Understanding the Clojure → macro
    http://blog.fogus.me/2009/09/04/un­derstanding-the-clojure-macro/
  44. Emacs LISP
    https://www.root.cz/clanky/historie-vyvoje-textovych-editoru-eine-zwei-emacs/#k08
  45. Programovací jazyk LISP a LISP machines
    https://www.root.cz/clanky/pro­gramovaci-jazyk-lisp-a-lisp-machines/
  46. Speciální formy, lambda výrazy a makra v programovacím jazyku LISP
    https://www.root.cz/clanky/specialni-formy-lambda-vyrazy-a-makra-v-programovacim-jazyku-lisp/
  47. Programovací jazyky používané (nejen) v SSSR (část 3 – LISP)
    https://www.root.cz/clanky/pro­gramovaci-jazyky-pouzivane-nejen-v-nbsp-sssr-cast-3-ndash-lisp/
Našli jste v článku chybu?