Neprocedurální techniky

Obecné

Existují hluboké teoretické důvody proč je vhodné nahlížet na implementaci nějakého predikátu/funkce/rozhraní jako na psaní důkazu (konstruktivního). Neprocedurální programování se často snaží přiblížit problému a také využívat technik podobných matematickým důkazům.

Indukce

  • rozdělení na jednotlivé případy a jejich vyřešení za pomoci rekurze. Pozor na korektnost indukce, tedy záruku konečnosti/efektivity výpočtu.
  • velmi vhodná pro uvažování. Datové struktury a různé problémy často mají induktivní charakter.
  • někdy potřebujeme problém zobecnit aby bylo možné indukci použít, například přidat další parametr.

Akumulátor

  • uložení stavu výpočtu v parametru predikátu/funkce.
  • umožňuje deklarativně psát ekvivalenty k cyklům a podobným imperativním technikám které vyžadují průběžné měnění nějakého stavu, což je užitečné především při snižování paměťových nároků koncovou rekurzí.

Haskell

Redukce seznamů

  • knihovní funkce začínají fold, mají různé varianty (v Data.List jsou všechny, v Prelude jen některé)
  • standardně: inicializace hodnoty pro prázdný seznam a pak postupné přikombinovávání prvků seznamu do výsledku
  • redukce může být uzávorkovaná zprava nebo zleva (l nebo r)
  • redukce může být líná nebo striktní (striktní má apostrof navíc)
  • existují i varianty končící znakem 1, které nevycházejí z inicializační hodnoty prázdného seznamu, ale pouze kombinují prvky v seznamu
  • v praxi užitečné v podstatě jen 2 varianty:
    • foldl' pro striktní redukci zleva, když chceme hned celý výsledek
    • foldr pro línou redukci zprava, když chceme líné generování větší struktury
  • redukce lze používat nejen na seznamech, ale i na mnoha jiných datových strukturách (typová třída Foldable)