18. března 2017

Catalanova čísla a syntax highlighting

Je to téměř 5 let, co jsem naposled napsal něco na tento blog. Ale doufám, že se to teď změní - moje láska ke Clojure opět propukla s neztenčenou silou a tak snad ponese nějaké užitečné ovoce.

Chvilku ale potrvá, než uvedu blog do použitelného stavu, takže začnu takovým zahřívacím tématem. Tedy, dvěma tématy - sice to není úplně fér, ale vrazil jsem do titulku dva nesouvisející motivy.

Syntax highlighting 3.0

Když jsem s Clojure před šesti lety začínal, bylo ve verzi 1.2 a jeho podpora v různých nástrojích byla nízká, nebo žádná. Jednu z věcí, které jsem tehdy řešil, bylo jak zobrazit na blogu syntax highlighting.

Moje první volba padla na tehdy všudypřítomný SyntaxHighlighter. Musel jsem použít jakýsi externí Clojure brush, protože SyntaxHighlighter dodnes nemá nativní podporu Clojure.

S výsledkem jsem nebyl spokojen, takže jsem po čase zvolil nové řešení - jako letitý uživatel famózního editoru Vim, jsem se rozhodl pro trochu ruční práce a zaangažoval vimovskou funkci :TOhtml. S tou jsem maximálně spokojen a používám ji i na svém druhém blogu SoftWare Samuraj. Přesto jsem se rozhodl potřetí pro změnu syntax highlightingu.

Ten třetí důvod má konsekvence s oživením blogu. Aniž bych si tady vylíval srdíčko, jeden z důsledků mých aktuálních rozhodnutí je, vybudovat si na svém GitHubu jakési Clojure portfolio (už jsem o tom kdysi psal).

Volba GitHubu pro mne nebyla úplně přímočará - nejsem "git guy" a pokud můžu, preferuji Mercurial. Pravdou ale je, že veškerá Clojure komunita je GitHubu, tak proč se tomu vzpírat. No, a když GitHub, tak Gist, to dá rozum.

Catalanova čísla

V rámci svého Clojure-zmrtvýchvstání jsem procházel své staré Clojure kódy a narazil jsem na jeden, který se mi líbil - funkce pro výpočet Catalanových čísel. Pikantní je, že si po těch pěti letech nepamatuju, proč jsem to napsal, nicméně funkce se mi líbily natolik, že jsem se rozhodl se o ně - v rámci zahřátí na provozní teplotu - podělit.

Catalanova čísla jsou sekvencí přirozených čísel, která má zajímavé využití v kombinatorice - binární stromy, průchod mřížkou(?), rozdělení polygonu na trojúhelníky ad. Sekvence je definována následujícím vztahem:


Pokud, tak jako já, nejste úplně kovaní v matematice, tak chviličku googlování potrvá, než zjistíte, že pro implementaci tohoto vzorečku budete potřebovat kombinační číslo (binomial coefficient) a tím pádem faktoriál. Pak už je jednoduché poskládat tyto základní funkce do sebe, jako matrojšku:


Když už jsem se v tom tak vrtal, říkal jsem si: nedá se to udělat nějak jednodušeji, efektněji, víc "Clojure"? A dá. Jen je potřeba vyjít z jiného vzorečku, který definuje Catalanova čísla rekurzivně:
Při použití posledního vzorečku nám tak vyjde pěkná Clojure rekurze. Klíčová slova jsou speciální operátory loop a recur:


GitHub project

Pokud si chcete pohrát s Catalanovými čísly trochu víc, anebo dostat malý bonus navíc, podívejte se na můj projekt na GitHubu:
Navíc dostanete Leiningen projekt, testy v Midje a lazy sekvenci Catalanových čísel.

Související články

3 komentáře:

  1. O clojure vím velmi málo. Líbí se mi, chtěl bych se naučit víc, ale nepropadl jsem tomu jako groovy. Nedokážu si to zatím namapovat na produkční kód.

    A k tomu víc clojure kódu, není if náhodou méně clojure?

    OdpovědětVymazat
    Odpovědi
    1. if je standardní součástí jazyka (viz special forms) a běžně se vyskytuje ve funkcích clojure.core. Možná, že v jiných funkcionálních jazycích je to méně vhodné, ale v Clojure to nikdo neřeší.

      Vymazat
    2. A ještě k tomu "propadnutí" - on je to opravdu velký myšlenkový skok přijít z OOP k Lispu/Clojure. Dneska už mi to tak nepřijde, ale tehdy, když jsem s Clojure začínal, to bylo jako paralelní vesmír. Naprosto "alien" způsob myšlení.

      Vymazat