Funkcionalno programiranje (Haskell)

Eto, prvo pitanje.

Why? Zašto prelaziti na funkcionalno programiranje? Koji su benefiti? Neki konkretan (kratki primjer)?

Ok, to nije jedno pitanje

Nema bas radoznalih, ha?

Nema veze... odrzavat cu temu zivom kako-tako dok se ne pojavi netko hrabar i dovoljno zainteresiran.

Kratak tutorial sa jako dobrim primjerom rijesavanja problema koristeci 'naprednije' tehnike kao sto su monadi, u ovom slucaju je to State:

http://www.lpenz.org/articles/hedsl-sharedexpenses/

Vjerojatno ce preletjeti preko glave svakom tko ne zna Haskell, ali slobodno pitajte, probat cu objasnit sto znam.

Bok,

evo jedno pitanje koje je možda malo van teme. Donekle si svladao (ne mislim vrijeđati, samo znam da uvijek ima mjesta za napredak) FP i Haskell te vidiš u tom principu budućnost programiranja. Da li iz ove perspektive možeš dati svajet nekom tko manje pozna programiranje da možda krene drugim putem ako cilja na FP tj. da si od početka znao da želiš ovako programirati kako bi krenuo prema svladavanju toga.

Ima tutoriala, ima svega.

Al daj ti nama usporedi neki jednostavan programcic u javi, pythonu, c/c++ s istovjetnim kodom u haskellu tak ce se najlakse vidjet razlika, par prednosti i mozda koja mana.

Mogli bi reći da je LINQ (u .Netu) jako, jako blizu tome.

Ne znam koliko si gledao po tome (linq, lambde, delegati, virtualne metode...) ali dobar dio ovih ružnih for...next gluposti se rješava sa njime. Primjer:

List<Person> persons = new List<Person>();

persons.Add(new Person(1, "Pero", "Perić");

....

persons.Add(new Person(7, "Marko", "Marković");

persons.Add(new Person(8, "Ivo", "Ivić");

var someUsers = persons.Where(x => x.Id > 6);

LINQ je uglavnom upravo FP orijentiran: umjesto loopova, koristis map i reduce (odnosno fold). Razlika je samo u tome sto je LINQ embeddan unutar OOP jezika, pa je samim time ogranicen sintaksom. Primjerice, koliko ja znam - u LINQ-u ne mozes parcijalno primjeniti funkcije/metode, ne mozes ih komponirati, i ne mozes forsirati cisti code (bez sideeffecta) kroz compiler, svo izvrsavanje je striktno (a ne lijeno), ne postoje beskonancne vrijednosti, etc... Vjerujem da postoji neki tip "Optional" ili "Maybe" koji pokusava imitirati monadske sposobnosti ali ako je to ista slicno javi - onda je poprilicno neugledno i ne-elegantno.

Sto se tice tipova - znas o cemu se radi i u Haskellu. Tipovi su staticki i striktni; razlika je u tome da ih ne moras (iako mozes) rucno pisati. Zbog nacina na koji tipovi funkcioniraju (algebarski,  teorija kategorija), compiler moze sam skuziti sto je koji tip.

Ideja da se tipovi trebaju 'komentirati' kroz code je nasljedje OOP-a, i nije problem u jeziku vec u nacinu razmisljanja - prvoj i najvecoj kocnici kod prelaska na neki FP jezik.

Postoji parameterizacija tipova (npr. kao templateovi u C++u ili generici u C#-u), i typeclass da bi se parameterizirani tip ogranicio. Vise-manje te stvari samo kreiraju los code (npr. existential typeclass antipattern), jer ljudi zaboravljaju da su funkcije uglavnom puno mocniji alat.

Nadalje, tipovi se ponasaju i kao tipovi, enumeracije i unioni. Primjerice, recimo da imamo tip Foo, mozemo napraviti dva konstruktora, Bar i Moo, koji uzimaju drugacije vrijednosti pored parameteriziranog tipa 'a':

data Foo a = Bar Int a | Moo String a

I na kraju, ono sto je po meni najbitnije - instancirati tip kao neku typeclassu ("naslijediti") moze se dogoditi svagdje, cime se postuje open-closed princip. Recimo da zelimo da nas tip bude Monad. Ovaj code moze stajati gdje god:

instance Monad Foo where
  return = Moo
  (Bar a) >>= f = f a
  (Moo a) >>= f = f a

Edit:

mislim da je zadnji primjer koji sam naveo u biti najinteresantniji, ne zato jer je one-liner, vec zato jer koristi sve sto Haskell stavlja barem klasu-dvije (;-)) ispred drugih jezika: monadi, kompozicija funkcija, kliesli strelice te parcijalna aplikacija.

main = readFile >=> foldl1 (>>) . map putStrLn . concat . map words . lines $ "textfile"

Pojasnit cu sto se dogadja:
$ operator je aplikator s najnizim mogucim prioritetom. Primjerice, bas kao sto su zbrajanje i mnozenje operacije drugacijeg prioriteta, tako i ovaj aplikator forsira aplikaciju funkcije tek nakon sto se sve ostalo razvije.
. je kompozicija funkcije, odnosno, output jedne funkcije postaje input druge, stvarajuci novu funkciju.
>=> je kliesli kompozicija koja omogucuje kompoziciju monada na slican nacin na koji se komponiraju funkcije.

>> operator je monadsko spajanje u kojem se vrijednost prethodnog monada zanemaruje.

Dakle, kod se cita od operatora najveceg prioriteta prema operatoru najnizeg. Operator aplikacije funkcije je najjaci (obican space, " "), dakle prvo rijesavamo funkcije map, koje uzimaju dva parametra: funkciju s jednim parametrom i listu. Kao sto vidimo, mi predajemo samo jedan parametar, sto se zove parcijalna aplikacija, i kao rezultat dobit cemo dvije funkcije koje imaju definiran prvi parametar ali im nedostaje drugi.

Nakon toga, rijesavamo . operator, komponirajuci funkcije s desna na lijevo:

lines ima tip String -> [String], odnosno iz stringa vraca listu stringova. Lines tokenizira string po newlinesima.

To se komponira na parcijalno aplicirani "mapWords" koji prima listu stringova i vraca listu listi Stringova [[String]]. Words tokenizira string po spaceovima.

Onda ide concat, koji prima listu listi bilo cega, i konkatenira liste u jednu veliku, dakle [[a]] -> [a]

Onda opet parcijalno aplicirani map koji uzima listu Stringova i kreira listu IO () vrijednosti, dakle [IO ()]. Ove IO vrijednosti imaju sideeffect da isprintaju dani string na konzolu.

Nakon toga ide fold [IO ()] u singularni IO (), i to se radi kroz operator >>, odnosno, lancano spajamo IO () vrijednosti jednu za drugom u jednu veliku akciju. Operator >> ima tip u ovom slucaju IO a -> IO b -> IO b, sto znaci uzima IO s tipom a i IO s tipom b i vraca IO s tipom b (gdje naravno a i b mogu biti isti tipovi).

Koristim fold funkciju 'fold1' sto znaci da foldam listu s lijeva nadesno i bez startne akumulacijske vrijednosti; prva vrijednost je ujedno i prva vrijednost iz liste.

Tip ove velike anonimne funkcije je sada: String -> IO ()

S obzirom da je ulazna vrijednost 'cista' a izlazna monadska, mozemo upotrijebiti monadsku kompoziciju (>=>) i lancano spojiti readFile izlaz na ulaz nase funkcije. readFile vraca "IO String" vrijednost, odnosno String zamotan u IO monad (jer se taj string dobija kroz sideeffect). Kad to spojimo kroz monadski bind, nasa anonimna funkcija prima String ali mora obavezno vratiti vrijednost zamotanu u isti monad (IO) sto se vec dogadja.

readFile ima tip String -> IO String, sto znaci da to komponirano s nasom funkcijom sad ima tip String -> IO ()

main trazi IO () tip, sto znaci da trebamo aplicirati String vrijednost na nasu monadsku funkciju i tu u pricu ulazi aplikator $ jer se to "izvrsava" zadnje. Dakle, aplicirajuci String "textfile" na String -> IO (), dobijamo IO () vrijednost koju mozemo pridruziti u main.

Voila.

Zgodno i iznenadjujuce, nedavno sam gledao novitete u Javi i vidio da guraju malo funkcionalnih stvari, ali kad sam vidio Optional, smucilo mi se. Pomislio sam da je sve tako nezgrapno rijeseno. Ovo izgleda puno bolje.

Velika prednost Haskella je u tome sto se drzi striktno funkcijske paradigme, implementira software patterne kroz visu matematiku, te kroz striktne tipova separira -na razini compilera- cist code od IO codea. Ima drugih jezika koji se drze cisto jedne paradigme, (npr. Erlang i Clojure) ali nemaju striktnu separaciju, ocekuje se od korisnika da na to pazi. Dokle to moze pomoci u produkcijskoj okolini, smatram da pocetnicima samo otezava ispravno ucenje.

Sto se tice multi-paradigm jezika (cak i Python ulazi ovdje jer ima stvarno fino razvijene FP facilitye), vidim mnogo ljudi u beginners channelima na IRC-u kako -nazalost- prenose znanja i navike iz drugih paradigmi u funkcionalnu, i samim time sebi odmazu. Naravno, ljudi uce na drugacije nacine, no mislim da je jedini nacin da se vide sve prednosti i mane funkcionalnog programiranja - programirati funkcionalno. Ako odjednom nemas pristup varijablama, loopovima i ostalim imperativnim konstruktima, morat ces se prisiliti razmisljati na drugaciji nacin (ili odustati), a u tome lezi srz ucenja neceg novog.

Haskell je vrlo neugodan u pocetku, sve se cini napornim i neprirodnim; problem nije u jeziku, nego u navikama.

Ovaj topic u Quori je okupio pristase FP jezika, i nasiroko objasnjava ono sto sam ja u pocetku pokusao sazeti:

https://www.quora.com/What-are-the-pros-and-cons-of-F-versus-Haskell-as-functional-programming-languages

"For that reason I'd advise Haskell if you want to ensure you get the gist of functional programming fully. Else you'd need to check yourself every time to make sure you didn't simply write a translated imperative algorithm."

@Floki:

jel moguce u F#-u parcijalno aplicirati?

Primjerice, jel mozes pozvati (+) sa samo jednom vrijednosti, i dobiti natrag funkciju koja prima jedan parametar manje?

Odlicna tema!

Sto se tice funkcijskog (ne funkcionalnog :P) programiranja nekada davno bio sam na par predavanja, onda u nedostatku vremena odustao. Kad si me vec sjetio na to, dobio sam ideju da ove godine dovrsim zapoceto.

Jedan od velikih pluseva FP je sto je puno, puno lakse formalno, matematicki dokazati ispravnost programa. Kod imperativnih jezika taj je problem puno tezi, postoje alati poput NuSMV-a koji koriste BDD i SAT rjesivace, a SAT je jedan od prvih problema za koji je dokazano da je NP tezak sto predstavlja poprilican problem.

A sto se koristenja tice, s obzirom da najvise programiram u Pythonu, redovito koristim list comprehension, generatore, lambda funkcije (iako osakacene u odnosu na punokrvni FP jezik), map (iako ga se da zamijeniti list comprehensionom) i reduce. Takoder, u Pythonu su funkcije gradani prve klase (kao i ostalo xD). No, to je to. Python nije nesto brutalan po pitanju FP-a, to je prvenstveno OO jezik s primjesama FP-a (nema izrazito bitne tail rekurzije, npr.). Tako da je Python izrazito krasan kad se pise OO, ali kad se pise neki ozbiljniji FP, onda je prilicno manje krasan :D. Medutim, za jednostavne stvari je ok. EDIT: Jos kad se sjetim da Guido svako malo prijeti da ce izbaciti map, reduce i filter, haha.

To je otprilike to sto se tice mog poznavanja FP-a. Pratim temu i dalje (za vise cu se javiti tamo negdje krajem ove godine xD).

Zgodan mi je ovaj F#!

No, za ovu potrebu, to mogu biti i funkcije i u OOP jeziku ili obicne lambde, ali svidja mi se sto se notacija koristi jednako svadgje, u haskellu izrazavas tipove na skoro isti nacin.

Pitam se da li ima pattern matching u F#-u (lijen sam proguglati), odnosno moze se izbjeci if <parametar> then / else u tijelu funkcije, i to gurnes u sam pocetak. Primjeti takodjer da u Haskellu zagrade koristimo iskljucivo za odredjivanje prioriteta operacije. Aplikacija funkcije je obican space izmedju imena i parametara i rijesava se s lijeva na desno (tehnicki, prvi parametar se aplicira i vraca funkciju s n-1 parametara, pa se aplicira drugi koji vraca funkciju s n-2 i tako do kraja).

Prepravit cu factorial u Haskell, ovaj put cu rucno napisati type cisto jer je dobra navika. I factorial i square imaju barem par nacina na koji se daju napisati

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1) -- naivno
-- factorial n = foldl (*) 1 [1..n]   -- foldanje limitirane liste s mnozenjem
-- factorial n = product [1..n]     -- produkt liste :-D

square :: (Int -> Int) -> Int
square f n = (f n) * (f n)     -- cista i jednostavna, naivna verzija
-- square f   = (*) <$> f <*> f   -- eta-redukcija (uklanjanje parametara) i higher level kompozicija funkcija
                  -- zbog cinjenice da su sve funkcije takodjer i funktori u Haskellu i vecini drugih FP jezika

Kao sto se vidi, pattern matching radi od prvog prema zadnjem, i mogu se koristiti konkretne vrijednosti za parametre (bas kao i u matematici za nekontinuirane funkcije ili za rubove). Tako funkcija kaze da je za factorial od 0 = 1, a za sve ostalo rekurzija. Pattern matching se moze normalno izvrsavati nad svakim tipom, i compiler pomaze kod nekompletnih patterna ili ambigous matchanja.

U drugoj definiciji squarea (ne mogu obje biti aktivne naravno!), aplicirao sam prvo f na operator mnozenja, a nakon toga toj funkciji pridruzio ponovno f.

To znaci da rezultat 'square' u drugoj varijanti vise nije vrijednost, vec funkcija Int -> Int!

Da stvar bude komicnija, ako bas zelis sprckati code do kraja i kriptirati ga, lol - moguce je ukinuti i f parametar, sprckati zajedno <$>, <*> i (*) operatore tako da u tijelu funkcije uopce ne moras specificirati niti jedan parametar :-D

Nisam siguran tocno kako, prva ideja mi je vratila gresku 'infinite type construction error':

square = (<*>) <*> ((<$>) (*))

, ali siguran sam da se moze :-D

Ovaj nacin rijesavanja problema je ono sto FP cini FP-om. U Bruce Eckelovoj knjizi o C++, on kaze da tko radi s C++-om a ne razumije/koristi virtualne funkcije - taj ne koristi OOP. Mislim da za FP i higher level funkcije ovo vrijedi jednako.

Sve u svemu, vrlo vrlo zgodno i mocno prckanje!

Trenutno, gnjavim se dosta s monad transformerima. Razumijem princip, razumijem zasto i razumijem kako, no dok slazem code, sve mi se cini kao da vise pogadjam sto napraviti, nego zapravo razumijem sto radim.

Sredio sam EitherT Error IO () da radi (mogucnosti Either i IO) jer vrtim IO code koji moze propasti a ne zelim skrsiti aplikaciju... htio bi dodati logiranje s Writerom ali pogubio sam se.

Edit:

pet minuta kasnije, rascistio probleme. Sve radi ko puska. Tri transformera stackana jedan na drugi, jedino me buni intuicija. Covjek bi mislio da tip kaze, test vraca either koji je ili String, ili WriterT monad s IO-om (Writer je log), tako da logicki gledano ispada da ako dobijes lijevu stranu EitherT-a, onda ne dobijes ni log ni IO side-effecte.

No, kako je ispalo na kraju - transformere unwrappas s lijeva na desno, tako da prvi unwrap mora biti na EitherT-u (runEitherT) koji vraca WriterT String IO (Either String ()). Drugi unwrap vraca writer (koji ima tip (vrijednost, log)), tako da se dobije IO (Either String (), String).

pocetni type (Writer, Either i IO monadi)

test :: EitherT String (WriterT String IO) ()

izvrsavanje

runWriterT . runEitherT $ test

izlazni tip (koji se unutar IO monada -npr. main- moze bindati na neku funkciju koja prima tuple kojem je first Either, a second String), pa onda pozvati funkciju 'either' na first i vidjeti sto dalje. Log je prisutan u oba slucaja.

Cool!

IO (EIther String (), String)

Znas kako kazu, da je posao programera konstantno ucenje?

Pa, ja sam gotovo siguran da je ovo to. Nauciti Python kad jednom znas npr. Ruby nije neki problem. U biti nauciti skoro bilo koji imperativni/OOP jezik kad vec znas jedan je nista.

Jedini jezik koji se razlikuje jest asembler, no on je toliko ovisan o hardveru da ne mozes skoro ni pricati o tome kako znas assembler generalno.

Ispravno funkcijsko (j*** se domagoj :-D) programiranje je tesko. Ne inherentno, nego zato jer je tesko okrenuti glavu u pravom smjeru i ostaviti stare navike, no prednosti koje donosi (neke sigurne, neke samo naslucujem) jednostavno ce pomesti svaki drugi jezik. Samo pricekaj da mladci sa faksa pocnu otvarati startupove na bazi funkcijskog programiranja. Mi starci, ako se ne prilagodimo - postat cemo obsolete.

Haskell je k'o Vim. Uzasna pocetna krivulja, ali jednom kad udjes u stos - vise neces ni pomisljati na ista drugo.

Jesi li probao neke bazicne programcice sastaviti u F#-u?

Iskreno, rekurziju sam koristio jednom ili dvaput, najvise. Rekurzija je kao 'goto' u imperativnom jeziku - ima primjenu, i primjenjeno na pravi nacin zaista cisti code, ali uglavnom nema smisla. Mapovi i foldovi su, ja mislim, osnovni principi - rade na listama (jer su liste funktori) i jednostavno je razviti intuiciju.

Kasnije, mozes 'upgradeati' map u 'fmap' - aplicirati funkciju na bilo koji funktor istog tipa, npr. Maybe (ne znam kako se Maybe zove u F#). U Haskellu, Maybe je i funktor, i applicative, i monad, i monoid, a mislim cak i Traversable. Kad 'doktoriras' Maybe, Either i te pocetne tipove, onda se okrenes natrag funkcijama, jer su i funkcije (barem u Haskellu) takodjer i funktori i applicative.

Tako da ti to nekako otvori vrata prema onome sto FP zapravo jest.

Probaj umjesto tih matematickih algoritama rijesiti neki drugi problem, cak i neko binarno stablo (append, delete, search) bi bila, ja mislim, puno bolja praksa.

Ja radim neki mali nethack (tj. dva).

 Cool beans, congrats :-D

Procitaj ovo, izguglao sam sada: https://en.wikibooks.org/wiki/F_Sharp_Programming/Computation_Expressions

Ne sjecam se tocno jesu li me monadi ili kompozicije gurnuli preko ruba, ali u svakom slucaju, vrlo vrijedno stivo. Nemoj da te obeshrabri uvodna recenica; monadi su u principu stvarno jednostavni ali zbunjuje njihova primjena upravo zato jer su drugaciji od svega na sto smo navikli u imperativnim programima.

Aha, koncept tih monada je u stvari izvršavanje jedne funkcije i predaja njene povratne vrijednosti drugoj funkciji.

A maybe monad je onaj koji lanac funkcija privede kraju sa nekom vrijednošću ili prekine izvršavanje lanca i vrati none, ovisno o uvjetima.

Našao sam jedan zadatak na netu, od nekog x oduzimamo u nizu 10, 30 i 50, ako x kojeg smanjujemo oduzimajem tih vrijednosti bude manji  od tih djeljitelja program se prekida i vraća none, ako x bude veći od svih djeljitelja vraćamo taj krajnji x.

Primjer:

x = 100

100 - 10

90 - 30

60 - 50

x = 10

x = 5

5 - 10

x = None

Tip je napisao sugared verziju, a ja sam napisao desugared verziju i decrement verziju odnosno ručno napisani bind metod. Kad god sam zapeo, pomoglo je što sam vizualizirao u desugared verziji.

let tryDecr x n =
    match x > n with
    | true -> Some(x-n)
    | _ -> None

let decrement x  =
    let bind(input, rest) =
        match input with
        | Some a -> rest a
        | _ -> None
    bind(tryDecr x 10, fun y ->
        bind(tryDecr y 30, fun z ->
            bind(tryDecr z 50, fun t -> Some t)))

type MaybeBuilder() =
  member this.Bind(input, rest) =
         match input with
         | Some a -> rest a
         | _ -> None
  member this.Return(a) = Some a
 
let maybe = new MaybeBuilder()

let desugared x =
    maybe.Bind(tryDecr x 10, fun y ->
        maybe.Bind(tryDecr y 30, fun z ->
            maybe.Bind(tryDecr z 50, fun t ->
                maybe.Return(t)
            )
        )
    )

let sugared x =
    maybe {
        let! y = tryDecr x 10
        let! z = tryDecr y 30
        let! t = tryDecr z 50
        return t
    }