[BLOG] Introduktion till programmering, del 6- Funktionell p

I denna kategori diskuteras inlägg på blog.m.nu
Användarvisningsbild
supportM
Moderator
Inlägg: 342
Blev medlem: 20 aug 2014, 10:27
Ort: Linköping

[BLOG] Introduktion till programmering, del 6- Funktionell p

Inlägg av supportM » 22 okt 2014, 10:30

Detta inlägg kommer från ett blogginlägg. För att läsa originalinlägget, klicka här »

Ännu en onsdag, introduktionen fortsätter!

Bild

Förra veckan tittade vi på import av bibliotek och grundläggande GPIO på Raspberry Pi .

Som du kanske minns har vi kort nämnt Funktionell programmering i ett av de första avsnitten. Nu ska vi titta lite mer på det, och på samma gång lära oss olika sätt att lösa samma problem!

När man programmerar funktionellt försöker man alltid bryta ner problemen i små funktioner, och låter dessa samverka för att skapa en större helhet. Matematiska funktioner är en inspiration, men dessa är också relativt lätta att implementera. Här är ett exempel på den matematiska funktionen "fakultet", skriven i Python:
def fak (x):
 svar = 1
 while x > 0:
  svar = x*svar
  x = x-1
 return svar
OBS! Använder ett enda mellanslag för indenteringen i denna kod, för TAB ville inte fungera här i blogginlägget. Därför är inte koden riktigt lika tydlig som vanligt.

Första raden sätter vi "svar" till 1, annars blir beräkningen i while-loopen (svar = x*svar) alltid 0, och det vill vi ju inte. Loopen körs sedan tills vi kommer ner till 0, och därefter returneras svaret. Det finns ett problem med den här koden. Kan du upptäcka vad? Svar finns i "spoiler"-rutan här nedan!

[spoiler title='Felet med koden?' collapse_link='true']In-värdet till funktionen, x, kan vara godtyckligt heltal. Fakultetsfunktionen fungerar dock bara för alla heltal större än noll. Lösning? Man inför en kontroll av invärdet innan resten av funktionen körs:
if x 0)"
else:
return fakiter(x, 1)

def fakiter (x, acc):
if x == 1:
return acc
else:
return fakiter (x-1, acc*x)
Men, hallå! Det här blev ju inte mindre kod!

Nej, det är sant. Det är mer kod nu (eftersom det är två funktioner). Men hälften av koden är en stödfunktion som först kontrollerar invärdet (att det är ett heltal, och större än 0), och sedan anropar beräkningsfunktionen. "fakiter" är själva beräkningsfunktionen, men då den också har ett ackumulator-invärde kan man dölja detta för användaren med en "frontfunktion", som jag har gjort.

Nu är ju Python smart på många sätt, så vi kunde lika gärna sätta ett standardvärde på acc=1 i fakiter(). Då hade vi kunnat skippa hjälpfunktionen, eller placera felkontrollen i samma funktion.

Så vad händer då i funktionen "fakiter"? Jo, först kontrolleras om det nuvarande talet är 1. I så fall avbryts beräkningen och resultatet, acc, returneras. Är x större anropar vi funktionen på nytt, men vi minskar x med 1 och multiplicerar vårt nuvarande resultat med x. Man kan alltså säga att anropen sker så här (användaren anropar bara "fak(3)":
fak(3)
fakiter(3, 1)
fakiter(3-1, 1*3) -> fakiter(2, 3)
fakiter(2-1, 3*2) -> fakiter(1, 6)
x == 1, returnera 6
Smart, eller hur? Men nu ska vi titta på det andra sättet att beräkna rekursivt. Det är ännu häftigare!

Vi behåller vår hjälpfunktion, mest för att det är praktiskt att kontrollera invärden:
def fak (x):
if not isinstance(x, int) or x 0)"
else:
return fakrec(x)

def fakrec (x):
if x == 1:
return 1
else:
return x * fakrec(x-1)
Denna funktion ser hyfsat lika ut, eller hur? Beräkningen sker dock helt annorlunda. I den första varianten hade vi en ackumulator som samlade in vårt resultat, men här bygger vi upp beräkningen innan hela uttrycket beräknas. Ungefär så här kan man säga att exekveringen ser ut (återigen, endast fak(3) anropas av användare):
fak(3)
fakrec(3)
3 * fakrec(2)
3 * 2 * fakrec(1)
3 * 2 * 1
6
I det fallet x är 1 i den här funktionen returneras 1. Detta är eftersom vi sköter multiplikationen samtidigt som vi gör vårt rekursiva anrop (sista raden i fakrec), så vi vill avsluta med ett heltal.

En sak som också är bra att tänka på är att "return" alltid avslutar funktionen. Det betyder att "else:" i våra rekursiva funkioner är onödigt att skriva, eftersom return-anropet inuti if-satsen bara anropas när vi är färdiga med beräkningen.

Här är de båda funktionerna, utan "else:" och med standardvärde på acc:
def fakrec (x):
if x == 1:
return 1
return x * fakrec(x-1)

def fakiter (x, acc=1):
if x == 1:
return acc
return fakiter (x-1, acc*x)
Det var lite om rekursion, och allt för denna vecka!

Nästa vecka tar vi upp avancerade datatyper och objekt! Håll ut så länge :)

Uppdatering: Nästa avsnitt finns nu uppe!