Programovacie schémy

1. Na hornej úrovni (top)

Redukcia zoznamu (top)

(defun <redukcia> (zoz)
 (cond ((null zoz) <neutralny-prvok>)
       (T (<reduk-funkcia> (first zoz) (<redukcia> (rest zoz))))
 )
)

Príklad, spočítanie čísel. (1 2 3) -> 6
(defun sum (zoz)
 (cond ((null zoz) 0)
       (T (+ (first zoz) (sum (rest zoz))))
 )
)

Ten istý príklad, ale riešený pomocou rekurzie na chvoste.
(defun sum1 (zoz)
 (sum-aux zoz 0)
)

(defun sum-aux (zoz aux)
 (cond ((null zoz) aux)
       (T (sum-aux (rest zoz) (+ (first zoz) aux)))
 )
)

Zobrazenie (top)

(defun <zobrazenie> (zoz)
 (cond ((null zoz) NIL)
       (T (cons (<transf-funkcia> (first zoz)) (<zobrazenie> (rest zoz))))
 )
)

Príklad, čísla v zozname sa umocnia. (1 2 3) -> (1 4 9)
(defun map-square (zoz)
 (cond ((null zoz) NIL)
       (T (cons (* (first zoz) (first zoz)) (map-asquare (rest zoz))))
 )
)

Filter (top)

(defun <filter> (zoz)
 (cond ((null zozo) NIL)
       ((<test> (first zoz)) (<filter> (rest zoz)))
       (T (cons (first zoz) (<filter> (rest zoz))))
 )
)

Príklad, vynechanie čísel. (a 1 c 2) -> (a c)
(defun zrus-cisla (zoz)
 (cond ((null zoz) NIL)
       ((NUMBERP (first zoz)) (zrus-cisla (rest zoz)))
       (T (cons (first zoz) (zrus-cisla (rest zoz))))
 )
)

Počítanie prvkov (top)

(defun <spoc> (zoz)
 (cond ((null zoz) 0)
       ((<test> (first zoz))) (+ 1 (<spoc> (rest zoz))))
       (T (<spoc> (rest zoz)))
 )
)

Príklad, spočíta čisla. (a 1 2 b) -> 2
(defun spocitaj-cisla (zoz)
 (cond ((null zoz) 0)
       ((NUMBERP (first zoz))) (+ 1 (spocitaj-cisla (rest zoz))))
       (T (spocitaj-cisla (rest zoz)))
 )
)

Hľadanie prvkov (top)

(defun <hladaj> (zoz)
 (cond ((null zoz) NIL)
       ((<test> (first zoz)) (first zoz))
       (T (<hladaj> (rest zoz)))
 )
)

Príklad, vráti prvé číslo. (a b c 7 10 1) -> 7
(defun hladaj-preve-cislo (zoz)
 (cond ((null zoz) NIL)
       ((NUMBERP (first zoz)) (first zoz))
       (T (hladaj-preve-cislo (rest zoz)))
 )
)

Generovanie zoznamu (top)

Existuje viacero možností, podľa typu generovania.
Uvádzame príklad a k nemu príslušnú schému.

(defun <urob-zoznam> (par)
 (cond ((<ukonc-test> par) NIL)
       (T (cons (<transf> par) (<urob-zoznam> (<reduce> par))))
 )
)

Príklad z čísla>0, vytvorí zoznam ktorý obsahuje čísla
od 1 až po dané číslo. 4 -> (1 2 3 4)
(defun urob-zoznam (cislo)
 (cond ((= cislo 0) NIL)
       (T (cons cislo (urob-zoznam (- cislo 1))))
 )
)

2. Na ľubovoľnej úrovni (deep)

Základ schém na ľubovoľnej úrovn (deep)

Väčšina schém na ľubovoľnej úrovni má podobný základ, preto ho tu uvádzame.

(defun <name> (sv)
 (cond ((<test> sv) <form1>)
       ((ATOM sv) <form2>)
       (T (<some-fun> (<name> (first sv)) (<name> (rest sv))))
 )
)

Zobrazenie (deep)

(defun <zobraz-h> (sv)
 (cond ((<test> sv) (<transf> sv))
       ((ATOM sv) sv)
       (T (cons (<zobraz-h> (first sv)) (<zobraz-h> (rest sv))))
 )
)

Príklad, funkcia ktorá pripočíta 1 ku každému číslu.
V zozname sú čísla, alebo NIL. (1 4 (2 3)) -> (2 5 (3 4))
(defun add1 (sv)
 (cond ((NUMBERP sv) (+ 1 sv))
       ((null sv) NIL)
       (T (cons (add1 (first sv)) (add1 (rest sv))))
 )
)

Počítanie prvkov (deep)

(defun <pocet> (sv)
 (cond ((<test> sv) 1)
       ((ATOM sv) 0)
       (T (+ (<pocet> (first sv)) (<pocet> (rest sv))))
 )
)

Príklad počet atómov s vlastnosťou číslo. ((1) 2 3) -> 3
(defun pocet (sv)
 (cond ((NUMBERP sv) 1)
       ((ATOM sv) 0)
       (T (+ (pocet (first sv)) (pocet (rest sv))))
 )
)

Redukcia (deep)

(defun <reduk-h> (sv)
 (cond ((<test> sv) sv)
       ((ATOM sv) <neutralny-prvok>)
       (T (<fun-r> (<reduk-h> (first sv)) (<reduk-h> (rest sv))))
 )
)

Príklad, sčíta hodnoty čísel. (1 (2 3)) -> 6
(defun summ (sv)
 (cond ((<test> sv) sv)
       ((ATOM sv) 0)
       (T (+ (summ (first sv)) (summ (rest sv))))
 )
)

Hľadanie prvkov (deep)

(defun <hladaj-h> (sv)
 (cond ((<test> sv) sv)
       ((ATOM sv) NIL)
       (T (OR (<hladaj-h> (first sv)) (<hladaj-h> (rest sv))))
 )
)

Poznámka k OR: Využíva sa tu skutočnosť, že vyhodnocovanie operátora OR
je GC Lispe je implementované ako tzv. lazy evaluation, teda ak splní
aspoň jedna podmienka operátora, už sa nevyhodnocujú daľšie.

Predikáty (deep)

(defun <predikat> (sv)
 (cond ((<test> sv) NIL/T)
       ((ATOM sv)   T/NIL)
       (T (<log-fun> (<predikat> (first sv)) (<predikat> (rest sv))))
 )
)

<predikat><poradie T a NIL><log-fun> Popis
 NONE      NIL T            AND      T, ak v zozname nieje žiadny prvok s danou vlastnosťou.
 EVERY     T NIL            AND      Test, či všetky prvky maju danu vlastnosť.
 SOME      T NIL            OR       Test, či sa v zozname nachadza aspoň 1 prvok s danou vlastnosťou.
 SOME-NOT  NIL T            OR       Test, či sa v zozname nachadza prvok s inou vlastnosťou ako je naša.

Filter (deep)

PRE ZOZNAMY (zoz)
(defun <filter> (zoz)
 (cond ((null zoz) NIL)
       ((<test> (first zoz)) (<filter> (rest zoz)))
       ((ATOM (first zoz)) (cons (first zoz) (<filter> (rest zoz))))
       (T (cons (<filter> (first zoz)) (<filter> (rest zoz))))
 )
)

Príklad, zruší čísla. (1 (2 b) c) -> ((b) c)
(defun zrus-cisla (zoz)
 (cond ((null zoz) NIL)
       ((NUMBERP (first zoz)) (zrus-cisla (rest zoz)))
       ((ATOM (first zoz)) (cons (first zoz) (zrus-cisla (rest zoz))))
       (T (cons (zrus-cisla (first zoz)) (zrus-cisla (rest zoz))))
 )
)

Poznámka: Pre bodka-dvojice je funkcia zložitejšia. Treba brať do
úvahy, že nielen (FIRST sv), ale aj (REST sv) môže byť atóm.

Autori

Posledná aktualizácia 4. 9. 2001