Uvod v funkcijsko programiranje

Uvod v funkcijsko programiranje#

Prednosti funkcijskega programiranja ne bomo posebej naštevali, a v obzir moramo vzeti tudi dve njegovi slabosti. Prva je ta, da so funkcijski jeziki namenjeni izražanju idej in so zato precej oddaljeni od dejanskih strojnih ukazov, ki smo jih spoznali v prejšnjem poglavju. Zaradi tega je potrebnega kar nekaj truda za njihovo učinkovito izvajanje. Druga pa je višji nivo abstrakcije, ki seveda vodi do bolj jedrnatih programov, a hkrati tudi ni pisan na kožo vsakemu programerju.

Glede prve slabosti vam ni treba skrbeti, saj so večino truda opravile že generacije raziskovalcev in inženirjev pred vami. Po izbiri študija sodeč pa vam tudi druga ne bi smela predstavljati večjih ovir. Se bosta pa obe vseeno poznali, saj se zaradi njuju funkcijske ideje niso tako hitro prijele, funkcijski jeziki pa so v praksi ostali nedodelani in malo ezoterični. Ideje, ki so jih prevzeli uveljavljeni jeziki, pa je treba seveda združiti z vsemi obstoječimi, kar zopet vodi v svoje težave. V zadnjih letih se situacija spreminja na bolje, vendar še vedno nismo na točki, ko bi imeli dobro podprt jezik z jasno izraženimi funkcijskimi ideji.

Ker so ideje seveda pomembnejše, si bomo ogledali programski jezik OCaml, ki je bil eden prvih in je še danes eden najbolj popularnih funkcijskih jezikov. OCaml morda ni najbolj razširjen funkcijski jezik, so pa v njem ideje izražene najbolj neposredno.

Osnove OCamla#

Aritmetični izrazi#

(Imperativna) navada zapoveduje, da mora prvi program na zaslon izpisati “Hello, world!”. Mi bomo začeli drugače, bolj matematično, in raje začeli z enostavnim izračunom:

7 * 6

- : int = 42

Opazimo lahko, da je OCaml je poleg končne vrednosti izpisal tudi njen tip int. Tipom se bomo še posvetili, mi pa izračun naredimo še malo bolj zapleten z uporabo funkcije succ, ki izračuna naslednika:

succ 6 * 6

- : int = 42

V funkcijskih jezikih je uporaba funkcij tako pogosta, da jo želimo napisati na čim krajši način. Zato argumentov ni treba pisati v oklepajih. Tako kot ima množenje prednost pred seštevanjem, ima uporaba funkcije (oz. aplikacija) višjo prioriteto kot računske operacije, zato se je izračun izvedel kot (succ 6) * 6 = 7 * 6 = 42 in ne kot succ (6 * 6) = succ 36 = 37.

Uporabimo lahko tudi funkcijo več argumentov, v kateri argumente zopet ločimo kar s presledkom:

min 8 7 * 6

- : int = 42

Definicije#

Z ukazom let ime = ... lahko vrednost izračuna poimenujemo za kasnejšo uporabo:

let odgovor = min 8 7 * 6

val odgovor : int = 42

let malo_slabsi_odgovor = odgovor - 1

val malo_slabsi_odgovor : int = 41

Vrednosti lahko definiramo tudi lokalno z izrazom let ime = ... in .... V tem primeru bodo definicije na voljo v delu in ..., izven pa ne.

let odgovor =
  let prvi_delni_izracun = min 8 7 in
  let drugi_delni_izracun = max 6 5 in
  prvi_delni_izracun * drugi_delni_izracun

val odgovor : int = 42

prvi_delni_izracun

File "[7]", line 1, characters 0-18:
1 | prvi_delni_izracun
    ^^^^^^^^^^^^^^^^^^
Error: Unbound value prvi_delni_izracun

Če želimo, lahko več lokalnih definicij hkrati podamo tako, da jih ločimo z and.

let odgovor =
  let prvi_delni_izracun = min 8 7
  and drugi_delni_izracun = max 6 5 in
  prvi_delni_izracun * drugi_delni_izracun

val odgovor : int = 42

Razlika med tem in gnezdenimi lokalnimi definicijami je v tem, da so vrednosti definirane hkrati, zato se ne morejo nanašati ena na drugo:

let odgovor =
  let prvi_delni_izracun = min 8 7 in
  let drugi_delni_izracun = prvi_delni_izracun - 1 in
  prvi_delni_izracun * drugi_delni_izracun

val odgovor : int = 42

let odgovor =
  let prvi_delni_izracun = min 8 7
  and drugi_delni_izracun = prvi_delni_izracun - 1 in
  prvi_delni_izracun * drugi_delni_izracun

File "[10]", line 3, characters 28-46:
3 |   and drugi_delni_izracun = prvi_delni_izracun - 1 in
                                ^^^^^^^^^^^^^^^^^^
Error: Unbound value prvi_delni_izracun

Definicije funkcij#

Funkcije v OCamlu definiramo podobno kot vrednosti, le da za njihovim imenom naštejemo še imena argumentov:

let kvadriraj x = x * x

val kvadriraj : int -> int = <fun>

K tipu funkcije se bomo vrnili kasneje. Funkcije potem uporabimo kot običajno:

kvadriraj 4

- : int = 16

kvadriraj (-8)

- : int = 64

Tu smo morali uporabiti oklepaje, saj OCaml ni občutljiv na presledke in bi izraz kvadriraj -4 razumel kot odštevanje kvadriraj - 4.

Na podoben način lahko definiramo funkcije več argumentov:

let obseg_pravokotnika a b =
  2 * (a + b)

val obseg_pravokotnika : int -> int -> int = <fun>

obseg_pravokotnika 6 15

- : int = 42

let povrsina_kvadra a b c =
  2 * (a * b + a * c + b * c)

val povrsina_kvadra : int -> int -> int -> int = <fun>

Ime dvomestne funkcije je lahko sestavljeno tudi iz simbolov. V tem primeru ga pišemo med oklepaje, funkcijo pa uporabljamo v infiksni obliki:

let ( -- ) a b = max a b - min a b

val ( -- ) : int -> int -> int = <fun>

( -- ) 42 24

- : int = 18

42 -- 24

- : int = 18

24 -- 42

- : int = 18

Osnovni tipi#

Ena izmed največjih prednosti OCamla je njegov bogat in dovršen sistem tipov. Vsak pravilen program v OCamlu ima svoj tip, ki ga OCaml samodejno preveri pred vsakim izvajanjem, kar polovi ogromno napak.

Cela števila `int`#

Cela števila pripadajo tipu int, ki smo ga že spoznali. Za razliko od Pythona celoštevilsko delimo z /, ostanek pa izračunamo z mod:

1024 / 100

- : int = 10

1024 mod 100

- : int = 24

Prav tako za razliko od Pythona OCamlov tip int ne podpira poljubno velikih števil, zato lahko pri nekaterih operacijah pride do prekoračitve obsega:

4611686018427387902 + 1

- : int = 4611686018427387903

4611686018427387902 + 2

- : int = -4611686018427387904

Števila s plavajočo vejico `float`#

Tipu float pripadajo števila s plavajočo vejico, ki jih pišemo kot drugod, razlika pa se pojavi pri operacijah, saj OCaml loči med operacijami na celih številih ter operacijami na številih s plavajočo vejico, ki se končajo s piko.

12.0 *. (34.0 +. 67.0) -. 89.0

- : float = 1123.

1024. /. 100.

- : float = 10.24

sqrt 2.

- : float = 1.41421356237309515

Kot smo že omenili, OCaml preverja ustreznost tipov, in tako na primer operacija * sprejme dva argumenta tipa int in int tudi vrne. Če ji damo argumente tipa float, se bo OCaml pritožil, saj med tema dvema tipoma strogo loči:

2 * 3.141592

File "[28]", line 1, characters 4-12:
1 | 2 * 3.141592
        ^^^^^^^^
Error: This expression has type float but an expression was expected of type
         int

Pisati bi morali 2. *. 3.141592 ali pa vrednosti eksplicitno pretvoriti s funkcijo:

float_of_int 10

- : float = 10.

int_of_float 3.141592

- : int = 3

Nizi `string`#

Nizi pripadajo tipu string, pišemo pa jih med dvojne narekovaje. Stikanje nizov je pogosta operacija, ki jo pišemo kot ^:

let fun_prog = "Funkcijsko " ^ "programiranje"

val fun_prog : string = "Funkcijsko programiranje"

Na voljo imamo tudi funkcije za pretvorbo v nize in iz nizov, pri čemer slednje lahko sprožijo napako:

string_of_int 100

- : string = "100"

int_of_string "100"

- : int = 100

int_of_string "sto"

Exception: Failure "int_of_string".
Raised by primitive operation at unknown location
Called from Stdlib__Fun.protect in file "fun.ml", line 33, characters 8-15
Re-raised at Stdlib__Fun.protect in file "fun.ml", line 38, characters 6-52
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 89, characters 4-150

Več funkcij za delo z nizi najdemo v standardni knjižnici, ki je razdeljena na module, na primer:

osnovni modul Stdlib, ki je vedno naložen in ga ni treba posebej navajati,
modul String za delo z nizi,
modul List za delo s seznami ali
modul Random za delo s psevdonaključnimi vrednostmi.

Do funkcij iz danega modula dostopamo prek zapisa ImeModula.ime_funkcije:

String.length fun_prog

- : int = 24

String.cat "Uvod v " (String.lowercase_ascii fun_prog)

- : string = "Uvod v funkcijsko programiranje"

"Uvod v " ^ String.lowercase_ascii fun_prog

- : string = "Uvod v funkcijsko programiranje"

Logične vrednosti `bool`#

Tipu bool pripadajo logične vrednosti, kjer imamo na voljo obe logični konstanti ter običajne logične operacije, pri čemer konjunkcijo in pišemo kot &&, disjunkcijo ali pa kot ||. Na voljo imamo tudi običajne relacije za primerjavo:

3 <= 8

- : bool = true

3 <= 8 && 8 <= 6

- : bool = false

Logične vrednosti lahko uporabljamo v pogojnih izrazih:

let abs x =
  if x < 0 then -x else x

val abs : int -> int = <fun>

Pogojni izrazi so lahko tudi vsebovani v drugih izrazih. Na primer, funkcija v spodnjem izrazu je rezultat pogojnega izraza:

(if 1 = 3 then pred else succ) 5 * 7

- : int = 42

Za primerjavo enakosti uporabljamo operaciji = in <>, ki argumente primerjata glede na vrednosti. Na voljo sta tudi primerjavi == in !=, ki gledata identičnost argumentov in ju uporabljamo le takrat, kadar smo v to popolnoma prepričani, saj nam sicer dajeta nepričakovane odgovore:

"A" == "A"

- : bool = false

Dobili smo false, ker je za vsako stran OCaml naredil svoj niz in ta niza shranil na dve različni mesti v pomnilniku. Če bi naredili en sam niz, bi enakost veljala:

let a = "A"

val a : string = "A"

a == a

- : bool = true

Enotski tip `unit`#

V OCamlu imamo tudi enotski tip unit, ki vsebuje samo eno vrednost:

()

- : unit = ()

Toda če je () edina vrednost svojega tipa, kakšen je njen namen, saj ne nosi nobene informacije?

Poglejmo si najprej funkcijo Random.int, ki za argument sprejme celo število n in vrne naključno število med 0 in n - 1:

Random.int 6

- : int = 0

Podobno kot si lahko izberemo naključno število, lahko izberemo tudi naključno logično vrednost s pomočjo funkcije Random.bool. Toda Random.bool ne potrebuje nobenega argumenta, ki bi določal množico vrednosti, med katerimi izbiramo. Toda funkcijo moramo vseeno poklicati na nekem argumentu, zato v tem primeru uporabimo ():

Random.bool ()

- : bool = false

Podobno lahko s funkcijo print_endline na zaslon izpišemo podani niz. Toda izpisani niz ni rezultat, ki bi ga vrnila funkcija, temveč njen stranski učinek. A vsaka funkcija mora imeti rezultat, zato v tem primeru zopet vrnemo ():

print_endline "Hello, world!"

Hello, world!

- : unit = ()

Vidimo, da OCaml najprej izpiše niz, nato pa vrne ().

Znaki `char`#

Tipu char pripadajo posamezni znaki, ki jih pišemo med enojne narekovaje.

'a'

- : char = 'a'

Funkcije za delo z znaki so na voljo v modulu Char. Dva primera sta funkciji code, ki znak pretvori v njegovo ASCII kodo, ter chr, ki naredi ravno obratno.

Char.code 'x'

- : int = 120

Char.code 'y'

- : int = 121

Char.chr 122

- : char = 'z'

Primer: Cezarjeva šifra#

Za malo večji primer si oglejmo Cezarjevo šifro, ki je ena najstarejših šifrirnih tehnik. Pri Cezarjevi šifri vsak znak zamenjamo z ustrezno zamaknjenim znakom v abecedi. Na primer, pri zamiku 10 bi A zamenjali s K, B z L in tako naprej. Cezarjev znameniti citat “Veni, vidi, vici” bi tako postal “Foxs, fsns, fsms”.

ABCDEFGHIJKLMNOPQRSTUVWXYZ    VENI, VIDI, VICI
KLMNOPQRSTUVWXYZABCDEFGHIJ    FOXS, FSNS, FSMS

Najprej napišimo funkcijo, ki zamakne en sam znak. Pri tem menjamo samo velike tiskane črke, ostale znake (npr. ločila in presledke) pa pustimo nespremenjene.

let cezarjeva_sifra zamik znak =
  if 'A' <= znak && znak <= 'Z' then
    let mesto_znaka = Char.code znak - Char.code 'A' in
    let novo_mesto = (mesto_znaka + zamik) mod 26 in
    Char.chr (Char.code 'A' + novo_mesto)
  else
    znak

val cezarjeva_sifra : int -> char -> char = <fun>

cezarjeva_sifra 10 'R'

- : char = 'B'

Šifriranje celotnega niza enostavno naredimo tako, da s pomočjo funkcije String.map funkcijo za šifriranje znaka uporabimo na vsakem znaku posebej.

let zasifriraj zamik niz =
    let zasifriraj_znak znak = cezarjeva_sifra zamik znak in
    String.map zasifriraj_znak niz

val zasifriraj : int -> string -> string = <fun>

zasifriraj 10 "VENI, VIDI, VICI"

- : string = "FOXS, FSNS, FSMS"

Sporočilo lahko odšifriramo tako, da uporabimo ravno obratni zamik.

zasifriraj (26 - 10) "FOXS, FSNS, FSMS"

- : string = "VENI, VIDI, VICI"

Funkcije#

Funkcijski tipi#

Vsaka vrednost v OCamlu ima svoj tip, tudi funkcije. Tip funkcije je oblike tip_arg -> tip_rez, kjer je tip_arg tip argumenta funkcije, tip_rez pa tip njenega rezultata. Na primer float_of_int vzame int in vrne float:

float_of_int

- : int -> float = <fun>

Podobno je z ostalimi funkcijami, ki smo jih spoznali:

int_of_float

- : float -> int = <fun>

String.length

- : string -> int = <fun>

print_endline

- : string -> unit = <fun>

Prisotnost tipa unit v argumentih ali rezultatih funkcije nakazuje, da se bodo najverjetneje zgodili učinki, saj ni razloga, da bi funkcija izračunala samo trivialni rezultat (). Podobno funkcija iz prazne vrednosti () težko izračuna kaj zanimivega.

Funkcije več argumentov#

Podoben tip imajo tudi funkcije več argumentov:

let zmnozi x y = x * y

val zmnozi : int -> int -> int = <fun>

Funkcija zmnozi sprejme dve celi števili tipa int in vrne njun produkt, ki je ravno tako tipa int. Podobno funkcija String.cat sprejme dva niza vrne njun stik.

String.cat

- : string -> string -> string = <fun>

Seveda ni treba, da so vsi tipi enaki. Funkcija cezarjeva_sifra, ki smo jo spoznali malo prej, vzame zamik tipa int in znak tipa char ter vrne zašifrirani znak, ki je ravno tako tipa char.

let cezarjeva_sifra zamik znak =
  if 'A' <= znak && znak <= 'Z' then
    let mesto_znaka = Char.code znak - Char.code 'A' in
    let novo_mesto = (mesto_znaka + zamik) mod 26 in
    Char.chr (Char.code 'A' + novo_mesto)
  else
    znak

val cezarjeva_sifra : int -> char -> char = <fun>

Delna uporaba#

Najpomembnejša lastnost funkcij, ki sprejmejo več argumentov, je ta, da jih lahko tudi delno uporabimo tako, da jim podamo samo nekaj argumentov. Za primer vzemimo funkcijo zasifriraj, ki sprejme zamik in niz ter vrne zasifriran niz:

let zasifriraj zamik niz =
  let zasifriraj_znak znak = cezarjeva_sifra zamik znak in
  String.map zasifriraj_znak niz

val zasifriraj : int -> string -> string = <fun>

Če funkciji podamo samo zamik, ne dobimo napake, kot bi jo v večini programskih jezikov, temveč funkcijo, ki čaka še na drugi argument:

let rot13 = zasifriraj 13

val rot13 : string -> string = <fun>

V tem primeru uporabimo zamik 13 in dobimo funkcijo, ki vsak niz zašifrira z zamikom 13. Ta zamik je poseben, saj je sam svoj obrat, zato lahko isto funkcijo uporabimo za šifriranje in odšifriranje.

rot13 "VENI, VIDI, VICI"

- : string = "IRAV, IVQV, IVPV"

rot13 "IRAV, IVQV, IVPV"

- : string = "VENI, VIDI, VICI"

Z delno uporabo lahko programe precej skrajšamo. Za primer si spet oglejmo funkcijo zasifriraj.

let zasifriraj zamik niz =
  let zasifriraj_znak znak = cezarjeva_sifra zamik znak in
  String.map zasifriraj_znak niz

val zasifriraj : int -> string -> string = <fun>

V njej smo uporabili pomožno funkcijo zasifriraj_znak : char -> char, ki znak zašifrira z poprej podanim zamikom. Ta funkcija se obnaša tako, kot da funkciji cezarjeva_sifra podali samo zamik. Zato lahko zgornjo vrstico na krajše napišemo kot:

let zasifriraj zamik niz =
  let zasifriraj_znak = cezarjeva_sifra zamik in
  String.map zasifriraj_znak niz

val zasifriraj : int -> string -> string = <fun>

Ker je definicija zasifriraj_znak precej preprosta, jo lahko vstavimo kar neposredno:

let zasifriraj zamik niz =
  String.map (cezarjeva_sifra zamik) niz

val zasifriraj : int -> string -> string = <fun>

Tudi String.map lahko delno uporabimo tako, da ji podamo samo funkcijo, ki jo želimo uporabiti na vsakem znaku, in nazaj dobimo funkcijo iz nizov v nize:

let zasifriraj zamik =
  String.map (cezarjeva_sifra zamik)

val zasifriraj : int -> string -> string = <fun>

Končna definicija je precej bolj jedrnata: na vsakem znaku uporabi cezarjevo šifro z danim zamikom. Ko se bomo navadili na osnovne tehnike funkcijskega programiranja, bo taka definicija tudi bolj pregledna.

Funkcije višjega reda#

Funkcije so lahko tudi argumenti drugih funkcij. Na primer funkcija String.exists sprejme funkcijo tipa char -> bool in niz ter vrne true, če funkcija najde znak, za katerega je funkcija resnična. Na primer, če gledamo, ali niz vsebuje samoglasnik, lahko definiramo:

let je_samoglasnik znak =
  String.contains "aeiou" (Char.lowercase_ascii znak)

val je_samoglasnik : char -> bool = <fun>

je_samoglasnik 'A'

- : bool = true

Če bi radi vedeli, ali niz vsebuje samoglasnik, bi lahko napisali String.exists je_samoglasnik niz. Z delno uporabo pa lahko napišemo kar:

let vsebuje_samoglasnik =
  String.exists je_samoglasnik

val vsebuje_samoglasnik : string -> bool = <fun>

vsebuje_samoglasnik "čmrlj"

- : bool = false

Tudi tip funkcije String.exists kaže, da sprejme dva argumenta: funkcijo tipa char -> bool in niz string.

String.exists

- : (char -> bool) -> string -> bool = <fun>

Pri tem je treba biti pozoren na postavitev oklepajev. Če bi jih izpustili, bi dobili tip char -> bool -> string -> bool, kar pa je funkcija, ki sprejme tri argumente, znak char, logično vrednost bool in niz string.

Kadar funkcija za argument sprejme drugo funkcijo, govorimo o funkcijah višjega reda. Običajne funkcije med števili, nizi, seznami in podobnimi vrednostmi so funkcije prvega reda. Funkcija \(n\)-tega reda pa je taka, ki za argument sprejme funkcijo \(n - 1\)-tega reda. Pri tem predmetu bomo spoznali tudi funkcije tretjega reda, velika večina funkcij, s katerimi se bomo ukvarjali, pa bodo funkcije prvega ali drugega reda.

Anonimne funkcije#

Napišimo funkcijo, ki vrne prezrcaljen niz:

let zrcali niz =
  let n = String.length niz in
  let znak_na_zrcalnem_mestu i = String.get niz (n - i - 1) in
  String.init n znak_na_zrcalnem_mestu

val zrcali : string -> string = <fun>

zrcali "perica reze raci rep"

- : string = "per icar ezer acirep"

Včasih majhnih funkcij kot je zgornja ni smiselno poimenovati. Precejšen del pisanja si prihranimo z uporabo anonimnih, torej nepoimenovanih funkcij, ki so oblike fun arg -> .... Na primer, zgornjo funkcijo bi lahko napisali preprosto kot:

let zrcali niz =
  let n = String.length niz in
  String.init n (fun i -> String.get niz (n - i - 1))

val zrcali : string -> string = <fun>

ki deluje enako kot zgornja definicija, le da nam pomožne funkcije ni bilo treba poimenovati. Še en primer je funkcija, ki preveri, ali so vsi znaki v nizu števke:

let je_stevilo niz =
  String.for_all (fun znak -> '0' <= znak && znak <= '9') niz

val je_stevilo : string -> bool = <fun>

Anonimne funkcije lahko sprejmejo tudi več argumentov. Za primer si najprej oglejmo funkcijo String.mapi, ki deluje podobno kot String.map, le da poleg znaka sprejme še njegov indeks:

let posmehljivo niz =
  let soda_malo_liha_veliko i c =
    if i mod 2 = 0 then Char.lowercase_ascii c else Char.uppercase_ascii c
  in
  String.mapi soda_malo_liha_veliko niz

val posmehljivo : string -> string = <fun>

posmehljivo "Ja, funkcijsko programiranje je res najboljše!"

- : string = "jA, fUnKcIjSkO PrOgRaMiRaNjE Je rEs nAjBoLjšE!"

S pomočjo anonimnih funkcij bi to na krajše napisali kot:

let posmehljivo niz =
  String.mapi
    (fun i c -> if i mod 2 = 0 then Char.lowercase_ascii c else Char.uppercase_ascii c)
    niz

val posmehljivo : string -> string = <fun>

posmehljivo "Anonimne funkcije mi prihranijo toliko truda pri poimenovanju."

- : string = "aNoNiMnE FuNkCiJe mI PrIhRaNiJo tOlIkO TrUdA PrI PoImEnOvAnJu."

Z delno uporabo pa vse skupaj napišemo še na krajše:

let posmehljivo =
  String.mapi (fun i -> if i mod 2 = 0 then Char.lowercase_ascii else Char.uppercase_ascii)

val posmehljivo : string -> string = <fun>

posmehljivo "Delna uporaba definicije naredi sploh zelo pregledne."

- : string = "dElNa uPoRaBa dEfInIcIjE NaReDi sPlOh zElO PrEgLeDnE."

Sestavljeni tipi#

Poleg preprostih vrednosti poznamo tudi sestavljene.

Seznami#

Sezname v OCamlu pišemo med oglate oklepaje, vrednosti pa ločimo s podpičji. Vse vrednosti v seznamih morajo biti enakega tipa, seznam pa ima potem tip oblike tip_el list, kjer je tip_el tip komponent.

[1; 2; 3; 4]

- : int list = [1; 2; 3; 4]

['a'; 'b'; 'c'; 'd']

- : char list = ['a'; 'b'; 'c'; 'd']

Sezname pa seveda lahko dobimo kot rezultate drugih funkcij (zaenkrat samo tistih, ki so jih napisali drugi):

String.split_on_char ' ' "Uvod v funkcijsko programiranje"

- : string list = ["Uvod"; "v"; "funkcijsko"; "programiranje"]

Najkoristnejše funkcije za delo s seznami so v modulu List:

List.map String.length ["Uvod"; "v"; "funkcijsko"; "programiranje"]

- : int list = [4; 1; 10; 13]

List.filter (fun x -> x < 5) [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 9]

- : int list = [3; 1; 4; 1; 2; 3]

List.flatten [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]]

- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

Nabori#

Poleg seznamov, ki vsebujejo poljubno število vrednosti istega tipa, pozna OCaml tudi nabore, ki vsebujejo fiksno število vrednosti različnih tipov. Nabore pišemo med navadne oklepaje, komponente pa ločimo z vejico.

(25, "junij", 1991)

- : int * string * int = (25, "junij", 1991)

(4220, "Škofja Loka")

- : int * string = (4220, "Škofja Loka")

Kot vidimo, imajo nabori tip označen s kartezičnim produktom τ₁ * τ₂ * … * τ_n, kjer so τ_i tipi posameznih komponent. Naborov velikosti ena ni, ker niso potrebni, nabor velikosti 0 pa je natanko en in smo ga že spoznali. To je (). Ker kartezičnega produkta nič tipov ne moremo zapisati, tip praznega nabora označujemo z unit.

Poglavitni namen naborov je pisanje funkcij, ki vrnejo več rezultatov:

List.partition (fun x -> x < 5) [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 9]

- : int list * int list = ([3; 1; 4; 1; 2; 3], [5; 9; 6; 5; 5; 9])

Pri zapisu naborov lahko oklepaje tudi izpustimo, vendar tega raje ne počnimo.

1, 2 < 3, "abc"

- : int * bool * string = (1, true, "abc")

To možnost omenjamo samo zato, da boste lahko razumeli pogosto napako: če se pri pisanju seznamov zmotimo in namesto podpičij pišemo vejice, dobimo seznam z enim elementom, ki je nabor:

[1, 2, 3, 4]

- : (int * int * int * int) list = [(1, 2, 3, 4)]

[1; 2; 3; 4]

- : int list = [1; 2; 3; 4]

Razstavljanje z vzorci#

Na parih (torej naborih velikosti 2) imamo na voljo funkciji fst in snd, ki projecirata na prvo in drugo komponento.

fst (5, true)

- : int = 5

V lokalnih definicijah in argumentih funkcij lahko nabore razstavimo s pomočjo vzorcev. Na primer, namesto:

let raztegni faktor koord =
  (faktor *. fst koord, faktor *. snd koord)

val raztegni : float -> float * float -> float * float = <fun>

lahko pišemo:

let raztegni faktor koord =
  let (x, y) = koord in
  (faktor *. x, faktor *. y)

val raztegni : float -> float * float -> float * float = <fun>

ali še bolje kot:

let raztegni faktor (x, y) =
  (faktor *. x, faktor *. y)

val raztegni : float -> float * float -> float * float = <fun>

Vrednosti lahko ignoriramo z vzorcem _

let poste = [(1000, "Ljubljana"); (2000, "Maribor"); (3000, "Celje")]

val poste : (int * string) list =
  [(1000, "Ljubljana"); (2000, "Maribor"); (3000, "Celje")]

List.split poste

- : int list * string list =
([1000; 2000; 3000], ["Ljubljana"; "Maribor"; "Celje"])

let (_, imena_krajev) = List.split poste

val imena_krajev : string list = ["Ljubljana"; "Maribor"; "Celje"]

Vzorce lahko uporabljamo tudi v definicijah funkcij in anonimnih funkcijah:

let stara_posta (postna, ime) = (60000 + postna, ime) in
List.map stara_posta poste

- : (int * string) list =
[(61000, "Ljubljana"); (62000, "Maribor"); (63000, "Celje")]

List.map (fun (postna, ime) -> (60000 + postna, ime)) poste

- : (int * string) list =
[(61000, "Ljubljana"); (62000, "Maribor"); (63000, "Celje")]

Morebitne vrednosti `τ option`#

Včasih imamo opravka s funkcijami, ki jih ne moremo povsod dobro definirati. Na primer, vsak niz ne predstavlja števila. Če funkcijo int_of_string uporabimo na takem nizu, bomo dobili napako ob izvajanju.

int_of_string "100"

- : int = 100

int_of_string "sto"

Exception: Failure "int_of_string".
Raised by primitive operation at unknown location
Called from Stdlib__Fun.protect in file "fun.ml", line 33, characters 8-15
Re-raised at Stdlib__Fun.protect in file "fun.ml", line 38, characters 6-52
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 89, characters 4-150

Varnejši način je, da uporabimo tip 'a option, ki predstavlja morebitno vrednost tipa 'a:

int_of_string_opt "100"

- : int option = Some 100

int_of_string_opt

- : string -> int option = <fun>

List.filter_map int_of_string_opt ["100"; "sto"; "123"; "tisoč"]

- : int list = [100; 123]

Polimorfizem#

Vsaka vrednost v OCamlu ima natančno določen tip. Kakšen pa je tip funkcije List.rev, saj lahko z njo obračamo tako sezname logičnih vrednosti, sezname števil, sezname seznamov števil, …

List.rev [false; true]

- : bool list = [true; false]

List.rev [1; 2; 3; 4]

- : int list = [4; 3; 2; 1]

Je List.rev torej tipa bool list -> bool list ali int list -> int list ali int list list -> int list list? V resnici je lahko tipa α list -> α list za poljuben tip α. To v OCamlu označimo kot 'a list -> 'a list. In res:

List.rev

- : 'a list -> 'a list = <fun>

Parametrično polimorfne vrednosti#

Vrednostim, ki imajo v tipih spremenljivke, pravimo parametrično polimorfne. Polimorfne zaradi tega, ker lahko delujejo pri več tipih, parametrično pa zato, ker pri vseh tipih delujejo na enak način.

List.flatten

- : 'a list list -> 'a list = <fun>

List.filter

- : ('a -> bool) -> 'a list -> 'a list = <fun>

Tudi nekatere vrednosti so parametrično polimorfne:

[]

- : 'a list = []

Poznamo tudi tako imenovani ad hoc polimorfizem, kjer pri nekaterih tipih funkcije delujejo na en način, pri nekaterih na drugačen, pri tretjih pa sploh ne. Primer takega polimorfizma je na primer + v Pythonu: števila sešteva, sezname in nize stika, na funkcijah pa ne deluje. OCaml ad hoc polimorfizma nima, ker povzroča težave pri določanju tipov.

Polimorfni tipi z več parametri#

V parametrično polimorfnih funkcijah lahko nastopa več parametrov. Na primer, projekcija na prvo komponento vzame par iz kartezičnega produkta poljubnih dveh tipov in slika v drugega:

snd

- : 'a * 'b -> 'b = <fun>

List.map

- : ('a -> 'b) -> 'a list -> 'b list = <fun>

List.filter_map

- : ('a -> 'b option) -> 'a list -> 'b list = <fun>

List.combine

- : 'a list -> 'b list -> ('a * 'b) list = <fun>

Primer: veriženje#

Funkcije verižimo z operacijo |>

let ( |> ) x f = f x

val ( |> ) : 'a -> ('a -> 'b) -> 'b = <fun>

String.length (String.trim "   beseda   ")

- : int = 6

"   beseda   " |> String.trim |> String.length

- : int = 6

"100,sto,123,tisoč"
|> String.split_on_char ','
|> List.filter_map int_of_string_opt

- : int list = [100; 123]

Recimo, da bi radi izločili vsa števila v posameznih vrsticah besedila.

1000,Ljubljana        [[1000];
sto,100          ~>    [100];
1,a,2,b,3              [1; 2; 3]]

let stevila_v_vrstici vrstica =
  vrstica |> String.split_on_char ',' |> List.filter_map int_of_string_opt

val stevila_v_vrstici : string -> int list = <fun>

let stevila_v_besedilu besedilo =
  besedilo |> String.split_on_char '\n' |> List.map stevila_v_vrstici

val stevila_v_besedilu : string -> int list list = <fun>

"1000,Ljubljana
sto,100
1,a,2,b,3
" |> stevila_v_besedilu

- : int list list = [[1000]; [100]; [1; 2; 3]; []]

Curryrane funkcije#

Funkcijam več argumentov, kot jih poznamo v OCamlu, pravimo curryrane. Imenujejo se po logiku (Haskellu Brooksu Curryju, 1900–1982), ki je bil eden prvih raziskovalcev idej, na katerih temeljijo funkcijski jeziki. Na curryrane funkcije dveh argumentov lahko gledamo kot na funkcije enega argumenta (prvega), ki vrnejo funkcijo enega argumenta (drugega). Ko ta funkcija dobi še drugi argument, ima na voljo vse, kar potrebuje, in lahko izračuna končno vrednost.

Tako je definicija funkcija več argumentov fun x y -> ... v resnici samo okrajšava za gnezdeni funkciji enega argumenta fun x -> fun y -> .... Prav tako je f arg1 arg2 samo okrajšava za (f arg1) arg2, saj f uporabimo na prvem argumentu arg1 in dobimo funkcijo f arg1, ki jo uporabimo še na drugem argumentu arg2. Pravimo, da je aplikacija levo asociativna.

Če bi želeli, bi se lahko odločili, da bi bila aplikacija desno asociativna, torej da bi a b c pomenilo a (b c), kar bi bilo koristno za veriženje funkcij, saj bi namesto f (g x) lahko pisali kar f g x. Vendar je takih primerov veliko manj kot klicev funkcij več argumentov, zato je leva asociativnost boljša izbira. Veriženje pa lahko tako ali tako pišemo kot x |> g |> f ali f @@ g @@ x.

Funkcijski tip A -> B -> C predpisujemo funkcijam, ki sprejemajo dva argumenta: najprej sprejmejo argument tipa A, nato pa vrnejo funkcijo, ki čaka še drugi argument tipa B. Torej je A -> B -> C okrajšava za A -> (B -> C). Podobno je A -> B -> C -> D okrajšava za A -> (B -> (C -> D)). Operacija -> ki iz dveh tipov vrne tip funkcij med njima je torej desno asociativna.

Lahko bi se dogovorili tudi drugače in rekli, da je -> levo asociativna operacija. S tem bi bil tip A -> B -> C okrajšava za tip funkcij drugega reda (A -> B) -> C. Ker je koristnih funkcij višjega reda veliko manj kot funkcij več argumentov, je desna asociativnost boljša izbira.

Namesto curryranih funkcij bi za funkcije več argumentov lahko uporabili tudi običajne funkcije, ki sprejmejo par:

let zmnozi x y = x * y
let zmnozi' (x, y) = x * y

val zmnozi : int -> int -> int = <fun>

val zmnozi' : int * int -> int = <fun>

zmnozi 6 7

- : int = 42

zmnozi' (6, 7)

- : int = 42

V tem primeru jih seveda ne moremo uporabiti samo na enem argumentu:

zmnozi 6

- : int -> int = <fun>

zmnozi' 6

File "[135]", line 1, characters 8-9:
1 | zmnozi' 6
            ^
Error: This expression has type int but an expression was expected of type
         int * int

Prednost Curryranih funkcij je, da jih lahko uporabimo delno, nato pa dobljeno funkcijo preostalih argumentov uporabimo v kakšni funkciji drugega reda:

List.map (zmnozi 6) [1; 2; 3; 4; 5; 6; 7]

- : int list = [6; 12; 18; 24; 30; 36; 42]

Seveda pa sta tipa A * B -> C in A -> B -> C izomorfna, saj vsebujeta vsebinsko enake, le po obliki različne funkcije. Med njima obstaja izomorfizem, tako kot med množicama \(C^{A \times B} \cong (C^B)^A\). Postopku pretvorbe iz običajne funkcije v curryrano pravimo curryranje:

let curry f = fun x y -> f (x, y)

val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

let zmnozi'' = curry zmnozi'

val zmnozi'' : int -> int -> int = <fun>

List.map (zmnozi'' 2) [1; 2; 3; 4; 5; 6; 7]

- : int list = [2; 4; 6; 8; 10; 12; 14]

Kot vsak izomorfizem ima tudi curryranje svoj inverz, ki mu pravimo razcurriranje

let uncurry g = fun (x, y) -> g x y

val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>

(uncurry zmnozi) (6, 7)

- : int = 42

Primerjava s Pythonom#

Kljub temu da Python in OCaml podpirata precej podobnih konceptov (funkcije, pogojne stavke, sezname, nabore, tipe, …), pa imata tudi kar nekaj razlik.

Funkcijsko in imperativno programiranje#

Ena izmed njih je način, na katerega te konstrukte uporabljamo. OCaml je deklarativni jezik, kar pomeni, da programe sestavljamo s pomočjo definicij vrednosti. Natančneje, OCaml je funkcijski jezik, saj pri sestavljanju ključno vlogo igrajo funkcije (poznamo tudi logične deklarativne jezike, kot na primer Prolog, kjer vrednosti opisujemo s pogoji, ki računalnik vodijo do končne rešitve). Na primer, \(10!\) v OCamlu najenostavneje izračunamo tako, da napišemo njeno matematično definicijo:

let rec fakulteta n =
  if n = 0 then 1 else n * fakulteta (n - 1)
in fakulteta 10

- : int = 3628800

Kljub temu da tudi Python vsebuje prvine funkcijskega programiranja, pa je v osnovi imperativni (zaradi vloge objektov pa tudi objektni) jezik, kjer računalnik usmerjamo prek zaporedja ukazov, ki začetno stanje spravijo v želeno stanje. Na primer, fakulteto bi izračunali tako, da bi si izbrali spremenljivko za hranjenje vrednosti, nato pa to spremenljivko postopoma spreminjali, dokler ne bi dobili iskanega števila:

fakulteta = 1
for i in range(1, 11):
    fakulteta *= i

Statični in dinamični tipi#

Ena izmed razlik med jezikoma je tudi v sistemu tipov. OCaml tipe preverja statično, torej še pred izvajanjem. Če napišemo:

let je_majhen x =
  if x < 10 then "Da" else false

File "[143]", line 2, characters 27-32:
2 |   if x < 10 then "Da" else false
                               ^^^^^
Error: This expression has type bool but an expression was expected of type
         string

dobimo napako, še preden funkcijo pokličemo. V nasprotju z OCamlom bo Python enako definicijo sprejel:

def je_majhen(x):
    return 'Da' if x < 10 else False

vendar bo ta v nekaterih primerih delala uspešno, v drugih pa ne:

>>> je_majhen(3) + '!'
'Da!'

>>> je_majhen(10) + '!'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s)
  for +: 'bool' and 'str'

Kot vidimo v opozorilu, je Python tipe sicer preveril (zato računalnik ni na slepo delal z ničlami in enicami, kar bi lahko vodilo do hujših napak), vendar šele takrat, ko smo program izvedli. Pravimo, da ima Python dinamičen sistem tipov.

Izpeljava tipov#

Prav tako so OCamlovi tipi precej bogatejši, na primer za spodnji seznam in funkcijo OCaml zelo natančno pove, kakšne oblike sta:

[(1, ['a']); (10, []); (0, ['x'; 'y'])]

- : (int * char list) list = [(1, ['a']); (10, []); (0, ['x'; 'y'])]

fun x -> [(x ^ "!", 0)]

- : string -> (string * int) list = <fun>

Python pa sporoči le to, da sta seznam in funkcija:

>>> type([(1, ['a']), (10, []), (0, ['x', 'y'])])
<type 'list'>

>>> type(lambda x: [(x + '!', 0)])
<type 'function'>

OCaml tipe tudi sam izračuna. Na primer, spodnja funkcija vzame funkcijo f ter jo dvakrat zaporedoma uporabi na 0. Iz tega sledi, da mora f sprejeti argument tipa int. Ker rezultat f 0 znova podamo f, mora tudi ta biti int, zato je tip funkcije f enak int -> int, kar OCaml sam izračuna:

let dvakrat_na_nic f = f (f 0)

val dvakrat_na_nic : (int -> int) -> int = <fun>

dvakrat_na_nic succ

- : int = 2

Vaje#

Vektorji#

Napišite funkcijo razteg : float -> float list -> float list, ki vektor, predstavljen s seznamom števil s plavajočo vejico, pomnoži z danim skalarjem.

let primer_vektorji_1 = razteg 2.0 [1.0; 2.0; 3.0]

val primer_vektorji_1 : float list = [2.; 4.; 6.]

Napišite funkcijo sestej : float list -> float list -> float list, ki vrne vsoto dveh vektorjev.

let primer_vektorji_2 = sestej [1.0; 2.0; 3.0] [4.0; 5.0; 6.0]

val primer_vektorji_2 : float list = [5.; 7.; 9.]

Napišite funkcijo skalarni_produkt : float list -> float list -> float, ki izračuna skalarni produkt dveh vektorjev. Pri tem si lahko pomagate s funkcijo vsota_seznama : float list -> float, definirano prek funkcije List.fold_left, ki jo bomo spoznali kasneje:

let vsota_seznama = List.fold_left (+.) 0.

val vsota_seznama : float list -> float = <fun>

let primer_vektorji_3 = skalarni_produkt [1.0; 2.0; 3.0] [4.0; 5.0; 6.0]

val primer_vektorji_3 : float = 32.

Napišite funkcijo norma : float list -> float, ki vrne evklidsko normo vektorja.

let primer_vektorji_4 = norma [3.0; 4.0]

val primer_vektorji_4 : float = 5.

Napišite funkcijo vmesni_kot : float list -> float list -> float, ki izračuna kot med dvema vektorjema v radianih.

let primer_vektorji_5 = vmesni_kot [1.0; 0.0] [0.0; 1.0]

val primer_vektorji_5 : float = 1.57079632679489656

Napišite funkcijo normirani : float list -> float list, ki normira dani vektor.

let primer_vektorji_6 = normirani [3.0; 4.0]

val primer_vektorji_6 : float list = [0.600000000000000089; 0.8]

Napišite funkcijo projeciraj : float list -> float list -> float list, ki izračuna projekcijo prvega vektorja na drugega.

let primer_vektorji_7 = projekcija [3.0; 4.0] [1.0; 0.0]

val primer_vektorji_7 : float list = [3.; 0.]

Generiranje HTML-ja#

Napišite funkcijo ovij : string -> string -> string, ki sprejme ime HTML oznake in vsebino ter vrne niz, ki predstavlja ustrezno HTML oznako.

let primer_html_1 = ovij "h1" "Hello, world!"

val primer_html_1 : string = "<h1>Hello, world!</h1>"

Napišite funkcijo zamakni : int -> string -> string, ki sprejme število presledkov in niz ter vrne niz, v katerem je vsaka vrstica zamaknjena za ustrezno število presledkov.

let primer_html_2 = zamakni 4 "Hello,\nworld!"

val primer_html_2 : string = "    Hello,\n    world!"

Napišite funkcijo ul : string list -> string, ki sprejme seznam nizov in vrne niz, ki predstavlja ustrezno zamaknjen neurejeni seznam v HTML-ju:

let primer_html_3 = ul ["ananas"; "banana"; "čokolada"]

val primer_html_3 : string =
  "<ul>\n  <li>ananas</li>\n  <li>banana</li>\n  <li>čokolada</li>\n</ul>"

Nakupovalni seznam#

Napišite funkcijo razdeli_vrstico : string -> string * string, ki sprejme niz, ki vsebuje vejico, loči na del pred in del za njo.

let primer_seznam_1 = razdeli_vrstico "mleko, 2"

val primer_seznam_1 : string * string = ("mleko", "2")

Napišite funkcijo pretvori_v_seznam_parov : string -> (string * string) list, ki sprejme večvrstični niz, kjer je vsaka vrstica niz oblike "izdelek, vrednost", in vrne seznam ustreznih parov.

let primer_seznam_2 = pretvori_v_seznam_parov "mleko, 2\nkruh, 1\njabolko, 5"

val primer_seznam_2 : (string * string) list =
  [("mleko", "2"); ("kruh", "1"); ("jabolko", "5")]

Napišite funkcijo pretvori_druge_komponente : ('a -> 'b) -> (string * 'a) list -> (string * 'b) list, ki dano funkcijo uporabi na vseh drugih komponentah elementov seznama.

let primer_seznam_3 =
  let seznam = [("ata", "mama"); ("teta", "stric")] in
  pretvori_druge_komponente String.length seznam

val primer_seznam_3 : (string * int) list = [("ata", 4); ("teta", 5)]

Napišite funkcijo izracunaj_skupni_znesek : string -> string -> float, ki sprejme večvrstična niza nakupovalnega seznama in cenika in izračuna skupni znesek nakupa.

let primer_seznam_4 = 
  let nakupovalni_seznam = "mleko, 2\njabolka, 5"
  and cenik = "jabolka, 0.5\nkruh, 2\nmleko, 1.5" in
  izracunaj_skupni_znesek cenik nakupovalni_seznam

val primer_seznam_4 : float = 5.5