\documentstyle[czech]{article}
%\documentstyle[czech,twocolumn]{article}
\begin{document}
\begin{verbatim}
Uprava podla r. 1996, 1999

- �vod, hist�ria,
     literat�ra:
     H. Abelson, G.J.Sussman, J.Sussman:
     Structure and Interpretation of Computer Programs,
     MIT Press 1985
- implement�cia XSCHEME:
     server barbora: N:\msdos\xscheme\.
- interpret, read-eval-print cyklus
- (exit)
     ukon�enie programu, pou�i� v z�tvork�ch

- vyjadrovacie prostriedky jazyka pre:
  - element�rne v�razy
  - mo�nosti kombin�cie
  - mo�nosti abstrakcie
- dva druhy objektov - m��u ma� zhodn� syntax
  - proced�ry (program)
  - data

- z�klady jazyka:
- ��sla, aj re�lne
- zoznamy ako volania funkci�
- +, -, *, /,  aj viacargumentov�
pr.: >(* (+ 2 2 2) (+ 3 3 3 ))
     54
- vyhodnocovanie, voln� syntax, medzery ako oddelova�e
     ka�d� v�raz m� v�sledn� hodnotu, ktor� sa vracia

- premenn�, men�
- �peci�lna forma define pre defin�ciu hodn�t (glob�lnych)
     premenn�ch
(define delka 7)
(define obvod (* delka 4))
     ; okam�it� vyhodnotenie, vykon� sa: obvod := 28
- okolie (enviroment) ako ,,abstraktn�" pam��
  - obsahuje dvojice meno_premennej - hodnota
  - v okol� sa zhroma��uj� v�zby z "define"-formy, v�zby
form�lnych parametrov proced�r na pred�van� hodnoty a v�zby
ur�en� v "let"-forme

- vyhodnocovanie v�razov:
  - najprv sa vyhodnotia podv�razy (rekurz�vne)
  - aplikuje sa proced�ra  (hodnota naj�av�ieho prvku - oper�tor)
     na hodnoty ostatn�ch argumentov - operandy
- vyhodnocovanie zlo�en�ho v�razu - odspodu, pr�klad
  - vyhodnocovanie ��sel, vstavan�ch oper�torov, ostatn�ch mien
  - �peci�lne formy (napr. define, exit) a ich argumenty sa
     vyhodnocuj� �peci�lne
  - vyhodnocovanie z�vis� na okol�

- defin�cie (u��vate�sk�ch) proced�r
  schematicky: (define (<meno> <form�lne_parametry>) <telo>)
  pr. (define (kvadr�t x) (* x x))
      (define (l1_norma x y) (abs (- x y)))

- pr�klad zlo�itej�ieho vyhodnocovania:
  - v SCHEME sa pou��va:
     substitu�n� model,
     odpoved� volaniu hodnotou, preto�e v�etky parametry vstupuj�
           do fnc. vyhodnoten�
pr.: (define (sucet_kvadratov  x y) (+ (kvadrat x) (kvadrat y)))
     (define (f a) (sucet_kvadratov (+ a 1) (* a 2)))
postup vyhodnocovania:
(f 5)                  ; volanie
(sucet_kvadratov (+ 5 1) (* 5 2))  ; rozvinutie funkcie f
     ; a nahrada form�lneho param. a aktu�lnou hodnotou 5
(sucet_kvadratov 6       10     )  ; vyhodnotenie arg.
(+ (kvadrat 6) (kvadrat 10))       ; rozvinutie fnc. sucet_kvadratov
(+ (* 6 6 )    (* 10 10)   )       ; rozvinutie fnc. kvadrat, 2x
(+ 36          100         )       ; redukcia vstavanej fnc.
136                                ; vysledok

- in� vyhodnocovac� model (pou��van� v in�ch funcion�lnych
           jazykoch):
  expanzia a� na element�rne oper�tory, potom redukcie (tzv.
     volanie menom)
  - nev�hody volania menom: viacn�sobn� vyhodnocovanie spolo�n�ch
     podv�razov
  - v�hoda - lep�ia kone�nos�
     na tom istom programe sa volanie hodnotou zacykl�, ale volanie
     menom skon��: napr. ak sa zacykl� vyhodnocovanie argumentu,
     ktor� sa potom nepou��va.

- �peci�lne formy:
  - pre podmienen� pr�kaz:
  (cond  (<podm1> <v�raz1>)
         (<podm2> <v�raz2>)
         ...
         (<podmN> <v�razN>))
  - podmienky sa postupne zhora vyhodnocuj�, prv�, ktor� sa spln�
     nech je podm_i, potom sa vyhodnocuje v�raz_i a jeho hodnota
     je hodnotou celej podmienky
  - postupn� vyhodnocovanie podmienok -
     je d�le�it�, ale je to odch�lenie od deklarativity
  - pr�klad (define (abs x)
                 (cond ((> x 0) x)
                       ((= x 0) 0)
                       (else    (- x))
            )    )
  - pravdivostn� hodnoty - false je (), nil, #f
    - in� hodnoty sa ch�pu ako true
  - posledn� z�chytn� podmienka - (ELSE ...)
  - ak nie je splnen� �iadna podmienka, chovanie z�vis� na
implement�cii:
     1. cond vr�ti nil
     2. v�sledok je nedefinovan� (tj. n�hodn�)
     3. behov� chyba

- vstavan� fce <, =, >, <=, >=

- (if <podm> <v�raz> <alternat�va>)
  - podmienky ako str��e - d�le�itos� postupn�ho vyhodnocovania v
     podmienkach
  pr.: (define (moje_if ...) ...)
    - moje_if vyhodnot� obidve vetvy, aj ke� niektor� z nich nem�
           zmysel (tj. sp�sob� behov� chybu), pr�padne sa zacykl�
    - pr.: faktorial(0) = 0 * faktorial(-1)

- vstavan� funkcie and, or - na �ubovo�nom po�te argumentov
- (not arg)

Pr. zlo�itej��:
Newtonova itera�n� met�da v�po�tu odmocniny x.
x1 (po�iato�n� odhad) = 1
�al�� odhad: x_(i+1)= priemer(x_i, x/x_i)
po�adovan� presnos�: |odhad - x| < 0.001

(define (sqrt x)
  (define (presny? odhad x)                    -- pomocn� fnc.
    (< (abs (- (kvadrat odhad) x)) .001 ))
  (define (priemer x y)
    (/ (+ x y) 2))
  (define (zlepsi odhad x)
    (priemer odhad (/ x odhad)))
  (define (sqrt_iter odhad x)
    (if (presny? odhad x)
        odhad
        (sqrt_iter (zlepsi odhad x) x)))
 (sqrt_iter 1 x))                              -- telo

- define m� blokov� �trukt�ru
  - pomocn� proc. s� schovan�
- viazan� (~lok�lne) x voln� (~glob�lne) premenn�
  - form�lne parametre
- vyhodnocovanie vo�n�ch premenn�ch
  - z�vis� na "nadradenom" okol�

- program�torsk� techniky:
- (line�rna) rekurzia:
  (define (faktorial n)
    (if (= n 1)
        1
        (* n (faktorial (- n 1)))))
  - rekurzia
  - pou��va z�sobn�k, spotreba pam�ti O(n)
  - intern� postup v�po�tu je tento (vyhodnocovanie if
           preskakujem):
     (f 4)
     (* 4 (f 3))
     (* 4 (* 3 (f 2)))
     (* 4 (* 3 (* 2 (f 1))))
     (* 4 (* 3 (* 2 1)))
     (* 4 (* 3 2))
     (* 4 6)
     24

- iter�cia:
  (define (faktorial n)
    (f_iter 1 1 n))
  (define (f_iter s c n)         s��in ��ta� n, invariant s=(c-1)!
    (if (> c n)
         s
         (f_iter (* s c) (+ c 1) n)))
  - iter�cia
  - pou��va stavov� premenn�
    - �pln� ,,stav" v�po�tu m�m pr�stupn� (tj. pod kontrolou)
    - pam�� : O(1) - pri dobrej implement�cii
    - postup v�po�tu (vyhodnocovanie if preskakujem):
     (faktorial 4)
     (f-iter  1 1 4)
     (f-iter  1 2 4)
     (f-iter  2 3 4)
     (f-iter  6 4 4)
     (f-iter 24 5 4)
     24

- Fibonacciho ��sla, dva programy pre porovnanie
  - rekurz�vny, neline�rny
  (define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          ( else (+ (fib (- n 1))
                    (fib (- n 2)) ))))

  - itera�n�
  (define (fib n)
    (fib_iter 1 0 n))
  (define (fib_iter a b citac)
    (if (= citac 0)
        b
        (fib_iter (+ a b) a (- citac 1))))
  - pri itera�nom sp�sobe si v stavov�ch premenn�ch (ktor�ch je
ur�it� po�et) pam�t�m stav v�po�tu, resp. zauj�mav�/potrebn�
�as� stavu. Ak budem po��ta� nejak� in� postupnos�, v ktorej
�al�� �len z�vis� na kon�tantnom po�te predch�dzaj�cich �lenom,
m��em roz��ri� po�et stavov�ch premenn�ch - argumentov. Ak budem
po��ta� postupnos�, kde �al�� �len z�vis� na v�etk�ch
predch�dzaj�cich �lenoch postupnosti, nem��em pred�va� jednotliv�
�leny samostatne, ale m��em ich preda� v�etky naraz: budem ma�
(jeden) stavov� argument, ktor� bude obsahova� dosia� spo��tan�
�as� postupnosti. Samozrejme v tomto pr�pade bude ve�kos�
spotrebovanej pam�ti z�visie� na reprezent�cii stavov�ho
argumentu.

- pr.: Euklidov alg. - najv���� spol. delite�
  (define (nsd a b)
    (if (= b 0)
        a                          ; v�sledok
        (nsd b (remainder a b))))  ;
  -- remainder - vstavan� fnc., zvy�ok po delen� (modulo)

- (1999) deklarativnost FP
  definicia funkcie je rovnost, tj. zapis 
    (define (f args) telo)
  sa deklarativne pochopi ako (definicna) rovnost f(args) = telo

  - proceduralne sa rovnosti pouzivaju orientovane, tj. ako 
	prepisovacie pravidla
  - podmienky v tele: funkcia je niekolko podmienenych rovnosti

  - vypocet odpoveda rieseniu sustavy rovnic
    - zadanie (tj. program a volanie) je sustava rovnic 
	v implicitnom tvare - tj. prave strany obsahuju volania
	inych funkcii
    - riesenie je v explicitnom (vyriesenom) tvare: prava strana 
	neobsahuje volania inych funkcii, len hodnoty, tj. datove 
	struktury (aj zlozene ...)
  - program je teoria, ktoru mozete skumat, upravovat beznymi 
	matematickymi a logickymi metodami
    - skumat: ci odpoveda zamyslanej semantike, ci platia invarianty
    - upravovat: do efektivnejsieho tvaru

- programovanie funkci� vy���ch r�dov, funkcion�lne parametre
pr.: s��et kvadr�tov ��sel od a do b
(define (sum2 a b)
  (if (> a b)
      0
      (+ (kvadrat a)
         (sum2 (+ a 1) b ))))
- analogicky by sme nap�sali funkciu sum1 pre s��et ��sel od a
     do b

- abstrakcia:
Chceme definova� funkciu, ktor� odpoved� "sume", ale nie "sume
kvadr�tov"
  - abstraktne:
  (define ( <meno>  a b)
    (if (> a b)
        0
        (+ ( <funkcia> a)
           ( <meno> ( <next> a) b))))
  - <funkcia> a <next> sa stan� parametrami:

  - konkr�tne v scheme:
  (define (sum f a next b)         -- f a next s� funk�n� param.
    (if (> a b)
        0
        (+ (f a)                         -- volanie f
           (sum f (next a) a next b))))

  - pou�itie sum - defin�cia p�vodn�ch funkci� sum1 a sum2
  (define (sum2 a b) (sum kvadrat a 1+ b))
  (define (sum1 a b) (sum id      a 1+ b))
    - ost�va definova�: id, 1+

- pou�itie sum: v numerickom integrovan�
- in� mo�n� abstrakcia: sum ako iterat�vny v�po�et
- je mo�n� e�te vy��ia abstrakcia:
  - funkcii sum (s��tanie)  s oper�ciami 0 a + je podobn�
    funkcia PI  (n�sobenie) s oper�ciami 1 a *

- �peci�lna forma: lambda
  defin�cia anonymnej proced�ry
  - m� zmysel, len ak sa proced�ra pou�ije len jedenkr�t
    p��e na mieste jedin�ho pou�itia
  - syntax:
  (lambda ( <form�lne_parametre> )  <telo> )
  pr.:
  (define (sum1 a b )
    (sum (lambda (x) x)                  -- identita
         a
         (lambda (x) (+ x 1))            -- 1+
         b ))

  - define pre proced�ry je syntaktick� cukor:
  (define (sum1 a b) <telo> ) je interne to ist� ako:
  (define sum1 (lambda (a b) <telo> ))

  - spec. forma lambda je konstruktor funkcii, 
	vyhodnotenie (s danymi argumentami) je selektor
  - funkcie su objekty "prvej kategorie":
    je ich mozne predavat ako parametre, vracat ako hodnoty, 
	integrovat do datovych struktur ...
  - anomymne funkcie su casto jednoucelove parametre funkcii 
	vyssich radov
  - ! potreba lambda funkcii svedci o inom sposobe programovania:
    1) hodnota vyrazu (tj volania) funkcie sa pouziva jedenkrat,
	v kontexte podla miesta vyskytu 
    2) programy je mozne parametrizovat kodom, tj. lambda funkciou
       - aj anonymnym, jednoucelovym
       - aj dynamicky vytvorenym
	
- zlozene d.s.
  - na implementa�nej �rovni je definovany konstruktor a selektory:
  
  jedin� zlo�en� datov� �trukt�ra - dvojica, p�r (angl. pair)
  kon�truktor: (cons x y) - vr�ti dvojicu
  selektory: car, cdr - prv� a druh� zlo�ka
  plat�:
  >(define a (cons 1 2))
  a
  >(car a)
  1
  >(cdr a)
  2
  >a
  (1 . 2)	; vypis parov

  - dvojica v pam�ti - cons vyhrad� pam�� a zap��e adresy svojich
     argumentov:
                       �����������������������������Ŀ
    implement�cia      � pointer na x � pointer na y �
                       �������������������������������

- pracova� len s dvojicami je nepr�jemn�:
  kon�trukcia zoznamov, ako d.�.:
  >(list 1 2 3)
  (1 2 3)
  - zoznam je syntaktick� cukor pre postupnos� cons 
	(asociovanu doprava)
    ekv.: (cons 1 (cons 2 (cons 3 ())))

- reprezentacia termov, s obecnym poctom argumentov:
  hlava je funkcny symbol, telo je zoznam argumentov
  matematicky : 	1 + 2 * (3 + 4)
  reprezentacia:        (+ 1 (* 2 (+ 3 4)))

- pr. n-t� prvok zoznamu
  (define (nth n x)
     (if (= n 0)       -- zacneme od 0 (na rozdiel od slajdov)
         (car x)
         (nth (- n 1) (cdr x)) ))
          ^spracovanie ^tela zoznamu

- pr. d��ka zoznamu
  (define (length x)
    (if (null? x)      ; test na pr�zdnos� zoznamu x
        0
        (+ 1 (length (cdr x))) ))
                     \-----/ 
			typicky: hodnota sa pouzije na mieste
    	vyskytu ako parameter dalsej funkcie 
	=> nepotrebujeme priradenie
  - ale: mozne nevyhody:
    - viacnasobne pocitanie hodnoty (neefektivita)
    - definovanie lokalnych pomocnych podvyrazov (prehladnost)
    => specialna forma let

- �peci�lna forma: let
  defin�cia lok�lnych v�zieb
  - syntax:
    (let (( <prem1> <v�raz1)
          ( <prem2> <v�raz2)
           ...
          ( <premN> <v�razN))
      <telo> )
  - vyhodnotia sa v�etky <v�raz>y, potom sa <prem>enn� asociuj�
so spo��tan�mi hodnotami a potom sa <telo> vyhodnot� v takto
vzniknutom okol�.
  - let je ,,blok", rozsah platnosti premenn�ch je telo, po jeho
ukon�en� sa ,,oddefinuj�"
  - v�razy sa v�hodnocuj� s��asne, s pou�it�m extern�ho okolia
     (na rozdiel od pou�itia nieko�kych define za sebou)
    => vyhodnocovanie a priradenie je paraleln�, tj. v�menu hodn�t
     dvoch premenn�ch m��eme nap�sa�
     (let ((a b) (b a)) <telo>)
  - let je syntaktick� cukor pre:
  ((lambda ( prem1  prem2  ... premN ) telo )  -- aplikuj fnc
             vyraz1 v�raz2 ... v�razN )        -- na argumenty
     - pri vyhodnocovan� funkcie sa najprv vyhodnotia aktu�lne
           parametre, potom sa navia�u na form�lne parametre
           a potom sa vyhodnocuje telo
- pou�itie: pr.:
  - defin�cia pomocn�ch v�po�tov, napr. viacn�sobne pou�it�ch
     volan�; ak by sa nepou�ilo let, ka�d� volanie fce kvadr�t sa
     vyhodnocuje zvl���
  (define (g x)
    (let ((y (kvadrat x)))
      (/ y (+ y 1))))

  - forma let neumo��uje defin�ciu vz�jomne rekurz�vnych
(pomocn�ch) funkci� pou�it�ch v tele hlavnej funkcie
  => �pec. forma LETREC so zhodnou syntaxou, ale pou�itie
     <prem>enn�ch vo <v�raz>och sa odkazuje na pr�ve definovan�
     <prem>enn�, nie na ich hodnoty z glob�lneho okolia
    - implementacne zavisle

  - implementacia vazieb: okolie je zoznam dvojic meno-hodnota.
    Pri vyhodnocovani sa hlada prvy vyskyt premennej v okoli.
    Let prida dvojice na zaciatok (zoznamu) okolia. 
    Vyhodnocovaci stroj si pamata zaciatok okolia.
    - technicke detaily: dva sposoby vazby premennych: 
        staticky a dynamicky.
      - staticky (v Scheme): premenna ma hodnotu z okolia v ktorom 
	bola definovana
      - dynamicky (Lisp): premenna ma hodnotu z okolia, v ktorom 
	bola volana

- define, lambda a let umo��uj� myslie� a programova�
funkcion�lne.

--- (zlo�en�) datov� �trukt�ry:
- datov� abstrakcie
  - chceme nejak� reprezent�ciu pre racion�lne ��sla, komplexn�
     ��sla ...
- popis line�rnej kombin�cie: ax+by
  (define (lin_komb a b x y)
     (add (mul a x) (mul b y)))
  t�to defin�cia/program by mal sl��i�, ak x a y s� ��sla,
     vektory alebo matice
  - lin_komb nem��e pozna� vn�torn� �trukt�ru (typ) x, y
    => abstraktn� data
  - lin_komb nem��e pozna� konkr�tne funkcie add, mul
    => generick� oper�tory
- probl�m viacer�ch reprezent�ci�:
    komplexn� ��sla m��u by� zadan�/reprezentovan� v s�radnicovom
alebo pol�rnom tvare. Chceme, aby oper�tory prij�mali obidva
tvary.
  - mo�n� rie�enie:
    data si sebou nes� (aj) inform�ciu o type:
    { ,,suradnicov�_tvar", x, y }
    { ,,pol�rny_tvar",     uhol, velkost }
    - (rozne) konstruktory pre komplexne cisla
    (define (mk_polar velkost uhol) 
	(cons 'polar (cons velkost uhol)) )
    (define (mk_rect real imag)
	(cons 'rect (cons real imag)) ) 
  - oper�tory si maj� mo�nos� zisti�, ak� data dostali.
    
- vytv�ranie datov�ch �trukt�r
  - nem�me spr�vu pam�ti, pointry (pod svojou kontrolou)
  - kon�truktor : vznik d.�. zo zlo�iek, (podobn� ,,new"
     v Pascale), vracia ,,objekt"
  - selektor(y) : pr�stup na zlo�ky v ,,objekte"
  - kon�truktor a selektory umo��uj� v�robu d.�. a pr�cu s d.�.
na n�zkej �rovni abstrakcie, maj� odtieni� konkr�tnu
reprezent�ciu d.�.

- pr. racion�lne ��sla
  kon�truktor, vracia ,,racion�lne_��slo" :
     (make_rac <citatel> <menovatel>)
  selektory - vracaj� zlo�ky:
     (citatel <rac>)
     (menovatel <rac>)
  - pozn.: kon�truktor a selektory musia by� kompatibiln�, ale
selektory nemusia vracia� presne to, �o dostal kon�truktor. Napr.
pri (ka�dej) kon�trukcii rac. ��sla m��e prebehn�� vydelenie citate�a 
a menovate�a ich najv����m spolo�n�m delite�om.

- oper�cie s rac. ��slami:
  - s��tanie rac. ��sel
    vytvor�m nov� rac. ��slo pre s��et - pomocou kon�truktoru
    na argumenty pristupujem len pomocou selektorou
    (define (+rac x y)
       (make_rac (+ (* (citatel x)   (menovatel y))
                    (* (menovatel x) (citatel   y)))
                 (* (menovatel x) (menovatel y)) ))

- (jedna mo�n�) reprezent�cia rac. ��sel:
  (define (make_rac x y) (cons x y))
  (define (citatel x)   (car x))
  (define (menovatel x) (cdr x))

- abstrak�n� bari�ry (v pr�pade rac. ��sel):
    u��vatelsk� program ...
      (program) pou��va rac. ��sla
        - navrhuje u��vate�
    (interface) +rac -rac *rac /rac =rac ...
      (program) pravidl� pre po��tanie s rac. ��slami
        - navrhuje tvorca oper�ci� s  rac. ��slami
    (interface) make_rac citatel menovatel
      (program) implement�cia r.�. ako dvoj�c
        - navrhuje tvorca d.�. pre rac. ��sla
    (interface) cons car cdr
      (program) implement�cia dvoj�c
        - navrhuje implement�tor scheme

- priklady na rozne spracovanie hornerovej schemy
  A) vyhodnotenie Hornerovej schemy
  - vstup je zoznam koeficientov a hodnota 
  - vysledok je cislo     
; koeficienty su vo vsetkych prikladoch od najnizsieho
(define (eval_hs koefs x)
	(if (NULL? Koefs)
	    ()
	    (+ (car koefs) 
	       (* x (eval_h (cdr koefs) x)) )))
  
  B) vytvorenie funkcie, ktora vyhodnocuje H.s.
  - vstup su len koeficienty, vystup je funkcia, az ta dostane 
	hodnotu
  - vracaju sa (anonymne) funkcie
  - pri pouziti v tele je vytvorenu funkciu nutne 
	aplikovat na hodnotu x
(define (mk_hsf koefs)	; "chyba" parameter pre x
    (if (null? koefs)
       (lambda (x) 0)
       (lambda (x) (+ (car koefs)
                      (* x
                         ((mk_hsf (cdr koefs)) x) ))) ))
  - pouzitie
>((mk_hsf '(3 2 1)) 2)
17
; testy
(define (t2 x) ((mk_hsf '(3 2 1)) x))
(write (map (mk_hsf '(3 2 1)) '(0 1 2 3)))  (newline)
  ;>>(3 6 11 18) 

 C) Vytvorenie symbolickeho vyrazu
  - vstup su koefs a MENO premennej
  - vystup je (vyhodnotitelny) vyraz (s neefektivitou na konci)
(define (mk_hsexp koefs prem)	; parameter prem je MENO premennej
    (if (null? koefs)
       0
       (list '+ (car koefs)
             (list '* prem (mk_hsexp (cdr koefs) prem)) ))) 

  - pouzitie: 
    - symbolicka hodnota y sa vyskytuje vo vyraze
>(mk_hsexp '(3 2 1) 'y)
(+ 3 (* y (+ 2 (* y (+ 1 (* y 0))))))
  
  - varianta z prednasky: 
(define (mk_hsexp1 koefs prem)	; parameter prem je MENO premennej
    (cond ((null? koefs) 0)	; prazdny zoznam
	  ((null? (cdr koefs)) (car koefs)) ; jednoprvkovy,
		; vracia sa cislo z hlavy
          (else
            (list '+ (car koefs)
              (list '* prem (mk_hsexp (cdr koefs) prem))) )))) 
>(mk_hsexp '(3 2 1) 'y)
(+ 3 (* y (+ 2 (* y 1))))

  - varianta s backquote:
    ...
    (else `(+ ,(car koefs) 
              (* ,prem ,(mk_hsexp (cdr koefs) prem))) )) ))

- pouzitie pre vyhodnotenie 
  - pre funkcie eval a apply neexistuje typ v typovanom jazyku
    => nejdu priamociaro previest do typovaneho jazyka (Haskell)
ad B)
  - vytvorena funkcia je v internom tvare:
>(mk_hsf '(3 2 1))
#<Procedure #ee2>

  - aplikacia funkcie na zoznam argumentov
>(apply (mk_hsf '(3 2 1)) '(2) ))     ; ocakava 1 argument
11		; vysledok
    - apply sa v pripade, ze je (v case "kompilacie") znamy pocet
argumentov, moze nahradit klasickym volanim (f a1 ... an). Ak nie je
znamy pocet argumentov, musime pouzit apply
 
ad C)
  - vstavana funkcia eval vyhodnocuje vyrazy, tj. je to interpret 
	zdrojoveho kodu
>(define y 2)	; s let to nefunguje
>(eval (mk_hsexp '(3 2 1) 'y)) 
11
  - u eval su technicke problemy s vazbou premennych:
    - hodnota y musi byt definovana 

- symbolick� data - dosia� sme pracovali len s ��slami
  ako odl��ime symbolick� data, ktor� sa nemaj� vyhodnocova� od
     premenn�ch, ktor� sa maj� vyhodnocova�?
  idea: �peci�lna forma quote

  (quote data) - vr�ti data bez vyhodnotenia
  'data        - to ist�, ale skr�tene; syntaktick� cukor

  - pr.:
  >(list 'a 'b)        -- nevyhodnocuje a ani b
  (a b)
  >(car '(a b c))      -- (1) , argumentom car je zoznam (a b c)
  a                    -- jeho prv� prvok je a.
  >(list 'car (list 'quote '(a b c)))
  (car (quote (a b c))) -- ,,syntakticky" zhodn� s (1), ale toto
                             je v�sledok (tj. data)

  - v�etko sa vyhodnocuje, ale kon�tanty sa vyhodnotia na seba
    => nemusia by� uveden� apostrofom
    ��sla        3     3.14
    re�azce      "pgm/meno.txt"
    znaky        #\a
    logick�      #t    #f

- in� datov� �trukt�ry: bin�rne vyh�ad�vacie stromy
     vrchol m� tri zlo�ky: L, R    �av� a prav� podstrom
                           H       hodnotu
     dve mo�nosti reprezent�cie vrcholu:
     a)    .                       b)    .
          / \                           / \
         H   .                         L   .
            / \                           / \
           L   R                         H   .
                                            / \
                                           R   ()
  - realiz�cia:
  a) (define (make_t L H R)        ; kon�truktor
           (cons H (cons L R)) )
     (define (getl T) (cadr T))    ; selektory
     (define (getr T) (cddr T))
     (define (geth T) (car T))
  b) (define (make_t L H R)        ; kon�truktor
           (list L H R) )
     (define (getl T) (car T))     ; selektory
     (define (getr T) (caddr T))
     (define (geth T) (cadr T))
  - nad takto definovan�m interface m��em budova� �al�ie
     proced�ry
  - syntaktick� cukor: (cadr x) je skr�tena verzia (car (cdr x)),
analogicky pre ostatne cxxr a cxxxr

- pr�klady
; append - sp�janie zoznamov
(define (app2 a b)
  (if (null? a)
       b
       (cons (car a) (app2 (cdr a) b))))

; reverse - naivn� obr�tenie zoznamu
(define (rev a)
  (if (null? a)
      ()
      (app2 (rev (cdr a)) (list (car a)))))
- DC: obr�tenie v line�rnom �ase s pou�it�m akumul�tora

- funkcie vy���ch r�dov: obsahuj� funkcion�lne parametre
MAP ... funkcia, ktor� aplikuje dan� funkcion�lny parameter
(jedn�ho argumentu) na ka�d� prvok zoznamu a z v�sledkov utvor�
zoznam
(zjednodu�en� verzia, vstavan� funkcia MAP je obecnej�ia)
  (define (MAP f l)
    (if (null? l)                 ; test pr�zdneho zoznamu
        '()                       ; v�sl. je pr�zdny zoznam
        (cons (f (car l))         ; v�sl. je zoznam, hlava vznikne
                                  ; aplik�ciou f na hlavu l
              (MAP f (cdr l)) )))  ; telo z�skame z rekurzie
pr. volania:
     > (map (lambda (x) (* x x)) '(2 3 4))
     (4 9 16)
     > (map kvadrat '(2 3 4))
     (4 9 16)
- vstavan� MAP m� premenn� po�et parametrov - zoznamov, ktor� je
schopn� spracova�. Funkciu dan� ako parameter vol� postupne na
prv� prvky zoznamov, druh� prvky zoznamov ... a z v�sledkov
zostav� v�sledn� zoznam. Z popisu plynie, �e v�etky zoznamy musia
ma� zhodn� d��ku.
pr. volan�
>(map < '(1 4) '(2 3))
(#t ())
  ; vracia sa dvojprvkov� zoznam, jeho hodnoty s� true #t
     a false () a vznikn� z volan� (< 1 2) a (< 4 3)
>(map + '(1 2 3 4) '(5 6 7 8))
(6 8 10 12)


FILTER ... funkcia, ktor� dostane funkcion�lny parameter (jednoho
argumentu) a zoznam. Zo zoznamu vypusti v�etky prvku, pre ktor�
nie je splnen� dan� fnc. parameter
(define (filter f l)
  (if (null? l)
      '()                                      ; sprac. l=()
      (if (f (car l))                          ; test hlavy
          (cons (car l) (filter f (cdr l)))    ; pridanie hlavy
          (filter f (cdr l)) )))               ; vynechanie hlavy
  - v�imnite si, �e hoci s� v tele pou�it� dve rekurz�vne
volania, ka�d� je v inej vetve if-pr�kazu. Preto sa z nich vykon�
najviac jedno a v�po�et zost�va line�rny.
- pou�itie:
     (define (between a z x) (and (< a x) (< x z)))
     >(filter  (lambda (x) (between 3 5 x)) '(1 2 3 4 5 6))
     (3 4 5)

MAP a FILTER vyjadruj� parametrick� sp�soby spracovania zoznamu,
pri�om oper�cie, ktor� sa maj� uskuto�ni� na jednotliv�ch
prvkoch, s� dan� funkcion�lnym parametrom.
Ak v�sledok v�po�tu nem� by� zoznam, ale �ubovo�n� datov�
�trukt�ra (jednoduch� alebo rekurz�vna), mus�me ma� obecnej�ie
parametrick� spracovanie zoznamu.

FOLDR ... zvinutie zoznamu sprava
- volanie (FOLDR op e '(x1 x2 ... xn)) vykon� v�po�et
  x1 op (x2 op (... xn-1 op (xn op e)... ))
(define (foldr f e l)
  (if (null? l)
      e
      (f (car l) (foldr f e (cdr l))) ))
  - e je �asto neutr�lny/jednotkov� prvok k oper�cii f
pr�klady:
- (define (suma l) (foldr + 0 l))  ; scita vsetky ��sla
- (define (PI   l) (foldr * 1 l))  ; vyn�sob� v�etky ��sla
- (define (length l)   ; po��tanie d��ky zoznamu
     (foldr (lambda (x y) (+ y 1)) 0 l))
- (define (append x y) (foldr y cons x)) ; spajanie dvoch zoznamov
- (define (mappend l) (foldr append () l)) ; spajanie zoznamov
- (define (insert x l)
     (cond ((null? l) (list x))
           ((< (car l) x) (cons (car l) (insert x (cdr l)) ))
           (else (cons x l)) ))
  (define (insertsort l)     ; znamy insertsort
     (foldr insert () l))
  - map pomocou fold: 
  (define (map f l) 
    (foldr (lambda (x y) (cons (f x) y)) () l) )
    -(hodili by sa nejake operacie na funkciach: skladanie ...)

- m�me bin�rnu funkciu max po��taj�cu maximum, chceme maximum
     zoznamu
  (define (maxl l) (foldr max (car l) (cdr l)))
     ; maximum nem� zmysel z pr�zdneho zoznamu
  - podobne priemer nem� zmysel po��ta� z pr�zdneho zoznamu
    => vymyslie� (a naprogramova�) in� oper�ciu, ktor�
       spracov�va nepr�zdne zoznamy
    => foldr1, ktor� spracuje jeden (posledn�) prvok zoznamu
       - pre po��tanie priemeru sa mus� v�sledok (dvojica ��sel pre
s��et a po�et) e�te po skon�en� rekurzie vydeli� - tj. potrebujeme
postspracovanie mimo rekurziu

FOLDL ... zvinutie zoznamu zlava
- volanie (FOLDL op e '(x1 x2 ... xn)) vykon� v�po�et
  ((...((e op x1) op x2) ... op xn-1) op xn
(define (foldl f e l)
  (if (null? l)
      e
      (foldl f (f e (car l)) (cdr l)) ))
  - e sa pou��va ako akumul�tor medziv�sledkov
pr�klady:
- mnoh� asociat�vne z u� uveden�ch vy��ie
- (define (reverse l)        ; obr�tenie zoznamu
     (foldl (lambda (x y) (cons y x)) () l))   ;
  - odpoveda pouzitiu akumulatoru

- niektore operacie nemaju definovanu hodnotu na prazdnom zozname, 
napr min a max. Pre tieto operacie je vhodny mierne upraveny 
prechod strukturou, foldr1, resp. foldl1
  (define (foldr1 op l)
    (cond ((null? l) (write 'error_in_foldr1)) ; prazdne l
          ((null? (cdr l)) (car x))	; jednoprvkovy l
          (else (op (car l) (foldr1 op (cdr l)))) ))
    - foldr1 moze potrebovat predspracovanie prvku pomocou map.
	Ina moznost by bola zadat specialnym funkcionalnym parametrom,
	 ako sa spracuje posledny prvok

  - foldl1 sa od foldl odlisuje na zaciatku, preto rekurziu nemusime 
explicitne, ale s pomocou fold 
  (define (foldl1 e op l)
    (if (Null? l) 
        (write '(error in_foldl1 empty_list))
        (foldl (car l) op (cdr l)) ))

- nie vzdy su priebezne vysledky vo forme pozadovanej pre vystup.
Napriklad aritmeticky priemer je mozne napisat pomocou fold, ale
musim si pamatat dve hodnoty pre pocet a sucet prvkov. 
Az po skonceni rekurzie sa spocita pozadovany vysledok
  (define (priemer l)
    (/ (suma l) (length l)) ; 2x fold
  - takto napisany priemer ma dve nevyhody: 
    1) priemer nie je definovany pre prazdny zoznam 
       => lepsie je pouzit foldr1
    2) struktura sa prechadza dvakrat
       => vylepsit:
Operacia bude pracovat s dvojicami (pocet,sucet), 
map prevedie zoznam cisel na zoznam dvojic. 
Let potrebujeme na zapamatanie vysledku, z ktoreho potom 
vytahujeme jednotlive zlozky.
  (define (priemer1 l)
    (let ((a (foldr1 (lambda (x y) 
                       (cons (+ (car x) (car y))
                             (+ (cdr x) (cdr y)) ))
                     (map (lambda (x) (cons 1 x)) l) )))
         (/ (cdr a) (car a)) ))

- parametrick� oper�cie je mo�n� definova� aj na in�ch d.�., napr.
na maticiach:
MAPMAT ako parametrick� un�rna oper�cia s maticou po prvkoch:
funkcia MAPMAT, ktor� dostane funkcion�lny parameter f
a aplikuje ho na v�etky prvky matice. MAPMAT musi pozna�
a vyu��va� vn�torn� �trukt�ru matice.
- matica je reprezentovan� ako zoznam zoznamov: m��eme nap�sa�
explicitn� dvojit� rekurziu, ale tie� m��eme pou�i� map na
spracovanie ka�dej �rovne zoznamov => dostaneme dve vnoren�
volania map:
(define (mapmat f m)
     (map                          ; aplik�cia na riadky
           (lambda (v) (map f v))  ; sprac. prvkov v riadku
              m ))                 ;
pou�itie:
>(mapmat (lambda (x) (* 10 x)) '((1 2) (3 4)))
((10 20) (30 40))

- DC: definova� MAPMAT pre riedku reprezent�ciu mat�c, tj. matica
je dan� ako zoznam troj�c pre v�etky nenulov� koeficienty:
     (index_i, index_j, hodnota_ij)

MAP2MAT ako paramerick� bin�rna oper�cia s maticami po prvkoch
(define (map2mat f m1 m2)
     (map                ; aplik�cia na dvojice zhodn�ch riadkov
        (lambda (v1 v2) (map f v1 v2)) ; spracovanie riadkov
           m1 m2))
defin�cia s��tania (analogicky od��tania) mat�c:
(define (+mat m1 m2) (map2mat + m1 m2))

DC: zobecnenie n�sobenie mat�c, kde oper�cia skal�rneho s��inu
dvoch vektorov sa abstrahuje na form�lny parameter.

--- funkcie ako v�stupn� hodnoty:
- defin�cia zlo�enia dvoch funkci� jednej premennej:
(define (slozeni f g)
     (lambda (x) (f (g x))) )      ; vracia sa funkcia
- pou�itie:
>((slozeni kvadrat 1+) 3)
16
  - vyhodnot� sa volanie funkcie "slozeni", ktor� vytvor� a vr�ti
nejak� funkciu (resp. reprezent�ciu funkcie), t� sa potom
aplikuje na ��slo 3 a vyhodnot� sa.

- pr�klad: defin�cia funkcion�lu "+n", ktor� k ��slu n vr�ti
funkciu jednoho argumentu, ktor� pri��tava n (vracia sa inkrement
o n)
(define (+n n) (lambda (x) (+ x n))
  pou�itie:
     >((+n 3) 5)
     8
     >(map +n '(1 2 3))
     -- vr�ti trojprvkov� zoznam funkci�, kde prv� funkcia
           inkrementuje o 1, druh� o 2 a tretia o 3


------------------
- vstavan� proced�ry: podrobnej�ie v manu�le
     (LOAD subor)
           na��ta s�bor
           pr.: (load "pgm/moje.s")
             ! aj v ceste su lomitka
     (EXIT) ukon�enie pr�ce

- testy ...
(null? x)        vracia #t, ak x je ()
- aritmetika ...
- de�trukt�vne priradenia
(set! premenn� v�raz)
(set-car! dvojica v�raz)
(set-cdr! dvojica v�raz)

- sekven�n� v�po�ty
(BEGIN <v�raz> ...)
(SEQUENCE <v�raz> ...)

- definovanie a z�skavanie vlastnost� symbolov
- vstup/vystup

- vyhodnocovanie
MAP - u� bolo
(APPLY fnc zoznam_argumentov)
     aplikuje funkciu na zoznam argumentov
     pr.: >(apply * '(2 3 4))
           24
     - argumenty s� data, ktor� m��em ich vytvori� (na��ta�)
     po�as behu programu a n�sledne pou�i� pri vyhodnocovan�
(EVAL v�raz)
     vyhodnot� v�raz
     pr.: >(EVAL '(* 2 3 4))
          >(EVAL (LIST * 2 3 4))
          24
     - v�raz, ktor� sa doteraz spracov�val a tvoril ako data,
     m��em prehl�si� sa zdrojov� k�d a necha� ho vyhodnoti�
     => str�ca sa rozdiel medzi datami a programom

; Erathostenovo sito
; najprv pomocn� predik�ty:
; v�roba intervalu ako d.�.
(define (int od do)
  (if (> od do)
       ()
       (cons od (int (1+ od) do)) ))

; filter zoznamu l pod�a predik�tu pred
(define (fl pred l)
  (cond ((null? l) '())
        ((pred (car l)) (cons (car l) (fl pred (cdr l))) )
        ( else (fl pred (cdr l))) ))

; delite�nos�
(define (delit x y)
  (= (remainder x y) 0))
- pou�itie:
(define (delit2 x) (delit x 2))

; ladiaci test
(write (fl delit2 (int 1 10)))

; vlastn� E. sito
(define (sito l)
  (if (null? l)
    ()
    (let ((prvoc (car l))) ; "v�zna�n� lok. hodnota" -prvo��slo
      (write (list prvoc)) ; ladiaca tla�
      (cons prvoc          ; n�jden� �al�ie prvo��slo
           (sito (fl (lambda (x) (not (delit x prvoc))) (cdr l))) ))))
                 ; zoznam prefiltrujeme pod�a nedelite�nosti
                 ; aktu�lnym prvo��slom

; ladenie
(write (sito (int 2 20)))
(define (test c)
  (sito (int 2 c)) )
(write (test 30))

- in� realiz�cia car, cdr a cons
car, cdr a cons musia sp�na� podmienky:
(car (cons x y)) = x
(cdr (cons x y)) = y
tieto pravidl� popisuj� koretnos� interface

cons realizovan� pomocou dispatch proced�ry
(define (cons x y)
     (define (dispatch m)
           (cond ((= m 0) x)
                 ((= m 1) y)
                 (else (error "CONS - unexpected arg." m)) ))
     dispatch)   ; cons vracia funkciu
realiz�cia selektorov - volanie vr�tenej funkcie a vhodn�mi
     parametrami
(define (car z) (z 0))
(define (cdr z) (z 1))

e�te in� mo�nos� realiz�cie:
(define (cons x y) (lambda (m) (m x y))
(define (car z) (z (lambda (p q) p)))
(define (cdr z) (z (lambda (p q) q)))

- str�ca sa rozdiel medzi programom a datami, preto�e data s�
realizovan� pomocou v�zieb zachyten�ch vo funkci�ch

- lok�lne premenn� pre stavy a podobnos� s OOP
Preto�e m��em vraca� funkcie ako v�sledky volan�, ni� nebr�ni
tomu, aby sa pri vytv�ran� nejakej d.�. nevytvorili s��asne
funkcie, ktor� s �ou bud� pracova�
- bankov� aplik�cia:
vytvor�m ��et, ktor� si pam�t� zostatok, s� definovan� funkcie
na vyberanie a vkladanie na ��et
(define (make_ucet zostatok)       ; kon�truktor ��tu
     (define (vyber suma)          ; def. lok�lnej fnc.
       (if (>= zostatok suma)
           (sequence (set! zostatok (- zostatok suma))
                     zostatok)
           "Nedostatok hotovosti"))
     (define (vloz suma)           ; dal�ia lok. fnc.
       (set! zostatok (+ zostatok suma))
       zostatok)
     (define (spracuj m)     ; dispatch fnc.
       (cond ((eq? m 'vyber) vyber) ; fnc. vyber vol�m id. vyber
             ((eq? m 'vloz)  vloz)
             (else (error "MAKE_UCET: Nezn�ma spr�va" m))
     ) )
  spracuj) ; vracia sa dispatch funkcia
pou�itie:
>(define acc (make_ucet 1000))
acc
>((acc 'vyber) 600)
400
>((acc 'vyber) 500)
"nedostatok hotovosti"
>((acc 'vloz) 900)
1300
  -- (acc 'vyber) sa vyhodnot� na funkciu lok�lne zn�mu pod
menom vyber, ktor� sa aplikuje na hodnotu 600, resp. 500 a vracia
v�sledok, ktor� sa potom vyp��e
  - dispatch funkcia, v tomto pr�pade spracuj, umo�nuje k symbolu
(vyber, vloz) vr�ti� "metodu", ktor� sa m��e pou�i� pre zmenu
stavu "objektu".
 - Na rozdiel od OOP:
     - dispatch funkciu si mus�me naprogramova� sami
     - nem�me tu �iadnu "typov�" kontrolu, ktor� by po�as
       prekladu (na��tavania zdroj�ku) poznala, �e pr�pustn�
       argumenty pre acc s� len 'vyber a 'vloz
     - nen� tu hierarchia a dedi�nos�

----
CVICENIA. 2002, 25.11.
(ob��ben�) Hornerovo sch�ma: (define (hs koefs x) ...)
- viz inde
- ot�zka vhodn�ho poradia koeficientov: dve mo�nosti:
 - pre rekurz�vne spracovanie koef. od abs. �lenu a_0
(pou��va "hs (cdr koefs)" )
 - pre vyhodnocovanie pomocou akumul�tora: naopak od najvy��ieho �lenu
a_n
- vracanie funkci�:
namiesto funkcie dvoch argumentov vyrobim funkciu, ktor� pre
dan� koeficienty vyrob� funkciu ("skompiluje"), ktor� po��ta hodnotu
polynomu pre dan� x. Tj. navratov� hodnota(!) funkcie gen_hs je
funkcia (v nejakej internej reprezent�cii, ktor� je mo�n�
vyhodnoti�, ale nie vyp�sa�)

(define (gen_hs koefs)
        (lambda (x) (hs koefs x))
)
- lambda je kon�truktor funkcie (...), vznik� anonymn� funkcia, ktor�
pou�ijem na mieste v�skytu (alebo si ju pomenujem)
- ot�zka: ako s� zviazan� koefs.

; volanie
> ((gen_hs '(2 1 5)) 3)
; ab       cd        e

vysvetlenie:
podv�raz <d> je zoznam koeficientov, v�aka quote <c> sa nevyhodnocuje.
V�raz <b> sa vyhodnot� na anonymn� funkciu, ktor� sa vyhodnot� v  r�mci
v�razu <a> a parametrom <e>

; povodn� volanie: pre porovnanie:
> (hs '(2 1 5) 3)

- quote, aj v (p�sanom) jazyku:
�ekn�te odpov�� vs. �ekn�te "odpov��".

- generovanie vyv��en�ho stromu
  vstup: usporiadan� zoznam, pocet pouzitelnych prvkov
  vystup: dvojica vyvazeny vyh�. strom, nepou�ite prvky zo zoznamu.
 -
(define (vyvazeny s n)
  (cond ((= n 0) (cons nil s))  ; vraciam prazdny strom a pov. zoznam
        ((= n 1) (cons (mk_tree nil (car s) nil))       ; jednoprv. str.
                       (cds s) ))       ; a zvy�ok zoznamu
        (else
         (letrec                ; rekurzivne let
           ((nl (div (- n 1) 2))        ; velkost laveho
            (nr (div n       2))        ; velkost praveho
            (outl (vyvazeny s nl))      ; vyroba laveho podstromu
            (outr (vyvazeny (cdr  ; uberame 1 prvok zo zvysku pre akt.v.
                             (cdr outl)) ; zvysok po vyrobe laveho
                            nr))        ; velkost praveho, 2. arg.
           )   ; koniec "rekurz�vnych" def. (s� pouziteln� vnoren� let)
           (cons        ; v�roba v�sledku: dvojice
             (mk_tree (car outl)  ; lavy podstrom ako car z outl
                      (car        ; vybranie vnutorneho vrcholu
                        (cdr outl)) ; zo zvy�ku po lavom
                      (car outr)) ; vybratie praveho podstromu
             (cdr outl)         ; vybratie zvy�ku
) )     )) )             ; ...

- ak pou��vam len! kon�truktory a selektory, potom mo�em zmeni�
reprezent�ciu stromov bez zmeny programov (ale kon�tr. prazdneho stromu
je v programe natvrdo).
(define (mk_tree l x r) ; kon�truktor nepr�zdneho stromu
        (cons l (cons x r))) ; trojica, ako dve dvojice
(define (lavy s)        ; def. selektorov
        (car s))        ; vybratie
(define (pravy s)
        (cddr s))       ; vybratie
... ; pre vrchol : DC
- in� repr.: ako trojprvkov� zoznam. Menej efekt�vna (pam��ovo a
n�sledne aj �asovo), podrobnost viz inde (tu��m). DC: ko�truktory a
selektory

DC:
zipWith f as bs: vol� funkciu f na odpovedaj�ce si p�ry prvkov. Zoznamy
s� obecne rozne dlh�.

---------------
cvi�enia 1996
mergesort

rok 1995
na svojom prvom cvi�en� som robil (ale a� po tretej predn��ke):
n�vrh d.�. pre datumy, kon�truktor, selektory
  rozdiel medzi (cons rok (cons mesiac den)) a
                (list rok mesiac den)
  pr�znak ,,typu"
append zoznamov
reverse zoznamov, rekurz�vne aj iterat�vne
multiappend - dost�va zoznam zoznamov, v�etky sp�ja do jednoho
  abstrakcia - sp�jaciu oper�ciu a neutr�lny prvok na sp�jenie ()
     nahradi� parametrami
  defin�cia sumy (a �stne s��inu) zoznamu
�al�ia abstrakcia - namiesto sumy chcem priemer
  - potrebujem ,,pracovn� hodnoty" - dvojice po�et_prvkov,suma
    -''- transform�ciu z vstupn�ch hodn�t do pracovn�ch
                       z pracovn�ch na v�sledn� - v interface
  - pr�ca s dvojicami - pomocou lambda proced�r

- �al�ie n�pady
  - filter zoznamu - napr. len p�rne ��sla,
                           (ne)delite�n� dan�m ��slom
    - abstrakcia filtra - s parametricky dan�m testom
  - Erathostenovo sito
    - potrebuje vygenerovanie intervalu
    - pou��va (abstraktn�) filter
  - n�sobenie riedkych mat�c, ? s��tanie
  - nejak� symbolick� v�po�ty
    - derivovanie, ? zjednodu�ovanie
    - grafov� �lohy

---- 1999
- symbolick� v�po�ty a generovanie k�du:

- tvorba symbolick�ho v�razu k Hornerovej sch�me
  vstup je zoznam argumentov, v�stup je v�raz obsahuj�ci ��sla a
kon�tantu x
(define (h2v koefs)
  (cond ((null? koefs) (write "error in h2v -- pr�zdny zoznam koef."))
        ((null? (cdr koefs)) (car koefs)) ; posledny koef.
        (else (list '+                  ; v�stup je s��et
                    (list '*            ; s��inu
                          (h2v (cdr koefs))     ; polynomu
                          'x )                  ; a x
                    (car koefs) )) ))   ; s prv�m koeficientom
- volanie:
>(h2v '(3 2 1))
(+ (* (+ (* 1 x) 2) x) 3)
  - poradie argumentov sme si zvolili vo funkcii h2v

- kompil�cia v�razu:
  funkcion�lne programovanie m��e vraca� funkcie, tj. ak zad�m v�raz /pre
jednoduchos� jednej premennej/, vr�ti sa funkcia jednej premennej, ktor�
po��ta tento v�raz. E�te jednoduch�ie: v�raz je polynom po��tan�
hornerovou sch�mou, v�sledok je funkcia jednej remennej, ktor� po��ta
hodnotu polynomu.
  - vytvorenie funkcie pre hornerovu sch�mu:
    vstup je zoznam koeficientov vo vhodnom porad�, tj. od najni��ieho,
v�stup je funkcia. Z technick�ch d�vodov pr�zdny zoznam pova�ujeme za
polynom vracaj�ci v�dy 0. /DC: upravi� program, aby kon�il u posledn�ho
koeficientu./

  (define (mk_horner koefs)
    (if (null? koefs)
       (lambda (x) 0)
       (lambda (x) (+ (car koefs)
                      (* x
                         ((mk_horner (cdr koefs)) x) ))) ))
  - volanie:
  >((mk_horner '(3 2 1)) 2)
  11
  >(map (mk_horner '(3 2 1)) '(0 1 2 3)) ; vyhodnocuje viackr�t
  (3 6 11 18)
  >(let ((h (mk_horner '(3 2 1)) )) (cons (h 1) (h 2)) )
  (6 . 11)

  - DC varianta: tvorba funkcie v akumul�tore

  - kompil�cia v�razu:
  vstupom je v�raz s /bin�rnymi/ funk�n�mi symbolmi +, - a *, ��slami a
"premennou" x. Chceme vytvori� odpovedaj�cu funkciu v jednej premennej.
(define (v2f v)
    (cond ((eq? (car v) '+) (lambda (x) (+ ((v2f (cadr v)) x)
                                           ((v2f (caddr v)) x) )) )
          ((eq? (car v) '-) (lambda (x) (- ((v2f (cadr v)) x)
                                           ((v2f (caddr v)) x) )) )
          ((eq? (car v) '*) (lambda (x) (* ((v2f (cadr v)) x)
                                           ((v2f (caddr v)) x) )) )
          ((eq? v 'x) (lambda (x) x))
          ((number? v) (lambda (x) v))
          (otherwise (write "error")) ))

- map pre bin�rne stromy:
  kon�truktor (make_t l x r) pre nepr�zdne stromy, hodnota () pre
pr�zdne stromy
  de�truktory pre nepr�zdny strom:
  (getl s), (getr s), (getx s)
  - vlastn� map
  (define (mapt f s)
     (if (null? s)
        '()
        (make_t (mapt (getl s))
                (f s)
                (mapt (getr s)) ) ))
  - map nezavisi na konkretnej d.s., len na konstruktoroch

  pouzitie:
  vytvorenie p�ru, pri��tanie 1, funkcia pre pridanie kon�tanty
  >(mapt (lambda (x) (cons x x)) STROM)
  >(mapt (lambda (x) (+ x 1)) STROM)
  (define (pridej1k_t konst)
      (mapt (lambda (x) (cons konst x)) STROM) )

- zip pre b.s.
  (define (zipWith f s1 s2) ; v pripade nezhody vracia prazdny strom
    (cond ((null? s1) '() )
          ((null? s2) '() )
          (#t (make_t (zipWith f (getl s1) (getl s2))
                (f (getx s1) (getx s2))
                (zipWith f (getr s1) (getr s2)) ) )))
  - aplik�cia: zip, ktor� vytvor� dvojice
  (define (zip s1 s2)
    (zipWith cons s1 s2)) ; hm

- fold pre bin�rne stromy:
  (define (foldbt e f s)
    (if (null? s)
        e
        (f (foldbt (getl s))
           (getx s)
           (foldbt (getr s)) ) ))

  - aplik�cie foldbt:
    - v��ka stromu:
(define (vyska s) (foldbt 0 (lambda (l x r) (+ 1 (max l r))) s))

    - velkost stromu:
(define (size x) (foldbt 0 (lambda (l x r) (+ l 1 r)) s))
    - mapt pomocou foldbt
(define (mapt f s) 
  (foldbr () (lambda (fl x fr) (make_t fl (f x) fr)) s) )

    - kon�trukcia funkcie "member" pre dan� konkr�tny strom, ktor�
nevyu��va usporiadanie, tj. prech�dza cel� strom. (Preto�e v SCHEME je
vyhodnocovac� model call-by-value, foldbt mus� prejs� cel� strom)
(define (memberfbt s)
  (foldbt (lambda (k) #f)
          (lambda (fl x fr)
             (lambda (k) (or (fl k) (eq? k x) (fr k))) ) ))

    - in� je kon�trukcia funkcie, ak vyu�ijeme usporiadanie stromu.
Uvedomte si, �e pri kon�trukcii prech�dzame cel� strom, pri pou�it�
skon�truovanej funkcie u� len pr�spu�n� cestu.
(define (findfbt s)
  (foldbt (lambda (k) #f)
          (lambda (fl x fr)
            (lambda (k) (cond ((eq? k x) #t)
                              (( < k x) (fl k))
                              (otherwise (fr k)) ))) ))


 6,10.12.'99
- na tychto prikladoch by ste si mali uvedomit, ze vytvorenie pomocnych/
knizni�n�ch funkcii umozni spracovavat cele datove struktury naraz.
Naviac dovo�uje na tejto vy��ej urovni o datovych strukturach rozm���a�,
tj. neobsluhovat jednotlive pointry /spojov�ch �trukt�r/, polo�ky
/z�znamov/, pr�pady /tagu/ ...

- pr. antiunifik�cia:
S� dan� dva termy. Chceme vyrobi� term /v Prologovksom zmysle/, z
ktor�ho by sme mohli obiva termy dostat substit�ciou. Ako reprezent�ciu
premennej budeme pu��va� v�raz 'var .
  Postup: ak s� obidva termy jednoduch� kon�tanty, potom ak s� zhodn�,
v�sledok je t�to kon�tanta, in�� 'var. Ak s� obidva termy zoznamy
zhodnej d��ky, potom v�sledok je zoznam, ktor�ho prvky z�skame
rekurz�vne. In��, v�etne zoznamov r�znej d�zky, v�sledok je 'var.

 (define (au x y)
   (cond ((atom? x) (eq? x y))  ; ak sa zhoduju, y je tiez atom
         ((and (list? x) (list? y)
               (= (length x) (length y)) )
           (aul x y) )          ; antiunif. pre zoznamy
         (#t 'var)              ; inak nezhoda -> premenna
 ))
 (define (aul x y )
   (zipwith au x y))
 (define (zipwith f xs ys)      ; obecny sposob rekurzie
   (if (or (null? xs) (null? ys))
       '()
       (cons (f (car x) (car y))
             (zipwith (cdr xs) (cdr ys)) )))
 - iny sposob: zip do dvojic a potom map, ale s upravenou funkciou
 (define (zipwith f xs ys))
   (map
      (uncurry2 au)   ; (lambda (x) (au (car x) (cdr x))) ;
      (zip xs ys) ))

 - z funkcie dvoch premennych pre zipwith musime vyrobit funkciu jednej
premennej pre map. Ak uvazujeme obvyklu dvojicu vyrobenu pomocou cons,
je prevod (uncurry2 :: (a->b->c) -> a*b->c , pre dvojice)
 (define (uncurry2 f)
   (lambda (x) (f (car x) (cdr x))) )


- pr. v�stavba stromu AC, dopredn� fcia.
Dan� je zoznam slov, slov� s� /kv�li jednoduchosti/ po p�smen�ch.
Chceme vybudova� vyh�ad�vac� strom. Ka�d� uzol obsajhuje tri inform�cie:
1/ p�smeno, ktor� vedie do tohoto vrcholu, 2/ �i tu slovo kon�� /'ano
alebo 'ne/  3/ zoznam podstromov.
  Po navrhnut� tohoto programu mozeme roz��ri� storm a spracovanie, aby
namiesto inform�cie, �i tam slovo kon��, bolo uveden� konkr�tne slovo.
�alej mo�eme zavies� sp�tn� funkciu
  Idea: Tvor�me funkciu ac1. M�me zoznam slov /pre jednoduchos� po
p�smen�ch/, vyberieme prv� p�smeno z ka�d�ho slova a utvor�me dvojicu
p�smeno, slovo. Usporiadame /nen� to nutn�/ a rozdel�me na triedy
"ekvivalencie" pod�a prv�ho p�smena. Dostaneme zoznam dvoj�c,
|p�smeno.slova|. Na ka�d� prvok tohoto zoznamu zavol�me �al�iu funkciu
ac2. T� vyrob� po�adovan� trojicu |p�snemo, koncov�_info, zoznam
podstromov| takto. P�snemo je dostupn�, koncov� info sa z�ska prechodom
zoznamu a otestovan�m , �i taj je nejak� /jedin�/ jednop�smenn� slovo.
potom sa utrhne prv� p�smeno, pr�padn� pr�zdny zbytok odfiltruje a na
zost�vaj�ce �asti slov sa pust� rekurz�vne fcia ac1.
  /Celkov� n�vrh nie je ide�lny, ale n�zorn�. Boli by mo�n�
optimaliz�cie/.

 - predpoklad o vstupn�ch slov�ch: s� nepr�zdne
 (define (ac1 slova)
   (map ac2             ; spracovanie tried rozdelenych podla 1. pism.
        (partition              ; rozdeleni podla 1. zlozky
         (sort                  ; usp. podla 1 zlozky
          (map (lambda (x) (cons (car x) x)))   ; tvorenie dvojic
               slova)) ))       ; slova

 - fcia, ktor� vyrob� po�adovan� trojice:
 (define (ac2 x)
   (let ((z (cdr x)))
     (cons (car x)
      (cons (konec z) (ac1 (neukoncene z)) )) ))

 - celkove volanie: ak chceme vratit vysledok v podobe stromu, trojice:
  (ac2 (cons 'fiktivne pismeno slova))

 - konec je pomocna funkcia, ktora vracia symbol 'ano alebo 'ne podla
toho, ci sa v slovach  vyskytuje jednopismenne slovo (tj. take, ktore sa
nebude spracovavat rekurzivne).
 (define (konec x)
  (if           ; podla toho, ci najdeme jednopismenne slovo
   ( NULL? (filter      ; filtrujeme, viz niekde inde
     (lambda (y) (NULL? (cdr y))) ; test na jednopism slova
     (cdr x)            ; na druhej zlozke vstupu: slovach
   'ne                  ; nenaslo sa
   'ano )))             ; naslo sa

 - fcia neukoncene filtruje prve pismeno a potom prazdne slovo, ak
existuje
 (define (neukoncene ...))

 - zmena d.�. : inform�ciu o tom, �i nejak� slovo kon�� , sme
zjednodusili na 'ano/'ne. Pre dal�iu �as� algoritmu by bolo vhodn� anio
nahradit konkr�tnym slovom. pri s��asnom n�vrhu d.�. ale  zo slova
postupne uber�me p�smen� a na konci u� nem�me dos� inform�ci�, tj. cel�
slovvo. Jedna z mo�nost� je ku ka�d�muu slovu prida� to slovo e�te raz,
najlep3ie v podobe vhodnej pre dal3ie spracovanie alebo pre v7stup.
(pridat tuto informaciu dokazeme jednoducho pomocou map)
M��eme ho prida� do dvojice ako prvu zlo�ku, ale to bude zmanena� z�sah
do k�du na mnoh�ch miestach. Prid�me ho na koniec zoznamu p�smen, za
posledn�. Rekurz�vne spracovanie slov sa nezmen�, zmen� sa o�etrenie
koncov�ch podmienkok, tj. fc�. konec a neukon�en�.
 Reprezentacia slova bude vyzerat takto:
 '(h e r her) alebo '(h e r (h e r))

  - v s�vislosti s t�mito zmenami o v�hode typov: zmena reprezent�cie
sp�sob� zmenu typu /alebo zl� otypovanie/. Zmena typu /vstupu/ u
volajucej funkcie sposobi nutnost zmeny typu u volanej funkcie. Takto sa
zmena reprezentacie vdaka typovej kontrole odpropaguje cel�m programom,
bez nutnosti  ladenia.


- /continuation/
- /komb. pevn�ho bodu:
   F(YF) = YF, Y= \f.(\x.fxx)(\x.fxx)
   Theta TF->F(TF) , T= (\xy.y(xxy))(\xy.y(xxy))
   Tarau to u�� !?/
- /haskell: length x = fold 0 (const (1 +)) x /

------
p�r odladen�ch pr�kladov: rok 1995

; obecny akumulator - s jednotkov�m/koncov�m prvkom e
;   a s kombina�nou funkciou c, doprava asociat�vny
(define (acu e c l)
  (if (null? l)
      e
      (c (car l) (acu e c (cdr l))) ))

; pou�itia akumul�tora - suma a suma druh�ch mocn�n
(define (sum  l) (acu 0 + l))
(define (sum2 l) (acu 0 (lambda (x y) (+ (* x x) y)) l))

; ladiace testy
(write (sum (int 1 10)))
(write (sum2 (int 3 5)))

; pou�itie acc - minimum
(define (min1 l) (acu (car l) min (cdr l) ))  ;; len neprazdne
; ladiace testy
(write (min1 '(2 3 4)))
(write (min1 '(5 4 3)))

; pou�itie acc - append
(define (app1 l) (acu () (lambda (x y) (cons y x)) l))

; howgh
\end{verbatim}
\end{document}
