Funkcionalno programiranje u Haskellu

Dio 1. Uvod

Serija sadržaja:

Imperativno programiranje

Najčešće imperativni jezici, u kojem se izračun svodi na uzastopno izvršavanje instrukcija. Rješavanje problema na imperativnom jeziku svodi se na opisivanje onoga što je potrebno učiniti da bi se dobio rezultat. Klasični primjeri su FORTRAN (1957), ALGOL (1958) i C (1972).

Imperativni jezici su bliski von Neumannovoj arhitekturi. U njima značajan dio koda zauzima dodjela vrijednosti varijablama.

Varijable smatraju se vremenski promjenjivim memorijskim stanicama. Trenutne vrijednosti varijabli u programu čine promjenjivo stanje.

Primjer imperativnog koda je postupak za izračunavanje faktorijala u C:

int fac (int n) (int x = 1; dok (n> 0) (x = x * n; n = n-1;) vrati x;)

Ovdje se ponavljanje operacije množenja izražava kroz petlju. Tijekom izračuna mijenjaju se vrijednosti varijabli x i n.

Inicijalizacija: n: = 3; x: = 1; Prva iteracija ciklusa: x: = 1 * 3 = 3; n: = 3-1 = 2; Druga iteracija ciklusa: x: = 3 * 2 = 6; n: = 2 - 1 = 1; Treća petlja ciklusa: x: = 6 * 1 = 6; n: = 1 - 1 = 0; Rezultat - 6

Funkcionalni jezici odnositi se na deklarativno- u njima program točno formulira traženi rezultat računanja u smislu ovisnosti funkcija jedna od druge, a detalji računanja (na primjer, kako točno vrijednosti treba staviti u memoriju i poslati) padaju na ramena jezične implementacije.

Značajke i funkcionalnost

U matematičkom smislu funkcija f: X → Y je pravilo koje dodjeljuje element x iz skupa X ( područja) element y = f x iz skupa Y ( suregije).

Važno je da je funkcija ispravno definirana, odnosno da ne smije biti nejasnoća oko njezine vrijednosti za svaki argument.

Ako su vrijednosti definirane za sve elemente regije, tada se funkcija naziva univerzalno definirana; inače se naziva djelomičnim.

Kao i u matematici, u funkcionalnim jezicima koji nas zanimaju ne postoje ćelije koje pohranjuju različite vrijednosti. Varijable su samo imena vrijednosti.

Tipično, jednadžbe se koriste za definiranje funkcije u funkcionalnom jeziku. Na primjer,

fac 0 = 1 fac n = n * fac (n-1)

n - formalni argument funkcije fac. Desno nakon znaka = opisano je, što funkcija radi sa svojim argumentom. Osnovne funkcije za množenje i oduzimanje pišu se pomoću infiksnih (navedenih između argumenata) operatora * i -.

Ovdje postoje dvije jednadžbe. Prilikom izračunavanja funkcije, jednadžbe se pregledavaju redom. Ako je n = 0, tada će se koristiti prva jednadžba. Ako je n ≠ 0, onda neće raditi, a koristi se drugi.

Imajte na umu: argumenti funkcije navedeni su pored njenog naziva, odvojeni razmakom. To je zgodno jer je upotreba funkcije vrlo česta u funkcionalnim programima (Tablica 1).

Pisanje iz matematike	Pisanje na Haskellu
f (x)	f x
f (x, y)	f x y
f (g (x))	f (g x)
f (g (x), h (y))	f (g x) (h y)
f (x) + g (x)	f x + g x
f (x + y)	f (x + y)
f (-x)	f (-x)

Tablica 1. Zapisivanje primjene funkcije u matematici i u Haskellu

Jednadžbe za fac čine točnu definiciju funkcije, a ne slijed računskih koraka, kao što je bio slučaj u imperativnom kodu.

Koristi se rekurzija, tj. fac se definira kroz sebe. Ova definicija funkcionira jer se fac izražava u terminima jednostavnijeg slučaja i, u konačnici (ako je n ≥ 0), doseže osnovni slučaj n = 0. Izračun fac 3 prema ovoj definiciji može se izvesti na sljedeći način (pojednostavljeni izrazi su podvučeni na svakom koraku):

fac 3 → 3 * fac 2 → 3 * (2 * fac 1) → 3 * (2 * (1 * fac 0)) → 3 * (2 * (1 * 1)) → 3 * (2 * 1) → 3 * 2 → 6

Ovdje smo primijenili f na vrijednost 3. Štoviše, 3 se zove stvarni argument.

Funkcionalni pristup usredotočuje se na evaluaciju izraza, a ne na izvršavanje naredbi. Zapravo, funkcionalni program je izraz, a njegovo izvršenje odgovara evaluaciji izraza.

Prilikom evaluacije prepisujemo izraze zamjenom vrijednosti za varijable i primjenom funkcija dok se ne dobije konačni rezultat.

Imajte na umu da za n< 0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).

Sada zapisujemo funkciju koja izračunava binomni koeficijent za cijeli broj k i realni r

Za k ≥ 0, imamo izraz u kojem nazivnik sadrži upravo definirani faktorijel broja k, a brojnik sadrži padajuću faktorijalnu snagu

Zapišimo rekurzivnu definiciju za to:

ffp r 0 = 1 ffp r k = (r-k + 1) * ffp r (k-1)

Prva jednadžba ne koristi r, tako da možete koristiti rezervirano mjesto _ i napisati ffp _ 0 = 1.

U to se može uvjeriti

(provjeriti). Stoga se faktorijske jednadžbe mogu zamijeniti s

fac n = ffp n n

Nakon što smo zapisali jednadžbe za ffp funkciju, možemo je zamisliti kao apstraktnu crnu kutiju s dva ulaza i jednim izlazom bez brige o tome što se točno događa unutra. Sve što nam je sada važno je ispravan prikaz ulaza i izlaza.

Slika 2. Crna kutija koja izračunava opadajući faktorijalni stupanj

Uzmimo još jednu crnu kutiju (/) s dva ulaza x i y i izlazom jednakim kvocijentu x / y:

izračunat će sljedeću shemu:

Slika 3. Sklop crne kutije za izračun binomnog koeficijenta

Odgovara izrazu

ffp r k / fac k

Definirajmo traženu funkciju:

binc r k | k> = 0 = ffp r k / fac k | inače = 0

Takav zapis naziva se jednadžba s uvjetima (usporedi s matematičkom notacijom definicije). Nakon | a postoje uvjeti ispred znaka =. "Inače" znači "inače". O tome će se detaljno raspravljati u sljedećim člancima.

Primjer izračunavanja binc 6 2:

binc 6 2 → ffp 6 2 / fac 2 → (5 * ffp 6 1) / fac 2 → (5 * (6 * ffp r 0)) / fac 2 → (5 * (6 * 1)) / fac 2 → (5 * 6) / fac 2 → 30 / fac 2 → 30 / ffp 2 2 → 30 / (1 * ffp 2 1) → 30 / (1 * (2 * ffp r 0)) → 30 / (1 * ( 2 * 1)) → 30 / (1 * 2) → 30/2 → 15

Kada smo spajali crne kutije, pretpostavili smo da, prvo, one uvijek daju isti rezultat za iste ulaze i, drugo, ne utječu na rad drugih kutija.

To dovodi do važnog koncepta čistoće.

Čistoća

Prilikom poziva postupci u imperativnom jeziku, često ne samo da mu prenosimo argumente i dobijemo rezultat, nego i očekujemo nuspojava- nešto što nije povezano s prijevodom argumenata u povratnu vrijednost (izlaz podataka u datoteku, promjena globalne varijable, itd.). Nažalost, nuspojave se često pojavljuju čak i kada nisu predviđene.

Ako funkcija ima nuspojave, onda njezino vrednovanje s istim argumentima u različitim kontekstima može proizvesti različite rezultate.

Ako ima puno nuspojava, programiranje postaje kompliciranije, pojavljuje se više pogrešaka u kodu, a njegovu ispravnost postaje teško provjeriti formalnim i neformalnim sredstvima.

Ovdje proceduru nismo nazvali funkcijom, jer u prisutnosti nuspojava postupak ne izgleda kao funkcija u matematičkom smislu (ponekad se takve funkcije nazivaju čist).

Ako nema nuspojava, izraz se uvijek može zamijeniti njegovom vrijednošću, a program će raditi kao i prije - to se zove transparentnost na linkovima... Isti izraz mora proizvesti isti rezultat kada se evaluira u bilo kojem trenutku.

Svaki izraz u funkcionalnom jeziku odgovara svom značenju; evaluacija samo mijenja izraz, ali ne utječe na vrijednost.

Programiranje bez nuspojava može se u potpunosti promatrati iz perspektive primjene funkcija na argumente.

Zove se jezik bez nuspojava čisto funkcionalno.

Jezici kao što su ML i Scheme općenito su funkcionalni u stilu, ali dopuštaju i zadatke i nuspojave.

Primjeri čisto funkcionalnih jezika su Miranda, Haskell i Clean.

U početku se može činiti da je čisto funkcionalni jezik nepraktičan, ali to je daleko od slučaja - za uspješno programiranje trebate se samo upoznati s nekim jednostavnim i elegantnim idejama (i zaboraviti na stare navike).

Lijenost i opuštenost

Kada se funkcija poziva po vrijednosti, njezini se argumenti prvo izračunavaju, a zatim se rezultirajuće vrijednosti prosljeđuju tijelu funkcije. Kada se pozivaju po potrebi, argumenti se prosljeđuju neizračunati i vrednuju u tijelu funkcije samo ako je potrebno.

To otprilike odgovara onome što funkcionalni jezici nazivaju željnom i lijenom evaluacijom. U energetskom se proračuna sve što je moguće, a u lijenom sve što je potrebno. (Odgodit ćemo formalni pristup ovom pitanju dok ne bude jasno koji model računanja leži u osnovi funkcionalnih jezika.)

Funkcija se u jednom od svojih argumenata naziva strogom ako uvijek zahtijeva svoju vrijednost da bi dobila rezultat. Ako vrijednost nije uvijek potrebna, tada se funkcija naziva lax za ovaj argument.

Na primjer, naša binc funkcija uvijek će zahtijevati k, ali r je potrebno samo ako je k ≥ 0.

U skladu s tim, govori se o jezicima s jakom semantikom i o jezicima s labavom semantikom. ("Lijenost" i "lijenost" nisu isti, već bliski pojmovi.)

Strogi jezik procjenjuje argumente prije pozivanja funkcije. Dakle, ako se evaluacija izraza e ne završi (zapetlja ili se zaustavi s greškom), tada se neće evaluirati ni uporaba funkcije f e.

Laganim jezikom, računanje se vrši prema potrebi. Ako f nije striktno, tada izračunavanje f e može završiti čak i ako izračunavanje e nije.

Na primjer,

označava popis od tri elementa. Izračun faktora (-1) je u petlji. To znači da će se izračunavanje popisa također odvijati u petlji.

Sada neka funkcija dužina vrati duljinu popisa. Izraz

duljina

neće se evaluirati u strogom jeziku, ali na nestrogom jeziku rezultat će biti 3, jer njihove vrijednosti nisu potrebne za brojanje elemenata.

Primjeri labavih jezika su Miranda i Haskell. Strogi jezici su ML i Scheme.

Pitanje ozbiljnosti je prilično suptilno i ne može se svesti na jednostavno "Što je prikladnije i učinkovitije?" > Propuštanje lijenih izračuna umjesto vrijednosti tijekom poziva funkcije je skupo. Istodobno, u mnogim situacijama, lijenost vam omogućuje uštedu na izračunima ili pisanje izraza koji se ne bi evaluirali ili bi se evaluirali neograničeno na energičnom jeziku.

Labavost je neovisna karakteristika čistoće, iako na mnogo načina pomaže jeziku da se suzdrži od nuspojava.

Pripovijetka

Funkcionalno programiranje crpi ideje iz kombinatorne logike i lambda računa.

Neki od prvih jezika s funkcionalnim stilom bili su LISP (1958), APL (1964), ISWIM (1966) i (1977).

Do kasnih 1980-ih već je postojalo mnogo funkcionalnih jezika. Među onima koji su imali značajan utjecaj na Haskell:

• (1973) - prvi jezik s tipkanjem Hindley-Milner.
• SASL, KRC, Miranda (1972-1985) - neki od prvih lijenih jezika.
• Hope (1980) jedan je od prvih jezika s algebarskim tipovima podataka. Haskell je razvila velika skupina istraživača od 1987. Nazvan je po Haskell Curryju.

Glavni zadatak na koji je dizajn bio usmjeren - Haskell je morao prikupiti dostupna dostignuća u području labavih čisto funkcionalnih jezika.

Novo u Haskellu su monade i klase tipova. Ostale prednosti posuđene iz drugih jezika su curry, algebarski tipovi podataka, podudaranje uzoraka. (Ovdje samo navodimo skup ključnih riječi; svi ovi koncepti će uskoro biti objašnjeni.)

Posljednji dokumentirani opis je Haskell 98, ali jezik se stalno razvija i postaje složeniji; Haskell se trenutno planira."

Haskell je postao najpopularniji labav, čisto funkcionalan jezik. U Haskellu su implementirani mnogi složeni projekti:

• Kompilatori i drugi razvojni alati.
• Distribuirani sustav kontrole verzija Darcs.
• Upravitelj prozora xmonad.
• HAppS poslužitelj web aplikacija.
• Pugs tumač / kompajler za Perl 6.
• Kućni operativni sustav.
• Jezik opisa hardvera Lava.
• LOLITA sustav za obradu prirodnog jezika.
• Sustavi za dokazivanje teorema Ekvinocij / Paradoks i Agda.

Glavni izvori informacija o Haskellu

Haskell ima široku i prijateljsku zajednicu.

Glavni izvor informacija je poslužitelj haskell.org.

• [e-mail zaštićen]- slobodna rasprava.
• [e-mail zaštićen]- jednostavnije teme za početnike.

  Na irc.freenode.net postoji vrlo živahan #haskell IRC kanal. Pruža brz i koristan odgovor na gotovo svako pitanje.

  Puno tematskih blogova prikupljeno je na http://planet.haskell.org/

• Nježan uvod u Haskell 98 dobar je uvod u Haskell.
• Za opsežnu dokumentaciju knjižnice pogledajte http://haskell.org/ghc/docs/latest/html/libraries/
• Službeno izvješće je The Haskell 98 Report.

Uređivanje i izvršavanje koda

Haskell implementacije

Formalno, Haskell nema niti jednu "standardnu" implementaciju.

Za interaktivni rad prikladan je lagani tumač Hugs.

Tu je i zanimljiv projekt pod nazivom Yhc, koji kompilira izvore u bajtkod, i Helium, tutorial verzija Haskell-a koja je prijateljska za početnike (na primjer, proizvodi jasnije poruke o pogrešci). Međutim, oni su još uvijek u razvoju.

GHC kompajler/interpretator postao je de facto standard. Najnapredniji je, u svemu odgovara standardu i nudi niz eksperimentalnih proširenja. Mi ćemo se koncentrirati na to.

GHC se može preuzeti s http://haskell.org/ghc/. Ako koristite GNU / Linux, provjerite unaprijed izgrađene verzije u vašoj distribuciji. Binarne datoteke se također mogu pronaći za MacOS X i Windows. (Imajte na umu da izgradnja GHC-a izravno iz izvora može biti prilično zamorna.)

Prvenstveno će nas zanimati interaktivni ghci program, u kojem je prikladno testirati primjere treninga.

Dakle, nakon instalacije GHC-a, možete pokrenuti ghci u terminalu:

Ovdje je Prelude naziv učitanog modula. Preludij sadrži osnovne definicije i uvijek je omogućen prema zadanim postavkama. Samostalnim proučavanjem ili prepisivanjem koda Prelude početnici mogu puno naučiti. (Vi i ja ćemo djelomično i ovo učiniti.)

Simbol> znači da ghci očekuje korisnički unos. To mogu biti Haskell izrazi, kao i naredbe za tumač.

Tipke ← i → pomiču kursor oko naredbenog retka ghci. i ↓ pomičite povijest naredbi naprijed-natrag.

Umjesto Prelude> ili drugih naziva modula, nastavit ćemo pisati ghci> (ako želite učiniti isto, pokrenite naredbu u ghci: set prompt "ghci>").

Za početak, ghci se može koristiti kao napredni kalkulator:

ghci> 1 * 2 + 2 * 3 + 3 * 5 23 ghci> 23 ^ 23 ghci> gcd 3020199 1161615 232323

Operatori su isti kao i na drugim jezicima (tablica 2).

Tablica 2. Aritmetički operatori iz Preludija

Koriste infiksnu notaciju i odgovarajući prioritet. Na primjer, 2 * 3 + 4 odgovara (2 * 3) +4, a 2 ^ 3 ^ 4 - 2 ^ (3 ^ 4). Možete staviti zagrade da promijenite prihvaćeni prioritet.

Ghci ima posebnu varijablu it, koja je jednaka vrijednosti posljednjeg uspješno evaluiranog izraza.

ghci> 15 - 2 13 ghci> to + 10 23

Uređivanje izvornog koda

Izvorni kod se može uređivati ​​u vašem omiljenom uređivaču teksta. Ipak, lijepo je imati isticanje sintakse Haskell-a, kao i podršku za usklađivanje koda (kao što ćemo vidjeti, to igra posebnu ulogu u Haskellu).

• Proširenje za Emacs: http://www.iro.umontreal.ca/~monnier/elisp/
• Proširenje za Vim: http://projects.haskell.org/haskellmode-vim/

Ostali razvojni alati opisani su na http://haskell.org/haskellwiki/Libraries_and_tools/Program_development

Hs ekstenzija datoteke koristi se za Haskell kod.

Ako napišete Haskell kod u datoteci foo.hs, tada se definicije učitavaju u ghci naredbom: load foo. Paralelno, datoteka se može uređivati ​​i, ako je potrebno, ponovno učitavati definicije pomoću: reload.

Trenutni direktorij se mijenja naredbom: cd (na primjer: cd / home / bob).

Možete preuzeti izvorni kod u prilogu članka i procijeniti izraze:

$ ghci ghci, verzija 6.10.3: http://www.haskell.org/ghc/:? za pomoć Učitavanje paketa ghc-prim ... povezivanje ... gotovo. Učitavanje cijelog broja paketa ... povezivanje ... završeno. Učitavanje baze paketa ... povezivanje ... gotovo. Preludij>: učitaj fph01.lhs Prevođenje glavnog (fph01.lhs, interpretirano) Ok, moduli su učitani: Glavni. * Glavni> ffp 6 6 720 * Glavni> fac 6 720 * Glavni> binc 6 2 15.0 * Glavni> binc 6.5 4 23.4609375

Ove i druge naredbe mogu biti skraćene - umjesto: load use: l, umjesto: reload -: r, i tako dalje.

Ispisuje se popis naredbi ljuske: pomoć. Za izlaz iz ghci-ja upišite: quit.

Tijekom našeg izlaganja često ćemo naići na jednostavne primjere koji se sastoje od jedne ili dvije jednadžbe. Mogu se ubrizgati izravno u ghci pomoću let:

ghci> neka dvostruko x = 2 * x ghci> duplo 23 46

Ako postoji nekoliko jednadžbi, onda ih je potrebno staviti u vitičaste zagrade i razdvojiti točkom i zarezom (u jednom od sljedećih članaka detaljno ćemo razmotriti takav zapis).

ghci> neka (fac 0 = 1; fac n = n * fac (n-1)) ghci> fac 23 25852016738884976640000

Zaključak

Pregledali smo općenito značajke funkcionalnog pristupa, povijest Haskell-a, glavne izvore informacija o jeziku i softveru koji nam je potreban u budućnosti. U sljedećim člancima istražit ćemo vrste i osnovnu sintaksu Haskell-a.

Funkcionalno programiranje
u Haskellu

Bilješke s predavanja

Rybinsk 2010

Uvod ................................................. ................................................................ ................. 3

1 Povijest funkcionalnog programiranja ................................................... ...... 4

2 Značajke funkcionalnih jezika .................................................. .................................... 5

2.1 Glavna svojstva ................................................. ................................................. 5

2.2 Prednosti ................................................................ ............................................... devet

2.3 Nedostaci ................................................................ ................................................................ jedanaest

3 Pregled postojećih jezika .................................................. .................................... 13

4 Osnovna načela jezika Haskell ........................................ .. ................................ 16

4.1 Interaktivno okruženje ................................................. ................................... 16

4.2 Struktura programa ................................................. ................................ osamnaest

4.3 Vrste funkcija ................................................................ ................................................. 22

4.4 Uvjetno računanje (grananje) ........................................ ................. 24

4.5 Usklađivanje uzoraka ................................................. .......................... 27

4.6 Popisi ................................................................ ................................................................ ........ 29

4.7 Lokalne definicije ................................................. .............................. 33

4.8 Dodatne značajke interaktivnog okruženja ................................. 35

4.9 Funkcije višeg reda ................................................. ................................. 36

4.10 Beskonačne strukture podataka ........................................................ ................ 37

5 Tipovi podataka i moduli ................................................. ................................................ 40

5.1 Korisnički definirani tipovi i strukture podataka ... 40

5.2 Moduli ................................................................ ................................................................ ...... 44

6 klase i monade ................................................................ ................................................................ ... 47

6.1 Klase ................................................................ ................................................................ ..... 47

6.2 I/O .............................................................. ................................................................ .. 49

7 primjera ................................................................ ................................................................ .............. 53

Zaključak................................................. ................................................................ ........ 54

Popis korištenih izvora .............................................................. ......................... 55

Uvod

Prije nego što opišemo izravno funkcionalno programiranje, osvrnimo se na povijest programiranja općenito. U 1940-ima pojavila su se prva digitalna računala koja su se programirala prebacivanjem raznih vrsta prekidača, žica i tipki. Broj takvih prebacivanja dosegao je nekoliko stotina i rastao je sa složenošću programa. Stoga je sljedeći korak u razvoju programiranja bio stvaranje svih vrsta asemblerskih jezika s jednostavnim mnemonikom.

Ali čak ni asembleri nisu mogli postati alat koji bi mnogi ljudi mogli koristiti, budući da su mnemonički kodovi još uvijek bili previše složeni, a svaki asembler je bio usko povezan s arhitekturom na kojoj se izvršavao. Sljedeći korak nakon asemblera bili su takozvani imperativni jezici visoke razine: BASIC, Pascal, C, Ada i drugi, uključujući objektno orijentirane. Takvi se jezici nazivaju imperativnim ("preskriptivnim") jer su usmjereni na sekvencijalno izvršavanje instrukcija koje rade s memorijom (tj. zadaci) i iterativnim petljama. Pozivi funkcija i procedura, čak i rekurzivni, nisu oslobodili takve jezike eksplicitne imperativnosti.

U paradigmi funkcionalnog programiranja, funkcija je kamen temeljac. Matematičke funkcije izražavaju odnos između ulaznih podataka i konačnog proizvoda procesa. Proces računanja također ima ulaz i izlaz, pa je funkcija savršeno prikladno i adekvatno sredstvo za opisivanje računanja. To je jednostavno načelo koje je temelj funkcionalne paradigme i funkcionalnog stila programiranja. Funkcionalni program je zbirka definicija funkcija. Funkcije se definiraju kroz druge funkcije ili rekurzivno kroz same sebe. U funkcionalnom jeziku, programer samo treba opisati željeni rezultat kao sustav funkcija.

2 Povijest funkcionalnog programiranja

Kao što znate, teorijske temelje imperativnog programiranja postavili su još 1930-ih godina Alan Turing i John von Neumann. Teorija na kojoj se temelji funkcionalni pristup također je rođena 1920-ih i 1930-ih. Među programerima matematičkih temelja funkcionalnog programiranja su Moses Scheinfinkel i Haskell Curry, koji su razvili kombinatornu logiku, te Alonzo Church, tvorac λ-računa (lambda račun).

Teorija je ostala teorija sve dok početkom 1950-ih John McCarthy nije razvio Lisp jezik, koji je postao prvi gotovo funkcionalni programski jezik i ostao jedini dugi niz godina. Lisp je još uvijek u upotrebi, nakon mnogo godina evolucije zadovoljava suvremene potrebe.

U vezi sa sve većom složenošću softvera, tipkanje počinje igrati sve važniju ulogu. Krajem 70-ih i početkom 80-ih godina XX. stoljeća intenzivno su se razvijali modeli tipkanja prikladni za funkcionalne jezike. Većina ovih modela uključivala je podršku za moćne mehanizme kao što su apstrakcija podataka i polimorfizam. Pojavljuju se mnogi funkcionalni jezici tipkanja: ML, Scheme, Hope, Miranda, Clean i mnogi drugi. Osim toga, broj dijalekata se stalno povećava. Gotovo svaka funkcionalna programska grupa ima svoj jezik. To je spriječilo daljnje širenje ovih jezika i izazvalo mnoge manje probleme. Kako bi popravila situaciju, zajednička skupina vodećih istraživača u području funkcionalnog programiranja odlučila je ponovno stvoriti prednosti različitih jezika u novom univerzalnom funkcionalnom jeziku. Prva implementacija ovog jezika, nazvana Haskell po Haskell Curryju, nastala je početkom 90-ih.

3 Značajke funkcionalnih jezika

Kao i svaka grupa programskih jezika, funkcionalni jezici imaju neke značajke koje ih razlikuju od drugih jezika i čine ih upravo funkcionalnim programskim jezicima.

3.1 Osnovna svojstva

Među svojstvima funkcionalnih jezika obično se razlikuju sljedeća:

- kratkoća i jednostavnost;

- jako kucanje;

- funkcije su vrijednosti;

- čistoća (bez nuspojava);

- odgođeni (lijeni) izračuni;

- modularnost.

Razmotrimo svako od ovih svojstava detaljnije.

Kratkoća i jednostavnost

Programi funkcionalnih jezika općenito su kraći i jednostavniji od onih u imperativnim jezicima. Jedan od najčešćih primjera je brzo sortiranje Hoare.

U imperativu C brzo se sortiranje obično implementira ovako:

void qsort (int a, int l, int r)

int i = l, j = r, x = a [(l + r) / 2];

dok (a [i]< x) i++;

dok (x< a[j]) j--;

int temp = a [i];

dok ja<= j);

ako (l< j) qsort (a, l, j);

ako ja< r) qsort (a, i, r);

U funkcionalnom jeziku Haskell-a, isto sortiranje je napisano mnogo kraće i jasnije:

qsort (x: xs) = qsort

++ [x] ++ qsort

Ovaj primjer treba čitati na sljedeći način: ako je popis za razvrstavanje prazan, tada će rezultat sortiranja također biti prazna lista, u suprotnom se odabiru glava i rep popisa (prvi element popisa i popis preostali elementi, eventualno prazni), a rezultat će biti konkatenacija (spajanje) sortiranog popisa svih repnih elemenata koji su manji od glave, popisa iz same glave i popisa svih repnih elemenata koji su veći od ili jednake glavi.

Kôd funkcionalnog jezika pobjeđuje u veličini i jasnoći koda. Dodatno, gornja C implementacija sortira niz čiji su elementi cjelobrojnog tipa (int), dok implementacija Haskell može sortirati popise elemenata bilo kojeg tipa na kojem je definirana operacija usporedbe.

Jako tipkanje

Većina funkcionalnih programskih jezika je jako tipizirana. Snažno tipkanje podrazumijeva ispunjenje sljedećih preduvjeta:

- svaka vrijednost, varijabla, argument i povratna vrijednost funkcije u fazi izrade programa bezuvjetno je vezana za određeni tip podataka koji se ne može mijenjati tijekom izvršavanja programa;

- funkcije mogu prihvatiti i vratiti vrijednosti koje imaju strogo isti tip podataka kao što je navedeno u opisu funkcije;

- svaka operacija zahtijeva argumente strogo definiranih tipova;

- implicitna konverzija tipa nije dopuštena (to jest, prevoditelj tretira svaki pokušaj korištenja vrijednosti različitog tipa od one opisane za varijablu, argument, funkciju ili operaciju kao grešku).

U teoriji programiranja, jako tipkanje je neizostavan element osiguranja pouzdanosti razvijenog softvera. Kada se koristi ispravno (što znači da program deklarira i koristi zasebne tipove podataka za logički nekompatibilne vrijednosti), štiti programera od jednostavnih, ali teško dostupnih pogrešaka povezanih s dijeljenjem logički nekompatibilnih vrijednosti, koje ponekad proizlaze jednostavno iz rudimentarne pogreške. Takve se pogreške otkrivaju čak i u fazi kompilacije programa, dok kada je moguće implicitno baciti gotovo bilo koju vrstu jedne na drugu (kao, na primjer, u klasičnom jeziku C), te se pogreške otkrivaju samo tijekom testiranja, a ne sve i ne sve odjednom.

Funkcionira kao vrijednosti

U funkcionalnim programskim jezicima, funkcije se mogu koristiti kao i bilo koji drugi objekti, mogu se proslijediti drugim funkcijama kao argumenti, vratiti kao rezultat drugih funkcija, pohraniti u liste i druge strukture podataka. Funkcije koje uzimaju ili vraćaju druge funkcije kao argumente nazivaju se funkcijama višeg reda.

Korištenje funkcija višeg reda omogućuje vam stvaranje fleksibilnijih funkcija, čime se povećava mogućnost ponovne upotrebe vašeg koda. Primjer je obično prosljeđivanje funkcije za usporedbu elemenata funkciji sortiranja.

Čistoća

Čistoća leži u odsutnosti nuspojava pri izračunu vrijednosti funkcije. Nuspojava funkcije je sposobnost čitanja i mijenjanja vrijednosti globalnih varijabli, izvođenja ulazno-izlaznih operacija, reagiranja na iznimne situacije i mijenjanja vrijednosti ulaznih varijabli u procesu izračunavanja svojih proračuna. Stoga, ako takvu funkciju pozovete dvaput s istim skupom vrijednosti ulaznih argumenata, rezultati izračuna mogu se razlikovati, a stanje nekih globalnih objekata (na primjer, vrijednosti varijabli) može također promijeniti. Te se funkcije nazivaju nedeterminističkim funkcijama s nuspojavama.

U čistom funkcionalnom programiranju, ista funkcija s istim argumentima uvijek vraća isti rezultat. Stvoreni objekti se ne mogu mijenjati ili uništavati, samo možete kreirati nove na temelju postojećih. Zbog čistoće, programi ne samo da postaju jasniji, već i pojednostavljuju organizaciju paralelizma u njima, budući da se funkcije mogu izračunati neovisno jedna o drugoj. Ako se rezultat čiste funkcije ne koristi, tada se njegova evaluacija može izostaviti bez štete za druge izraze. A ako ne postoji ovisnost podataka između dvije čiste funkcije, tada možete promijeniti redoslijed njihovog izračuna ili ih izračunati paralelno. U takvom slučaju, prevodilac može koristiti bilo koju računsku politiku. To prevoditelju daje slobodu da kombinira i reorganizira evaluaciju izraza u programu.

Lijeno računanje

U tradicionalnim jezicima, prije pozivanja funkcije, izračunavaju se vrijednosti svih njenih argumenata. Ova metoda pozivanja funkcija naziva se poziv po vrijednosti. Ako se neki od argumenata ne upotrijebi, onda su izračuni izgubljeni. Mnogi funkcionalni jezici koriste drugačiji način pozivanja funkcija - "pozovi kada je potrebno". Štoviše, svaki argument funkcije izračunava se samo ako je njegova vrijednost neophodna za izračunavanje rezultata funkcije. Na primjer, operacija veznika C ++ (&&) ne zahtijeva procjenu vrijednosti drugog argumenta ako je prvi netočan.

Lazy evaluation u nekim slučajevima omogućuje vam da ubrzate izvršavanje programa, a također vam omogućuje korištenje raznih beskonačnih struktura podataka.

Modularnost

Mehanizam modularnosti omogućuje da se programi podijele na nekoliko relativno neovisnih dijelova (ili modula) s dobro definiranim odnosima među njima. To olakšava dizajn i naknadno održavanje velikih softverskih sustava. Podrška za modularnost nije značajka funkcionalnih programskih jezika, ali je podržava većina ovih jezika.

3.2 Prednosti

Funkcionalni programski jezici imaju nekoliko prednosti u odnosu na imperativne jezike. Korištenje paradigme funkcionalnog programiranja povećava pouzdanost programa, brzinu njihovog pisanja, praktičnost jediničnog testiranja, mogućnost optimizacije tijekom kompilacije, te mogućnost automatskog organiziranja paralelizma.

Pouzdanost programiranja

Nedostatak nuspojava onemogućuje mnoge pogreške koje je teško pronaći, kao što je slučajno dodjeljivanje nevažeće vrijednosti globalnoj varijabli. Strogo statičko tipkanje omogućuje u fazi kompilacije da se uhvati veliki broj pogrešaka povezanih s netočnom upotrebom nekih podataka.

Zanimljiva značajka funkcionalnih jezika je da su pogodni za matematičku analizu. Budući da je funkcionalni jezik samo implementacija formalnog sustava, sve matematičke operacije koje bi se mogle izvesti na papiru također se odnose na programe napisane na takvom jeziku. Na primjer, prevodilac može pretvoriti dijelove koda u ekvivalentne, ali učinkovitije dijelove matematičkim dokazivanjem da su dijelovi ekvivalentni. Štoviše, pomoću ovih tehnologija možete dokazati da su određeni dijelovi vašeg programa točni.

Pogodnost testiranja jedinica

Budući da funkcija u funkcionalnom programiranju ne može generirati nuspojave, objekti se ne mogu mijenjati unutar opsega i izvan njega (za razliku od imperativnih programa, gdje jedna funkcija može promijeniti neku vanjsku varijablu koju čita druga funkcija). Jedini učinak evaluacije funkcije je rezultat koji vraća, a jedini faktor koji utječe na rezultat su vrijednosti argumenata.

Stoga je moguće testirati svaku funkciju u programu jednostavnim procjenom iz različitih skupova vrijednosti argumenata. U tom slučaju ne morate brinuti o pozivanju funkcija ispravnim redoslijedom ili o ispravnom formiranju vanjskog stanja. Ako bilo koja funkcija u programu prođe jedinične testove, tada možete biti sigurni u kvalitetu cijelog programa. U imperativnim programima provjera povratne vrijednosti funkcije nije dovoljna: funkcija može modificirati vanjsko stanje, koje također treba provjeriti, što se ne mora raditi u funkcionalnim programima

Mogućnosti optimizacije

Opis programa u obliku skupa funkcija bez eksplicitnog navođenja redoslijeda njihovog izračuna i čistoće funkcija omogućavaju primjenu prilično složenih i učinkovitih metoda automatske optimizacije na funkcionalne programe.

Još jedna prednost funkcionalnih programa je što pružaju najšire mogućnosti za automatsku paralelizaciju izračuna. Budući da je odsutnost nuspojava zajamčena, u bilo kojem pozivu funkcije uvijek je moguće paralelno vrednovati dva različita argumenta - redoslijed kojim se evaluiraju ne može utjecati na rezultat poziva.

Dokaz svojstava funkcija

Budući da proračun funkcija u funkcionalnom programiranju ne uzrokuje nuspojave, za analizu takvih funkcija primjenjive su matematičke metode (npr. metoda matematičke indukcije). To vam omogućuje da dokažete ispravan rad funkcija, ili nekih drugih njihovih svojstava, bez testiranja.

3.3 Nedostaci

Nedostaci funkcionalnog programiranja proizlaze iz istih značajki. Nedostatak zadataka i njihova zamjena generiranjem novih podataka dovodi do potrebe za stalnom dodjelom i automatskim oslobađanjem memorije, pa visoko učinkovit sakupljač smeća postaje obavezna komponenta u sustavu izvršavanja funkcionalnog programa. Da bi skupljanje smeća bilo učinkovito, morate pratiti reference podataka, što također zahtijeva vrijeme i memoriju. Nedostatak petlji za industrijske programe prilično je ozbiljno ograničenje, budući da mnogi algoritmi zahtijevaju vrlo duge ili čak formalno beskonačne petlje, koje je neučinkovito ili čak nemoguće predstaviti u rekurzivnom obliku jer je potrebna dubina rekurzije prevelika. U određenoj mjeri, potonji nedostatak može se zaobići automatskim pretvaranjem rekurzije u petlju, koju izvode neki prevoditelji funkcionalnih jezika za specifičan slučaj repne rekurzije, ali ne dopuštaju svi oblici rekurzije takvu konverziju (međutim, oni koji se ne može pretvoriti u takvu konverziju ne može biti dizajnirani su kao jednostavan ciklus i na imperativnim jezicima).

Kako bi se prevladali ovi nedostaci, mnogi funkcionalni jezici uključuju imperativne programske alate koji vam omogućuju da eksplicitno odredite redoslijed radnji, koristite petlje i nuspojave (na primjer, ulazne i izlazne operacije).

4 Pregled postojećih jezika

Trenutno je razvijen veliki broj funkcionalnih programskih jezika. Svi oni imaju jedinstvene karakteristike, pozitivne i negativne kvalitete. Najčešći i najučinkovitiji danas su sljedeći jezici ili jezične obitelji:

Razmotrimo značajke svakog od ovih jezika:

– Lisp... Ime je dobila po engleskom LIST Processing - obrada liste. Lisp je jedan od najranijih funkcionalnih programskih jezika. Lisp programi i podaci predstavljeni su sustavima linearnih popisa znakova. Lisp je, zajedno s Adom, prošao kroz temeljni proces standardizacije za vojnu i industrijsku uporabu, što je rezultiralo standardom Common Lisp. Njegove implementacije postoje za većinu platformi. Prva upotreba Lisp-a bila je povezana sa simboličkom obradom podataka i procesima donošenja odluka. Najpopularniji dijalekt Common Lisp-a danas je univerzalni programski jezik. Široko se koristi u raznim projektima: internetski poslužitelji i usluge, aplikacijski poslužitelji i klijenti koji komuniciraju s bazama podataka, znanstveno računalstvo i programi za igre.

– Haskell... To je jedan od najčešćih lijenih programskih jezika. Ima vrlo razvijen sustav tipkanja. U posljednje vrijeme skup primijenjenih knjižnica se širi, jezik se integrira u uobičajene softverske sustave, što jezik čini sve privlačnijim za profesionalne programere. Glavne značajke jezika: sposobnost korištenja lambda apstrakcije; funkcije višeg reda; djelomična primjena; nedopustivost nuspojava (čistoća jezika); lijeno ocjenjivanje; usklađivanje uzoraka, funkcionalni uzorci; parametarski polimorfizam i polimorfizam klasa tipova; statičko tipkanje; automatsko zaključivanje tipa (temeljeno na Hindley-Milner modelu tipkanja); algebarski tipovi podataka; vrste podataka s parametrima; rekurzivni tipovi podataka; apstraktni tipovi podataka (enkapsulacija); navesti shvaćanja; stražarski izrazi (čuvari); sposobnost pisanja programa s nuspojavama bez kršenja paradigme funkcionalnog programiranja pomoću monada; mogućnost integracije s programima implementiranim u imperativnim programskim jezicima kroz otvorena sučelja (standardna ekstenzija jezika sučelja stranih funkcija).

– ML(Meta Language) je obitelj strogih funkcionalnih programskih jezika s razvijenim sustavom polimorfnih tipova i modulima koji se mogu parametrirati. ML se predaje na mnogim zapadnim sveučilištima. Jako tipiziran jezik sa statičkim tipkanjem i aplikativnim izvršavanjem programa. Glavne prednosti ML-a su visoka provjerljivost programa, jednostavnost otklanjanja pogrešaka, potencijal za visoku optimizaciju, jedinstvena kratkoća pisanja. Glavni nedostaci su složenost sintakse, nepoznavanje prihvaćenih sporazuma i ograničenja, praktična nemogućnost makrotransformacija.

– Erlang- funkcionalni programski jezik koji vam omogućuje pisanje programa za različite vrste distribuiranih sustava. Razvio i održava Ericsson. Jezik uključuje sredstva za generiranje paralelnih procesa i njihovu komunikaciju slanjem asinkronih poruka. Program se prevodi u bytecode, koji se izvršava od strane virtualnog stroja radi prijenosa. Ključ Erlanga je njegov lagani procesni model. Da parafraziramo Erlangov slogan “Sve je objekt”, možemo reći “Sve je proces”. Procesi su jeftini, stvaranje procesa ne zahtijeva više resursa nego pozivanje funkcije. Jedini način na koji procesi komuniciraju je asinkrono slanje poruka.

Od ovih jezika, Haskell je najistaknutiji predstavnik funkcionalnih programskih jezika. Ima jednostavnu sintaksu i sva gore navedena svojstva za funkcionalne jezike.

5 Osnovni principi jezika Haskell

Kao što je rečeno, programski jezik Haskell je funkcionalni jezik i ima sva gore navedena svojstva.

Prvo, pogledajmo potrebne alate za rad. Najrašireniji i najučinkovitiji prevodilac danas je GHC(Glasgow Haskell Compiler). Distribuira se pod otvorenom licencom, a svatko može preuzeti njegov izvorni kod ili kompajliranu verziju za popularne operativne sustave sa službene stranice http: // haskell. org / ghc / (osim toga, postoji mnogo dodatnih informacija o jeziku na http: // haskell.org /).

Uz sam prevodilac, GHC uključuje GHCi interaktivno okruženje (GHC interactive), Haskell interpreter koji vam omogućuje procjenu svih izraza i tumačenje napisanih programa.

Nažalost, potpuno opremljeno razvojno okruženje za Haskell još nije razvijeno (osim, možda, Leksah, razvojnog okruženja za Haskell napisane u Haskellu i nekoliko dodataka za Visual Studio i Eclipse), ali često samo mogućnosti dovoljan je napredni uređivač teksta (na primjer, Notepad ++, gedit, kate) s isticanjem sintakse i nekim drugim značajkama.

5.1 Interaktivno okruženje

Interaktivno okruženje GHCi može procijeniti bilo koji Haskell izraz. Pogledajmo osnove rada s ovim okruženjem. Da biste ga pokrenuli (nakon instaliranja GHC-a ili Haskell-Platforme), samo pokrenite ghci program u konzoli (ili odaberite odgovarajući program s popisa svih programa). Nakon pokretanja, konzola će prikazati upit:

Prelude znači naziv trenutnog modula, prema zadanim postavkama učitava se standardni Prelude modul koji sadrži sve glavne funkcije i tipove podataka.

Ovdje možemo procijeniti bilo koji izraz, na primjer, običan aritmetički izraz:

Kao što vidimo, interaktivno okruženje je izračunalo rezultat izraza i ispisalo ga u novom retku. Pokušajmo izračunati kompliciraniji izraz:

Preludij> 1-2 * (4-3 ^ 2)

Eksponencijacija (^) je standardni operator definiran u standardnom modulu Prelude zajedno s operacijama zbrajanja i množenja.

Osim aritmetičkih izraza u interaktivnom okruženju, moguće je izračunati bilo koje druge funkcije definirane u standardnom modulu, ili u bilo kojoj drugoj učitanoj od strane korisnika.

Da biste izračunali vrijednost funkcije, napišite njezino ime i navedite argumente, odvojene razmacima. Na primjer, standardni modul definira funkciju max koja bira maksimalnu vrijednost iz dva argumenta. Možete ga koristiti ovako:

Preludij> max 7 100

Ovaj primjer izračunava najviše dva broja, sedam i sto. Kao što vidimo, rezultat evaluacije funkcije je broj 100.

Bilo koji izrazi (ali samo odgovarajućeg tipa; vrste su detaljnije razmatrane u drugim odjeljcima) mogu djelovati kao argumenti funkciji, na primjer:

Preludij> max (2 ^^ 3)

Ovaj primjer utvrđuje da je dva na deseti stepen veće od deset na treći stepen. Imajte na umu da je stavljanje argumenata u zagrade potrebno kako bi se razlikovalo koji je dio izraza argument. Na primjer, ako izostavite zagrade drugog argumenta, dobit ćete pomalo neočekivani rezultat:

Preludij> max (2 ^ 10) 10 ^ 3

Bez zagrada, ovaj izraz se tumači kao maksimum od dva broja (1024 i 10), podignuta na treći stepen.

Osim toga, GHCi interaktivno okruženje može automatski dovršiti nazive unesenih funkcija. Ako upišete samo početni dio naziva funkcije i pritisnete tipku "Tab" na tipkovnici, tada će GHCi pokušati dovršiti naziv funkcije na onu koja je dostupna među dostupnim definicijama (iz standardnog modula ili povezanog od strane korisnika) . Na primjer, ako upišete "maxi" i pritisnete "Tab", tada će GHCi naziv funkcije dodati na "maximum". U slučaju da je nemoguće nedvosmisleno dopuniti (postoji nekoliko prikladnih opcija), tada se prikazuju sve moguće opcije:

max maxBound maksimum

Sada možete odrediti naziv funkcije (dodavanjem nekoliko slova) i ponovno pritisnuti tipku "Tab".

Dovršavanje je vrlo korisno kada se koristi veliki broj funkcija s dugim nazivima.

5.2 Struktura programa

Haskell prevoditelji i tumači rade s datotekama s ekstenzijom * .hs koji sadrži tekst programa. Tekst programa ima sljedeću strukturu:

1. na početku programa može se navesti naziv trenutnog modula i izvezene definicije;

3. ostatak programa zauzimaju razne definicije – definicije funkcija, tipova podataka i klasa.

Najjednostavniji program može sadržavati samo definicije funkcija (u ovom slučaju se uvozi samo standardni modul Prelude, koji sadrži većinu standardnih funkcija i tipova podataka; naziv modula je prema zadanim postavkama postavljen kao Glavni).

Najjednostavnija funkcija možda uopće ne uzima argumente, već samo vraća neku vrijednost. U ovom slučaju, definicija se sastoji od naziva funkcije, znaka jednakosti "=" i nekog izraza po kojem će se izračunati vrijednost ove funkcije. U poznatim terminima, takva se funkcija može nazvati varijabla ili konstanta, ali to nije sasvim točno. U funkcionalnom programiranju funkcije bez argumenata nazivaju se simbolima. Razmotrimo primjer:

Ovaj primjer deklarira simbol s imenom pet, koji ima cjelobrojnu vrijednost 5. Imena u Haskell-u razlikuju velika i mala slova, to jest, Five i pet su različita imena. Osim toga, uvodi se dodatno ograničenje na prvo slovo naziva - nazivi funkcija i njihovi argumenti mogu početi samo malim slovom (pet, max, min, x, y), a nazivi tipova podataka (Bool , Integer, Double), moduli (Main, Test) i klase (Eq, Ord, Num) - samo s velikim slovima (velika slova).

Pogledajmo kompliciraniji primjer:

tri = jedan + dva

Ovdje su deklarirana tri simbola - jedan, dva, tri. Kao što možete vidjeti iz primjera, svaka definicija zauzima jedan redak i odvojeni su samo krajem retka (prazni redovi će biti zanemareni). Simboli jedan i dva definirani su na isti način kao simbol pet u prethodnom primjeru, ali definicija simbola tri koristi već postojeće definicije. Kao što možete pretpostaviti, simbol tri će imati vrijednost 3.

Redoslijed definicija nije važan, odnosno sljedeći primjer će biti potpuno sličan prethodnom:

tri = jedan + dva

Učitajmo naš primjer u GHCi interaktivno okruženje. Da biste to učinili, prilikom pokretanja ghci-a navedite naziv datoteke s tekstom programa kao parametar naredbenog retka (na primjer, Test.hs) (u operacijskim sustavima Windows samo trebate otvoriti datoteku, koju instalira GHC automatski dodjeljuje ghci za otvaranje * .hs datoteka). Ako program ne sadrži pogreške, tada ćemo vidjeti već poznatu prompt:

Ovdje je Main naziv trenutnog modula (moduli su detaljnije obrađeni u odgovarajućem poglavlju). GHCi vam omogućuje da izračunate bilo koju funkciju iz trenutnog modula. Na primjer, izračunajmo naš simbol tri:

Mogući su i složeniji izrazi:

* Glavni> (tri + dva) ^ 2

* Glavni> max jedan dva

Dalje, pogledajmo funkcije s argumentima. Za razliku od konvencionalnih programskih jezika, ne morate pisati argumente u zagradama i razdvojiti ih zarezima da biste prosljeđivali argumente. Funkcija se poziva u sljedećem obliku: func x1 x2 x3… xN, gdje je func naziv funkcije, a xi i-ti argument. Rezultat funkcije bit će objekt, kao što je broj, popis, funkcija, lambda izraz ili bilo koja druga struktura podataka.

Opis funkcije s argumentima praktički je isti kao i opis simbola u prethodnim primjerima. Definicija funkcije nalazi se u zasebnom redu i ima sljedeći oblik: func x1 x2 x3… xN = izraz, gdje je func naziv nove funkcije, xi je naziv i-tog argumenta, izraz je izraz.

Na primjer, dodajmo funkciju koja dodaje dva broja postojećem Testu. hs.

Sada možemo ponovno učitati izmijenjeni modul u interaktivnom okruženju. Da biste to učinili, samo ponovno pokrenite ghci ili upotrijebite standardnu ​​naredbu ": r":

Prevođenje glavnog (Test.hs, interpretirano)

U redu, moduli su učitani: Glavni.

Nakon toga, nova funkcija postaje dostupna iz interaktivnog okruženja:

* Glavni> plus jedan 8

Još jedan primjer funkcije s argumentima:

Svaka definicija zauzima jedan redak, međutim, ako je radi jasnoće prikladnije podijeliti definiciju u nekoliko redaka, tada možete koristiti sljedeću značajku: svaki red koji počinje s uvlačenjem većim od prethodnog smatra se njegovim nastavkom. Na primjer, funkciju plus možemo napisati u dva retka ovako:

Haskell komentari u jednom retku počinju s dvije crtice:

plus x y = x + y - funkcija zbrajanja

Blok komentar počinje s "" i završava s "":

ova funkcija vraća broj koji je za 1 veći

nego što se prima kao argument

5.3 Vrste funkcija

Haskell je jako tipiziran jezik, sve funkcije u njemu imaju strogo definiran tip. Međutim, u prethodnim primjerima nismo specificirali tip, budući da tumači i prevoditelji jezika Haskell imaju moćan mehanizam zaključivanja tipa. Vrsta funkcija (i njihovi argumenti) se u većini slučajeva može zaključiti iz definicija tih funkcija. Neke funkcije mogu biti polimorfnih tipova (takve se funkcije mogu primijeniti na argumente različitih tipova), na primjer, prethodno zadana funkcija plus može zbrajati cijele i realne brojeve.

Kao što je ranije spomenuto, nazivi tipova počinju velikim slovima. Evo nekih od standardnih tipova:

	Opis
	cijeli broj od - do
	dugi cijeli broj, bez granica (omogućena je ugrađena duga aritmetika)
	pravi broj
	realni broj dvostruke preciznosti
	popis elemenata nekog tipa a, na primjer, popis cijelih brojeva zapisuje se kao
	string (ili popis znakova), ekvivalent
	boolean (može biti True ili False)
	skup od dva elementa tipa a i b (npr. (String, Bool))
	skup od tri elementa tipa a, b i c (npr. (String, Bool, Int))

Ako programer želi sam odrediti tip funkcije i njezine argumente, ili je automatsko zaključivanje tipa ove funkcije nemoguće, onda mora napraviti dodatnu definiciju koristeći operator indikacije tipa “::”. Na primjer, da biste opisali funkciju koja vraća stvarnu vrijednost, možete napisati sljedeći kod:

Prvi redak znači da je funkcija pi tipa Double, zatim sama definicija funkcije, što znači da funkcija pi vraća približnu vrijednost pi. Ako funkcija ima jedan argument, tada je njezin tip opisan na sljedeći način:

inc :: Integer -> Integer

Ova notacija znači da funkcija inc pretvara argument Integer u rezultat Integer.

Ako funkcija ima dva argumenta, njen opis izgleda ovako:

snaga :: Double -> Integer -> Double

Funkcija snage uzima dva argumenta - realnu bazu x i cjelobrojnu potenciju od n, ali funkcija daje pravi broj.

Općenito, opis tipa funkcije izgleda ovako:

naziv :: X1 -> X2 -> ... -> XN -> Y

Ovdje je naziv naziv funkcije, Xi je tip i-tog argumenta, Y je tip funkcije.

Kao što je ranije spomenuto, navođenje tipova nije obvezno, ali njegovo prisustvo može pružiti dodatnu kontrolu nad ispravnošću konstruiranih izraza u deklaraciji funkcije. Osim toga, u nekim slučajevima korištenja polimorfnih tipova nemoguće je odrediti tip funkcije bez eksplicitnog navođenja tipa.

Ovdje su neke od standardnih funkcija.

Funkcije	Opis
	tradicionalne aritmetičke operacije
	dijeljenje realnih brojeva
	dizanje broja na pozitivni cijeli broj
	dizanje broja na stvarni stepen
	cjelobrojno dijeljenje i ostatak od dijeljenja cijelih brojeva
	Korijen
	trigonometrijske funkcije
asin, akos, atan	inverzne trigonometrijske funkcije
	usporedba za jednakost i nejednakost
>, <, >=, <=	usporedba
	logičke operacije
	prvi element para (dvostruke torke)
	drugi element para
	rep (svi elementi osim prvog) popisa

5.4 Uvjetno računanje (grananje)

U tradicionalnim programskim jezicima, glavni načini organiziranja grananja su uvjetna izjava (ako je onda drugačije) i naredba izbora (case or switch). Osim toga, Haskell koristi podudaranje uzoraka u definicijama funkcija i takozvanim zaštitnim izrazima. Pogledajmo pobliže svaku od ovih metoda.

Konstrukt ako-onda-drugo

Sintaktička struktura "ako-onda-drugo" omogućuje procjenu različitih izraza ovisno o rezultatima određenog uvjeta:

ako<условие>zatim<выражение1>drugo<выражение2>

Ovdje<условие>- neki izraz tipa Bool. Za razliku od imperativnih jezika, u Haskellu je konstrukcija if-onda-else izraz koji mora imati neku vrstu rezultata. U tom smislu, potrebna je grana else i vrste izraza<выражение1>i<выражение2>moraju odgovarati.

Razmotrimo, kao primjer, funkciju za izračunavanje najviše dva broja:

max a b = ako je a> b onda a drugo b

Kao što je već spomenuto, konstrukcija "ako-onda-drugo" je izraz koji ima rezultat. Stoga se može koristiti kao dio drugog izraza:

* Glavno> 5 + ako je False onda 1 ostalo 0

* Glavno> (ako je True onda 1 ostalo 0) + 5

Imajte na umu da su u posljednjem primjeru potrebne zagrade. Bez zagrada, izraz će se tumačiti drugačije:

* Glavno> ako je istina onda 1 ostalo 0 + 5

Sve što je napisano iza riječi "ostalo" odnosi se na izraz grane else.

Konstrukcija kućišta

Razmotrimo, kao primjer, funkciju za izračunavanje danog Fibonaccijevog broja:

fib n = slučaj n od

_ -> fib (n-1) + fib (n-2)

Baš kao i uvjetni izraz "ako-onda-drugo", izraz padeža ima rezultat i stoga može biti dio drugih izraza.

Razmotrimo općenito izraz padeža:

slučaj<выражение0>od

<образец1> -> <выражение1>

<образец2> -> <выражение2>

<образецN> -> <выражениеN>

Ovdje je rezultat izračuna<выражение0>je dosljedno uparen s uzorcima. Ako je podudaranje s i-tim uzorkom uspješno, rezultat cijelog slučaja bit će rezultat i-tog izraza. Usklađivanje uzoraka bit će detaljnije razmotreno u odgovarajućem odjeljku, ali se za sada može smatrati usporedbom sa zadanim konstantama.

Imajte na umu da svaki uzorak mora biti napisan u novom retku s uvlačenjem većim od uvlačenja rezerviranog velikog slova riječi. Također, uvlake ispred uzoraka trebaju biti međusobno jednake.

Osim toga, prihvatljiv je alternativni način pisanja izraza padeža bez korištenja uvlačenja:

fib n = slučaj n od (1-> 1; 2-> 1; _-> fib (n-1) + fib (n-2))

Ova metoda je kompaktnija, ali manje opisna. Općenito:

slučaj<выражение0>od (<образец1> -> <выражение1> ; <образец2> -> <выражение2> ; ... ; <образецN> -> <выражениеN> }

Definicije funkcija

U Haskell-u, ista funkcija može imati nekoliko definicija, koje se razlikuju po načinu na koji su njeni argumenti napisani. Zapis argumenta naziva se uzorak, a kada se funkcija evaluira, proslijeđeni argumenti se uparuju s obrascima u definicijama.

Razmotrimo kao primjer funkciju izračunavanja Fibonaccijevog broja.

fib n = fib (n-1) + fib (n-2)

Prilikom izračunavanja vrijednosti funkcije, njezin se jedini argument uparuje s obrascima njezinih definicija od vrha do dna. Ako je argument bio broj 2, tada prvo podudaranje neće uspjeti, a drugo će uspjeti i kao rezultat toga funkcija će poprimiti vrijednost 1. Ako se argument ne podudara s uzorcima u prve dvije definicije, tada će definitivno odgovara nazivu argumenta n (u ovom slučaju, n će uzeti vrijednost proslijeđenog argumenta), a izračunat će se zbroj dva prethodna Fibonaccijeva broja.

Ako se među definicijama funkcije ne pronađe odgovarajuća funkcija, doći će do pogreške i izvođenje programa će se zaustaviti.

Čuvarski izrazi

Posljednji način odabira alternativa pri izračunavanju rezultata funkcija su takozvani zaštitni izrazi. Oni (za razliku od if-then-else i case izraza) mogu se koristiti samo u definicijama funkcija:

<имя функции> <список аргументов функции>

|<условие1> = <выражение1>

|<условие2> = <выражение2>

|<условиеN> = <выражениеN>

Svi znakovi "|" moraju početi na vlastitoj liniji i s jednim uvlačenjem. Prilikom izračunavanja vrijednosti funkcije, svi uvjeti koji su izrazi tipa Bool ponavljaju se od vrha do dna. Kada se pronađe i-ti uvjet, čiji je rezultat True, procjenjuje se izraz i čiji će rezultat biti rezultat funkcije.

Na primjer, napišimo funkciju pronalaženja Fibonaccijevog broja:

| inače = fib (n-1) + fib (n-2)

Ovdje je inače svjesno istinit uvjet, uvijek jednak True.

5.5 Usklađivanje uzoraka

Usklađivanje uzoraka je prikladan način povezivanja različitih dijelova vrijednosti danim imenima (znakovima). Usklađivanje uzoraka koristi se u definicijama i u izrazima.

Prilikom definiranja funkcija dolazi do podudaranja uzorka u argumentima. U najjednostavnijem slučaju, kada su argumenti specificirani samo imenima, cijeli su argumenti vezani za ta imena. Na primjer:

f x = fst x + snd x

Ova funkcija izračunava zbroj elemenata tuple. Standardne funkcije fst i snd dobivaju prvi i drugi element tuple.

* Glavno> f (2,4)

Koristeći podudaranje uzoraka, možemo istaknuti sadržaj argumenta ove funkcije na opisniji način:

Prilikom izračunavanja ove funkcije iz (2,4), elementi ove torke će se uskladiti s uzorkom navedenim u definiciji funkcije, odnosno simbol "a" će imati vrijednost 2, a simbol "b" će poprimiti vrijednost 4.

Ovako možemo definirati analoge funkcija fst i snd:

Imajte na umu da definicija fst1 ne koristi x, a definicija snd1 ne koristi y. U takvim slučajevima, kada se dio uzorka (ili cijeli argument) ne koristi, nije potrebno navoditi naziv tog dijela (ili argumenta) - umjesto naziva dovoljno je navesti znak podvlake "_". Poništimo ove funkcije:

Koristeći ovaj način pisanja, ne morate smišljati nazive za nepotrebne dijelove uzoraka, a pri čitanju definicije funkcije odmah postaje jasno da se ovaj dio argumenta ne koristi.

Uzorci mogu specificirati bilo koje konstruktore (u prethodnom primjeru korišten je konstruktor tuple), na primjer, konstruktore za popis, tuple ili bilo koje prilagođene vrste podataka, kao i specifične vrijednosti argumenata (kao u primjeru o Fibonaccijevim brojevima). U nekim slučajevima, podudaranje može biti neuspjeh, u kojem slučaju se pokušava sljedeće podudaranje (iz sljedeće definicije ili uzorka slučaja). Razmotrimo primjer:

f _ 0 = pogreška "podjela s nulom"

f (a, b) c = (a + b) / c

Ovdje će pri izračunavanju funkcije f drugi argument biti jednak 0, tada će se za izračunavanje funkcije odabrati prva definicija, inače druga, budući da je usporedba s imenom uvijek uspješna. Funkcija pogreške zaustavlja izvođenje programa s navedenim tekstom pogreške. Primjeri korištenja opisane funkcije:

* Glavno> f (1,2) 3

* Glavno> f (3.2) 1

* Glavno> f (5.5) 5

* Glavno> f (5.5) 0

*** Iznimka: dijeljenje s nulom

Osim toga, svaki uzorak se može imenovati tako da se strukturiranom argumentu može pristupiti i po elementima i u cijelosti. Operator @ koristi se za imenovanje uzorka. Prethodi mu ime preko kojeg možete pristupiti argumentu u cjelini, a zatim i samom obrascu. Na primjer,

func1 [e-mail zaštićen](a, b) = a + b + func2 p

func2 (a, b) = a * b

5.6 Popisi

Popis je jedna od najvažnijih struktura podataka koja sadrži elemente istog tipa. Popis ne može sadržavati elemente različitih tipova (za razliku od tuples). Za opis tipa "lista" koriste se uglaste zagrade. Na primjer, to je opis tipa popisa elemenata booleovog tipa.

Popisi se stvaraju pomoću konstruktora popisa - operacije ":". Popis može biti prazan ili se može sastojati od glave (prvi element popisa) i repa (popis ostalih elemenata). Prazan popis označava se praznim uglastim zagradama: "", a popis glave x i repa y piše se pomoću konstruktora popisa: "x: y".

Postoji i prikladniji način za pisanje popisa: navođenjem stavki u uglastim zagradama. Na primjer, popis cijelih brojeva od 1 do 3 mogao bi se napisati ovako:

1: = 1:2: = 1:2:3:

Konstruktor popisa može se koristiti s podudaranjem uzoraka. Ovo će podijeliti popis proslijeđen kao argument na glavu i rep, kojima se može pristupiti putem znakova navedenih u obrascu. Ako je popis prazan, podudaranje u ovoj definiciji neće uspjeti.

Na primjer, možete opisati funkciju preuzimanja glave popisa:

Gornja implementacija funkcije glave ne koristi rep popisa, njezin naziv možete zamijeniti podvlakom:

Na sličan se način može opisati operacija uzimanja repa liste.

Ove dvije funkcije (glava i rep) će izbaciti pogrešku ako im se proslijedi prazan popis, jer podudaranje neće uspjeti.

Razmotrimo još jedan primjer funkcije za rad s listama: funkciju za izračunavanje duljine popisa:

duljina (_: t) = 1 + duljina t

Ako je ulazni popis prazan, tada će prva definicija raditi kao rezultat usporedbe, u suprotnom druga.

Nizovi u Haskellu su popisi znakova. Znakovi se pišu u apostrofima (na primjer, "c"), a nizovi su u navodnicima (na primjer, "string"). Bilo koji niz može biti predstavljen u standardnoj notaciji popisa, na primjer, niz "string" sličan je popisu ["s", "t", "r", "i", "n", "g"] . Rad sa nizovima je isti kao rad s listama.

Stavkama popisa pristupa se uzastopno postupnim odsijecanjem glave i repa. Na primjer, da biste dobili n-ti element liste (počevši od 0), možete napisati funkciju:

dobitiN (x: _) 0 = x

getN (_: t) n = getN t (n-1)

Uzimanje n-tog elementa liste implementirano je u standardnu ​​funkciju "!!". Koristi se ovako:

Ovdje je popis popis, n je broj elementa koji se traži. Stavke se numeriraju počevši od nule. Ako je duljina popisa manja ili manja od broja traženog elementa, izračun ove funkcije će dovesti do pogreške.

Osim toga, moguće je specificirati popise nabrojanih elemenata (na primjer, cijeli brojevi ili simboli) na sljedeći način:

Ovdje je X1 početak aritmetičke progresije, a X2 njen kraj. Na primjer, to je popis. Na taj način se mogu specificirati samo rastuće liste s korakom jednakim jedan. Ako trebate postaviti slijed s drugim korakom, tada možete koristiti sljedeći zapis:

U ovoj varijanti X1 je prvi element niza, X2 je drugi, X3 je mogući posljednji. Korak sekvence je odabran kao X2-X1, a slijed sadrži elemente koji se nalaze samo između X1 i X3. Na primjer, to je popis.

Postoji i način stvaranja popisa na temelju postojećih. Općenito, ova metoda se može napisati na sljedeći način:

[<выражение> | <образец> <- <список>, <ограничение1>, ..., <ограничениеN>]

S određenog popisa odabiru se elementi koji odgovaraju uzorku i zadovoljavaju sva ograničenja, a lista se formira od elemenata izračunatih izrazom koji koristi ovaj uzorak. Na primjer,

[x ^ 2 | x<- ,mod x 3 == 0]

Ovaj izraz konstruira popis kvadrata neparnih brojeva od jedan do 30, djeljivih s 3. Rezultat je:

Osim toga, funkcija mape, definirana u standardnom modulu, vrlo je korisna pri radu s listama. Primjenjuje neku funkciju na zadani popis i vraća popis koji je rezultat primjene ove funkcije na elemente izvornog popisa. Funkcija karte može se implementirati na sljedeći način:

karta :: (a -> b) -> [a] -> [b]

karta f xs =

Odnosno, kao svoj prvi argument uzima funkciju koja pretvara objekte tipa a u objekte tipa b, a kao drugi argument popis elemenata tipa a. Rezultat funkcije mape je popis elemenata tipa b.

Kada koristite funkciju mape, zgodno je koristiti neimenovane funkcije koje su opisane kao λ-izrazi (o čemu se detaljnije govori u odjeljku o funkcijama višeg reda). Na primjer, popis kvadrata brojeva od 1 do 10 može se opisati na sljedeći način:

karta (\ x-> x * x)

Rezultat ove funkcije je popis:

Budući da Haskell ima ugrađenu operaciju eksponencijalnosti, ovaj se popis može dobiti na sljedeći način:

karta (^ 2)

Također, možete koristiti bilo koje druge funkcije, na primjer:

map inc

Razmotrimo nekoliko funkcija definiranih u standardnom modulu za rad s listama.

Naziv funkcije		Opis
		glava (prvi element) popisa
		rep (sve osim prvog elementa) popisa
		posljednji element liste
		svi elementi popisa osim posljednjeg
	[a] → Int → a	element sa zadanim brojem
		izračunavanje duljine liste
	Int → [a] → [a]	uzeti n prvih elemenata s popisa
	Int → [a] → [a]	odbaciti prvih n elemenata s popisa
		proširivanje popisa obrnutim redoslijedom
	(Broj a) => [a] → a	zbroj stavki popisa
	(Broj a) => [a] → a	proizvod stavki popisa
	[a] → [a] → [a]	spajanje popisa

5.7 Lokalne definicije

Haskell je čisti funkcionalni programski jezik, stoga ne može imati globalne varijable, štoviše, uopće nema varijable. Nijedan objekt se ne može promijeniti, samo se novi može dobiti pomoću starog. Funkcijski parametri i lokalne funkcije mogu poslužiti kao neke "zamjene" za varijable.

Postoje dva načina za opisivanje lokalnih funkcija: korištenjem rezervirane riječi gdje i neka... Definiranje lokalnih funkcija s gdje se može koristiti samo u definiciji funkcije. Definirajmo funkciju za izračunavanje aritmetičke sredine tri broja:

prosjek3 x y z = s / 3

Općenito, upotreba where može se napisati ovako:

<имя функции> <аргументы> = <выражение>

<определение 1>

<определение 2>

<определение N>

Sve definicije moraju biti u istom uvlačenju, ali više od retka koji sadrži gdje. Po želji možete koristiti sljedeću sintaksu:

<имя функции> <аргументы> = <выражение>gdje (<определение 1> ; <определение 2> ; ... ; <определение N> }

Drugi način (koristeći let) može se koristiti u bilo kojem izrazu (ne samo pri definiranju funkcija). Za razliku od where, definicije lokalne funkcije moraju biti napisane prije samog izraza. Ponovno napišite prethodni primjer:

prosjek3 x y z =

Općenito, ova metoda izgleda ovako:

<определение 1>

<определение 2>

<определение N>

<выражение>

Sve definicije moraju biti isto uvučene, ali više od retka koji sadrži let. Riječ u mora biti uvučena barem neka. Po želji možete koristiti sljedeću sintaksu:

neka (<определение 1> ; <определение 2> ; ... ; <определение N>) u<выражение>

U ovom slučaju, uvlačenje se zanemaruje.

5.8 Dodatne značajke interaktivnog okruženja

U interaktivnom okruženju GHCi, osim evaluacije funkcija ili izraza, postoje mnoge dodatne značajke. Mnogi od njih dostupni su putem naredbi koje počinju sa znakom ":". Na primjer, pisanjem naredbe ":?" možete vidjeti popis svih ostalih naredbi (auto-dovršavanje također radi po naredbama). Pogledajmo najkorisnije naredbe.

: t - dobiti tip navedenog izraza. Na primjer:

* Glavni>: t obrnuto (rep "mama")

naličje (rep "mama") ::

: i - dobivanje informacija o funkciji (tip, u kojem je modul ili klasa definiran). Na primjer:

* Glavni>: preokrenuti

obrnuto :: [a] -> [a] - Definirano u GHC. Popis

: l - učitati navedeni modul i učiniti ga trenutnim.

: m - učitavanje ili istovar navedenog modula.

: q - zatvori GHCi.

Još jedna korisna značajka je mogućnost definiranja funkcija izravno u GHCi. Za to se koristi pojednostavljena let konstrukcija. Na primjer:

* Glavni> neka je f x = x + 2 * x

Kompletna let konstrukcija vrijedi samo unutar svog izraza:

* Glavni> neka je z = 10 u z + z

: 1: 0: Nije u opsegu: `z"

GHCi izvještava da dano ime nije definirano u trenutnom opsegu.

5.9 Funkcije višeg reda

U Haskellu se funkcije mogu koristiti kao i svaki drugi objekt - mogu se pohraniti u liste i torke, proslijediti drugim funkcijama i vratiti kao rezultat drugih funkcija.

Funkcije koje prihvaćaju ili vraćaju druge funkcije nazivaju se funkcijama višeg reda. Jedna takva funkcija, na primjer, je funkcija mape, koja primjenjuje danu funkciju na sve elemente popisa.

Ispravno ispunite ovaj odjeljak

Razmotrimo funkciju zbrajanja dva broja:

plus x y = x + y

Funkcija plus može se opisati drugačije:

Operacija +, koja je zatvorena u zagradama, funkcija je 2 varijable, stoga, primjenom dva parametra na nju, dobit ćemo njihov zbroj kao rezultat. Ako na ovu funkciju primijenimo samo jedan argument, na primjer, broj 3, dobivamo funkciju jednog argumenta, koji specificira dodavanje ovog argumenta broju 3:

Ovaj proces postupnog dijeljenja funkcija na funkciju koja uzima jedan parametar i funkciju koja vraća drugu funkciju koja izračunava sve ostalo naziva se funkcija currying.

Druga varijanta opisa plus funkcije:

Koristeći funkciju plus (bilo koja od gore navedenih implementacija), može se napisati funkcija povećanja:

inc x = plus 1 x

Koristeći currying, možete dobiti drugu implementaciju iste funkcije:

Ispada da funkcija inc vraća funkciju koja dodaje 1 jednom od svojih parametara.

Osim ovog načina pisanja funkcija u Haskell-u, postoji način korištenja λ-računa.Na primjer, funkcija plus se može implementirati na sljedeći način:

plus = \ x y -> x + y

Ovdje “\” znači početak λ-izraza, zatim su navedeni parametri (x y), a nakon strelice (->) je izraz.

λ-račun se može koristiti za definiranje neimenovanih funkcija. Na primjer, možete koristiti funkciju dodavanja bez posebnog opisivanja:

Ovaj izraz je funkcija. Stoga ćemo, primjenjujući parametre na njega, dobiti rezultat.

(\ x y -> x + y) 3 6

Rezultat će biti broj 9.

Neimenovane funkcije korisne su, na primjer, prilikom prosljeđivanja funkcija kao parametara drugim funkcijama kada ne trebate odgovarajuće stilizirati funkciju.

Ako se bilo koji parametar funkcije ne koristi pri izračunavanju njezine vrijednosti, tada se njezin naziv može izostaviti i zamijeniti ga simbolom "_". Na primjer, funkcija koja vraća prvi parametar od dva mogla bi izgledati ovako:

Ili, u uobičajenom zapisu:

prvo dva x _ = x

5.10 Beskonačne strukture podataka

Haskell je jezik koji nije strog, odnosno koristi takozvanu lijenu (lijenu) evaluaciju. Kao što je gore spomenuto, to znači da se vrednuju samo oni izrazi koji su potrebni za izračunavanje rezultata funkcije. Razmotrimo funkciju definiranu kroz samu sebe:

Očito se njegova vrijednost ne može izračunati. Ako to pokušate učiniti, pojavit će se beskonačna petlja. Razmotrimo još jednu funkciju:

Njegova vrijednost ne ovisi o parametru x. Stoga ga nema potrebe izračunati. I evaluacija izraza

neće uzrokovati beskonačnu petlju i vratit će rezultat jednak 1.

Ovakva lijena evaluacija omogućuje vam organiziranje beskonačnih struktura podataka poput beskonačnih popisa. Jedan od najjednostavnijih načina za stvaranje beskonačnih popisa je korištenje aritmetičkih progresija. Da biste to učinili, ne morate navesti kraj intervala. Na primjer, sljedeće liste su beskonačne:

Postavljaju ih samo prva dva elementa, po kojima se izračunava korak progresije. Ako drugi element progresije nije naveden (kao u prvom primjeru), tada se korak uzima jednakim 1.

Na tim popisima moguće je izvoditi iste operacije i koristiti iste funkcije kao i za obične liste, koje ne zahtijevaju sve elemente popisa za izračunavanje rezultata. Te funkcije uključuju uzimanje glave i repa, funkcije za dobivanje i-tog elementa popisa i tako dalje.

Beskonačni popisi korisni su za neke zadatke. Na primjer, izračun faktorijala može se provesti na sljedeći način:

činjenica n = lista činjenica !! n

lista činjenica = fl 1 1

gdje je fl x n = x: (fl (x * n) (n + 1))

Funkcija za određivanje faktorijala broja n (činjenica n) vraća kao rezultat n-ti element popisa činjenica, koji je beskonačan popis faktorijala svih prirodnih brojeva. Elementi ovog popisa se izračunavaju i zauzimaju memoriju samo kada je potrebno dohvatiti njihove vrijednosti.

Ne samo da popisi mogu biti beskonačni, već i bilo koje druge strukture podataka definirane od strane programera, kao što su stabla.

6 Tipovi podataka i moduli

6.1 Korisnički definirani tipovi i strukture podataka

Kada opisujete tipove funkcija, možda će vam trebati prilagođeni sinonimi za postojeće tipove. Na primjer, uz glomaznu definiciju određenog tipa, zgodno ga je imenovati jednim imenom. Nije baš ugodno svaki put napisati nešto poput [(Integer,)], prikladnije je ovoj vrsti dati ime, na primjer, MyType1. Ova definicija ima oblik:

upišite MyType1 = [(Integer,)]

Ova definicija tipa ne opisuje novu strukturu podataka, već samo daje naziv kombinaciji već postojećih tipova.

Za definiranje vlastite vrste podataka koristi se sljedeći unos:

podaci<имя> = <значение1> | <значение2> | ... | <значениеN>

Dakle, struktura podataka pod nazivom<имя>, što može biti 1, 2 i tako dalje do N. Ove vrijednosti tipa podataka su konstruktori podataka. Svaki konstruktor mora imati jedinstveno ime koje počinje velikim slovom. Naziv konstruktora podataka može biti isti kao i naziv tipa podataka Na primjer, opis tipa podataka "boja" može se predstaviti na sljedeći način:

podaci Boja = Crvena | Zelena | Plava

Osim toga, konstruktor može prihvatiti neke podatke kao funkciju. Na primjer, tip podataka o boji možete nadopuniti dodavanjem prikaza boje u kombinaciji crvene, zelene i plave:

podaci Boja = Crvena | Zelena | Plava | RGB Double Double Double Double

Ova notacija znači da objekti tipa Boja mogu poprimiti vrijednosti crvena, zelena, plava ili RGB r g b, gdje su r g b realni brojevi. Na primjer, možete definirati funkciju koja vraća žuto:

Određivanje tipova podataka može biti polimorfno, baš kao i specificiranje funkcija. Odnosno, možete odrediti tip podataka koji sadrži neki drugi, ali ne i određeni tip. Na primjer, standardni tip Maybe može se opisati na sljedeći način:

podaci Možda a = Ništa | Samo a

To znači da objekt tipa (Možda a) može biti ili Ništa ili Samo x, gdje je x objekt nekog tipa a. Usklađivanje uzoraka koristi se za pristup takvim objektima. Na primjer, možete implementirati funkciju unJust koja će vratiti sadržaj klase kontejnera Maybe ako nije Ništa.

nepravedno (Samo a) = a

Razmotrimo još jedan primjer:

pronađi :: (Eq a) => a -> [a] -> Možda Int

nađi _ = Ništa

| x == a = Samo 0

| inače = slučaj (nađi xs) od

(Samo ja) -> Samo (i + 1)

Ništa -> Ništa

Ova funkcija vraća indeks prvog pojavljivanja objekta koji je proslijeđen kao prvi parametar na popisu koji je proslijeđen kao drugi parametar, ili ništa ako ne postoji. Definicija funkcije koristi klasu Eq, koja ograničava tipove parametara funkcije na usporedive tipove. Nastava će biti obrađena u sljedećem poglavlju.

Bilo koja struktura podataka može se opisati pomoću ključne riječi data. Opišimo binarno stablo kao još jedan primjer:

Stablo podataka a = Nil | Čvor a (Stablo a) (Stablo a)

Ova definicija kaže da stablo s elementima tipa a može biti ili prazno stablo ili se sastojati od elementa tipa a i još 2 stabla, koja su definirana slično.

Opišimo funkciju dodavanja elementa binarnom stablu pretraživanja.

addtotree Nil x = Čvor x Ništa Ništa

addtotree (čvor y lijevo desno) x

| x

| x> y = Čvor y lijevo (dodatno stablo desno x)

| inače = Čvor y lijevo desno

Kada se doda na prazno stablo, rezultat je stablo s jednim čvorom koji sadrži element koji se dodaje. A u slučaju da stablo nije prazno, tada se, ovisno o odnosu dodanog elementa s elementom u korijenu stabla, odabire sljedeća strategija izračuna. Ako je element koji se dodaje manji, onda se mora dodati lijevom podstablu, dakle, rezultat će biti stablo s istim ključem i desnim podstablom, ali s novim lijevim podstablom dobivenim kada je element dodan starom . Ako je dodani element veći od korijena, to će rezultirati stablom s izmijenjenim desnim podstablom. Ako dodani element odgovara korijenskom, rezultat će odgovarati stablu proslijeđenom kao argumentu.

Izlaz stabla na ekranu ćemo organizirati u obliku s izbočinama, definiranjem funkcije pretvaranja njega (stabla) u niz.

showtree tree = showtr tree 0 gdje

showtr (Nil) n = repliciraj n "\ t" ++ "- \ n"

showtr (Čvor x lijevo desno) n =

showtr desno (n + 1) ++

repliciraj n "\ t" ++ prikaži x ++ "\ n" ++

showtr lijevo (n + 1)

Lokalna funkcija showtr uzima dva argumenta, stablo i razinu dubine. Korištena funkcija show je standardna funkcija za nizanje gotovo svih objekata u Haskellu.

Sada, kao rezultat evaluacije izraza

addtotree (addtotree (addtotree (addtotree

(addtotree (addtotree (addtotree Nil

što znači sekvencijalno zbrajanje stabla cijelih brojeva 5, 3, 8, 1, 4, 6, 9, dobivamo neki objekt tipa Tree. Prenoseći ga našoj funkciji showtree, dobivamo nizni prikaz ovog stabla.

Postoji još jedan način definiranja prilagođenih podataka - ključna riječ newtype. Njegova upotreba je gotovo ista kao i podaci, osim jedne stvari: tipovi podataka opisani s newtype imaju samo jedan konstruktor podataka s točno jednim poljem. Ova metoda se koristi za stvaranje nove vrste podataka na temelju postojeće:

novi tip MyInt = MyInt Int

Osim toga, moguće je definirati strukture podataka kao što su zapisi s imenovanim poljima. Korištenje običnih torva ili struktura podataka pri korištenju objekata s velikim brojem različitih svojstava nije uvijek prikladno. Morate zapamtiti redoslijed njihovog slijeda i kretati se samo po njemu ili pokrenuti odgovarajuću funkciju za svako od svojstava. Snimanje s imenovanim poljima automatizira ovaj proces, te omogućuje pristup njegovim elementima kroz nazive, što uvelike pojednostavljuje rad. Njihov opis je sljedeći:

<имя записи> {

<имя поля 1> :: <тип поля 1>,

<имя поля 2> :: <тип поля 2>,

<имя поля N> :: <тип поля N>}

Na primjer:

podaci Čovjek = Čovjek (

visina :: dupla,

Da biste definirali objekt ove vrste, možete napisati:

mike = čovjek (ime = "Mike", visina = 173,4, težina = 81,3)

Da biste promijenili takav objekt, točnije da biste dobili novi, ali s promijenjenim nekim od polja, možete napisati ovako:

john = mike (ime = "John")

6.2 Moduli

Haskell podržava modularno programiranje, odnosno program se može podijeliti u module, a svaki se modul može koristiti u više programa.

Svaki modul bi trebao izgledati ovako:

Ako je izborni dio izostavljen, tada se ovaj modul ne može koristiti iz drugih modula. Naziv modula, kao i tipovi podataka, moraju započeti velikim slovom i također odgovarati nazivu datoteke.

Da biste dobili pristup definicijama (funkcijama, vrstama podataka, klasama) u vanjskim modulima, morate ih opisati na samom početku programa na sljedeći način:

uvoz<модуль1>

uvoz<модульN>

<остальной код>

Nakon toga, sve definicije iz ovih modula postaju dostupne u trenutnom modulu. Ali ako su u trenutnom modulu definirane funkcije ili tipovi podataka koji se po imenu podudaraju s uvezenim, ili ako se funkcije ili tipovi podataka istog imena pojavljuju u različitim dodacima, pojavit će se pogreška. Kako bi se to izbjeglo, potrebno je zabraniti korištenje takvih definicija iz odgovarajućih modula. To se radi na sljedeći način:

uvoz<модуль>skrivanje (<скрываемые определения>)

Osim toga, prilikom opisivanja samog uvezenog modula moguće je kontrolirati pristup definicijama. Da biste to učinili, trebate navesti dostupne definicije u zagradama iza naziva modula:

modul<Имя>(<определения>) gdje<код>

Od svih opisa za vanjske module, bit će dostupni samo oni navedeni u zagradama.

Primjer je program od 3 modula:

-- Prog. hs

modul Prog gdje

uvoz Mod2 skrivanje (modfun)

modul Mod1 (modfun) gdje

modfun = pet * 2

modul Mod2 gdje

Funkcija modfun definirana u Mod1 modulu dostupna je iz Prog modula, ali funkcija pet nije dostupna.

7 Klase i monade

7.1 Klase

Haskell ne podržava objektno orijentiranu paradigmu. Ali se malo razlikuje od uobičajene, prihvaćene u drugim jezicima. Instanca klase je struktura podataka. Svaka klasa pretpostavlja opis nekih funkcija za rad s tipovima podataka, koji su primjerci ove klase.

Za definiranje klase koristi se sljedeći zapis:

razred [(<ограничения>) =>] <имя> <переменная типов>gdje<функции>

Varijabla tipa imenuje tip koji mora biti instanca ove klase. Nakon riječi gdje se nalaze opisi vrsta funkcija, kao i izražavanje nekih od tih funkcija međusobno. Uz pomoć ovih izraza, interpretator će moći definirati dio funkcija same instance klase, ako je naveden drugi dio. Ograničenja su definicija da instanca naše klase također mora biti instanca klasa navedenih ovdje. To je neka vrsta nasljedstva. Razmotrimo primjer:

klasa Eq a gdje

(==), (/ =) :: a -> a -> Bool

x == y = ne (x / = y)

x / = y = ne (x == y)

Klasa Eq je usporediva klasa tipa. Funkcije jednakosti i nejednakosti moraju biti definirane za svaku instancu ove klase. Drugi redak znači da funkcije (==) i (/ =) moraju uzeti dva argumenta tipa a i vratiti objekt tipa Bool, odnosno True ili False.

Sljedeći redovi u definiciji klase govore da ako je funkcija (/ =) definirana, onda je funkcija (==) definirana kroz nju u skladu s tim, i obrnuto. Zahvaljujući tome, programer samo treba definirati funkciju usporedbe za jednakost (ili nejednakost), a tumač će sam definirati drugu funkciju.

Još jedan primjer definicije klase, ali s nasljeđivanjem:

klasa Eq a => MyClass a gdje

myFunc :: [a] -> a -> Int

Kada je klasa definirana, možete deklarirati bilo koju vrstu podataka kao instancu ove klase:

primjer MyClass Double gdje

| x == z = 1 + myFunc xs z

| inače = myFunc xs z

Dakle, standardni tip Double deklariramo kao instancu naše klase MyClass i definiramo funkciju myFunc kao funkciju koja izračunava broj elemenata u prvom argumentu jednak drugom argumentu funkcije.

Nakon što definirate tip kao instancu klase, možete primijeniti opisane funkcije na objekte ovog tipa.

test = myFunc x 2 gdje

Klase se često koriste kada se opisuju funkcije s polimorfnim parametrima. Na primjer, ako trebate opisati funkciju koja koristi operaciju usporedbe za mnoge tipove podataka, morate navesti da njezini parametri koji sudjeluju u usporedbi moraju biti tipa Eq klase, što jamči implementaciju odgovarajuće funkcije.

Kada programer opisuje svoju strukturu podataka, ona ne pripada nijednoj od klasa. Ako je potrebno, programer mora implementirati odgovarajuće funkcije za svoju strukturu i naznačiti njezino članstvo u klasi. Na primjer, prethodno opisana struktura podataka stabla može se deklarirati kao instanca klase Show tako da je tumač može prikazati na ekranu bez pribjegavanja ručnom pozivu funkcije showtree. Da biste to učinili, napišite:

primjer Prikaži a => Prikaži (Stablo a) gdje

Nakon toga, kada interpretator primi rezultat tipa Tree, moći će ga prikazati na ekranu, a također bilo koja druga funkcija može pretvoriti objekt Tree u oblik niza pomoću funkcije show.

Osim toga, postoji još jedan način da se deklarira da tip pripada klasi. Jednostavnije je, ali možda neće uvijek zadovoljiti potrebe programera. Sastoji se od navođenja potrebnih klasa odmah pri deklariranju strukture:

podaci<имя> = <значение1> | <значение2> | ... | <значениеN>izvođenje (<класс1>,<класс2>,...,<классM>)

Ovdje će se potrebne funkcije automatski prikazati ako je moguće. Tako, na primjer, definirajmo naš tip Tree na instance klase Eq tako da se stabla mogu međusobno usporediti.

Stablo podataka a = Nil | Stablo a (Stablo a) (Stablo a)

Sada je moguće uspoređivati ​​stabla s operacijom "==" i omogućuje njihovo korištenje u funkcijama koje to zahtijevaju.

7.2 I/O

O monadama je moguće pisati više

Kao što je već spomenuto, Haskell je čisti funkcionalni programski jezik, odnosno funkcije u njemu ne mogu imati nuspojave, a redoslijed evaluacije funkcija nije definiran. Ali u nekim slučajevima nemoguće je bez toga. Takvi slučajevi uključuju rad s korisnikom, s datotekama, s bazama podataka i tako dalje. Jezik Haskell omogućuje definiranje takvih funkcija pomoću monada - posebnih klasa kontejnera. U učenju Haskell-a "monade se smatraju najtežim dijelom, pa krenimo odmah s primjerima. Objašnjenja nekih stvari bit će izostavljena kako ne bismo zbunili čitatelja. Razmotrimo sljedeći primjer:

putStrLn "Zdravo svijete!"

putStrLn "Zbogom svijete!"

U ovom primjeru, glavna funkcija ima nuspojave - kao rezultat njezine evaluacije, tekst se prikazuje na ekranu, a ona definira redoslijed evaluacije - prvo se na ekranu prikazuje prvi redak, a zatim drugi.

Kada se koristi do notacija, programiranje "nečistih" funkcija pomoću monada svodi se na gotovo poznato imperativno programiranje.

Svaki sljedeći redak mora biti funkcija posebnog tipa – monadičnog tipa. U slučaju rada s I/O, ovo je tip (IO a).

Za rad s naredbenim redom koriste se sljedeće funkcije:

putChar :: Char -> IO izlaz znakova

putStr :: String -> IO izlazni niz

putStrLn :: String -> IO izlaz u red s novim redom

IO a je monadni I/O tip koji u sebi skriva nuspojave. Tip IO String znači da će funkcija vratiti rezultat koji sadrži niz, a IO () znači da funkcija vraća rezultat koji ne sadrži ništa, značenje pozivanja je samo u nuspojavama (na primjer, izlaz). Primjer:

putStrLn "Kako se zoveš?"

Ime<- getLine

Tu dolazi na scenu "zadatak". Po analogiji s imperativnim jezicima, možemo reći da u red

Ime<- getLine

rezultat funkcije getLine dodijeljen je nazivu varijable. Ali, kao što znamo, u Haskellu nema varijabli, pa stoga ni dodjela. U ovom slučaju je stvoren objekt s imenom name čija je vrijednost jednaka rezultatu izračuna funkcije getLine. To jest, ako nakon toga opet pišeš

Ime<- getLine

tada će se stvoriti novi objekt čiji će se naziv preklapati s prethodnim.

Ovako se dohvaćaju rezultati monadskih funkcija. Da bi se "varijable" postavile na ovaj način vrijednostima običnih funkcija, koristi se pojednostavljena oznaka neka:

neka ime = "Ivan"

Grananje računskog procesa provodi se korištenjem istog if then else i slučaja:

putStrLn "Kako se zoveš?"

Ime<- getLine

"GHC" -> putStrLn "Ne! Ja sam GHC!"

_ -> putStrLn ("Bok," ++ ime ++ "!")

Ako bi se grana trebala sastojati od nekoliko funkcija, tada se koristi ključna riječ do:

putStrLn "Kako se zoveš?"

Ime<- getLine

putStrLn "Ne! Ja sam GHC!"

_ -> putStrLn ("Bok," ++ ime ++ "!")

Petlje se izvode pomoću rekurzije, kao što je gore prikazano, ili pomoću posebnih funkcija (također implementiranih rekurzivno). Ove funkcije uključuju funkciju mapM_. Njegov princip rada sličan je funkciji mape za popise - primjenjuje monadičnu funkciju na sve elemente popisa i izvršava ih uzastopno. Primjer:

napišiDigit x = učiniti

putStr "Zbrojke:"

mapM_ writeDigit

8 Primjeri

Navedite razne primjere (stabla pretraživanja, AVL stablo, bilo što)

Zaključak

Zaključak

Popis korištenih izvora

1 http: // ru. wikiknjige. org / wiki / Functional_Programming Basics

2 http: // www. ***** / članak / funcprog / fp. xml

3 Dushkin programiranje u jeziku Haskell - DMK Press, 2007. - 608 str.

4 http: // en. wikiknjige. org / wiki / Haskell / Pattern_matching

5 http: // www. haskell. org / tutorial /

Sintaksa za dva uzastopna identifikatora znači primjenu funkcije foo na njenu traku s argumentima:

U Haskell-u, pozivanje funkcije ne zahtijeva zagrade oko argumenta.

Zagrade se koriste za grupiranje argumenata:

akos (cos pi)

Funkcija višestrukih argumenata:

maksimalno 5 42

Operacija primjene funkcije asocijativna je na lijevo:

(maks. 5) 42

Funkcija max primjenjuje se uzastopno na dva argumenta.
Prevoditelj razumije konstrukciju f x y kako (f x) y, a ne obrnuto f (x y).

Izraz (maks. 5) ovo je takozvana aplikacija djelomične funkcije. Općenito, to se može formulirati na sljedeći način: ako imamo funkciju od N varijabli i gledamo na nju kao funkciju od N varijabli, onda je možemo gledati s druge strane i reći da je to funkcija jedne varijable koji nam vraća funkciju od N - 1 varijable.

3 + grijeh 42

3 + (maks. 5) 42

Sintaksa deklaracije prilagođene funkcije

Funkcija koja zbraja kvadrate dva argumenta koja su joj proslijeđena:

SumSquares x y = x ^ 2 + y ^ 2 rock "n" roll = 42

Naziv funkcije i nazivi formalnih parametara moraju početi malim slovima. I velika slova se koriste za definiranje tipova podataka.

Funkcija s tri argumenta koja izračunava duljinu 3D vektora:

LenVec3 x y z = sqrt (x ^ 2 + y ^ 2 + z ^ 2)

Da bismo definirali funkciju u GHCi interpreteru, moramo koristiti ključnu riječ let.

Neka su kvadrati zbroja x y = x ^ 2 + y ^ 2

Svojstvo čistoće funkcije

Važna karakteristika koja razlikuje funkcionalne jezike od imperativnih jezika je svojstvo čistoće funkcija. Sve funkcije u Haskellu su čiste. To znači da je vrijednost funkcije u potpunosti određena vrijednostima argumenata koji su joj proslijeđeni. Niti jedan drugi izvor podataka ne može utjecati na rezultat koji vraća funkcija. Ako vam je potrebna funkcija za preuzimanje podataka odnekud, onda joj morate proslijediti ovaj izvor podataka kao argument.

Funkcija koja ne uzima argumente je konstanta. Takva funkcija vraća istu vrijednost cijelo vrijeme, bez obzira na sve okolnosti.

Preludij> neka četrdeset dva = 39 + 3 Preludij> četrdeset dva 42

U Haskellu ne možete definirati funkciju koja ne uzima argumente i vraća različite vrijednosti za različite pozive.

Mehanizam za definiranje funkcija pomoću djelomične aplikacije

Na bilo koju funkciju možemo gledati kao na funkciju jednog argumenta koji vraća neku funkciju.

Preludij> neka max5 x = max 5 x Preludij> max5 4 5 Preludij> max5 42 42

Alternativna sintaksa za definiranje funkcije:

Preludij> neka max5 "= max 5 Preludij> max5" 4 5 Preludij> max5 "42 42

Skratili smo dodatni argument x s lijeve i desne strane. I napisali su da je funkcija max5 "samo djelomično primijenjena funkcija max. Dakle, možete definirati funkciju bez navođenja svih argumenata. Odgovarajući stil programiranja naziva se besmislenim.

Često je dizajn funkcija u Haskellu podešen na takav način da je djelomična primjena prikladna;

Preludij> neka ograničenje popusta proc zbroj = ako zbroj> = granica onda zbroj * (100 - proc) / 100 ostalo zbroj Preludij> pusti standardniPopust = popust 1000 5 Preludij> standardni popust 2000 1900,0 Preludij> standardni popust 900 900,0

Granični i proc parametri se rijetko mijenjaju. Parametar zbroja se, međutim, često mijenja. Zapravo, svaki put kada se ova funkcija pozove.

Pretpostavimo da razvijamo sučelje sustava prevođenja za prirodne jezike u Haskellu. Mora sadržavati funkciju prevođenja s parametrima text, languageFrom i languageTo. Kako bi bilo prikladno implementirati sljedeće funkcije:

• prevedi sa španjolskog na ruski,
• prevedi sa engleskog na ruski
• i prevedi na ruski

trebate rasporediti parametre sljedećim redoslijedom: prevedite jezikNa jezikIz teksta.

Upišite operator ->

Da biste napisali tip funkcije, trebate napisati tip njezinog argumenta i tip rezultata ove funkcije. U Haskellu, za opis tipa funkcije, operator -> je binarni operator u kojem je lijevi operand tip argumenta, a desni operand tip rezultata. Strelica je između lijevog i desnog operanda t, k, ovo je infiksni operator.

Preludij>: t not not :: Bool -> Bool Preludij> (&&) False True False Prelude> ((&&) False) True False

Vrsta posljednjeg izraza može se napisati na sljedeći način:
Bool -> (Bool -> Bool)
Operator tipa smatra se desnim asocijativnim. Stoga se Bool -> (Bool -> Bool) može prepisati kao Bool -> Bool -> Bool

Preludij>: t (&&) (&&) :: Bool -> Bool -> Bool

Prisjetimo se funkcije popusta koja je vraćala ukupan iznos kupnje uz mogući popust. Kao parametri proslijeđen je iznos bez zbroja popusta, postotak procene popusta, a popust je naplaćen ako preneseni iznos premašuje prag limita. Svi ovi parametri, kao i povratna vrijednost, mogu se pohraniti u tipu Double. Vrsta funkcije može se navesti u izvornoj datoteci zajedno s njezinom definicijom:

popust :: Dvostruko -> Dvostruko -> Dvostruko -> Dvostruko ograničenje popusta proc zbroj = ako zbroj> = limit onda zbroj * (100 - proc) / 100 ostalo zbroj

Imajte na umu da je deklaracija tipa neobavezna, iako se često preporučuje za potrebe dokumentacije. Obično se stavlja ispred definicije funkcije, iako se ova deklaracija najviše razine može postaviti bilo gdje u datoteci izvornog koda.

Standardni popust :: Dvostruki -> Dvostruki standardniPopust = popust 1000 5

Razmislite o funkciji twoDigits2Int, koja uzima dva znaka i vraća broj sastavljen od tih znakova ako su oba znaka numerički, i 100 u suprotnom. (Prvi znak se tretira kao broj desetica, drugi kao broj jedinica.)

Uvoz podataka.Char twoDigits2Int :: Char -> Char -> Int twoDigits2Int x y = ako jeDigit x && isDigit y onda digitToInt x * 10 + digitToInt y ostalo 100

GHCi> twoDigits2Int "4" "2" 42

Rekurzija

U imperativnim jezicima, petlja je glavni element ponavljajućeg računanja. U funkcionalnim jezicima, petlje nemaju previše smisla. Budući da funkcionalnim jezicima nedostaje koncept promjenjive varijable, ne postoji način da se razlikuje jedna iteracija petlje od druge. Za izvođenje ponavljajućih računanja u funkcionalnim jezicima koristi se rekurzija. Kako bi se spriječilo ponavljanje rekurzivne funkcije, ona mora ispunjavati sljedeće zahtjeve:

• pozivi funkcija na desnoj strani moraju se izvoditi na vrijednosti parametra koji nije formalni parametar funkcije;
• rekurzivni pozivi moraju biti negdje prekinuti (mora postojati tzv. uvjet prekida).

Faktorijel

Faktorijal n = ako je n == 0 onda 1 inače n * faktorijel (n - 1)

Implementacija izračuna faktorijala pomoću akumulirajućeg parametra:

Faktorski5 n | n> = 0 = pomoćnik 1 n | inače = pogreška "arg mora biti> = 0" pomoćnik acc 0 = acc pomoćnik acc n = pomoćnik (acc * n) (n - 1)

Takva implementacija u slučaju faktorijala ne donosi nikakve dodatne koristi, ali vrlo često takve implementacije mogu poboljšati učinkovitost rekurzivnih funkcija. U mnogim slučajevima, u rekurzivnim funkcijama, davanjem izravne definicije rekurzivne funkcije u terminima nje same, može se dobiti kvadratna ili više polinomna asimptotika. A u slučaju korištenja pomoćnih funkcija vrlo je često moguće ispraviti asimptotiku svođenjem na linearnu.

Dvostruki faktorijal

Razmotrimo funkciju koja izračunava dvostruki faktorijel, odnosno umnožak prirodnih brojeva koji ne prelaze zadani broj i imaju isti paritet. Na primjer: 7 !! = 7⋅5⋅3⋅1, 8 !! = 8⋅6⋅4⋅2. Pretpostavlja se da argument funkcije može imati samo nenegativne vrijednosti.

DoubleFact :: Integer -> Integer doubleFact n = ako je n<= 0 then 1 else n * doubleFact (n - 2 )

Fibonaccijev niz brojeva

U Haskellu je ova definicija data sljedećom funkcijom:

Fibonacci :: Integer -> Integer fibonacci n | n == 0 = 0 | n == 1 = 1 | n> 1 = fibonacci (n - 1) + fibonacci (n - 2) | n< 0 = fibonacci (n + 2 ) - fibonacci (n + 1 ) | otherwise = undefined

Implementacija funkcije za izračunavanje Fibonaccijevog broja, temeljena na izravnoj rekurzivnoj definiciji, izrazito je neučinkovita – broj poziva funkcije raste eksponencijalno s povećanjem vrijednosti argumenta. GHCi vam omogućuje praćenje upotrebe memorije i vremena utrošenog na evaluaciju izraza izvršavanjem naredbe: set + s:

* Fibonacci>: set + s * Fibonacci> fibonacci 30 832040 (16,78 sekundi, 409, 318, 904 bajta)

Koristeći mehanizam akumulatora, možete napisati učinkovitiju implementaciju koja ima linearnu složenost (prema broju rekurzivnih poziva):

Fibonacci ":: Integer -> Integer fibonacci" n = pomoćnik n 0 1 pomoćnik n a b | n == 0 = a | n> 0 = pomoćnik (n - 1) b (a + b) | n< 0 = helper (n + 1 ) b (a - b) | otherwise = undefined

Funkcije višeg reda

Funkcija višeg reda je funkcija koja uzima drugu funkciju kao argument. Funkcije višeg reda rijetke su u imperativnim jezicima. Primjer je funkcija sortiranja iz C standardne biblioteke. Kao prvi argument, binarni predikat za usporedbu prosljeđuje se funkciji sortiranja uz pomoć koje se kao drugi argument prosljeđuje niz i sortira. Funkcije višeg reda se vrlo često koriste u funkcionalnim jezicima i u Haskellu.

Preludij>: t ($) ($) :: (a -> b) -> a -> b

To je polimorfni tip. Dolar operator je funkcija dvaju argumenata. Njegov lijevi operand ili prvi argument (a -> b) je funkcija. Njegov desni operand a je proizvoljna vrijednost. Dolar operator jednostavno primjenjuje svoj prvi argument (a -> b) na svoj drugi argument a. Stoga je ovdje potrebno da tipovi budu dosljedni. Tip drugog argumenta dolar operatoru mora odgovarati tipu parametra funkcije koji je proslijeđen u prvom argumentu. Štoviše, rezultat izvršavanja dolar operatora rezultat je funkcije proslijeđene kao prvi argument. Budući da je tip rezultata b, rezultat izjave o dolaru je tip b.

Sljedeća upotreba vrijedi samo kada su a i b isti.

Preludij> neka apply2 fx = f (fx) Preludij>: t apply2 apply2 :: (t -> t) -> t -> t Prelude> apply2 (+ 5) 22 32 Prelude> apply2 (++ "AB") " CD "" CDABAB "

Prvi argument je doista funkcija, ali argument i povratna vrijednost su istog tipa. A drugi argument je vrijednost ovog tipa, a povratna vrijednost je također vrijednost ovog tipa. Stoga se funkcija apply2 može primijeniti na ograničeniji skup funkcija od dolara. Ako je dolar polimorfan u argumentima i povratnoj vrijednosti, onda je apply2 polimorfan u samo jednom parametru.

Funkcija flip iz standardne biblioteke definirana je na sljedeći način: flip f y x = f x y.

Preludij> flip (/) 4 2 0.5 Preludij> (/) 4 2 2.0 Preludij> flip const 5 True True Prelude>: t flip flip :: (a -> b -> c) -> b -> a -> c Preludij>: t flip const flip const :: b -> c -> c

(- Korisna funkcija višeg reda definirana je u modulu Data.Function -) na :: (b -> b -> c) -> (a -> b) -> a -> a -> c na op f x y = f x `op` f y (- Potrebna su četiri argumenta: 1) binarni operator s istim tipom argumenata (tip b), 2) funkcija f :: a -> b koja vraća vrijednost tipa b, 3,4) i dvije vrijednosti tipa a. Funkcija on primjenjuje f dvaput na dvije vrijednosti tipa a i prosljeđuje rezultat binarnom operatoru. Koristeći on, možete, na primjer, napisati funkciju zbrajanja kvadrata argumenata ovako :-) sumSquares = (+) `uključeno` (^ 2) (- Funkcija multSecond, koja množi druge elemente parova, implementirana je na sljedeći način -) multSecond = g `on` h g = (*) h = snd

Anonimne funkcije

U Haskellu, kao i u matematici, funkcije se obično imenuju. Kada trebamo pozvati funkciju, pozivamo je na ime. Međutim, postoji alternativni pristup koji se naziva anonimne funkcije.

Preludij> (\ x -> 2 * x + 7) 10 27 Preludij> neka f "= (\ x -> 2 * x + 7) Preludij> f" 10 27

To je anonimna funkcija ili lambda funkcija.

Postoji sintaktički šećer za pojednostavljenje zapisa.

Preludij> neka lenVec xy = sqrt $ x ^ 2 + y ^ 2 Preludij> neka lenVec x = \ y -> sqrt $ x ^ 2 + y ^ 2 Preludij> neka lenVec = \ x -> \ y -> sqrt $ x ^ 2 + y ^ 2 Preludij> lenVec 3 4 5.0 Preludij> neka lenVec = \ xy -> sqrt $ x ^ 2 + y ^ 2 Preludij> lenVec 3 4 5.0

Anonimne funkcije se koriste kada se koriste funkcije višeg reda.

(- Funkcija on3, ima sličnu semantiku kao on, ali uzima funkciju s tri mjesta kao prvi argument -) on3 :: (b -> b -> b -> c) -> (a -> b) -> a -> a -> a -> c on3 op f x y z = op (f x) (f y) (f z) (- Zbroj kvadrata tri broja može se napisati koristeći on3 ovako -) sum3squares = (\ x y z -> x + y + z) `on3` (^ 2)

Curried i uncurried funkcije

Sa sintaksom za pozivanje funkcija u Haskellu, možete navesti ne sve argumente, već samo dio njih. Prvih nekoliko argumenata funkcije može se navesti, a ostali se mogu odbaciti. Ovu ideju djelomične primjene funkcija izmislio je Haskell Curry i u njegovu čast takve funkcije s argumentima koji se prosljeđuju jedan po jedan nazivaju se curried. U Haskell-u, nisu sve funkcije curried. U Haskell-u možete definirati funkcije na torkama. U ovom slučaju, sintaksa za pozivanje funkcija izgledat će isto kao u običnim jezicima:
naziv_funkcije (prvi_argument, drugi_argument)

Preludij> prvi (1, 2) 1

Currying je postupak za prelazak s funkcija koje se ne koriste u karijerstvu na funkcije koje uzimaju argumente jedan po jedan. Zamislite da imamo funkciju višeg reda, kao što je on kombinator, on očekuje da 2 od svoja 4 argumenta budu funkcija. Prvi argument je funkcija s dva argumenta koja je ispisana. Haskell ima poseban kombinator curryja koji prelazi iz funkcije uncurried u curried funkciju. U sljedećem primjeru, curry pretvara funkciju specificiranu u paru u standardnu ​​curried funkciju od dva argumenta.

* Demo>: t on on :: (b -> b -> c) -> (a -> b) -> a -> a -> c * Demo>: t curry fst `on` (^ 2) curry fst `on` (^ 2) :: Broj b => b -> b -> b

Drugi primjer, funkcija prosječne vrijednosti koja se ne radi:

Prosj. :: (dvostruko, dvostruko) -> duplo prosječno p = (fst p + snd p) / 2

Funkcija curry avg `on` (^ 2) je funkcija koja izračunava prosjek kvadrata dviju vrijednosti koje su joj proslijeđene.

Curry funkcija je:

Preludij> neka cur fxy = f (x, y) Preludij>: t cur cur :: ((t1, t2) -> t) -> t1 -> t2 -> t Preludij>: t curry curry :: ((a , b) -> c) -> a -> b -> c

Kao svoj prvi argument uzima funkciju koja se ne koristi, tj. funkciju preko para, ali je pretvara kao povratnu vrijednost u curried funkciju u kojoj se argumenti prenose uzastopno.

Tu je i obrnuta funkcija bez curryja:

Preludij>: t uncurry uncurry :: (a -> Prelude>: t uncurry (flip const) uncurry (flip const) :: (b, c) -> c Prelude>: t snd snd :: (a, b) - > b

Modul Data.Tuple standardne biblioteke definira funkciju swap :: (a, b) -> (b, a), koja zamjenjuje elemente para:

GHCi> zamjena (1, "A") ("A", 1)

Ova funkcija se može izraziti kao:

Preludij> neka swap = uncurry (okreni (,)) Preludij> zamijeni (1, "A") ("A", 1)

Stroge i labave funkcije

Lijeno ocjenjivanje dovodi do činjenice da je u mnogim situacijama moguće eliminirati nepotpunost programa.

Const42 :: a -> Int const42 = const 42

Funkcija const42 potpuno zanemaruje vrijednost argumenta, stoga, u okviru modela lijenog izračuna, ako joj kao argument proslijedite bilo koji složeni izračun, tada se ovaj izračun nikada neće dogoditi. To znači da se bilo koji program, uključujući program koji se ne završava, može proslijediti kao argument const42.

* Demo> const42 True 42 * Demo> const42 123 42 * Demo> const42 (1 + 3) 42 * Demo> const42 undefined 42

Funkcije poput const42 nazivaju se opuštenim funkcijama. Ako je divergentni izračun proslijeđen funkciji kao argument, a rezultat je neka vrijednost koja nije divergentna, tada se takva funkcija naziva nestrogom. Funkcija se naziva strogom tako da ako joj proslijeđujemo divergentni argument, tada je vrijednost ove funkcije nužno divergentna. Funkcija s dva argumenta može biti stroga ili nestroga za drugi argument, ovisno o vrijednosti prvog argumenta. Analiza ozbiljnosti je potrebna kako bi Haskell program bio vrlo učinkovit.

28. studenog 2013. u 21:48 sati

Bilješke s predavanja "Haskell kao prvi programski jezik". 1. dio

• Haskell,
• Funkcionalno programiranje

• Vodič

Pozdrav Habr! Danas sam izvukao svoje stare bilješke o tečaju "Haskell kao prvi programski jezik" Sergeja Mihajloviča Abramova i pokušat ću što jasnije i na primjerima ispričati o ovom divnom jeziku onima koji ga još nisu upoznati. Priča je namijenjena nespremnom čitatelju. Pa čak i ako ste prvi put čuli riječ Haskell...

Osnovne Haskell vrste

Osnovne vrste jezika Haskell su:
Brojevi
Booleove vrijednosti
Simboli
Popisi
Naručeni skupovi (torke)
Funkcije

Brojevi
cijeli brojevi:
cijeli broj (-∞, ∞)
Int (-2 ^ 31, 2 ^ 31-1)
Definitivno postoji mnogo korisnih funkcija za cijele brojeve u uvodu (standardna biblioteka), uključujući pretvaranje u pomičući zarez (fromInt i fromInteger)

Brojevi s pomičnim zarezom:
Float (7 decimalnih mjesta)
Dvostruko (16 decimalnih mjesta)

Booleove vrijednosti
Bool (točno | netočno)
Operacije konjunkcije, disjunkcije i negacije (&&, ||, ne)

Simboli
znak ('a')
I funkcije Char to Int i Int to Char (ord, chr)

Popisi
Popisi mogu biti različiti:
- popis cijelih brojeva
- popis znakova (niz)
[] - niz
je popis funkcija
itd.

Nekoliko standardnih operacija u primjerima:
Glavna> glava
1
Glavni> rep
Glavna> duljina
2
Glavno> obrnuto
Glavno> 0:
Main> - prompt linija u konzoli ghci kompajlera
":" - operacija pričvršćivanja elementa na popis.

Naručeni setovi
primjeri:
(2.4, "mačka") (Plutanje,)
('A', Istina, 1) (Char, Bool, Int)
(, sqrt) (, Float-> Float)
(1, (2, 3)) (Int, (Int, Int))

Ali, srce Haskell-a i cjelokupnog funkcionalnog programiranja su, naravno, same funkcije!

Funkcije

Funkcija je, u modernoj matematici, korespondentni zakon koji povezuje svaki element x iz zadanog skupa A s jednim (ili nijednim) elementom y iz skupa B.
Haskell je, po svojoj namjeni, prije svega jezik matematičara, pa sintaksa ovdje odgovara što je moguće bliže ovoj definiciji.
Primjer:
kvadrat :: Integer -> Cjelobrojni kvadrat x = x * x
Kao što ste vjerojatno pogodili, ovo je funkcija kvadriranja broja. Analizirajmo ga detaljno:

Prvi red je deklaracija funkcije:
Function_name :: definition_space -> value_space
kvadrat :: Integer -> Integer
Ovdje treba reći da u Haskellu uopće nije potrebno uvijek deklarirati funkciju. U nekim slučajevima, tumač će već razumjeti koje domene i značenja određene funkcije imaju. Međutim, izostavljanje oglasa je loše ponašanje.

Drugi redak je definicija funkcije:
Parametri naziva_funkcije = Pravilo_izračunavanja
kvadrat x = x * x

Funkcija bez parametara nije ništa više od konstante:
e :: Float e = exp 1.0

Funkcija s više parametara:
Hvala na pojašnjenju ().
abcFormula :: Float -> Float -> Float -> abcFormula abc = [(-b + sqrt (b * b-4.0 * a * c)) / (2.0 * a), (-b-sqrt (b * b-) 4,0 * a * c)) / (2,0 * a)] - pronalazi korijene jednadžbe ax ^ 2 + bx + c = 0

Definicije funkcija s alternativama

Kao i svaki jezik, Haskell ima granaste konstrukcije.
Pogledajmo ih koristeći funkciju abs (modul) kao primjer.
Ako… onda… drugo…
abs1 x = ako je x> = 0 onda je x drugo -x

Slučaj… od…
abs2 x = slučaj x> = 0 od Točno -> x Netočno -> -x

No, osim standardnog if i case, Haskell ima vrlo lijepu i najčešće korištenu konstrukciju grananja. tzv. stražarski izrazi... Primjer:
abs3 x | x> 0 = x | x<0 = -x | otherwise = 0
Ravnu liniju treba čitati kao: "at".
Čitamo: „Funkcija abs3, s ulaznim parametrom x, za x> 0 uzima vrijednost x, za x<0 принимает значение -x, и в любом другом случае принимает значение 0».
Naravno, mogli smo sve zapisati i po dva garda izraza, ali ja sam zapisao tri da bi bilo jasno da ih može biti koliko hoćemo.
Inače je u uvodu definirano vrlo jednostavno:
inače :: Bool inače = Istina
Odnosno, možete sa sigurnošću napisati "Točno" umjesto "inače", ali ovo je, opet, loše ponašanje.

Usklađivanje uzoraka

Jedna od najčešćih i najučinkovitijih tehnika u Haskellu je podudaranje uzoraka. Umjesto parametra, funkciju možemo ubaciti u primjer kako bi parametar trebao izgledati. Ako se uzorak pojavi, funkcija se izvršava, ako ne, ide na sljedeći uzorak. Na primjer, definiranje faktorijala kroz rekurziju pomoću obrazaca:
činjenica :: Integer -> Cjelobrojna činjenica 0 = 1 činjenica n = n * činjenica (n-1)
Ista stvar, ali uz pomoć zaštitničkih izraza:
činjenica :: Integer -> Integer fact n | n == 0 = 1 | n> 0 = n * činjenica (n-1)
Postoji vrlo čest obrazac za popis: (x: xs). X - označava prvi element, XS - ostatak liste (osim prvog elementa). ":" - operacija pričvršćivanja elementa na popis. Primjeri iz predigre:
glava :: [a] -> glava (x: _) = x glava = pogreška "Prelude.head: prazan popis" rep :: [a] -> [a] rep (_: xs) = xs rep = pogreška "Preludij.rep: prazan popis"
Funkcija head uzima popis bilo čega [a] kao ulaz i vraća prvi element tog popisa. Funkcija rep uzima popis bilo čega [a] kao ulaz i uklanja prvi element s tog popisa.
"_" - znači da nas ovaj element ne zanima.

Eto, to je sve za danas. Ako bude interesa, u skoroj budućnosti ću napisati nastavak.

Iako ne zadovoljava jedan od vaših velikih kriterija (statički * unos), ja ću se osvrnuti na Python. Evo nekoliko razloga zbog kojih mislim da biste trebali pogledati ovo:

• Za imperativni jezik, ovo je iznenađujuće funkcionalno. Bila je to jedna od stvari koje su me pogodile kad sam za to saznao. Na primjer, pogledajte popise. Ima lambda, prvoklasne značajke i puno funkcionalno inspiriranih kompozicija na iteratorima (karte, nabori, patentni zatvarači...). To vam daje slobodu izbora paradigme koja najbolje odgovara problemu.
• IMHO ovo je, kao i Haskell, lijepo kodirati. Sintaksa je jednostavna i elegantna.
• Ima kulturu koja se usredotočuje na obavljanje stvari na jednostavan način umjesto da se previše usredotočuje na učinkovitost.

Razumijem ako tražite nešto drugo. Logičko programiranje, na primjer, može biti u vašoj ulici, kao i ostali.

* Pretpostavljam da ovdje podrazumijevate statičko tipkanje jer želite deklarirati tipove. Tehnički, Python - to je jako tipiziran jezik jer ne možete proizvoljno interpretirati, recimo, niz kao broj. Zanimljivo je da postoje Python derivati ​​koji omogućuju statičko tipkanje, kao što je Boo.

2018-12-04T00: 00Z

Ako tražite snažan (er) osobni prolog, Merkur je zanimljiv izbor. Radio sam to u prošlosti i svidjela mi se druga perspektiva koju mi ​​je dao. Također ima modificiranost (koji bi parametri trebali biti slobodni / fiksni) i determinizam (koliko rezultata ima?) u sustavu tipova.

Clean je vrlo sličan Haskellu, ali ima jedinstveno tipkanje koje se koristi kao alternativa Monadama (točnije, IO monadi). Jedinstvenost unosa također čini zanimljive stvari za rad s nizovima.

2018-12-11T00: 00Z

Budući da niste naveli nikakva ograničenja osim vlastitih subjektivnih interesa, a naglašavate "nagradu za učenje" (u redu, dobro, zanemarit ću ograničenje statičkog kucanja), predlažem učenje nekoliko jezika različitih paradigmi i po mogućnosti one koje su svakom od njih "uzorne".

• Lipsky dijalekt za podatkovni kod / homokoničnost i zato što su dobri, ako ne i najbolji, primjeri dinamičkih (više ili manje strogih) funkcionalnih programskih jezika
• Prolog kao prevladavajući logički programski jezik
• Čavrljanje kao jedini pravi OOP jezik (također zanimljiv zbog svog obično izrazito orijentiranog pristupa prema slikama)
• Može biti, Erlang ili Clojure, ako vas zanimaju jezici kovani za paralelno / paralelno / distribuirano programiranje
• Naprijed za programiranje usmjereno na stog
• (Haskell za snažno funkcionalno statički tipizirano lijeno programiranje)

Posebno Lisps (CL nije toliko kao Scheme) i Prolog (i Haskell) pokrivaju rekurziju.

Iako nisam guru ni za jedan od ovih jezika, proveo sam neko vrijeme sa svakim od njih osim Erlanga i Forta, i svi su mi pružili otvaranje i zanimljivo iskustvo učenja jer svaki pristupa rješavanju problema iz različitog kuta.

Dakle, iako se može činiti da sam zanemario dio o tome da nemate vremena isprobati više jezika, radije mislim da vrijeme provedeno s bilo kojim od njih neće biti izgubljeno i da biste trebali pogledati sve. ih.

2018-12-18T00: 00Z

U smislu onoga što odgovara vašem smjeru, čini se da je očigledan izbor logičan jezik poput Prologa ili njegovih izvedenica. Logičko programiranje može se izvesti vrlo uredno u funkcionalnom jeziku (pogledajte, na primjer, The Reasoned Schemer), ali možda ćete željeti izravno raditi s logičkom paradigmom.

Interaktivni teorijski sustav dokazivanja poput dvanaest ili coq također može razbuktati vašu maštu.

25.12.2018.00: 00Z

Želio bih proširiti svoje znanje o programiranju. (...) Mislio sam da bih ovdje postavio pitanje, kao i nekoliko stvari o vrsti jezika koji tražim. Neki od njih su subjektivni, neki su namijenjeni olakšavanju prijelaza s Haskell-a.

Sustav jakog tipa. (...) Također olakšava neformalno razmišljanje o ispravnosti mog programa. Brine me ispravnost, a ne učinkovitost.

Naglasak na rekurziji nad iteracijom. (...)

Bojim se da ovdje možete malo olakšati prijelaz. Vrlo strogi sustav tipova i čisto funkcionalni stil uobičajeni su u Haskellu, i gotovo sve što izgleda kao mainstream programski jezik zahtijevat će kompromis u barem jednom od njih. Dakle, imajući to na umu, evo nekoliko širokih prijedloga usmjerenih na očuvanje veći dijelove onoga što vam se sviđa kod Haskell-a, ali s nekim značajnim pomakom.

Zanemarite praktičnost i idite na "više Haskell nego Haskell": Haskellov tipski sustav pun je rupa zbog prekida i drugih neurednih kompromisa. Očistite nered i dodajte moćnije značajke i dobit ćete jezike poput Coq i Agda gdje tip funkcije sadrži dokaz njezine ispravnosti (možete čak pročitati i strelicu funkcije -> kao booleovu implikaciju!). Ovi jezici su korišteni za matematičke dokaze i za programe s iznimno visokim zahtjevima za točnost. Coq je vjerojatno najistaknutiji jezik stila, ali Agda ima više Haskell-y osjećaj (i također je napisan na Haskell-u).

Ne brojite vrste, dodajte još magije: ako je Haskell vještičarenje, Lisp je sirova, iskonska magija stvaranja. Lisp jezici (uključujući Shema i Clojure) imaju gotovo neusporedivu fleksibilnost u kombinaciji s ekstremnim minimalizmom. Jezicima u biti nedostaje sintaksa, pisati kod izravno kao strukturu podataka stabla; Metaprogramiranje u Lisp-u je lakše od nemetaprogramiranja u nekim jezicima.

Kompromitirajte malo i približite se mainstreamu: Haskell spada u široku obitelj jezika koji snažno utječu na ML, od kojih bi bilo koji od njih vjerojatno mogli migrirati bez prevelikih poteškoća. Haskell je jedan od najstrožih kada su u pitanju jamstva ispravnosti tipa i funkcionalnog stila, gdje su drugi često ili hibridni stilovi ili/ili prave pragmatične kompromise iz raznih razloga. Ako želite izložiti OOP i pristup raznim velikim tehnološkim platformama, također Scala na JVM-u, ili F # na .NET-u ima puno zajedničkog s Haskell-om, pružajući jednostavnu kompatibilnost s Java i .NET platformama. F # je izravno podržan od strane Microsofta, ali ima neka neugodna ograničenja u usporedbi s Haskellom i probleme s prenosivosti na platformama koje nisu Windows. Scala ima izravne kolege sustavu tipa Haskell i Javinom potencijalu za više platformi, ali ima težu sintaksu i nedostaje mu moćna podrška treće strane koju ima F #.