;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Priklady funkcionalov pracujucich nad linearnym zoznamom.
;;; Autor: Ivan Kapustik
;;; Funkcionaly, teda funkcie, ktorych argumenty su funkcie, poskytuju velku podporu pri
;;; tvorbe strucnych, efektivnych a zrozumitelnych programov vo funkcionalnych jazykoch.
;;; 
;;; Funkcinonaly aplikuju funkciu (funkcie) na vhodne upravene dalsie argumenty funkcionalu.
;;; To znamena, ze typicky aspon jeden z argumentov je strukturovaneho typu, najcastejsie zoznam.
;;; A prave pre zoznamy pozname tri zakladne typy funkcionalov:
;;;   1. transformacia alebo mapovanie
;;;   2. filtrovanie
;;;   3. redukcia, zozbieranie alebo zhrnutie
;;; 
;;; Uloha funkcie je transformovanie (mapovanie) vstupu na vystup. Funkcionalny program ziska
;;; vstupne hodnoty a postupne ho jednotlivymi funkciami transformuje na pozadovany vystup.
;;; Preto ma kazdy funkcionalny jazyk definovanych viacero mapovacich funkcionalov. (map, mapc, ...)
;;; Umoznuju efektivne mapovat vstupny zoznam na vystupny.
;;; Pretoze su definovane vsade, priklad pre ne tu neriesime.
;;; 
;;; Caste su aj filtrovacie funkcionaly, ale pretoze nemusia byt definovane vsade, uvadzame priklad.
;;; Filtrovacie funkcionaly chcu ako vstup taku funkciu, ktora je predikatom - vrati
;;; len hodnoty pravda/nepravda. Ako priklad je zadefinovany funkcional FILTER-BY, ktory prepusti
;;; na vystup prave tie hodnoty, pre ktore je predikat splneny. Za nim su priklady jeho pouzitia a aj
;;; priklad pouzitia vo vnutri funkcie QUICKSORT.
;;; Ine zaujimave filtrovacie funkcionaly su TAKE-WHILE/DROP-WHILE, ktore vratia/zahodia prve take
;;; hodnoty, pre ktore je predikat splneny. 
;;; 
;;; Zaujimave a znacne univerzalne su funkcionaly, ktore zozbieraju/zhrnu/zbalia zoznam do jednej
;;; hodnoty. Maju navyse jeden argument, ktory sa vola akumulator. Do neho postupne zbieraju vysledok.
;;; Funkcia, ktoru dostanu k dispozicii, musi mat dva argumenty - jeden pre prvok a druhy pre
;;; akumulator. Vystupom tejto funkcie je nova hodnota akumulatora, ktora sa pouzije pri spracovani
;;; dalsej hodnoty zoznamu. Akumulator sa tak postupne meni, az kym nie su spracovane vsetky prvky
;;; vstupneho zoznamu. Posledna hodnota akumulatora je vystupom funkcionalu.
;;; Najdolezitejsim reprezentantom tejto skupiny funkcionalov je FOLD. Standardne ma dve realizacie:
;;; FOLDL - spracuva prvky zoznamu zlava doprava a FOLDR - spracuva prvky sprava dolava.
;;; Na pripravenych prikladoch je vidno, ze tieto funkcionaly dokazu zastat nielen svoju primarnu
;;; ulohu, ale dokazu nahradit aj mapovanie a filtre. Na vizualne porovnanie a pochopenie spracovania
;;; zlava a sprava je vhodne pouzit (trace foldl) a (trace foldr), takze je vidno vstupne argumenty
;;; aj jednotlive vystupy.
;;; Dalsie zhrnajuce funkcionaly su FOLDL1/FOLDR1, ktore nevyzaduju akumulator ako argument, ale
;;; pouziju prvu/poslednu hodnotu zoznamu ako inicialnu hodnotu akumulatora. Na vstupe potrebuju
;;; neprazdny zoznam. Funkcionaly SCANL/SCANR maju argumenty ako FOLD, ale na vystupe poskytuju
;;; zoznam vsetkych priebezne vytvorenych hodnot akumulatora.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; filter-by :: function x [a] -> [a]
;;; function :: sv -> bool
(defun filter-by (f list)
  (cond ((null list) nil)
        ((funcall f (first list))(cons (first list)(filter-by f (rest list))))
	(t (filter-by f (rest list))) ))

;;odd-only
;(filter-by #'oddp '(5 6 7 4))
;;only-numbers
;(filter-by #'numberp '(() 5 6 a 7 4 b))
;;bigger-than-five
;(filter-by #'(lambda (n) (> n 5)) '(5 6 7 4))

;;; Zaujimave vyuzitie filter-by
;;; quicksort :: [num] -> [num]
(defun quicksort (lst)
  (cond ((null lst) nil)
        (t (append (quicksort (filter-by #'(lambda (n) (< n (first lst))) (rest lst)))        ;mensie nez pivot
                   (list (first lst))                                                         ;pivot
                   (quicksort (filter-by #'(lambda (n) (>= n (first lst))) (rest lst))) )) )) ;vacsie nez pivot


; (trace quicksort) ;;; Je vhodne pouzit trasovanie na zobrazenie cinnosti. Ukoncenie trasovania je (untrace)
;(quicksort '(5 3 6 7 4))

;;; Iny druh filtra - na vystup dava prvky zoznamu pokial je splnena podmienka.
;;; take-while :: function x [a] -> [a]
;;; function :: sv -> bool
(defun take-while (f lst)
  (cond ((null lst) nil)
	((funcall f (first lst))(cons (first lst)(take-while f (rest lst))))
	(t nil) ))

;;; Iny druh filtra - ignoruje prvky zoznamu pokial je splnena podmienka.
;;; drop-while :: function x [a] -> [a]
;;; function :: sv -> bool
(defun drop-while (f lst)
  (cond ((null lst) nil)
	((funcall f (first lst))(drop-while f (rest lst)))
	(t lst) ))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; foldl :: function x {a} x [a] -> {a}
;;; function :: a x {a} -> {a}  ;; puovodny foldl ma typ: {a} x a -> {a}
(defun foldl (f acc list)
  (cond ((null list) acc) ; Na zaver vrat akumulator
	(t (foldl f (funcall f (first list) acc)(rest list))) ))

;;; foldr :: function x {a} x [a] -> {a}
;;; function :: a x {a} -> {a}
(defun foldr (f acc list)
  (cond ((null list) acc) ; Na zaver vrat akumulator
        (t (funcall f (first list)(foldr f acc (rest list)))) ))


;;; Vyuzitie redukujucich funkcionalov fold
;;copy
;(foldr #'cons () '(5 6 7))
;;reverse
;(foldl #'cons () '(5 6 7))
;;product
;(foldl #'* 1 '(5 6 7))
;;sum
;(foldl #'+ 0 '(5 6 7))
;;maximum
;(foldl #'(lambda (m acc)(cond ((> m acc) m)(t acc))) 0 '(5 6 7 4))
;;all-numbers
;(foldl #'(lambda (m acc)(cond ((numberp m) acc)(t nil))) t '(5 6 7 4))
;(foldl #'(lambda (m acc)(cond ((numberp m) acc)(t nil))) t '(5 6 a 7 4 b))
;;some-numbers
;(foldl #'(lambda (m acc)(cond ((numberp m) t)(t acc))) nil '(() 5 6 a 7 4 b))

;;; Ako filtre:
;;odd-only
;(foldr #'(lambda (m acc)(cond ((oddp m) (cons m acc))(t acc))) () '(5 6 7 4))
;;only-numbers
;(foldr #'(lambda (m acc)(cond ((numberp m) (cons m acc))(t acc))) () '(() 5 6 a 7 4 b))