Keskustelu: Ohjelmointikysymykset: Haskell: Funktionaalisista ohjelmointikielistä

Kysyisin asioita liittyen funktionaalisiin ohjelmointikieliin.

1:S, K ja I kombinaattorit. Mitä ne tekevät?
2:Jos funktionaalisessa ohjelmoinnissa ei käytetä muuttujia, miten voidaan samaa tietoa(esim. inputista) käyttää kahdessä eri paikassa?
3:Mikä on lambda-abstraktio?
4:Mitä Täysin funktionaalista kieltä suosittelette?

1.
http://en.wikipedia.org/wiki/S_combinator­#Combinatory_calculi
I x = x, eli I on identiteettifunktio
K x y = x, eli K palauttaa ensimmäisen argumenttinsa ja unohtaa toisen
S x y z = (x z (y z)), eli ensin annetaan z x:lle ja y:lle argumentiksi, ja sitten sovelletaan (x z):n tulosta (y z):n tulokseen.

Nämä ovat lähinnä teoreetikoille mielenkiintoisia virityksiä, koska mikä tahansa lambdalauseke voidaan kirjoittaa käyttäen pelkästään näitä. Käytännön ohjelmoinnissa niitä ei käsittääkseni tarvitse.

2.
Funktionaalisessa ohjelmoinnissa kyllä käytetään muuttujia, joita voi käyttää niin monessa paikassa kuin lystää. Niitä vain ei voi ylikirjoittaa. Se, miten tällaisessa "tilattomassa" kielessä päästään käsiksi tilalliseen maailmaan, kuten inputtiin ja outputtiin, on vähän monimutkaisempi tarina.

3.
(Olkoon "\" = lambda)
Lambda-abstraktio muuttujalla x ja vartalolla t kirjoitetaan \x.t. Se vastaa yhden argumentin x ottavaa funktiota, joka sijoittaa x:n t:hen ja palauttaa tuloksen. Esim \x.(x+1) on funktio, joka plussaa argumenttiinsa yhden (olettaen, että kielessä on sisäänrakennettu +-operaatio). Lambda-abstraktiota sovelletaan ("kutsutaan") kirjoittamalla sen perään argumentti.
Esim. (\x.(x+1)) 3 -> 3+1 -> 4.

Useampiargumenttisia funktiota tehdään sisäkkäisillä lambda-abstraktioilla.
Esim. (\x.\y.(x+y)) 1 2 -> (\y.(1+y)) 2 -> 1+2 -> 3.

Argumentiksi voi antaa myös tavallisten arvojen (tässä lukujen) lisäksi toisia lambda-abstraktioita ("funktioita").
Esim. (\f.\x.f (f x)) on funktio, joka ottaa funktion f ja arvon x ja soveltaa f:ää x:ään kaksi kertaa.

Lambdakalkyyli on turing-täydellinen laskentasysteemi, eli sillä voidaan laskea kaikkea, mitä millä tahansa kunnon ohjelmointikielellä. Toisto saadaan aikaan rekursiolla, jota tehdään puhtaassa lambdakalkyylissa useimmiten Y-kombinaattorilla. Y-kombinaattorin ymmärtäminen voi olla aluksi jossain määrin hankalaa.

http://en.wikipedia.org/wiki/Lambda_calculus

4.
Haskellia.

map_ kirjoitti:

2.
Funktionaalisessa ohjelmoinnissa kyllä käytetään muuttujia, joita voi käyttää niin monessa paikassa kuin lystää. Niitä vain ei voi ylikirjoittaa. Se, miten tällaisessa "tilattomassa" kielessä päästään käsiksi tilalliseen maailmaan, kuten inputtiin ja outputtiin, on vähän monimutkaisempi tarina.

Ja tuosta monimutkaisuudesta mainittakoon vielä, että se on enemmänkin siellä teorian puolella. Täysin funktionaalisessa kielessä kun funktion tulisi palauttaa joka kerta sama arvo samoilla parametreilla. Tämä tietysti on ongelmallista, kun halutaan lukea syötettä.

Käytännössähän tuo syötteen lukeminen on sitten helppoa eikä tarvitse kummemmin olla tutustunut siihen teoriaan siellä takana, johon se pohjaa.

Ja noita muuttujia kannattaa ajatella enemmänkin matematiikasta tuttuina muuttujina, eikä imperatiivisesta ohjelmoinnista tuttuina muuttujina. Aluksi voi tuntua oudolta, että miten se ohjelmointi sitten muka onnistuu. Hetki voi mennä ennen kuin sisäistää funktionaalisen ohjelmoinnin ajattelutavan, varsinkin jos on aiemmin kovasti jollain imperatiivisella kielellä ohjelmoinnut.

Itse olen kyllä huomannut, kun ensin olen Haskellia kirjoittanut ja sen jälkeen on pitänyt Javalla jotain tehdä, niin jää jotenkin kaipaamaan esim. Haskellista tuttua helppoa listojen käsittelyä, kun joutuu Javassa jonkunlaista listaa käsittelemään. Java saattaa siten taas hetken tuntua hieman kankealta.

Itsekin Haskellia voin suositella, vaikkakaan ei muista funktionaalisista kielistä ole kokemusta. Hyvä paikka aloittaa on http://haskell.org/. Lisäksi kannattaa ainakin tutustua kirjaan Real World Haskell. Ilmeisesti kirjaa on kovin kehuttu, voittipa se jonkun Jolt Award -palkinnonkin. Se löytyy ilmaisesti luettavissa osoitteesta http://www.realworldhaskell.org

Olempa miettinyt, että pitäisi tänne putkaankin enemmän esimerkkejä funktionaalisista kielistä saada. Nyt kun niitä on kovin vähän, jos yhtään. Jos itse innostuisi jotain pientä Haskellilla väkertämään näytille.

map_ kirjoitti:

S x y z = (x z (y z)), eli ensin annetaan z x:lle ja y:lle argumentiksi, ja sitten sovelletaan (x z):n tulosta (y z):n tulokseen.

Onko (x z (y z)) tässä matemaattinen lauseke (x*z*(y*z)) vai jotain muuta? Siis selkokielellä mikä on S:n tulos jos X=2, Y=3 ja Z=4(Mikä on S 2 3 4). Onko se 96 vai jotain muuta?

map_ käytti tuossa lambda-kalkyylissä yleisesti käytettävää merkintää funkiokutsulle: lauseke, joka tavallisesti matematiikassa kirjoitettaisiin "f(x)" kirjoitetaan lambdakalkyylissä vain "f x". Useamman termin tapauksessa lauseke sulutetaan vasemmalle eli "f g x" vastaa funktiokutsua f(g(x)) (eikä f(g)(x) ).

Jälkimmäiseen kysymykseesi ei siten voi vastata, ennen kuin on määrittänyt mitä tarkoittaa funktiokutsu numeroiden yhteydessä. S-kombinaattorin tarkoitus onkin ottaa parametreinaan muita funktioita, ja koostaa niistä uusi funktio.

Ei tarkoita tuota kertolaskua. Tuossa nuo x y ovat jonkinlaisia funktioita. Tuossa lasketaan (y z) ja sen tulos annetaan (x z):lle. Ehkä wikipedian artikkelista löytynyt esimerkki voisi selventää tätä:

((S K K) x)
    = (S K K x)
    = (K x (K x))
    = x

Eli tuossa noilla S ja K kombinaattoreilla saavutetaan sama tulos kuin identiteettikombinaattorilla.

Joo tajusin. Aloittelin koodaamaan haskelilla, mutta tuli onglema. Jos funktiolla on monta parametriä miten niihin voidaan viitata ohjelmassa. Laitan koodin tähän.

itsearvo :: Integer -> Integer
itsearvo x
			| x<0 = -x
			| otherwise = x

samaItsearvo :: (Integer,Integer) -> Bool
samaItsearvo = itsearvo (EKA PARAMETRI) == itsearvo (TOKA PARAMETRI)

Pitäisi siis saada parametreihin viittaavat koodit kohtiin EKA PARAMETRI ja TOKA PARAMETRI.

Haetko jotain tällaista:

samaItseisarvo :: Integer -> Integer -> Bool
samaItseisarvo x y = itseisarvo x == itseisarvo y

Toki tuon voi tuplenkin avulla tehdä

samaItseisarvo2 :: (Integer,Integer) -> Bool
samaItseisarvo2 (x,y) = itseisarvo x == itseisarvo y

Itseasiassa tarvitsee toteuttaa vain toinen ja sitten käyttää joko curry tai uncurry funktiota, riippuen siitä kumman toteutit, niin saa toisen, jos siis tarvitsee molempia. Näin ikään

itseisarvo = curry itseisarvo2

tai sitten

itseisarvo2 = uncurry itseisarvo

Sisuaski kirjoitti:

Useamman termin tapauksessa lauseke sulutetaan vasemmalle eli "f g x" vastaa funktiokutsua f(g(x)) (eikä f(g)(x) ).

Käsittääkseni yleensä f g x = (f g) x /= f (g x), eli juuri toisin päin.

nörtti kirjoitti:

samaItsearvo :: (Integer,Integer) -> Bool
samaItsearvo = itsearvo (EKA PARAMETRI) == itsearvo (TOKA PARAMETRI)

Päärynämies näyttikin jo miten tuon voi tehdä. Haskellissa käytetään yleensä kaksi parametriä ottavaa versiota tuplen sijaan, koska partial application on kivaa.

Suosittelen tätä: http://learnyouahaskell.com/. Lähtee ihan perusteista liikkeelle ja selittää asiat hyvin. Sopii minusta paremmin aloittelijoille kuin Real World Haskell.

Kun sanotaan, ettei Haskellissa ole muuttujia, tarkoitetaan että kaikki muuttujat ovat vakioita (single assignment). Esimerkiksi x = x + 1 ei tarkoita ollenkaan samaa kuin imperatiivisissa kielissä.

Kovin montaa puhtaasti funktionaalista kieltä en tiedä, jos ei pieniä leikkikieliä lasketa. Clean on yksi vaihtoehto, mutta Haskell on kyllä selvästi suosituin.

funktio kirjoitti:

Sisuaski kirjoitti:

Useamman termin tapauksessa lauseke sulutetaan vasemmalle eli "f g x" vastaa funktiokutsua f(g(x)) (eikä f(g)(x) ).

Käsittääkseni yleensä f g x = (f g) x /= f (g x), eli juuri toisin päin.

Hupsista, joo, hyvä kun korjasit.

Clean vaikuttaa aika mielenkiintoiselta uniikkityyppeineen mutta sen ällöttävät verkkosivut ovat tähän mennessä hidastaneet enempää tutustumista :>. Voisi kai siihen kuitenkin tutustua kun tulkki on kuitenkin sentään vapaata koodia.