7 Rekurzija in rekurzivni tipi

Rekurzija je osnovni koncept v logiki, matematiki in računalništvu. V tej lekciji bomo spoznali vlogo rekurzije v programiranju in programskih jezikih.

7.1Rekurzija in negibne točke¶

Pravimo, da je funkcija rekurzivna, kadar kliče sama sebe. Kot primer vzemimo funkcijo f, ki računa faktorielo. V Javi bi jo zapisali takole:

public static int f(int n) {
    if (n == 0) {
        return 1 ;
    } else {
        return n * f(n - 1)
    }
}

Ekvivalentna definicija v Pythonu:

def f(n):
  if n == 0:
      return 1
  else:
      return n * f(n -1)

Ekvivalentna definicija v OCamlu:

let rec f n =
  if n = 0 then 1 else n * f (n - 1)

Ekvivalenta definicija v Haskellu:

f :: Integer -> Integer
f n = if n == 0 then 1 else n * f (n - 1)

Obravnavajmo verzijo v Haskellu. Funkcijo prepišemo takole:

f :: Integer -> Integer
f = \n -> if n == 0 then 1 else n * f (n - 1)

Sedaj definicijo razstavimo na dva dela: na telo rekurzije, ki samo po sebi ni rekurzivno, in na rekurzivni sklic funkcije f same nase:

telo :: (Integer -> Integer) -> (Integer -> Integer)
telo self =  \n -> if n == 0 then 1 else n * self (n - 1)

f :: Integer -> Integer
f = telo f

Pravimo, da smo razprli rekurzivno zanko.

Rekurzivno funkcijo f smo zapisali kot negibno točko funkcije telo.

V našem primeru je $h$ funkcija telo, $X$ je tip Integer -> Integer in $x$ je f. Negibne točke so pomembne tudi na drugih področjih matematike in o njih matematiki veliko vedo.

Ali je tudi rekurzivna funkcija dveh argumentov negibna točka, na primer funkcija, ki računa binomske koeficiente?

binom :: (Integer, Integer) -> Integer
binom (n, k) = if k == 0 || k == n then 1 else binom (n - 1, k - 1) + binom (n - 1, k)

Seveda, saj lahko binom še vedno razstavimo na telo funkcije in sklic samega nase:

telo :: ((Integer, Integer) -> Integer) -> ((Integer, Integer) -> Integer)
telo self = \(n, k) -> if k == 0 || k == n then 1 else self (n - 1, k - 1) + self (n - 1, k)

binom :: (Integer, Integer) -> Integer
binom = telo binom

Kaj pa definicija rekurzivnih funkcij f in g, ki kličeta druga drugo?

Na primer, obravnavajmo funkcijo f, ki kliče f in g, ter funkcijo g, ki kliče f:

f x = if x == 0 then 1 + f (x - 1) else 2 + g (x - 1)
g y = if y == 0 then 1 else 3 * f (y - 1)

Če ju združimo v urejeni par (f, g) in ju zapišemo z λ-računom, dobimo

(f, g) = ((λ x . if x == 0 then 1 + f (x - 1) else 2 + g (x - 1)),
          (λ y . if y == 0 then 1 else 3 * f (y - 1)))

To je rekurzivna definicija urejenega para (funkcij), kar prepišemo v

(f, g) = t (f, g)

kjer je

t = λ (f', g') . ((λ x . if x = 0 then 1 + f' (x - 1) else 2 + g' (x - 1)),
                 (λ y . if y = 0 then 1 else 3 * f' (y - 1)))

Torej tudi za hkratne rekurzivne definicije velja, da so to negibne točke.

7.2Operator fix¶

Recept za rekurzivno funkcijo je vedno isti:

1. Zapišemo telo t funkcije.

2. Definiramo negibno točko f = t f.

Pri tem je samo drugi korak rekurziven in vedno enak. Zapišemo ga lahko kot funkcijo fix, ki izračuna negibno točko dane funkcije:

fix :: (a -> a) -> a
fix t = t (fix t)

V Haskellu tip (a -> a) -> a pomeni »funkcija, ki sprejme funkcjo tipa a -> a in vrne vrednost tipa a. Pri tem je tip a poljuben, pravimo, da je parameter.

Vso rekurzijo smo “spravili” v fix. Od tu naprej bi lahko rekurzivne funkcije definirali s pomočjo fix:

f :: Integer -> Integer
f = fix (\ self n -> if n == 0 then 1 else n * self (n - 1))

Poglejmo postopek še enkrat, tokrat zapisan z λ-računom:

1. Prvotna definicija f se glasi: f n = if n = 0 then 1 else n * f (n - 1)

2. Zapišemo s pomočjo λ-abstrakcije: f = λ n . if n = 0 then 1 else n * f (n - 1)

3. Ločimo rekurzijo in telo funkcije: f = t f kjer je t = (λ g n . if n = 0 then 1 else n * g (n - 1))

4. S pomočjo fix definiramo f: f = fix t

7.3Iteracija je poseben primer rekurzije¶

V ukaznem programiranju poznamo zanke, na primer zanko while:

while b do c done

Tudi ta je negibna točka! Res, taka zanka je ekvivalentna svojemu »odvitju«

if b then (c ; while b do c done) else skip

Če pišemo W za našo zanko, dobimo:

W ≡ (if b then (c ; W) else skip)

Torej je W negibna točka funkcije

t = (λ V . if b then (c ; V) else skip)

saj velja

(while b do c done) = t (while b do c done)

7.4Rekurzivni seznami¶

Rekurzivno lahko definiramo tudi razne druge strukture, ne samo funkcij. Na primer, neskončni seznam

ℓ = [1, 2, 1, 2, 1, 2, ...]

lahko v Haskellu definiramo rekurzivno:

ℓ = 1 : 2 : ℓ

7.5Rekurzivni tipi¶

V tem razdelku bomo spet delali z OCamlom, kasneje pa v Haskellu. Do sedaj smo spoznali podatkovne tipe:

• produkt a * b in zapisi

• vsota a + b

• eksponent a → b

S temi konstrukcijami ne moremo dobro predstaviti bolj naprednih podatkovnih tipov, kot so seznami in drevesa. Poglejmo na primer, kako se tvori sezname celih števil:

• prazen seznam: [] je seznam

• sestavljen seznam: če je x celo število in ℓ seznam, je tudi x :: ℓ seznam

Zapis [1; 2; 3] je okrajšava za 1 :: (2 :: (3 :: [])).

Seznami so rekurzivni podatkovni tip, saj gradimo sezname iz seznamov. Brez uporabe posebnih oznak [] in :: bi zgornjo definicijo zapisali takole (oznaki Nil in Cons izhajata iz programskega jezika LISP, kjer pišemo nil in (cons x ℓ)):

• prazen seznam: Nil je seznam

• sestavljen seznam: če je x celo število in ℓ seznam, je tudi Cons (x, ℓ) seznam

Seznam [1; 2; 3] je okrajšava za Cons (1, Cons (2, Cons (3, Nil))).

V OCamlu se tako definicijo zapiše takole:

type seznam =
  | Nil
  | Cons of int * seznam

Spet imamo opravka z rekurzijo. Tipi, ki se sklicujejo sami nase v svoji definiciji, se imenujejo rekurzivni tipi.

In spet vidimo, da je rekurzija negibna točka. Podatkovni tipi seznam je negibna točka za preslikavo T, ki slika tipe v tipe:

seznam = T (seznam)

kjer je T definiran kot

T a = (Nil | Cons of int * a)

Z besedami: T je funkcija, ki sprejme poljuben tip a in vrne vsoto tipov Nil | Cons of int * a.

7.5.1Induktivni tipi¶

Izhajamo iz definicije seznama:

type seznam = Nil | Cons of int * seznam

Vprašajmo se: ali ta definicija zajema neskončne sezname? Na primer:

Cons (1, Cons (2, Cons (3, Cons (4, Cons (5, ...)))))

Ali se mora to kdaj zaključiti z Nil? Možna sta dva odgovora. Če zahtevamo, da morajo biti elementi rekurzivnega tipa končni, govorimo o induktivnih tipih. Če pa dovolimo neskončne elemente, govorimo o koinduktivnih tipih.

Poglejmo najprej induktivne podatkovne tipe. To so rekurzivni tipi, v katerih vrednosti sestavljamo začenši z osnovnimi s pomočjo konstruktorjev in neskončne vrednosti niso dovoljene. Primeri:

1. naravna števila

2. končni seznami

3. končna drevesa

4. abstraktna sintaksa jezika:

   • programski jeziki

   • jeziki za označevanje podatkov

5. hierarhija elementov v uporabniškem vmesniku

7.5.2Splošni rekurzivni tipi¶

Rekurzivni tipi so lahko zelo nenavadni:

type d = Foo of (d -> bool)

Vrednost tipa d je oblike Foo f, kjer je f funkcija iz d v bool. Ali znate zapisati kako tako vrednost?

7.5.3Strukturna rekurzija¶

Ker so induktivni podatkovni tipi definirani rekurzivno, jih običajno obdelujemo z rekurzivnimi funkcijami. Kot primer si oglejmo, kako bi implementirali iskalna drevesa.

Obravnavajmo preprosta iskalna drevesa, v katerih hranimo cela števila. Iskalno drevo je

• bodisi prazno

• bodisi sestavljeno iz korena, ki je označen s številom x, ter dveh poddreves l in r pri čemer velja:

  • vsa števila v vozliščih l so manjša od x,

  • vsa števila v vozliščih r so večja od x

Primer drevesa:

       5
      / \
     3   8
      \   \
       4  10
         /  \
        9   20

Podatkovni tip v OCaml se glasi:

type searchtree = Empty | Node of int * searchtree * searchtree

V tipu nismo shranili informacije o tem, da je iskalno drevo urejeno! Če bo programer ustvaril iskalno drevo, ki ni pravilno urejeno, prevajalnik tega ne bo zaznal.

7.6Koinduktivni tipi¶

Poznamo še en pomembno vrsto rekurzivnih tipov, to so koinduktivni tipi. Pojavljajo se v računskih postopkih, ki so po svoji naravi lahko neskončni.

Tipičen primer koinduktivnega tipa je komunikacijski tok podatkov:

• bodisi je tok podatkov prazen (komunikacije je konec)

• bodisi je na voljo sporočilo x in preostanek toka

Primere take komunikacije najdemo povsod, kjer program komunicira z okoljem ali z drugim programom: odjemalec s strežnikom, dva programa med seboj, program z uporabnikom ipd.

Če preberemo zgornjo definicijo kot induktivni tip, se ne razlikuje od definicije seznamov. To bi pomenilo, da bi moral biti komunikacijski tok vedno končen, kar je nespametna predpostavka. V praksi seveda komunikacija ni dejansko neskončna, a je potencialno neskončna, kar pomeni, da lahko dva procesa komunicirata v nedogled in brez vnaprej postavljene omejitve.

Koinduktivni tipi so rekurzivni tipi, ki dovoljujejo tudi neskončne vrednosti. Vendar pozor, kadar imamo opravka z neskončno velikimi seznami, drevesi itd., moramo paziti, kako z njimi računamo. Izogniti se moramo temu, da bi neskončno veliko drevo ali komunikacijski tok poskušali izračunati v celoti do konca.

Haskell ima koinduktivne podatkovne tipe.

7.6.1Tokovi¶

Poglejmo različico tokov, ki so vedno neskončni, ker pri njih koinduktivna narava pride še bolj do izraza. Tok je:

• sestavljen iz sporočila in preostanka toka

Če to definicijo preberemo induktivno, dobimo prazen tip, saj ne moremo začeti. Res, če zapišemo v OCaml

type 'a stream = Cons of 'a * 'a stream

dobimo podatkovni tip, ki nima nobene končne vrednosti. Vrednost bi bila nujno neskončna, na primer:

• Cons (1, Cons (2, Cons (3, Cons (4, …))))

• Cons (1, Cons (1, Cons (1, Cons (1, …))))

OCaml sicer dopušča nekatere take vrednosti z definicijo let rec:

# let rec s = Cons (1, Cons (2, s)) ;;
val s : int stream = Cons (1, Cons (2, <cycle>))

A te vrednosti le pokvarijo induktivno naravo tipov, hkrati pa ne dovoljujejo poljubnih neskončnih vrednosti. Če bi imele v praksi uporabno vrednost, bi jih morda tolerirali, ker pa jih redkokdaj uporabimo, smo lahko nekoliko razočarani nad odločitvijo snovalcev OCamla, da jih dovolijo.

7.6.2Tokovi v Haskellu¶

Ista definicija v Haskellu deluje, ker ima Haskell koinduktivne tipe.

V Haskellu podatkovne tipe pišemo nekoliko drugače:

• imena tipov se piše z velikimi začetnicami: Bool, Integer, ...

• produkt tipov a in b zapišemo (a,b), se pravi tako kot urejene pare. Na primer, elementi tipa (Bool, Int) so (False, 0), (False, 42), (True, 23) itd.

• enotski tip pišemo (), torej tako kot njegovo edino vrednost.

• zapis e :: t pomeni »e ima tip t«, zapis e : t pa seznam z glavo e in repom t (ravno obratno, kot v OCamlu)

• podatkovni tip uvedemo z določilom data in parameter pišemo za ime tipa z malimi črkami. Torej namesto 'a stream zapišemo Stream a.

A to so le podrobnosti konkretne sintakse.

Poglejmo definicijo tokov in njihovo uporavo na preprostih primerih:

-- neskončen podatkovni tok elementov tipa a
data Stream a = Cons a (Stream a)

-- Prvih n elementov toka pretvori v seznam
to_list :: Integer -> Stream a -> [a]
to_list 0 _ = []
to_list n (Cons x s) = x : (to_list (n-1) s)

-- rep podatkovnega toka
rest :: Stream a -> Stream a
rest (Cons _ s) = s

-- konstantni podatkovni tok, ki vedno vrača x
constant :: a -> Stream a
constant x = Cons x (constant x)

-- uporabi funkcijo na vseh elementih toka
streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f (Cons x s) = Cons (f x) (streamMap f s)

-- spni dva tokova z dano funkcijo
streamZip :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
streamZip f (Cons x s) (Cons y t) = Cons (f x y) (streamZip f s t)

-- filtriraj tok z dano Boolovo funkcijo
streamFilter :: (a -> Bool) -> Stream a -> Stream a
streamFilter p (Cons x s) | p x       = Cons x $ streamFilter p s
                          | otherwise = streamFilter p s

-- Tok naravnih števil
natural = Cons 0 $ streamMap (+ 1) natural

-- Tok števil od n naprej
naturalFrom :: Integer -> Stream Integer
naturalFrom n = Cons n $ naturalFrom (n + 1)

-- Kvadrati naravnih števil
squares = streamMap (\ n -> n * n) natural

-- Fibonaccijeva števila
fibonacci = Cons 0 $ Cons 1 $ streamZip (+) fibonacci (rest fibonacci)

-- Eratostenovo sito in praštevila
erastoten :: Stream Integer -> Stream Integer
erastoten (Cons k s) =
    Cons k $ erastoten (streamFilter (\ n -> n `mod` k /= 0) s)

primes :: Stream Integer
primes = erastoten $ naturalFrom 2

7.6.3Tokovi v OCamlu¶

V OCaml lahko simuliramo tokove z uporabo tehnike zavlačevanja (angl. »thunk«).

Denimo da imamo izraz e tipa t, ki ga zaenkrat še ne želimo izračunati. Tedaj ga lahko predelamo v funkcijo fun () -> e (po angleško se imenuje taka funkcija thunk), ki je tipa unit -> t. Ker je e znotraj telesa funkcije, se bo izračunal šele, ko funkcijo uporabimo na (). Od tod dobimo idejo, kako bi predstavili t.i. lene vrednosti v OCaml:

type 'a stream = Cons of 'a * (unit -> 'a stream)

Primeri uporabe:

type 'a stream = Cons of 'a * (unit -> 'a stream)

(* Neskončni tok enic *)
let enice =
  let rec e () = Cons (1, e) in
  e ()

(* Neskončni tok k, k+1, k+2, ... *)
let rec count k = Cons (k, (fun () -> count (k+1)))

(* Neskončni tok enic *)
let rec enice =
  let rec generate () = Cons (1, generate) in
  generate ()

(* Prvih n elementov toka pretvori v seznam *)
let rec to_list k s =
  match (k, s) with
  | (0, _) -> []
  | (n, Cons (x, s)) -> x :: to_list (n-1) (s ())

(* n-ti element toka *)
let rec elementAt k s =
  match (k, s) with
  | (0, Cons (x, _)) -> x
  | (n, Cons (_, s)) -> elementAt (n-1) (s ())

(* Potenčne vrste. Tok a₀, a₁, a₂, ... predstavlja potenčno vrsto

      a₀ + a₁ x + a₂ x² + a₃ x³ + ...
 *)

(* Izračunaj vrednost potenčne vrste s v točki x, uporabi prvih n členov *)
let rec eval n x s =
  let rec loop k xpow v (Cons (a, t)) =
    match k with
    | 0 -> v
    | k ->  loop (k-1) (xpow *. x) (v +. a *. xpow) (t ())
  in
  loop n 1.0 0.0 s

(* V pythonu:

   def eval (n, x, s):
     k = n
     xpow = 1.0
     v = 0
     while k > 0:
       a = s.getNext()
       v = v + a * xpow
       xpow = xpow * x
       k = k - 1
     return v
 *)

(* Potenčna vrsta za eksponentno funkcijo exp(x). Koeficienti so:

   1/0!, 1/1!, 1/2!, 1/3!, 1/4!, …
 *)
let exp =
  let rec exp k a = Cons (a, fun () -> exp (k+1) (a /. float k)) in
  exp 1 1.0

(* Potenčna vrsta za sinus *)
let sin =
  let rec sin k a = Cons (0.0, fun () -> Cons (a, fun () -> sin (k+2) (-. a /. float (k * (k+1)))))
  in sin 2 1.0

(* Odvod vrste

      a₀ + a₁ x + a₂ x² + a₃ x³ + a₄ x⁴ + ...

   je

      a₁ + 2 a₂ x¹ + 3 a₃ x² + 4 a₄ x³ + ...

 *)
let diff (Cons (_, s)) =
      let rec diff' k (Cons (a, s)) = Cons (float k *. a, fun () -> diff' (k+1) (s ()))
      in diff' 1 (s ())

let cos = diff sin

7.6.4Vhod/izhod kot koinduktivni tip¶

Še en primer koinduktivnega tipa je vhod/izhod (input/output). Tokrat s koinduktivnim tipom izrazimo strukturo programa, ki izvaja operaciji Read in Write:

-- Program, ki simulira operaciji Read in Write s podatkovnim tipom

data InputOutput a =
    Read (String -> InputOutput a) -- program prebere niz in nadaljuje delo
  | Write (String, InputOutput a)  -- program izpiše niz in nadaljuje delo
  | Return a                       -- program konča z danim rezultatom

-- Primer: program, ki izpiše "Hello, world!" in konča z rezultatom ()
hello_world :: InputOutput ()
hello_world = Write ("Hello, world!", Return ())

-- Primer: greeter n uporabnika n-krat vpraša po imenu in ga pozdravi, nato
--         vrne 42
greeter :: Integer -> InputOutput Integer
greeter 0 = Return 42
greeter n = Write ("Your name?", Read (\ str -> Write ("Hello, " ++ str, greeter (n-1))))

-- Lahko bi naredili tudi potencialno neskončni program?
annoyance :: InputOutput ()
annoyance = Write ("Should I stop? (Y/N)",
                    Read (\answer -> case answer of { "Y" -> Write ("Bye", Return ()) ; _   -> annoyance }))

-- Ker simuliramo I/O, moramo simulirati tudi operacijski sistem.
-- To naredimo s funkcijo, ki sprejme seznam vhodnih nizov,
-- niz, v katerem hranimo do sedaj izpisane podatke, in program.
-- Funkcija vrne rezultat programa in skupni niz, ki ga je program izpisal.
os :: [String] -> String -> InputOutput a -> (a, String)
os  _            output (Return v)       = (v, output)
os (str : input) output (Read p)         = os input output (p str)
os []            output (Read _)         = error "kernel panic: input not available"
os input         output (Write (str, p)) = os input (output ++ str) p

primer1 = os [] "" hello_world
-- Dobimo: ((),"Hello, world!")

primer2 = os ["Janezek", "Micka", "Mojca", "Darko"] "" (greeter 3)
-- Dobimo: (42,"Your name?Hello, JanezekYour name?Hello, MickaYour name?Hello, Mojca")

primer3 = os ["Janezek", "Micka", "Mojca", "Darko"] "" (greeter 5)
-- Dobimo izjemo: *** Exception: kernel panic: input not available

-- Neskončen seznam "N"
no = "N" : no
primer4 = os no "" annoyance
-- Dobimo: se zacikla