Funkcionalno programiranje u Haskell-u

Dio 1. Uvod

Serija sadržaja:

Imperativno programiranje

Najčešće imperativni jezici, u kojem se izračun svodi na sekvencijalno izvršenje instrukcije. Rješenje problema u imperativnom jeziku svodi se na opis 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 Neumann arhitekturi. U njima je značajan dio koda zauzet dodjeljivanjem vrijednosti varijablama.

Varijable smatra se memorijskim ćelijama koje variraju u vremenu. Trenutne vrijednosti varijabli u programu formiraju stanje koje se mijenja.

Primjer imperativnog koda je procedura 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 ciklus. Tokom izračunavanja mijenjaju se vrijednosti varijabli x i n.

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

Funkcionalni jezici referirati na deklarativno- u njima program precizno formulira potreban rezultat proračuna u smislu ovisnosti funkcija jedna o drugoj, i detalje izračuna (na primjer, kako točno vrijednosti treba staviti u memoriju i prenijeti ) padaju na pleća jezičke implementacije.

Funkcije i funkcionalnost

U matematičkom smislu funkcija f: X → Y je pravilo koje odgovara elementu x iz skupa X ( oblasti) element y = f x iz skupa Y ( kodomene).

Važno je da funkcija bude pravilno definirana, tj. ne bi trebalo biti nejasnoća oko njene vrijednosti za svaki argument.

Ako su vrijednosti definirane za sve elemente domene, tada se funkcija poziva svugdje definirana; inače se naziva parcijalnim.

Kao iu matematici, u funkcionalnim jezicima koji nas zanimaju ne postoje ćelije koje pohranjuju razna značenja. Promjenljive su samo imena vrijednosti.

Obično, za definiranje funkcije u funkcionalni jezik koriste se jednadžbe. Na primjer,

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

n- formalni argument fac funkcije. Na desnoj strani nakon što je opisan znak =, šta 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 jednačine. Prilikom izračunavanja funkcije, jednačine se traže po redoslijedu. Ako je n = 0, tada će se koristiti prva jednačina. Ako je n ≠ 0, onda neće raditi, a koristi se drugi.

Imajte na umu da su argumenti funkcije navedeni pored njenog imena, odvojeni razmakom. Ovo je zgodno jer je upotreba funkcije vrlo česta u funkcionalnim programima (tabela 1).

Upis u matematiku	Pisanje na Haskell-u
f(x)	f x
f(x,y)	f x y
f(g(x))	f(gx)
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)

Tabela 1. Primjena funkcije u matematici i Haskell-u

Jednačine za fac čine tačnu definiciju funkcije, a ne niz računskih koraka, kao što je bio slučaj u imperativnom kodu.

Koristi se rekurzija, tj. fac se definiše u terminima za sebe. Ova definicija funkcionira jer se fac izražava u terminima jednostavnijeg slučaja i na kraju (ako je n ≥ 0) dolazi do osnovnog slučaja n = 0. Izračunavanje fac 3 prema ovoj definiciji može se izvršiti na sljedeći način (pojednostavljeni izrazi su podvučeni na svakom korak):

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. U ovom slučaju, 3 se poziva stvarni argument.

Funkcionalni pristup je fokusiran na evaluaciju izraza, a ne na izvršavanje naredbi. U stvari, funkcionalni program je izraz, a njegovo izvršenje odgovara evaluaciji izraza.

Prilikom izračunavanja, prepisujemo izraze, zamjenjujući vrijednosti za varijable i primjenjujući funkcije, dok se ne dobije konačni rezultat.

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

Sada pišemo funkciju koja za cijeli k i realni r izračunava binomni koeficijent

Za k ≥ 0, imamo izraz u kojem je imenilac faktorijel broja k upravo određenog, a brojilac je opadajuća faktorijalna snaga

Napišimo rekurzivnu definiciju za to:

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

Prva jednačina ne koristi r, tako da možete koristiti zamjenu _ i napisati ffp _ 0 = 1 .

To se može potvrditi

(provjeri ovo). Stoga se faktorske jednačine mogu zamijeniti sa

fac n = ffp n n

Nakon što zapišemo jednadžbe za ffp funkciju, možemo je zamisliti kao apstraktnu crnu kutiju sa dva ulaza i jednim izlazom, bez obzira na to što se događa unutra. Sve što nam je sada važno je ispravan prikaz ulaza za izlaz.

Slika 2. Crna kutija izračunava opadajuću faktorijalnu snagu

Uzmite drugu crnu kutiju (/) sa dva ulaza x i y i izlazom jednakim količniku x/y:

izračunao bi ovako:

Slika 3. Šema iz crne kutije, koji izračunava binomni koeficijent

Odgovara izrazu

ffp rk / fac k

Definirajmo traženu funkciju:

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

Takav zapis naziva se jednačina sa uslovima (uporedi sa matematičkom notacijom definicije). Nakon | a ispred znaka = postoje uslovi. "inače" znači "inače". O tome će se detaljno raspravljati u narednim člancima.

Primjer proračuna 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 povezivali crne kutije, mislili smo na to da, prvo, one uvijek daju isti rezultat za iste ulaze i, drugo, ne utiču na rad drugih kutija.

Ovo vodi do važan konceptčistoća.

Čistoća

Kada je pozvan procedure u imperativnom jeziku, često ne samo da mu prenosimo argumente i dobijemo rezultat, već i očekujemo nuspojava- nešto što nije povezano s prevođenjem argumenata u povratnu vrijednost (izlaz podataka u datoteku, promjena globalne varijable, itd.). Nažalost, nuspojave se često javljaju čak i kada nisu predviđene.

Ako funkcija ima nuspojave, onda njeno vrednovanje s istim argumentima u drugom kontekstu može proizvesti različite rezultate.

Ako ima mnogo nuspojava, programiranje postaje komplikovanije, javlja se više grešaka u kodu i postaje teško provjeriti njegovu ispravnost i formalnim i neformalnim sredstvima.

Ovdje nismo proceduru nazvali funkcijom jer, u prisustvu nuspojava, procedura nije kao funkcija u matematičkom smislu (ponekad se takve funkcije nazivaju cisto).

Ako nema nuspojava, izraz se uvijek može zamijeniti njegovom vrijednošću, a program će raditi kao i prije - to se zove transparentnost linkova. Isti izraz mora dati isti rezultat kada se evaluira u bilo koje vrijeme.

Svaki izraz u funkcionalnom jeziku ima svoje značenje; evaluacija samo modificira izraz, ne utječe na vrijednost.

Programiranje bez nuspojava može se u potpunosti sagledati u smislu 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 dozvoljavaju i dodjele i nuspojave.

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

Na prvi pogled može izgledati da je čisto funkcionalni jezik nepraktičan, ali to je daleko od slučaja - uspješno programiranje jednostavno zahtijeva upoznavanje s nekim jednostavnim i elegantnim idejama (i zaboravljanje starih navika).

Lijenost i lijenost

Kada se funkcija pozove po vrijednosti, njeni se argumenti prvo izračunavaju, a zatim se rezultirajuće vrijednosti prosljeđuju tijelu funkcije. Kada se pozivaju iz nužde, argumenti se prosljeđuju bez evaluacije i evaluiraju se u tijelu funkcije samo kada je to potrebno.

To otprilike odgovara onome što se u funkcionalnim jezicima naziva energično i lijeno vrednovanje. U energetskom slučaju se proračunava sve što je moguće, a u lijenom sve što je potrebno. (Odložit ćemo formalni pristup ovom pitanju dok ne saznamo koji model računanja leži u osnovi funkcionalnih jezika.)

Za funkciju se kaže da je stroga u odnosu na jedan od svojih argumenata ako uvijek zahtijeva svoju vrijednost da bi proizvela rezultat. Ako vrijednost nije uvijek potrebna, onda se kaže da funkcija nije stroga u odnosu na taj argument.

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

U skladu s tim, govori se o jezicima sa strogom semantikom i o jezicima sa nestrogom semantikom. („Lijenost“ i „lijenost“ nisu isti, već bliski pojmovi.)

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

Na jeziku koji nije strog, proračun se vrši po potrebi. Ako f nije striktno, onda se evaluacija f e može prekinuti čak i ako se evaluacija e ne završi.

Na primjer,

označava listu od tri elementa. Proračun fac (-1) petlji. To znači da će se izračunavanje liste također napraviti petlju.

Sada neka funkcija dužine vrati dužinu liste. Izraz

dužina

neće biti evaluirani u strogom jeziku, ali u jeziku koji nije strog rezultat će biti 3, jer njihove vrijednosti nisu potrebne za brojanje elemenata.

Primjeri nestriktnih jezika: Miranda i Haskell. Strogi jezici - ML i Scheme.

Pitanje strogosti je dovoljno suptilno da se ne može svesti na jednostavno “Šta je zgodnije i efikasnije?” >Prenošenje odgođenih kalkulacija umjesto vrijednosti tijekom poziva funkcije ima cijenu. Međutim, u mnogim situacijama, lijenost vam omogućava da uštedite na proračunima ili zapišete takve izraze koji se ne bi evaluirali ili bi se računali neograničeno na energičnim jezikom.

Labavost je nezavisna karakteristika čistoće, iako mnogo 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 sa funkcionalnim stilom bili su LISP (1958), APL (1964), ISWIM (1966) i (1977).

Do kraja 1980-ih već je postojalo mnogo funkcionalnih jezika. Među onima koje su imale značajan uticaj na Haskell su:

• (1973) je prvi jezik sa Hindley-Milnerovim kucanjem.
• SASL, KRC, Miranda (1972–1985) su neki od prvih lijenih jezika.
• Hope (1980) je jedan od prvih jezika sa algebarskim tipovima podataka. Haskell je razvila velika grupa istraživača od 1987. Nazvan je po Haskell Curryju.

Glavni zadatak na koji je dizajn bio fokusiran - Haskell je morao prikupiti dostupna dostignuća u oblasti nestriktnih čisto funkcionalnih jezika.

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

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

Haskell je postao najpopularniji nestrogi čisto funkcionalni jezik. Postoji mnogo složenih projekata implementiranih u Haskell-u:

• Kompajleri i drugi razvojni alati.
• Distribuirani sistem kontrole verzija Darcs.
• Menadžer prozora xmonad.
• HAppS Web Application Server.
• Pugs interpretator/kompajler za Perl 6.
• Kućni operativni sistem.
• Jezik opisa Lava hardvera.
• LOLITA sistem za obradu prirodnog jezika.
• Sistemi dokaza ekvinocija/paradoksa i Agda teorema.

Glavni izvori informacija o Haskell-u

Haskell ima široku i prijateljsku zajednicu.

Glavni izvor informacija je server haskell.org.

• [email protected]- slobodna diskusija.
• [email protected]– više jednostavne teme za početnike.

  Postoji veoma živahan #haskell IRC kanal na irc.freenode.net. U njemu možete brzo dobiti ljubazan odgovor na gotovo svako pitanje.

  Mnogo tematskih blogova ide na http://planet.haskell.org/

• Dobar uvod u Haskell bi bio Nježan uvod u Haskell 98.
• Za opsežnu bibliotečku dokumentaciju pogledajte http://haskell.org/ghc/docs/latest/html/libraries/
• Formalni izvještaj je Haskell 98 izvještaj.

Uređivanje i pokretanje koda

Haskell implementacije

Formalno, Haskell nema nijednu "standardnu" implementaciju.

Za interaktivni rad prikladan je lagani Hugs tumač.

Takođe imaju zanimljiv projekat Yhc kompajliranje izvorni kod u bajtkod, i Helium, varijanta Haskell-a prilagođena početnicima (na primjer, stvaranje jasnijih poruka o grešci). Međutim, oni su još uvijek u razvoju.

GHC kompajler/interpretator je postao de facto standard. Najnapredniji je, zadovoljava standarde u svemu i nudi niz eksperimentalnih proširenja. Fokusiraćemo se na to.

GHC se može preuzeti sa http://haskell.org/ghc/. Ako koristite GNU/Linux, pogledajte verzije u vašoj distribuciji. Za MacOS X i Windows takođe možete pronaći binarne datoteke. (Imajte na umu da izgradnja GHC-a direktno iz izvora može biti prilično zamorna.)

Prije svega će nas zanimati interaktivni ghci program, u kojem je zgodno testirati primjere obuke.

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

Ovdje Prelude je naziv učitanog modula. Prelude sadrži osnovne definicije i uvijek je omogućen prema zadanim postavkama. Samim proučavanjem ili prepisivanjem koda Prelude, početnici mogu mnogo naučiti. (I ti i ja ćemo to djelomično učiniti.)

Simbol > znači da ghci čeka na korisnički unos. To mogu biti Haskell izrazi, kao i komande za interpretator.

Koristite tastere ← i → da pomerite kursor oko ghci komandne linije. i ↓ skrolujte kroz istoriju komandi napred i nazad.

Umjesto Prelude> ili drugih naziva modula, nastavićemo da pišemo ghci> (ako želite da uradite isto, pokrenite komandu 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 oni koji su prihvaćeni na drugim jezicima (tabela 2).

Tabela 2. Aritmetički operatori iz Prelude

Oni koriste infiksnu notaciju i odgovarajući prioritet. Na primjer, 2*3+4 odgovara (2*3)+4, dok 2^3^4 odgovara 2^(3^4) . Zagrade se mogu koristiti za promjenu prihvaćenog prioriteta.

ghci ima posebnu varijablu it , koja je jednaka vrijednosti posljednjeg uspješno procijenjenog izraza.

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

Uređivanje izvornog koda

Izvorni kod se može uređivati ​​u svom omiljenom uređivač teksta. Imajući to u vidu, lepo je imati isticanje Haskell sintakse, kao i podršku za poravnanje koda (kao što ćemo videti, to igra posebnu ulogu u Haskelu).

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

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

Haskell kod koristi ekstenziju datoteke .hs.

Ako napišete Haskell kod u foo.hs, onda se definicije učitavaju u ghci naredbom: load foo. Paralelno, fajl se može uređivati ​​i, ako je potrebno, ponovo učitavati definicije sa :reload .

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

Možete preuzeti izvorni kod koji prati ovaj članak i procijeniti izraze:

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

Ove i druge komande se mogu skraćeno - umjesto: load koristiti: l , umjesto: reload -: r i tako dalje.

Popis naredbi interpretatora izlazi pomoću:help. Da biste napustili ghci, otkucajte :quit .

U toku našeg izlaganja često ćemo se susresti s jednostavnim primjerima koji se sastoje od jedne ili dvije jednačine. Mogu se uneti direktno u ghci sa let :

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

Ako postoji nekoliko jednadžbi, onda one moraju biti zatvorene u vitičaste zagrade i odvojene točkom i zarezom (u jednom od sljedećih članaka detaljno ćemo razmotriti takav zapis).

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

Zaključak

Pregledali smo u uopšteno govoreći karakteristike funkcionalnog pristupa, istorija Haskell-a, glavni izvori informacija o jeziku i softveru koji nam je potreban u budućnosti. U sljedećim člancima naučit ćemo tipove i osnovnu sintaksu Haskell-a.

Funkcionalno programiranje
Haskell

Bilješke sa predavanja

Rybinsk 2010

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

1 Istorija funkcionalnog programiranja.................................................. ........................ 4

2 Karakteristike funkcionalnih jezika.................................................. ......................................... pet

2.1 Glavne karakteristike ................................................................ ................................................................ ....... pet

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

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

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

4 Osnovni principi Haskell jezika................................................ ........................................ 16

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

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

4.3 Tipovi funkcija ................................................. ................................................................ ............ 22

4.4 Uslovni proračuni (grananje) ........................................ ................................ 24

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

4.6 Liste ................................................................ ................................................... ........ 29

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

4.8 Dodatne karakteristike 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 Prilagođeni tipovi i strukture podataka.................................................. 40

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

6 Klase i monade.................................................. ........................................................ ... ... 47

6.1 Časovi.................................................................. ................................................ ... ... 47

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

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

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

Spisak korišćenih izvora .............................................................. .................................................... 55

Uvod

Prije nego što direktno opišemo funkcionalno programiranje, okrenimo se istoriji programiranja općenito. 1940-ih pojavili su se prvi digitalni računari koji su se programirali prebacivanjem raznih vrsta prekidača, žica i dugmadi. Broj takvih prebacivanja dostigao je nekoliko stotina i rastao je sa usložnjavanjem programa. Stoga je sljedeći korak u razvoju programiranja bilo 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 je mnemotehnika još uvijek bila previše složena, a svaki asembler je bio čvrsto povezan s arhitekturom na kojoj je izveden. Sljedeći korak nakon asemblera bili su takozvani imperativni jezici visokog nivoa: BASIC, Pascal, C, Ada i drugi, uključujući objektno orijentisane. Takvi jezici se nazivaju imperativnim ("preskriptivnim") jer su fokusirani 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, kamen temeljac je funkcija. Matematičke funkcije izražavaju odnos između ulaznih podataka i konačnog proizvoda nekog procesa. Proces proračuna takođe ima ulaz i izlaz, tako da je funkcija sasvim prikladno i adekvatno sredstvo za opisivanje izračunavanja. To je ovaj jednostavan princip koji je u osnovi funkcionalne paradigme i funkcionalnog stila programiranja. Funkcionalni program je skup definicija funkcija. Funkcije se definiraju u terminima drugih funkcija ili rekurzivno u terminima samih sebe. U funkcionalnom jeziku, programer samo treba da opiše željeni rezultat kao sistem funkcija.

2 Istorija funkcionalnog programiranja

Kao što znate, teorijske osnove 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 godina. Među programerima matematičkih osnova funkcionalnog programiranja su Moses Sheinfinkel i Haskell Curry, koji su razvili kombinatornu logiku, kao i Alonzo Church, tvorac λ-računa (lambda račun).

Teorija je ostala teorija sve dok ranih 1950-ih John McCarthy nije razvio Lisp jezik, koji je postao prvi skoro funkcionalni programski jezik i ostao jedini dugi niz godina. Lisp je i dalje u upotrebi, nakon mnogo godina evolucije, zadovoljava savremene potrebe.

Sa sve većom složenošću softvera, kucanje igra sve važniju ulogu. Krajem 70-ih i ranih 80-ih godina XX vijeka intenzivno su se razvijali modeli kucanja pogodni za funkcionalne jezike. Većina ovih modela uključivala je podršku za tako moćne mehanizme kao što su apstrakcija podataka i polimorfizam. Pojavljuju se mnogi funkcionalni jezici kucanja: ML, Scheme, Hope, Miranda, Clean i mnogi drugi. Osim toga, broj dijalekata se stalno povećava. Gotovo svaka funkcionalna programska grupa koristila je svoj jezik. To je spriječilo dalje širenje ovih jezika i izazvalo mnoge manje probleme. Kako bi ispravila situaciju, zajednička grupa vodećih istraživača u oblasti funkcionalnog programiranja odlučila je da ponovo stvori vrline raznim jezicima na novom univerzalnom funkcionalnom jeziku. Prva implementacija ovog jezika, nazvana Haskell po Haskell Curryju, nastala je ranih 90-ih.

3 Karakteristike funkcionalnih jezika

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

3.1 Osnovna svojstva

Među svojstvima funkcionalnih jezika obično se izdvajaju sljedeće:

- kratkoća i jednostavnost;

– jako kucanje;

– funkcije su vrijednosti;

– čistoća (bez nuspojava);

– odložena (lijena) računanja;

- modularnost.

Razmotrimo svako od ovih svojstava detaljnije.

Kratkoća i jednostavnost

Programi na funkcionalnim jezicima obično su kraći i jednostavniji od istih programa na imperativnim jezicima. Jedan od najčešćih primjera je Hoareovo brzo sortiranje.

U imperativu C, brzo sortiranje se 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 (i<= j);

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

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

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

qsort(x:xs) = qsort

++ [x] ++ qsort

Ovaj primjer treba čitati ovako: ako je lista koju treba sortirati prazna, tada će rezultat sortiranja također biti prazna lista, u suprotnom, glava i rep liste (prvi element liste i lista preostalih elemenata , moguće prazno), a rezultat će biti spajanje (spajanje) sortirane liste svih repnih elemenata manje od glave, liste same glave i liste svih repnih elemenata većih ili jednakih glavi.

Kod u funkcionalnom jeziku pobjeđuje u pogledu veličine koda i vidljivosti. Dodatno, gornja C implementacija sortira niz čiji su elementi cjelobrojnog tipa (int), dok Haskell implementacija može sortirati liste elemenata bilo kojeg tipa na kojima je definirana operacija poređenja.

Jako kucanje

Većina funkcionalnih programskih jezika je snažno otkucana. Jako kucanje podrazumijeva sljedeće preduslove:

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

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

– svaka operacija zahtijeva argumente strogo definiranih tipova;

– implicitna konverzija tipa nije dozvoljena (to jest, kompajler percipira svaki pokušaj korištenja vrijednosti drugog tipa koja je deklarirana za varijablu, argument, funkciju ili operaciju kao grešku).

U teoriji programiranja, snažno kucanje je nezamjenjiv element u osiguravanju pouzdanosti razvijenog softvera. Kada se koristi ispravno (što znači da program deklarira i koristi odvojene tipove podataka za logički nekompatibilne vrijednosti), štiti programera od jednostavnih, ali teško dostupnih grešaka povezanih s dijeljenjem logički nekompatibilnih vrijednosti, koje ponekad proizlaze jednostavno iz jednostavne greške u kucanju. Takve greške se otkrivaju čak i u fazi kompilacije programa, dok se uz mogućnost implicitne konverzije gotovo svih tipova jedne u druge (kao, na primjer, u klasičnom jeziku C), ove greške otkrivaju samo tokom testiranja, a ne sve njih i to ne odmah.

Funkcionira kao vrijednosti

U funkcionalnim programskim jezicima, funkcije se mogu koristiti kao bilo koji drugi objekt, mogu se proslijediti drugim funkcijama kao argumenti, vraćeni kao rezultat drugih funkcija, pohranjeni u listama i drugim strukturama podataka. Funkcije koje uzimaju kao argumente ili vraćaju kao rezultate druge funkcije nazivaju se funkcijama višeg reda.

Upotreba funkcija višeg reda omogućava vam da kreirate fleksibilnije funkcije, čime se povećava mogućnost ponovne upotrebe koda. Kao primjer, obično se daje prosljeđivanje funkcije poređenja elemenata funkciji sortiranja.

Čistoća

Čistoća leži u odsustvu nuspojava pri izračunavanju vrijednosti funkcije. Nuspojava funkcije je mogućnost čitanja i mijenjanja vrijednosti globalnih varijabli, obavljanja ulaznih/izlaznih operacija, odgovaranja na iznimke, mijenjanja vrijednosti ulaznih varijabli u procesu izračunavanja svojih proračuna. Stoga, ako se takva funkcija dvaput pozove s istim skupom vrijednosti ulaznih argumenata, rezultati proračuna se mogu razlikovati, a stanje nekih globalnih objekata (na primjer, vrijednosti varijabli) se također može promijeniti. Takve funkcije se nazivaju nedeterminističke funkcije sa nuspojavama.

U čistom funkcionalnom programiranju, ista funkcija sa istim argumentima uvijek vraća isti rezultat. Kreirani objekti se ne mogu mijenjati ili uništavati, možete kreirati samo nove na osnovu postojećih. Zahvaljujući čistoći, programi ne samo da postaju jasniji, već je i organizacija paralelizma u njima pojednostavljena, jer 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 zavisnost podataka između dvije čiste funkcije, onda možete promijeniti redoslijed njihove evaluacije ili ih izračunati paralelno. U tom slučaju, prevodilac može koristiti bilo koju politiku evaluacije. Ovo prevodiocu daje slobodu da kombinuje i refaktoriše evaluaciju izraza u programu.

Lazy evaluation

U tradicionalnim jezicima, prije nego što se funkcija pozove, procjenjuju se vrijednosti svih njenih argumenata. Ova metoda pozivanja funkcija naziva se "poziv po vrijednosti". Ako se neki od argumenata ne koriste, onda su proračuni napravljeni uzalud. Mnogi funkcionalni jezici koriste različite metode pozivanja funkcija - "poziv po potrebi". U ovom slučaju, svaki argument funkcije se izračunava samo ako je njegova vrijednost neophodna za izračunavanje rezultata funkcije. Na primjer, C++ operator konjunkcije (&&) ne zahtijeva procjenu vrijednosti drugog argumenta ako je prvi netačan.

Lazy evaluacija u nekim slučajevima vam omogućava da ubrzate izvršavanje programa, a također vam omogućava da koristite različite beskonačne strukture podataka.

Modularnost

Mehanizam modularnosti omogućava vam da podijelite programe na nekoliko relativno nezavisnih dijelova (ili modula) sa dobro definiranim vezama između njih. Ovo olakšava proces projektovanja i naknadne podrške velikih softverskih sistema. Podrška za modularnost nije svojstvo funkcionalnih programskih jezika, ali je podržava većina njih.

3.2 Prednosti

Funkcionalni programski jezici imaju niz prednosti u odnosu na imperativne jezike. Upotreba paradigme funkcionalnog programiranja povećava pouzdanost programa, brzinu njihovog pisanja, pogodnost jediničnog testiranja, mogućnost optimizacije tokom kompilacije i mogućnost automatske organizacije paralelizma.

Pouzdanost programiranja

Odsustvo nuspojava onemogućava mnoge greške koje je teško pronaći, kao što je slučajno dodjeljivanje pogrešne vrijednosti globalnoj varijabli. Strogo statičko kucanje omogućava vam da uhvatite veliki broj grešaka u fazi kompilacije povezanih s netačnim korištenjem nekih podataka.

Zanimljiva karakteristika funkcionalnih jezika je da su podložni matematičkoj analizi. Budući da je funkcionalni jezik samo implementacija formalnog sistema, sve matematičke operacije koje bi se mogle obaviti na papiru važe i za programe napisane na takvom jeziku. Na primjer, kompajler može pretvoriti isječke koda u ekvivalentne, ali efikasnije isječke tako što će matematički dokazati da su isječci ekvivalentni. Štaviše, možete koristiti ove tehnike da dokažete da su određeni dijelovi vašeg programa ispravni.

Pogodnost testiranja jedinica

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

Stoga je moguće testirati svaku funkciju u programu jednostavnim procjenom iz različitih skupova vrijednosti argumenata. U ovom slučaju, ne morate brinuti o pozivanju funkcija u ispravnom redoslijedu, 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 nije potrebno u funkcionalnim programima

Opcije optimizacije

Opis programa u obliku skupa funkcija bez eksplicitne naznake redoslijeda njihovog izračunavanja 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 proračuna. Pošto je odsustvo nuspojava zagarantovano, u bilo kom pozivu funkcije uvek je dozvoljeno paralelno vrednovati dva različita argumenta - redosled kojim se vrednuju ne može uticati na rezultat poziva.

Dokaz svojstava funkcija

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

3.3 Nedostaci

Nedostaci funkcionalnog programiranja proizlaze iz istih karakteristika. Nedostatak dodjela i njihova zamjena generiranjem novih podataka dovodi do potrebe za stalnom dodjelom i automatskim oslobađanjem memorije, stoga visoko efikasan sakupljač smeća postaje nezaobilazna komponenta u sistemu izvršavanja funkcionalnog programa. Da bi sakupljanje smeća bilo efikasno, moraju se pratiti reference na podatke, što takođe zahteva vreme i memoriju. Odsustvo petlji za industrijske programe je prilično ozbiljno ograničenje, budući da mnogi algoritmi zahtijevaju vrlo duge ili čak formalno beskonačne petlje, koje su neefikasne ili čak nemoguće predstaviti u rekurzivnom obliku zbog prevelike potrebne dubine rekurzije. U određenoj mjeri, posljednji nedostatak može se zaobići automatskom konverzijom rekurzije u petlju, koju izvode neki prevodioci funkcionalnih jezika za konkretan slučaj repne rekurzije, ali ne dozvoljavaju svi oblici rekurzije takvu konverziju (međutim, oni koji nisu podložni takvoj konverziji ne mogu biti dizajnirani kao jednostavan ciklus i na imperativnim jezicima).

Da bi se prevladali ovi nedostaci, mnogi funkcionalni jezici uključuju imperativne programske alate koji vam omogućavaju da eksplicitno postavite redoslijed akcija, koristite petlje i koristite 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 porodice jezika:

Razmotrite karakteristike svakog od ovih jezika:

– Lisp. Ime je dobio po engleskom LIST Processing - obrada liste. Lisp je jedan od najranijih funkcionalnih programskih jezika. Programi i podaci u Lisp-u su predstavljeni sistemima linearnih lista simbola. Lisp jezik je, zajedno sa jezikom Ada, prošao kroz proces fundamentalne standardizacije za vojnu i industrijsku upotrebu, što je rezultiralo Common Lisp standardom. Njegove implementacije postoje za većinu platformi. Lispova prva upotreba bila je u simboličkoj obradi podataka i donošenju odluka. Najpopularniji dijalekt Common Lisp-a danas je univerzalni programski jezik. Široko se koristi u raznim projektima: Internet serveri i servisi, serveri aplikacija i klijenti koji komuniciraju sa bazama podataka, naučni proračuni i programi za igre.

– Haskell. To je jedan od najčešćih lijenih programskih jezika. Ima veoma napredan sistem kucanja. U poslednje vreme se širi skup primenjenih biblioteka, jezik se integriše u uobičajene softverske sisteme, što jezik čini sve privlačnijim profesionalnim programerima. Glavne karakteristike jezika: mogućnost upotrebe lambda apstrakcije; funkcije višeg reda; djelomična primjena; nedopustivost nuspojava (čistoća jezika); lijena evaluacija; usklađivanje uzoraka, funkcionalni uzorci (podudaranje uzoraka); parametarski polimorfizam i polimorfizam klase tipa; statičko kucanje; automatsko zaključivanje tipa (zasnovano na Hindley-Milner modelu kucanja); algebarski tipovi podataka; tipovi podataka sa parametrima; rekurzivni tipovi podataka; apstraktni tipovi podataka (enkapsulacija); uključenja liste (razumijevanja liste); čuvarski izrazi (čuvari); sposobnost pisanja programa sa nuspojavama bez kršenja paradigme funkcionalnog programiranja pomoću monada; mogućnost integracije sa programima implementiranim na imperativnim programskim jezicima kroz otvorena sučelja (standardna ekstenzija jezika sučelja stranih funkcija).

– ML(Meta Language) je porodica strogih funkcionalnih programskih jezika sa razvijenim sistemom polimorfnih tipova i modulima koji se mogu parametrirati. ML se predaje na mnogim zapadnim univerzitetima. Jezik jakog tipa sa statičkom provjerom tipa i aplikativnim izvršavanjem programa. Glavne prednosti ML-a su visoka provjerljivost programa, lakoća otklanjanja grešaka, potencijal za visoku optimizaciju i jedinstvena kratkoća pisanja. Glavni nedostaci su složenost sintakse, neobičnost usvojenih sporazuma i ograničenja, praktična nemogućnost makrotransformacija.

– Erlang- funkcionalni programski jezik koji vam omogućava da pišete programe za različite vrste distribuiranih sistema. Razvio i održava Ericsson. Jezik uključuje sredstva za generisanje paralelnih procesa i njihovu komunikaciju slanjem asinhronih poruka. Program se prevodi u bajt kod koji može izvršiti virtuelna mašina, što osigurava prenosivost. Glavna stvar kod Erlanga je njegov lagani procesni model. Da parafraziramo Erlangov slogan "Sve je objekt" ("Sve je objekt"), možemo reći "Sve je proces" ("Sve je proces"). Procesi su jeftini, kreiranje procesa ne zahtijeva više resursa nego pozivanje funkcije. Jedini način da procesi komuniciraju je kroz asinkrono slanje poruka.

Od ovih jezika, Haskell je najistaknutiji predstavnik funkcionalnih programskih jezika. Ima jednostavnu sintaksu i sve gore navedene karakteristike funkcionalnih jezika.

5 Osnovni principi Haskell jezika

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

Prvo razmislite o potrebnim alatima za rad. Najčešći i najefikasniji kompajler danas je GHC(Glasgow Haskell kompajler). Distribuira se pod otvorenom licencom i svako može preuzeti njegove izvorne kodove ili kompajliranu verziju za popularne operativne sisteme sa službene web stranice http://haskell. org/ghc/ (takođe pogledajte http://haskell.org/ za više informacija o jeziku).

Pored samog kompajlera, GHC uključuje GHCi (GHC interaktivno) interaktivno okruženje, Haskell interpreter koji vam omogućava da procenite sve izraze i interpretirate pisane programe.

Nažalost, potpuno funkcionalno Haskell razvojno okruženje još nije razvijeno (osim možda Leksaha, Haskell razvojnog okruženja napisanog na Haskell-u i nekoliko dodataka za Visual Studio i Eclipse), ali često samo napredni uređivač teksta (na primjer, Notepad++, gedit, kate) sa isticanjem sintakse i nekim drugim karakteristikama.

5.1 Interaktivno okruženje

Interaktivno okruženje GHCi može procijeniti bilo koji Haskell izraz. Razmotrite osnove rada sa 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 sa liste svih programa). Nakon pokretanja, na konzoli će se pojaviti prompt:

Prelude znači naziv trenutnog modula, po defaultu, standardni Prelude modul se učitava, 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 prikazalo ga u novom redu. Pokušajmo složenije izračunati izraz:

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

Eksponencijacija (^) je standardni operator definisan u standardnom modulu Prelude zajedno sa sabiranjem i množenjem.

Osim aritmetičkih izraza, u interaktivnom okruženju moguće je izračunati bilo koje druge funkcije definirane u standardnom modulu, ili bilo koje druge koje učitava korisnik.

Da bi se izračunala vrijednost funkcije, upisuje se njeno ime i specificiraju se argumenti, razdvojeni razmacima. Na primjer, standardni modul definira max funkciju, koja bira maksimalnu vrijednost iz dva argumenta. Možete ga koristiti ovako:

Preludij > max 7 100

IN ovaj primjer računa se maksimalno dva broja - sedam i sto. Kao što vidimo, rezultat proračuna funkcije je broj 100.

Argumenti funkcije mogu biti bilo koji izraz (ali samo odgovarajućeg tipa; tipovi se detaljnije razmatraju u drugim odjeljcima), na primjer:

Preludij> max (2^^3)

Ovaj primjer utvrđuje da je dva na deseti stepen veće od deset na treći. Imajte na umu da su zagrade oko argumenata potrebne da bi se razlikovalo koji dio izraza je argument. Na primjer, ako izostavimo zagrade drugog argumenta, dobićemo pomalo neočekivan rezultat:

Preludij > max (2^10) 10^3

Bez zagrada dati izraz interpretirano kao maksimum 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", onda će GHCi dovršiti naziv funkcije na "maximum". U slučaju da ga nije moguće nedvosmisleno dovršiti (postoji nekoliko odgovarajućih opcija), tada se prikazuju sve moguće opcije:

maxBound maksimum

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

Dovršavanje je vrlo korisno kada se koristi mnogo funkcija s dugim imenima.

5.2 Struktura programa

Haskell prevodioci i prevodioci rade sa datotekama sa ekstenzijom *.hs, koji sadrži tekst programa. Tekst programa ima sledeć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 Prelude modul, koji sadrži većinu standardnih funkcija i tipova podataka; naziv modula je po defaultu postavljen na Glavni).

Najjednostavnija funkcija možda uopće ne uzima argumente, već samo vraća neku vrijednost. U ovom slučaju, definicija se sastoji od imena funkcije, znaka jednakosti "=" i nekog izraza pomoću kojeg će se izračunati vrijednost ove funkcije. U poznatim terminima, takva funkcija se 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 pod nazivom pet, koji ima vrijednost jednaku cijelom broju 5. Imena u Haskell-u su osjetljiva na velika i mala slova, to jest, Five i pet su razna imena. Osim toga, uvodi se dodatno ograničenje na prvo slovo imena - imena funkcija i njihovi argumenti mogu početi samo s mala slova(pet, max, min, x, y), a nazivi tipova podataka (Bool, Integer, Double), modula (Main, Test) i klasa (Eq, Ord, Num) su samo velikim slovima.

Pogledajmo kompliciraniji primjer:

tri = jedan + dva

Ovdje su deklarirana tri znaka - jedan, dva, tri. Kao što možete vidjeti iz primjera, svaka definicija zauzima jedan red i odvojene su samo krajem reda (prazne linije će biti zanemarene). Simboli jedan i dva su definisani na isti način kao i simbol pet u prethodnom primjeru, a pri definiranju simbola tri koriste se 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 isti kao i prethodni:

tri = jedan + dva

Učitajmo naš primjer u GHCi interaktivno okruženje. Da biste to učinili, dovoljno je navesti ime datoteke sa tekstom programa kao parametar komandne linije prilikom pokretanja ghci-a (na primjer, Test. hs) (u Windows porodici dovoljno je samo otvoriti instaliranu datoteku od GHC-a automatski dodeljuje ghci za otvaranje * .hs fajlova). Ako program ne sadrži greške, tada ćemo vidjeti poznatu prompt:

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

Mogući su i složeniji izrazi:

*Glavno> (tri+dva)^2

*Glavno> maksimalno jedan dva

Zatim razmotrite funkcije s argumentima. Za razliku od konvencionalnih programskih jezika, prosljeđivanje argumenata ne zahtijeva da ih pišete u zagradama i odvojite ih zarezima. Funkcija se poziva u sljedećem obliku: func x1 x2 x3… xN, gdje je func ime funkcije, a xi je i-ti argument. Rezultat funkcije će biti neki objekat, na primjer, broj, lista, funkcija, lambda izraz ili bilo koja druga struktura podataka.

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

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

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

Prevođenje glavnog (test. hs, interpretirano)

Ok, moduli učitani: Glavni.

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

*Glavno> plus jedan 8

Još jedan primjer funkcije s argumentima:

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

Komentari u jednom redu u Haskell-u počinju s dvije crtice:

plus x y = x+y -- funkcija sabiranja

Blok komentar počinje sa “” i završava sa “”:

ova funkcija vraća broj veći od 1

nego primljeno kao argument

5.3 Tipovi 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 kompajleri jezika Haskell implementiraju moćan mehanizam zaključivanja tipa. Tip funkcija (i njihovi argumenti) se u većini slučajeva može zaključiti iz definicija tih funkcija. Neke funkcije mogu imati polimorfne tipove (takve funkcije se mogu primijeniti na argumente različitih tipova), kao što je prethodno prikazano plus funkcija može zbrajati cijele i realne brojeve.

Kao što je ranije spomenuto, imena tipova počinju velikim slovima. Evo nekoliko standardnih tipova:

	Opis
	cijeli broj od - do
	dugi cijeli broj, bez granica (ugrađena duga aritmetika)
	pravi broj
	realni broj dvostruke preciznosti
	lista elemenata nekog tipa a, na primjer, lista cijelih brojeva se piše kao
	string (ili lista znakova), ekvivalent
	boolean tip (uzima vrijednosti True ili False)
	skup od dva elementa tipa a i b (na primjer, (String, Bool))
	skup od tri elementa tipa a, b i c (na primjer, (String, Bool, Int))

Ako programer želi sam specificirati tip funkcije i njene argumente, ili automatska dedukcija tipa ove funkcije nije moguća, onda mora napraviti dodatnu definiciju koristeći operator specifikacije tipa “::”. Na primjer, da opišete funkciju koja vraća stvarnu vrijednost, možete napisati sljedeći kod:

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

inc::Integer -> Integer

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

Ako funkcija ima dva argumenta, njen opis izgleda ovako:

power::Double -> Integer -> Double

Funkcija snage uzima dva argumenta - realnu bazu x i cijeli broj stepena n, a rezultat evaluacije funkcije je realan broj.

Općenito, opis tipa funkcije izgleda ovako:

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

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

Kao što je ranije spomenuto, specificiranje tipova je opciono, ali njegovo prisustvo može pružiti dodatnu kontrolu nad ispravnošću konstruiranih izraza u deklaraciji funkcije. Također, u nekim slučajevima gdje se koriste polimorfni tipovi, nije moguće odrediti tip funkcije bez eksplicitnog specificiranja tipa.

Nabrojimo neke standardne funkcije.

Funkcije	Opis
	tradicionalne aritmetičke operacije
	dijeljenje realnih brojeva
	dizanje broja na pozitivni cijeli broj
	podizanje broja na pravi stepen
	cjelobrojna podjela i ostatak cjelobrojnog dijeljenja
	Kvadratni korijen
	trigonometrijske funkcije
asin, akos, atan	inverzne trigonometrijske funkcije
	poređenje za jednakost i nejednakost
>, <, >=, <=	poređenje
	logičke operacije
	prvi element para (dvostruka)
	drugi element para
	rep (svi elementi osim prvog) liste

5.4 Uslovni proračuni (grananje)

U tradicionalnim programskim jezicima, glavni načini za organizovanje grananja su uslovna izjava (ako onda drugačije) i naredba izbora (case or switch). Pored njih, Haskell koristi podudaranje uzoraka u definicijama funkcija i takozvanim guard izrazima. Pogledajmo detaljnije svaku od ovih metoda.

ako-onda-drugo konstrukcija

Konstrukcija sintakse "ako-onda-else" omogućava procjenu različitih izraza ovisno o rezultatima nekog uvjeta:

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

Evo<условие>- neki izraz tipa Bool. Za razliku od imperativnih jezika, u Haskell-u je konstrukcija "ako-onda-drugo" izraz koji nužno mora imati rezultat. U tom smislu, grana else je obavezna i vrste izraza<выражение1>I<выражение2>mora 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 netačno onda 1 drugo 0

*Glavno> (ako je istina onda 1 drugo 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 nakon riječi "else" odnosi se na izraz grane else.

konstrukcija kućišta

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

fib n = slučaj n od

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

Baš kao uslovni izraz Naredba slučaja "ako-onda-drugo" ima rezultat i stoga može biti dio drugih izjava.

Razmotrimo padežni izraz u opštem obliku:

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

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

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

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

Evo rezultata proračuna<выражение0>uzastopno upoređivan sa uzorcima. Kada se uspješno uporedi sa i-ti uzorak, rezultat cijelog slučaja će biti rezultat i-tog izraza. Usklađivanje uzoraka će biti detaljnije razmotreno u odgovarajućem odjeljku, ali se za sada može smatrati poređenjem sa datim konstantama.

Imajte na umu da svaki uzorak mora biti napisan u novom redu, uvučenom više od uvlake rezerviranog velikog slova riječi. Takođe, uvlake ispred uzoraka treba da budu jednake jedna drugoj.

Također, koristimo alternativni način za pisanje izraza velikih i malih slova 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 vizualna. Uglavnom:

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

Definicije funkcija

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

Razmotrimo, kao primjer, funkciju za izračunavanje Fibonačijevog broja.

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

Kada se funkcija evaluira, njen pojedinačni argument se upoređuje s njenim definicijskim obrascima od vrha do dna. Ako je argument bio broj 2, onda bi prvo podudaranje bilo neuspješno, a drugo bi uspjelo, što rezultira da će funkcija 1. uzeti vrijednost proslijeđenog argumenta), a izračunat će se zbir dva prethodna Fibonačijeva broja.

Ako se odgovarajuća funkcija ne pronađe među definicijama funkcije, tada će se pojaviti greška i program će se zaustaviti.

stražarski izrazi

Posljednji način odabira alternativa prilikom izračunavanja 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 biti jednom uvučeni. Prilikom izračunavanja vrijednosti funkcije, svi uvjeti koji su izrazi tipa Bool sortiraju se od vrha do dna. Kada se pronađe i-ti uslov, čiji je rezultat Tačan, procjenjuje se izraz i čiji će rezultat biti rezultat funkcije.

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

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

Ovdje je inače uvjet za koji se zna da je istinit i uvijek je jednak Tačan.

5.5 Usklađivanje uzoraka

Usklađivanje uzoraka je zgodan način da se različiti dijelovi neke vrijednosti povezuju sa datim imenima (znakovima). Uparivanje uzoraka se koristi u definicijama i u izrazima.

Prilikom definiranja funkcija, u argumentima dolazi do podudaranja uzorka. U najjednostavnijem slučaju, kada su argumenti dati samo imenima, argumenti su u potpunosti povezani s tim imenima. Na primjer:

f x = fst x + snd x

Ova funkcija izračunava zbir elemenata tuple. Standardne funkcije fst i snd dobijaju prvi i drugi element torke, respektivno.

*Glavno> f(2,4)

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

Kada se ova funkcija procijeni iz (2,4), elementi ovog tuple-a će se upariti sa obrascem navedenim u definiciji funkcije, to jest, znak "a" će uzeti vrijednost 2, a znak "b" će uzeti vrijednost 4.

Tako 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 obrasca (ili cijeli argument) ne koristi, nema potrebe za navođenjem naziva ovog dijela (ili argumenta) - umjesto imena dovoljno je navesti donju crtu "_ ". Redefinirajmo ove funkcije:

Koristeći ovu notaciju, ne morate smišljati imena za nepotrebne dijelove uzoraka, a kada se čita definicija funkcije, odmah postaje jasno da se ovaj dio argumenta ne koristi.

Uzorci mogu specificirati bilo koji konstruktor (u prethodnom primjeru korišten je konstruktor tuple), kao što su lista, tuple ili bilo koji konstruktor tipa podataka koji je definirao korisnik, kao i specifične vrijednosti argumenata (kao u primjeru o Fibonaccijevim brojevima ). U nekim slučajevima, podudaranje može propasti, u kom slučaju se pokušava koristiti sljedeće podudaranje (iz sljedeće definicije ili obrasca padeža). Razmotrimo primjer:

f _ 0 = greška "podjela na nulu"

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

Ovdje će, prilikom evaluacije funkcije f, drugi argument biti jednak 0, tada će se prva definicija odabrati za procjenu funkcije, u suprotnom druga, pošto je poređenje sa imenom uvijek uspješno. funkcija greške zaustavlja izvršavanje programa sa datim tekstom greš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

*** Izuzetak: deljenje sa nulom

Osim toga, svaki obrazac se može imenovati tako da se strukturiranom argumentu može pristupiti i element po element i kao cjelina. Operator @ se koristi za imenovanje uzorka. Prethodi mu ime preko kojeg se argumentu može pristupiti u cjelini, a zatim i sam obrazac. Na primjer,

func1 [email protected](a, b) = a + b + func2p

func2 (a, b) = a*b

5.6 Liste

Lista je jedna od najvažnijih struktura podataka, koja se sastoji od elemenata istog tipa. Lista ne može sadržavati heterogene elemente (za razliku od tuples). Uglaste zagrade se koriste za opisivanje tipa liste. Na primjer, je opis tipa liste elemenata booleovog tipa.

Liste se kreiraju pomoću konstruktora liste - operacije ":". Lista može biti prazna ili se sastojati od glave (prvi element liste) i repa (lista ostalih elemenata). Prazna lista je označena praznim uglastim zagradama: "", a lista koja se sastoji od glave x i repa y piše se pomoću konstruktora liste: "x:y".

Postoji i pogodniji način za pisanje lista: navođenje elemenata u uglastim zagradama. Na primjer, lista cijelih brojeva od 1 do 3 može se napisati ovako:

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

Konstruktor liste može se koristiti za usklađivanje uzoraka. Sa ovim poređenjem, lista koja je proslijeđena kao argument je podijeljena na glavu i rep, kojima se može pristupiti preko znakova navedenih u obrascu. Ako je lista prazna, onda se podudara ovu definicijuće biti neuspješno.

Na primjer, može se opisati funkcija za preuzimanje glave liste:

U gornjoj implementaciji funkcije glave, rep liste se ne koristi, njegovo ime možete zamijeniti donjom crtom:

Operacija preuzimanja repa liste može se opisati slično.

Ove dvije funkcije (glava i rep) će izbaciti grešku kada im se proslijede prazna lista, jer utakmica neće uspjeti.

Razmotrimo još jedan primjer funkcije za rad sa listama: funkciju za izračunavanje dužine liste:

dužina(_:t) = 1 + dužina

Ako je ulazna lista prazna, tada će prva definicija raditi kao rezultat poređenja, u suprotnom će raditi druga.

Stringovi u Haskell-u su liste znakova. Znakovi se pišu u apostrofima (na primjer, "c"), a nizovi se pišu u navodnicima (na primjer, "string"). Bilo koji niz može biti predstavljen u standardnoj notaciji za liste, na primjer, niz "string" je sličan listi ["s","t","r","i","n","g"] . Stringovi rade na isti način kao i liste.

Pristup elementima liste vrši se uzastopno postupnim odsijecanjem glave i repa. Na primjer, dobiti n-ti element listu (počevši od 0), možete napisati funkciju:

getN (x:_) 0 = x

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

Uzimanje n-tog elementa liste implementirano je u standardnoj funkciji "!!". Koristi se ovako:

Ovdje lista je lista, n je broj traženog elementa. Numerisanje elemenata počinje od nule. Ako je dužina liste manja ili jednaka broju elementa koji se traži, evaluacija ove funkcije će rezultirati greškom.

Također je moguće specificirati liste nabrojanih elemenata (na primjer, cijeli brojevi ili znakovi) na sljedeći način:

Ovdje je X1 početak aritmetičke progresije, a X2 njen kraj. Na primjer, je lista. Na ovaj način se mogu specificirati samo rastuće liste sa korakom jednakim jedan. Ako trebate navesti niz s drugim korakom, možete koristiti sljedeću notaciju:

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

Postoji i način da se definišu liste na osnovu postojećih. Općenito, ova metoda se može napisati na sljedeći način:

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

Sa određene liste biraju se elementi koji odgovaraju uzorku i zadovoljavaju sva ograničenja, a lista se formira od elemenata evaluiranih izrazom koji koristi ovaj obrazac. Na primjer,

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

Ovaj izraz konstruira listu kvadrata neparnih brojeva od jedan do 30 koji su djeljivi sa 3. Rezultat je:

Također vrlo korisna pri radu sa listama je funkcija mape definirana u standardnom modulu. Primjenjuje neku funkciju na datu listu i vraća listu dobivenu kao rezultat primjene ove funkcije na elemente originalne liste. Funkcija mape se može implementirati na sljedeći način:

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

mapf xs =

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

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

mapa(\x->x*x)

Rezultat ove funkcije je lista:

Budući da Haskell ima ugrađeni operator eksponencije, ova lista se može dobiti na sljedeći način:

mapa(^2)

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

map inc

Razmotrimo nekoliko funkcija definisanih u standardnom modulu za rad sa listama.

Naziv funkcije		Opis
		glava (prvi element) liste
		rep (sve osim prvog elementa) liste
		posljednji element lista
		svi elementi liste osim posljednjeg
	[a] → Int → a	element sa datim brojem
		izračunavanje dužine liste
	int → [a] → [a]	uzeti prvih n elemenata sa liste
	int → [a] → [a]	odbaciti prvih n elemenata sa liste
		preokrenuti listu
	(Broj a) => [a] → a	zbir elemenata liste
	(Broj a) => [a] → a	proizvod elemenata liste
	[a] → [a] → [a]	spajanje liste

5.7 Lokalne definicije

Haskell je čisti funkcionalni programski jezik, stoga ne može imati globalne varijable, u stvari, uopće nema varijable. Nijedan objekat se ne može promijeniti, samo se novi može dobiti pomoću starog. Parametri funkcije i lokalne funkcije mogu poslužiti kao neka “zamjena” 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 gdje se može napisati ovako:

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

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

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

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

Sve definicije moraju biti na istom uvlačenju, ali veće od reda koji sadrži gdje. Opciono 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. Prepišimo prethodni primjer:

prosjek3 x y z =

Općenito, ova metoda izgleda ovako:

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

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

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

<выражение>

Sve definicije moraju biti na istom uvlačenju, ali veće od reda koji sadrži let. Riječ in mora biti uvučena ne manje nego neka. Opciono možete koristiti sljedeću sintaksu:

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

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

5.8 Dodatne karakteristike interaktivnog okruženja

U interaktivnom okruženju GHCi, pored evaluacije funkcija ili izraza, postoji mnogo dodatne funkcije. Mnogi od njih su dostupni putem naredbi koje počinju znakom ":". Na primjer, pisanjem naredbe ":?" možete vidjeti listu svih ostalih naredbi (autodovršavanje također radi za komande). Razmotrimo najkorisnije naredbe.

:t - dobivanje tipa specificiranog izraza. Na primjer:

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

revers (rep "mama") ::

:i - dobijanje informacija o funkciji (tip, u kojem modulu ili klasi je definisana). Na primjer:

*Glavno> :i obrnuto

revers:: [a] -> [a] -- Definirano u GHC. Lista

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

:m - učitava ili isprazni navedeni modul.

:q - zatvori GHCi.

Još jedna korisna karakteristika je mogućnost definiranja definicija funkcija direktno u GHCi. Za to se koristi pojednostavljena let konstrukcija. Na primjer:

*Glavno> neka f x = x+2*x

Konstrukt full let radi samo unutar svog izraza:

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

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

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

5.9 Funkcije višeg reda

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

Funkcije koje prihvataju ili vraćaju druge funkcije nazivaju se funkcijama višeg reda. Jedna takva funkcija, na primjer, je funkcija mape, koja koristi datu funkciju na sve elemente liste.

Ispravno popunite ovaj odjeljak.

Razmotrimo funkciju sabiranja dva broja:

plus x y = x + y

Funkcija plus može se opisati drugačije:

Operacija +, koja je zatvorena u zagradama, je funkcija 2 varijable, dakle, primjenom dva parametra na nju, kao rezultat dobijamo njihov zbir. Ako se na ovu funkciju primjenjuje samo jedan argument, na primjer, broj 3, dobijamo funkciju jednog argumenta, koji specificira dodavanje ovog argumenta broju 3:

Ovaj proces postupnog dijeljenja funkcija u funkciju koja uzima jedan parametar i funkciju koja vraća drugu funkciju koja procjenjuje sve ostalo naziva se funkcija currying.

Druga verzija opisa plus funkcije:

Koristeći funkciju plus (bilo koju implementaciju iznad), možete napisati funkciju povećanja:

inc x = plus 1 x

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

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

Pored ovog načina pisanja funkcija u Haskell-u, postoji način da se one podese pomoću λ-računa.Na primjer, funkcija plus se može implementirati na sljedeći način:

plus = \x y -> x+y

Ovdje “\” označava početak λ-izraza, zatim se navode parametri (x y), a nakon strelice (->) dolazi 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, primjenom parametara na njega, dobivamo rezultat.

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

Rezultat će biti broj 9.

Anonimne funkcije su korisne, na primjer, prilikom prosljeđivanja funkcija kao parametara drugim funkcijama kada ne trebate formatirati funkciju u skladu s tim.

Ako se bilo koji parametar funkcije ne koristi pri izračunavanju njegove vrijednosti, tada se njegovo ime može izostaviti, zamjenjujući ga simbolom “_”. Na primjer, funkcija koja vraća prvi od dva parametra može izgledati ovako:

Ili, u normalnoj notaciji:

firstoftwox_=x

5.10 Beskonačne strukture podataka

Haskell se odnosi na jezike koji nisu strogi, odnosno koristi takozvanu odloženu (lijenu) evaluaciju. Kao što je gore pomenuto, to znači da se vrednuju samo oni izrazi koji su neophodni za izračunavanje rezultata funkcije. Razmotrimo funkciju definiranu u terminima za sebe:

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

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

neće ponavljati i vratit će rezultat jednak 1.

Takva lijena evaluacija vam omogućava da organizirate beskonačne strukture podataka, kao što su beskonačne liste. Jedan od mnogih jednostavne načine zadaci beskonačnih lista su zadaci aritmetičkih progresija. Za ovo 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 pretpostavlja da je korak 1.

Na ovim listama moguće je izvršiti iste operacije i primijeniti iste funkcije kao i za obične liste, koje ne zahtijevaju sve elemente liste za izračunavanje rezultata. Ove funkcije uključuju uzimanje glave i repa, dobijanje i-tog elementa liste i tako dalje.

Beskonačne liste su korisne za neke probleme. Na primjer, faktorski proračun se može implementirati 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-tog element liste činjenica, koji je beskonačna lista faktorijala svih prirodni brojevi. Elementi ove liste se izračunavaju i zauzimaju memoriju samo kada su potrebne njihove vrijednosti.

Ne samo da liste mogu biti beskonačne, već i bilo koje druge strukture podataka koje definiše programer, 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 već postojeće tipove. Na primjer, uz glomaznu definiciju određenog tipa, zgodno je nazvati ga jednim imenom. Nije baš lijepo svaki put napisati nešto poput [(Integer,)], zgodnije je ovom tipu dati ime, na primjer, MyType1. Takva definicija izgleda ovako:

tip MyType1 = [(Integer,)]

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

Sljedeća notacija se koristi za definiranje prilagođenog tipa podataka:

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

Dakle, struktura podataka pod nazivom<имя>, koji može uzeti vrijednost 1, vrijednost 2 i tako dalje do vrijednosti N. Ove vrijednosti tipa podataka su konstruktori podataka. Svaki konstruktor mora imati jedinstveno ime koje počinje sa veliko slovo. Ime konstruktora podataka može biti isto kao i ime tipa podataka. Na primjer, opis tipa podataka boje 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, možete povećati tip podataka o boji dodavanjem prikaza boje u kombinacijama 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:

Specificiranje tipova podataka može biti polimorfno, baš kao i specificiranje funkcija. To jest, možete postaviti tip podataka koji sadrži neki drugi, ali ne i određeni tip. Na primjer, standardni tip Možda se može opisati ovako:

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. Uparivanje uzoraka se koristi za pristup takvim objektima. Na primjer, možete implementirati funkciju unJust, koja će vratiti sadržaj klase kontejnera Maybe ako nije jednaka Nothing.

nepravedno (Samo a) = a

Razmotrimo još jedan primjer:

find:: (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 listi proslijeđen kao drugi argument, ili ništa ako ga nema. Definicija funkcije koristi klasu Eq, koja ograničava tipove parametara funkcije na uporedive tipove. O nastavi će biti riječi u sljedećem poglavlju.

Ključna riječ data može se koristiti za opisivanje bilo koje strukture podataka. Opišimo binarno stablo kao još jedan primjer:

Stablo podataka a = Ništa | Čvor a (Stablo a) (Stablo a)

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

Hajde da opišemo funkciju dodavanja elementa binarnom stablu pretraživanja.

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

addtotree (čvor y lijevo desno) x

|x

|x>y = Čvor y lijevo (addtotree desno x)

|inače = čvor y lijevo desno

Kada se doda na prazno stablo, rezultat je stablo sa jednim čvorom koji sadrži element koji se dodaje. A u slučaju da stablo nije prazno, u zavisnosti od odnosa dodanog elementa sa elementom u korenu stabla, bira se strategija naknadnog izračunavanja. Ako je element koji se dodaje manji, onda se mora dodati lijevom podstablu, pa će rezultat biti stablo sa istim ključem i desnim podstablom, ali sa novim lijevim podstablom dobijenim dodavanjem elementa starom. Ako je dodani element veći od korijenskog elementa, to će rezultirati stablom sa promijenjenim desnim podstablom. Ako dodani element odgovara korijenskom elementu, tada će rezultat odgovarati stablu proslijeđenom kao argument.

Organizirajmo prikaz stabla na ekranu u obliku sa ivicama, definirajući funkciju pretvaranja stabla u niz.

showtree stablo = showtr drvo 0 gdje

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

showtr(Čvor x lijevo desno) n =

showtr desno (n+1) ++

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

showtr lijevo (n+1)

Lokalna funkcija showtr uzima dva argumenta, stablo i nivo dubine. Funkcija show koja se koristi je standardna funkcija za nizanje gotovo svih objekata u Haskell-u.

Sada, kao rezultat evaluacije izraza

addtotree(addtotree(addtotree(addtotree

(addtotree (addtotree (addtotree Nil

što znači uzastopnim dodavanjem celih brojeva 5, 3, 8, 1, 4, 6, 9 stablu, dobijamo neki objekat tipa Tree. Prenoseći ga našoj funkciji showtree, dobijamo string reprezentaciju ovog stabla.

Postoji još jedan način definiranja korisničkih podataka - ključna riječ newtype. Njegova upotreba je skoro ista kao i data, osim jedne stvari: tipovi podataka opisani sa newtype imaju samo jedan konstruktor podataka sa tačno jednim poljem. Ova metoda se koristi za kreiranje novog tipa podataka na osnovu postojećeg:

newtype MyInt = MyInt Int

Osim toga, moguće je definirati strukture podataka kao što su zapisi sa imenovanim poljima. Upotreba običnih tuple-a ili struktura podataka kada se koriste objekti s velikim brojem različitih svojstava nije uvijek zgodna. Morate zapamtiti redoslijed njihovog niza i kretati se samo po njemu ili pokrenuti odgovarajuću funkciju za svako od svojstava. Imenovani zapis polja vam omogućava da automatizujete ovaj proces, i omogućava pristup njegovim elementima preko imena, što uveliko pojednostavljuje rad. Njihov opis je sljedeći:

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

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

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

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

Na primjer:

dataHuman = Human(

visina::dvostruka,

Za postavljanje objekta ovog tipa može se napisati:

mike = Čovjek(name="Mike",visina=173.4,weight=81.3)

Da biste promijenili takav objekt, tačnije, da biste dobili novi, ali sa promijenjenim nekim poljima, možete napisati ovako:

john = mike(name="John")

6.2 Moduli

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

Svaki modul bi trebao izgledati ovako:

Ako je opcijski dio izostavljen, onda se ovaj modul ne može koristiti iz drugih modula. Ime modula, kao i tipovi podataka, moraju početi velikim slovom, a također moraju odgovarati imenu datoteke.

Da biste dobili pristup definicijama (funkcijama, tipovima podataka, klasama) u eksternim modulima, potrebno ih je deklarirati 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 trenutni modul definira funkcije ili tipove podataka koji imaju isto ime kao uvezeni, ili ako različiti dodaci sadrže funkcije ili tipove podataka istog imena, tada će se pojaviti greška. Da 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, kada se opisuje sam uvezeni modul, moguće je kontrolisati pristup definicijama. Da biste to učinili, navedite dostupne definicije u zagradama iza naziva modula:

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

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

Primjer je program sa 3 modula:

-- Prog. hs

modul Prog gdje

uvoz Mod2 sakrivanje (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 podržava objektno orijentisanu paradigmu. Ali malo se razlikuje od uobičajene usvojene u drugim jezicima. Instanca klase je struktura podataka. Svaka klasa pretpostavlja opis nekih funkcija za rad sa tipovima podataka koji su instance ove klasa.

Sljedeća notacija se koristi za definiranje klase:

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

Varijabla tipa imenuje tip, koji mora biti instanca ove klase. Nakon riječi gdje su opisi tipova funkcija, kao i izraz nekih od ovih funkcija jedne kroz druge. Sa ovim izrazima, interpretator će moći definirati dio funkcija same instance klase, ako je dat drugi dio. Ograničenja su definicija da instanca naše klase također mora biti instanca klasa navedenih ovdje. To je kao nasledstvo. Razmotrimo primjer:

klasa Eq a gdje

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

x == y = nije (x/=y)

x /= y = nije (x==y)

Klasa Eq je klasa uporedivih tipova. Za svaku instancu ove klase, funkcije jednakosti i nejednakosti moraju biti definirane. Drugi red znači da funkcije (==) i (/=) moraju uzeti dva argumenta tipa a i vratiti objekat tipa Bool, tj. Tačno ili Netačno.

Sljedeći redovi u definiciji klase kažu da ako je funkcija (/=) definirana, onda je funkcija (==) definirana kroz nju u skladu s tim, i obrnuto. Zahvaljujući tome, dovoljno je da programer definira samo funkciju poređenja za jednakost (ili nejednakost), a tumač će sam odrediti drugu funkciju.

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

class Eq a => MyClass a where

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

Jednom kada je klasa definirana, možete deklarirati tip podataka kao instancu te klase:

instanca MyClass Double gdje

|x==z = 1 + myFunc xs z

|inače = myFunc xs z

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

Definiranjem tipa kao instance klase, možete primijeniti opisane funkcije na objekte tog tipa.

test = myFunc x 2 gdje

Klase se često koriste kada se opisuju funkcije s polimorfnim parametrima. Na primjer, ako želite opisati funkciju koja koristi operaciju poređenja za mnoge tipove podataka, morate specificirati da njeni parametri koji učestvuju u usporedbi moraju biti tipa Eq klase, što jamči implementaciju odgovarajuće funkcije.

Kada programer opisuje svoju strukturu podataka, ona ne pripada nijednoj klasi. Ako je potrebno, programer mora implementirati odgovarajuće funkcije za svoju strukturu i naznačiti svoje članstvo u klasi. Na primjer, prethodno opisana struktura podataka Tree može se proglasiti instancom klase Show tako da je tumač može prikazati na ekranu bez pribjegavanja ručnom pozivu funkcije showtree. Da bismo to uradili, pišemo:

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

Nakon toga, kada interpretator primi rezultat tipa Tree, moći će ga prikazati na ekranu, a bilo koja druga funkcija će moći konvertirati Tree objekt u string formu 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 prilikom deklarisanja strukture:

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

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

Stablo podataka a = Ništa | Stablo a (Drvo a) (Drvo a)

Sada je moguće upoređivati ​​stabla s operacijom “==” i omogućava im da se koriste 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 kojim se funkcije evaluiraju nije definiran. Ali u nekim slučajevima to se ne može izostaviti. Takvi slučajevi uključuju rad sa korisnikom, sa datotekama, sa bazama podataka itd. Haskell obezbeđuje specifikaciju takvih funkcija koristeći monade - posebne klase kontejnera. U učenju Haskell-a monade se smatraju najtežim dijelom, pa krenimo odmah s primjerima. Objašnjenja nekih stvari će biti izostavljena kako ne bi zbunili čitaoca. Razmotrite sljedeći primjer:

putStrLn "Zdravo svijete!"

putStrLn "Zbogom svijete!"

U ovom primjeru, glavna funkcija ima nuspojave - kao rezultat njene evaluacije, na ekranu se prikazuje tekst, a u njemu je definiran redoslijed evaluacije - prvi se prikazuje prvi red, zatim drugi.

Kada se koristi do notacija, programiranje "nečistih" funkcija korištenjem monada svodi se na gotovo uobičajeno imperativno programiranje.

Svaki sljedeći red mora biti funkcija posebnog tipa - monadičnog tipa. U slučaju rada sa input-output, ovo je tip (IO a).

Za rad sa komandnom linijom koriste se sljedeće funkcije:

putChar::Char -> IO izlaz karaktera

putStr::String -> IO izlazni niz

putStrLn:: String -> IO izlazni niz sa 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 string, 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

Ovdje na scenu stupa "zadatak". Po analogiji sa imperativnim jezicima, to možemo reći u redu

ime<- getLine

rezultat funkcije getLine je dodijeljen varijabli name. Ali, kao što znamo, u Haskell-u nema varijabli, a samim tim ni dodjela. U ovom slučaju je kreiran neki objekat pod imenom name, čija je vrijednost jednaka rezultatu izračunavanja funkcije getLine. To jest, ako nakon toga ponovo pišemo

ime<- getLine

tada će se kreirati novi objekt čije će se ime preklapati s prethodnim.

Ovako se dobijaju rezultati monadskih funkcija. Da bi se "varijable" postavile kao vrijednosti običnih funkcija na ovaj način, koristi se pojednostavljena oznaka let:

neka ime = "Jovan"

Grananje računskog procesa vrši 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 grana treba da se sastoji 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 implementiraju korištenjem rekurzije, kao što je prikazano gore, ili korištenjem posebnih funkcija (koje se također implementiraju rekurzivno). Ove funkcije uključuju funkciju mapM_. Njegov princip rada je sličan funkciji mape za liste - primjenjuje monadičnu funkciju na sve elemente liste i sekvencijalno ih izvršava. primjer:

writeDigit x = do

putStr "cifre:"

mapM_writeDigit

8 Primjeri

Navedite razne primjere (drveta pretraživanja, AVL stablo, bilo šta drugo)

Zaključak

Zaključak

Spisak korištenih izvora

1 http://ru. wikibooks. org/wiki/Functional_Programming Fundamentals

2 http://www. *****/article/funcprog/fp. xml

3 Duškinovo programiranje u Haskelu - DMK Press, 2007. - 608 str.

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

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

Sintaksa za dva uzastopna identifikatora znači primjenu funkcije foo na njen argument bar:

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

Zagrade se koriste za grupisanje argumenata:

akos (cos pi)

Funkcija sa više argumenata:

max 5 42

Operacija primjene funkcije je lijevo asocijativna:

(maks. 5) 42

Funkcija max primijenjen uzastopno na dva argumenta.
Kompajler razumije konstrukciju f x y kako (fx)y, a ne obrnuto f(xy).

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 je kao funkciju od N varijabli, onda to možemo gledati s druge strane i reći da je to funkcija jedne varijabla koja nam vraća funkciju od N - 1 varijable.

3+sin42

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

Ime funkcije i imena formalnih parametara moraju početi malim slovima. Velika slova se koriste za definiranje tipova podataka.

Funkcija od tri argumenta koja izračunava dužinu 3D vektora:

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

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

Neka sumSquares x y = x^2 + y^2

Svojstvo čistoće funkcije

Važna karakteristika koja razlikuje funkcionalne jezike od imperativnih jezika je svojstvo čistoće funkcije. Sve funkcije u Haskell-u su čiste. To znači da je vrijednost funkcije u potpunosti određena vrijednostima argumenata koji su joj proslijeđeni. Nijedan drugi izvor podataka ne može utjecati na rezultat koji vraća funkcija. Ako želite da funkcija preuzme podatke odnekud, onda joj morate proslediti ovaj izvor podataka kao argument.

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

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

U Haskell-u ne možete definirati funkciju koja ne uzima argumente i vraća različite vrijednosti na različite pozive.

Mehanizam definicije karakteristika s djelomičnom primjenom

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 definicije 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. Na ovaj način možete definirati funkciju bez specificiranja svih argumenata. Odgovarajući stil programiranja naziva se bez tačke.

Često se dizajn funkcija u Haskell-u prilagođava tako da je djelomična primjena zgodna;

Preludij > neka ograničenje popusta proc zbroj = ako suma >= 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. Ali parametar sume se često mijenja. Zapravo, svaki put kada se ova funkcija pozove.

Pretpostavimo da razvijamo interfejs za sistem prevođenja prirodnog jezika u Haskell-u. Trebao bi sadržavati funkciju prevođenja sa tekstualni parametri, languageFrom i languageTo. Kako bi bilo zgodno implementirati sljedeće funkcije:

• prevedi sa španskog na ruski,
• prevediFromEnglishToRussian
• i prevedi na ruski

trebate urediti parametre ovim redoslijedom: prevedite jezikNa jezikIz teksta.

Operator nad tipovima ->

Da biste napisali tip funkcije, morate napisati tip njenog argumenta i tip rezultata ove funkcije. U Haskell-u, -> operator se koristi za opisivanje tipa funkcije, a to je binarni operator čiji je lijevi operand tip argumenta, a desni operand je tip rezultata. Strelica je između lijevog i desnog operanda jer je infiksni operator.

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

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

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

Podsjetimo funkciju popusta koja je vratila ukupan iznos kupovine uz mogući popust. Njemu su kao parametri proslijeđeni iznos bez sume popusta, postotak postupka popusta, a popust je izračunat ako je preneseni iznos premašio prag limita. Svi ovi parametri, kao i povratna vrijednost, mogu se pohraniti u tipu Double. Tip funkcije se može navesti u datoteci izvornog koda zajedno sa njenom definicijom:

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

Imajte na umu da je deklaracija tipa opciona, iako se često preporučuje kao dokumentacija. Obično se stavlja ispred definicije funkcije, iako je ova deklaracija vrhunski nivo može se postaviti bilo gdje u izvornom fajlu.

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 znak se tretira kao jedinice.)

Import Data.Char twoDigits2Int :: Char -> Char -> Int twoDigits2Int x y = ako jeDigit x && isDigit y onda digitToInt x * 10 + digitToInt y else 100

GHCi > twoDigits2Int "4" "2" 42

rekurzija

U imperativnim jezicima, glavni element ponovljenih izračunavanja je petlja. Petlje nemaju mnogo smisla u funkcionalnim jezicima. Budući da u funkcionalnim jezicima ne postoji koncept promjenjive varijable, ne postoji način da se razlikuje jedna iteracija petlje od druge. Rekurzija se koristi u funkcionalnim jezicima za izvođenje ponavljajućih proračuna. Da se rekurzivna funkcija ne bi petljala, ona mora ispunjavati sljedeće zahtjeve:

• pozivi funkcije na desnoj strani moraju se izvršiti na vrijednosti parametra koji nije formalni parametar funkcije;
• rekurzivni pozivi se moraju negdje prekinuti (mora postojati tzv. uvjet završetka).

Faktorski

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

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

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

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

dvostruki faktorijal

Razmotrimo funkciju koja izračunava dvostruki faktorijel, odnosno proizvod prirodnih brojeva koji ne prelaze dati 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 )

Fibonačijev niz brojeva

U Haskell-u, ova definicija je data sljedećom funkcijom:

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

Implementacija funkcije za izračunavanje Fibonačijevog broja, zasnovana na direktnoj rekurzivnoj definiciji, izuzetno je neefikasna – broj poziva funkcije raste eksponencijalno sa rastom vrednosti argumenta. GHCi vam omogućava da nadgledate upotrebu memorije i vrijeme potrebno za procjenu izraza pokretanjem naredbe :set +s:

* Fibonači > : set + s * Fibonači > fibonači 30 832040 (16,78 sekundi, 409 318 904 bajtova)

Koristeći mehanizam akumulatora, možete napisati efikasniju implementaciju koja ima linearnu složenost (u smislu broja 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 su rijetke u imperativnim jezicima. Primjer je funkcija sortiranja iz C standardne biblioteke. Kao prvi argument, binarni predikat poređenja se prosljeđuje funkciji sortiranja, uz pomoć koje se sortira niz, koji se prosljeđuje kao drugi argument. U funkcionalnim jezicima i u Haskellu funkcije višeg reda se koriste vrlo često.

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

Ovo je polimorfni tip. Dolar operator je funkcija dva argumenta. Njegov lijevi operand ili prvi argument (a -> b) je funkcija. Njegov desni operand a je vrijednost proizvoljnog tipa. Dolar operator jednostavno primjenjuje svoj prvi argument (a -> b) na svoj drugi argument a. Stoga je ovdje neophodno da tipovi budu konzistentni. Tip drugog argumenta dolar operatora mora odgovarati tipu parametra funkcije koji je proslijeđen u prvom argumentu. Štaviše, rezultat dolar operatora je rezultat funkcije koja se prosljeđuje kao prvi argument. Pošto je tip rezultata b, rezultat dolar operatora je tip b.

Sljedeća aplikacija 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 zaista funkcija, ali argument i povratna vrijednost su istog tipa. A drugi argument je vrijednost ovog istog 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.

Prelude > flip (/ ) 4 2 0.5 Prelude > (/ ) 4 2 2.0 Prelude > 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 sa argumentima istog tipa (tip b), 2) funkcija f:: a -> b, 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 sabiranja kvadrata argumenata ovako:-) sumSquares = (+ ) `na` (^ 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 Haskell-u, kao iu matematici, funkcije se obično imenuju. Kada trebamo pozvati funkciju, pozivamo je na njeno ime. Međutim, postoji alternativni pristup koji se zove 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 koji pojednostavljuje notaciju.

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

Anonimne funkcije se koriste u korištenju funkcija višeg reda.

(- Funkcija on3, ima semantiku sličnu on, ali uzima ternarnu funkciju 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) (- Zbir 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 poziva funkcije Haskell, moguće je navesti ne sve argumente, već samo dio njih. Prvih nekoliko argumenata funkcije može biti specificirano, a ostali odbačeni. Ovu ideju djelomične primjene funkcija skovao je Haskell Curry, a po njemu se takve funkcije s argumentima koji se prosljeđuju jedan po jedan nazivaju curried. U Haskell-u, nisu sve funkcije iskrivljene. Haskell vam omogućava da definirate funkcije na torkama. U ovom slučaju, sintaksa za pozivanje funkcija izgledat će isto kao u običnim jezicima:
ime_funkcije (prvi_argument, drugi_argument)

Preludij > prvi (1,2) 1

Currying je procedura za prelazak sa funkcija koje se ne koriste u kariju na funkcije koje uzimaju argumente jedan po jedan. Zamislite da imamo funkciju višeg reda, kao što je on kombinator, on očekuje kao 2 od svoja 4 argumenta funkcije. Prvi argument je funkcija od dva argumenta koja se ispisuje. Haskell ima poseban kombinator karija koji vrši prelazak sa funkcije bez karija u funkciju sa karijem. IN sljedeći primjer curry pretvara funkciju datu preko para u standardnu ​​curried funkciju sa 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 koristi:

Prosjek :: (Dvostruki, Dvostruki) -> Dvostruki prosjek p = (fst p + snd p) / 2

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

Uređaj sa funkcijom curry:

Preludij > let 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

Za svoj prvi argument uzima funkciju koja nije uključena, tj. funkciju preko para, ali je pretvara kao povratnu vrijednost u curried funkciju kojoj se argumenti prosljeđuju sekvencijalno.

Postoji i inverzna funkcija uncurry:

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 > swap (1 ,"A" ) ("A" ,1 )

Ova funkcija se može izraziti kao:

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

Stroge i nestroge funkcije

Lijena evaluacija dovodi do činjenice da je u mnogim situacijama moguće eliminirati neokidanje programa.

const42 :: a -> int const42 = const 42

Funkcija const42 potpuno zanemaruje vrijednost argumenta, stoga, u okviru modela lijenog izračunavanja, ako proslijedite bilo koji složen proračun, onda se ova kalkulacija nikada neće dogoditi. A to znači da bilo koji program, uključujući i program koji se ne završava, može biti proslijeđen kao argument const42.

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

Funkcije kao što je const42 nazivaju se nestrogim funkcijama. Ako se divergentno izračunavanje prosljeđuje funkciji kao argument, a rezultat je neka nedivergentna vrijednost, tada se takva funkcija naziva nestrogom. Funkcija se naziva strogom tako da ako joj prenesemo divergentni argument, tada je vrijednost ove funkcije nužno divergentna. Funkcija od dva argumenta može biti stroga ili nestroga u odnosu na drugi argument, ovisno o vrijednosti njenog prvog argumenta. Analiza rigidnosti je neophodna da bi Haskell program bio veoma efikasan.

28. novembar 2013. u 21:48

Bilješke sa predavanja "Haskell kao prvi programski jezik". Dio 1

• haskell,
• Funkcionalno programiranje

• tutorial

Hi Habr! Danas sam izvadio svoje stare beleške o kursu "Haskell kao prvi programski jezik" Sergeja Mihajloviča Abramova i pokušaću da što jasnije i na primerima ispričam o ovom divnom jeziku onima koji ga još nisu upoznati. Priča je namenjena nespremnom čitaocu. Pa čak i ako je ovo prvi put da čujete riječ Haskell...

Osnovni Haskell tipovi

Osnovni tipovi Haskell jezika su:
Brojevi
Boolean vrijednosti
Simboli
Liste
Naručeni setovi (torke)
Funkcije

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

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

Boolean vrijednosti
Bool(Tačno|Netačno)
Operacije konjunkcije, disjunkcije i negacije (&&, ||, ne)

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

Liste
Liste mogu biti različite:
- lista cijelih brojeva
- lista znakova (string)
[] - niz
je lista funkcija
itd.

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

Naručeni setovi
primjeri:
(2.4, "mačka") (Float, )
('a', Tačno, 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, zakon korespondencije koji odgovara svakom elementu x iz datog skupa A sa jednim (ili nijednim) elementom y iz skupa B.
Haskell je, po svojoj namjeni, prije svega jezik matematičara, tako da sintaksa ovdje odgovara ovoj definiciji što je bliže moguće.
primjer:
kvadrat:: Integer -> Integer square x = x*x
Kao što ste vjerovatno pogodili, ovo je funkcija kvadriranja broja. Analizirajmo ga detaljno:

Prvi red je deklaracija funkcije:
function_name:: opseg_definicije -> raspon_vrijednosti
kvadrat::Integer -> Integer
Ovdje treba reći da u Haskell-u nije potrebno uvijek deklarirati funkciju. U nekim slučajevima, tumač će već razumjeti koji su opseg i značenje date funkcije. Međutim, izostavljanje oglasa je loše ponašanje.

Drugi red je definicija funkcije:
parametri ime_funkcije = pravilo_vrednovanja
kvadrat x = x*x

Funkcija bez parametara nije ništa drugo do konstanta:
e::Floate=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 jednačine ax^2+bx+c=0

Definicije funkcija s alternativama

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

Slučaj … od …
abs2 x = slučaj x>=0 od Tačno -> x Netačno -> -x

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

Pattern matching

Jedan od najčešćih i najefikasnijih trikova u Haskell-u je podudaranje uzoraka. Umjesto parametra, možemo dati funkciji primjer kako bi parametar trebao izgledati. Ako se uzorak podudara, funkcija se izvršava; ako ne, ide na sljedeći uzorak. Na primjer, definiranje faktorijala kroz rekurziju korištenjem obrazaca:
činjenica:: Integer -> Integer fact 0 = 1 činjenica n = n * činjenica (n-1)
Ista stvar, ali uz pomoć zaštitničkih izraza:
fact:: Integer -> Integer fact n | n==0 = 1 | n>0 = n*činjenica (n-1)
Postoji vrlo čest obrazac liste: (x:xs). X - označava prvi element, XS - ostatak liste (osim prvog elementa). ":" - operacija pričvršćivanja elementa na listu. Primjeri uvoda:
glava:: [a] -> glava (x:_) = x glava = greška "Prelude.head: prazna lista" tail:: [a] -> [a] rep (_:xs) = xs rep = greška "Prelude.tail: prazna lista"
Funkcija head uzima listu bilo čega [a] kao ulaz i vraća prvi element ove liste. Funkcija rep uzima listu bilo čega [a] kao ulaz i uklanja prvi element sa ove liste.
"_" - znači da dati element nismo zainteresovani.

Pa, to je sve za danas. Ako bude interesovanja, napisaću nastavak u bliskoj budućnosti.

Iako se ne poklapa sa vašim veliki kriterijumi(statički * unos), uradiću slučaj za Python. Evo nekoliko razloga zašto mislim da biste to trebali pogledati:

• Za imperativni jezik, ovo je iznenađujuće funkcionalno. To je bila jedna od stvari koje su me pogodile kada sam to saznao. Na primjer, pogledajte liste. Ima lambda, vrhunske funkcije i puno funkcionalno inspirisane kompozicije na iteratorima (mape, nabori, patentni zatvarači...). Ovo vam daje mogućnost da odaberete paradigmu koja najbolje odgovara problemu.
• IMHO, ovo je, kao i Haskell, lijepo kodirati. Sintaksa je jednostavna i elegantna.
• Ima kulturu koja se fokusira na obavljanje stvari na jednostavan način umjesto da se previše uredno fokusira na efikasnost.

Razumijem ako tražite nešto drugo. Logičko programiranje, na primjer, moglo bi biti u vašoj blizini, baš kao i ostali.

*Pretpostavljam da ovdje mislite na statičko kucanje pošto želite da deklarirate tipove. Tehnički, Python - to je jezik sa jakom kucanjem jer ne možete proizvoljno protumačiti, recimo, string kao broj. Zanimljivo je da postoje Python derivati ​​koji dozvoljavaju statičko kucanje, kao što je Boo.

2018-12-04T00:00Z

Ako želite snažan (er) lični prolog, Merkur je zanimljiv izbor. Radila sam to u prošlosti i svidjela mi se drugačija perspektiva koja mi je dala. Takođe ima modifikovanost (koji parametri bi trebali biti slobodni/fiksni) i determinizam (koliko rezultata ima?) u sistemu tipova.

Clean je vrlo sličan Haskell-u, ali ima jedinstveno kucanje koje se koristi kao alternativa Monadi (tačnije, IO monadi). Jedinstvenost unosa takođe čini zanimljiv materijal za rad sa nizovima.

2018-12-11T00:00Z

Budući da niste naveli nikakva ograničenja osim vlastitih subjektivnih interesa i naglašavate "nagradu za učenje" (u redu, ok, zanemariću ograničenje statičkog kucanja), predlažem učenje nekoliko jezika različitih paradigmi i po mogućnosti onih koji su "uzorni" za svakog od njih.

• Lipsky dijalekt za kod-podaci-podaci/homokoničnost i zato što su dobri, ako ne i najbolji, primjeri dinamičkih (manje ili više strogih) funkcionalnih programskih jezika
• Prolog kao dominantni logički programski jezik
• Mali razgovor kao jedini pravi OOP jezik (također zanimljiv zbog svog obično izuzetno usmjerenog pristupa prema slici)
• možda, Erlang ili Clojure, ako vas zanimaju jezici kovani za istovremeno/konkurentno/distribuirano programiranje
• Naprijed za programiranje orijentirano na stek
• (Haskell za strogo funkcionalno statički tipizirano lijeno programiranje)

Posebno Lisps (CL ne toliko kao Scheme) i Prolog (i Haskell) prihvataju rekurziju.

Iako nisam guru ni na jednom od ovih jezika, proveo sam neko vrijeme sa svakim od njih osim Erlanga i Fortha, i svi su mi pružili otvorena i zanimljiva iskustva učenja jer svaki pristupa rješavanju problema iz različitog ugla,

Dakle, iako može izgledati kao da sam zanemario dio o tome da nemam vremena da isprobam više jezika, radije mislim da vrijeme provedeno sa bilo kojim od njih neće biti izgubljeno i da biste trebali pogledati sve njih.

2018-12-18T00:00Z

U smislu onoga što odgovara vašem smjeru, očigledan izbor izgleda kao logičan jezik poput Prologa ili njegovih derivata. Logičko programiranje se može obaviti vrlo uredno u funkcionalnom jeziku (pogledajte npr. Reasoned Schemer), ali možda biste željeli direktno raditi s logičkom paradigmom.

Interaktivni teorijski sistem dokazivanja kao što je dvanaest ili coq također vam može oduševiti.

2018-12-25T00:00Z

Želio bih da proširim svoje znanje u programiranju. (...) Mislio sam da ovdje postavim pitanje, kao i nekoliko prijedloga o vrsti jezika koji tražim. Neki od njih su subjektivni, neki su namijenjeni da olakšaju prijelaz sa Haskell-a.

Sistem jakog tipa. (...) Takođe olakšava neformalno razmišljanje o ispravnosti mog programa. Brine me ispravnost, a ne efikasnost.

Naglasak na rekurziji, a ne iteraciji. (...)

Bojim se da ovdje možete malo olakšati prijelaz. Veoma jak sistem tipova i čisto funkcionalan stil su karakteristični za Haskell, i gotovo sve što izgleda kao mainstream programski jezik moraće biti kompromitovano, ali najmanje, na jednom od njih. Dakle, imajući to na umu, evo nekoliko širokih prijedloga usmjerenih na očuvanje veći dijelovi onoga što vam se sviđa kod Haskell-a, ali sa nekim značajnim pomakom.

Zanemarite praktičnost i idite na "više Haskell nego Haskell": Sistem tipa Haskell je pun rupa, zbog prekida i drugih neurednih kompromisa. Očistite nered i dodajte još moćne karakteristike i dobićete jezike poput Coq I Agda, gdje tip funkcije sadrži dokaz njene ispravnosti (možete čak pročitati i strelicu funkcije -> kao logičku implikaciju!). Ovi jezici su korišćeni za matematičke dokaze i za programe sa izuzetno visokim zahtevima za ispravnost. Coq je vjerovatno najistaknutiji jezik stila, ali Agda ima više Haskell-y osjećaj (i također je napisan na Haskell-u).

Ne uzimajte u obzir tipove, dodajte još magije: ako je Haskell vještičarenje, Lisp je sirova iskonska magija stvaranja. Lisp porodični jezici (uključujući Šema i Clojure) imaju gotovo neusporedivu fleksibilnost u kombinaciji s ekstremnim minimalizmom. Jezici u suštini nemaju sintaksu, pišu kod direktno kao strukturu podataka stabla; metaprogramiranje u Lisp-u je lakše od nemetaprogramiranja u nekim jezicima.

Napravite malo kompromisa i približite se mainstreamu: Haskell spada u široku porodicu jezika pod jakim uticajem ML-a, na koji biste verovatno mogli da pređete bez prevelikih poteškoća. Haskell je jedan od najstrožih kada su u pitanju garancije ispravnosti tipova i upotrebe funkcionalnog stila, gdje su drugi često ili hibridni stilovi ili/ili prave pragmatične kompromise na različitih razloga. Ako želite podvrgnuti OOP-u i pristup mnogim glavnim tehnološkim platformama Scala na JVM, ili f# u .NET-u ima dosta zajedničkog sa Haskell-om, pružajući laku kompatibilnost sa njim Java platforme i .NET. F# je direktno podržan od strane Microsofta, ali ima neka dosadna ograničenja u poređenju sa Haskell-om i probleme sa prenosivosti na platformama koje nisu Windows. Scala ima direktne kolege sa sistemom tipa Haskell i Javinim potencijalom za više platformi, ali ima težu sintaksu i nedostaje joj moćna podrška treće strane koju F# uživa.