Laboration 4 - Funktionell programmering

4.1 Inledning

Syftet med denna laboration är framför allt att öva på funktionell programmering. I denna laboration får du pröva på att hantera funktioner som in- och utdata, och att behandla dessa på ett mer matematiskt vis. Du kommer att få öva på att skapa mer generella funktioner för att behandla (marginellt mer) avancerade datastrukturer, och dessutom skriva ett par enkla exempelprogram som antyder hur detta kan användas inom beräkningsmatematik. Dessutom övas konceptet listbyggare, och det visas hur det kan knytas samman med det funktionella tänkandet.

Föreläsning 8 förbereder för denna laboration.

4.2 Listbyggare

Listbyggare (eng. list comprehensions) går ut på att man definierar en lista utifrån någon viss egenskap, till exempel genom att behandla alla element i en gammal lista på något vis. Detta behandlades i föreläsning 8 och du kan läsa mer om det i dokumentationen för Python 3.

Övning 401 Skapa en funktion dubblera_element som tar en lista med tal, och dubblerar alla element i listan. Använd listbyggare.

>>> dubblera_element([1, 2, 3, 4]) [2, 4, 6, 8]

Övning 402 Skapa en funktion alla_par_ordnade som tar ett tal n, och som med hjälp av listbyggare skapar alla par av element från 0 till n.

>>> alla_par_ordnade(2) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

Övning 403 Skapa en funktion distribuera som tar ett element och lägger in det i samtliga dellistor i en lista. Använd listbyggare. Koden inuti funktionen ska inte behöva bli mer än en rad.

>>> distribuera('k', [['o'], [0, 1, 2], ['o','o']]) [['o', 'k'], [0, 1, 2, 'k'], ['o', 'o', 'k']]

Övning 404 I Pascals triangel är varje tal summan av de två tal som står ovanför, förutom i kanterna där vi har ettor. Utöver att vara ett snyggt arrangemang av siffror är Pascals triangel ett visuellt uttryck för binomialkoefficienter, även kända som "n över k" som vi snubblade över i uppgift 1A.

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

Skriv en funktion pascal som givet ett tal n genererar de n första raderna i Pascals triangel till och med en viss rad. Svaret ska representeras som listor i listor, och du ska använda listbyggare för att lösa uppgiften.

>>> pascal(4) [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]

Du har tidigare skrivit en användbar funktion som kan användas för att generera talen i triangeln.

4.3 Funktioner som utdata

Det är ofta användbart att kunna skapa funktioner som skapar nya funktioner enligt någon viss specifikation. För att förstå hur man arbetar med detta, och för att förstå vad för slags information en funktion kan ha tillgång till, är det värt att ta en titt på begreppet closure.

Vi börjar med ett exempel:

def skapa_reklamfunktion(ställe): def faktiska_utskriftsfunktionen(): print("Ät mat från", ställe) return faktiska_utskriftsfunktionen

Här har vi nu en def inuti en def. Funktionen skapa_reklamfunktion kommer att returnera en funktion, nämnligen den lokala funktion som vi definierat på raderna ovanför return. Notera att det inte finns några parenteser på sista raden. Vi anropar inte funktionen faktiska_utskriftsfunktionen utan använder den som returvärde.

Nu ska vi försöka använda skapa_reklamfunktion.

>>> gör_reklam = skapa_reklamfunktion("CMOT Dibbler's") >>> gör_reklam <function faktiska_utskriftsfunktionen at 0x00C75A08> >>> ställe = "Harga's House of Ribs" >>> gör_reklam() Ät mat från <???>

Vad kommer att stå på sista raden i exemplet ovan? Vi börjar exemplet ovan med att göra en tilldelning som binder namnet gör_reklam till något. Detta något är det som kommer ut från beräkningen till höger om likhetstecknet. Vad som händer, steg för steg, är nu att vi inuti skapa_reklamfunktion definierar den lokala funktionen faktiska_utskriftsfunktionen. Denna funktion skickar vi sedan som utdata, så när anropet är klart är gör_reklam bundet till en funktion. Så långt är allt väl. Nu är frågan vad gör_reklam kommer att skriva ut när den anropas. Där funktionen skapades var ställe = "CMOT Dibbler's", men den anropas från topploopen i Python, där ställe = "Harga's House of Ribs". Så, vilket värde väljs?

I Python, och många andra språk, är svaret "CMOT Dibbler's". Vi ser alltså att vi har möjligheten att packa ihop en funktion och en uppsättning variabelvärden, så att funktionen "minns" dessa oavsett hur det ser ut utanför. Det här paketet av funktion och omgivning kallas ett closure.

Det här gör också att vi kan skapa olika reklamfunktioner - som inte kommunicerar med varandra - med hjälp av skapa_reklamfunktion.

>>> harga_reklam = skapa_reklamfunktion("Harga's House of Ribs") >>> dibbler_reklam = skapa_reklamfunktion("CMOT Dibbler's") >>> harga_reklam() Ät mat från Harga's House of Ribs >>> dibbler_reklam() Ät mat från CMOT Dibbler's

Övning 405 Skriv en funktion skapa_kodlås som tar en kod och ett hemligt meddelande, och ger en kodlåsfunktion. Den funktion som returneras ska inte returnera det hemliga meddelandet förrän den hemliga koden har givits.

>>> mitt_lås = skapa_kodlås(42, 'Lita inte på Lupine!') >>> mitt_lås <function lås at 0x00C75E40> >>> mitt_lås(123) Fel kod! >>> mitt_lås(42) Lita inte på Lupine!

4.4 Anonyma funktioner, λ

Hittills har vi knutit alla funktioner vi har skapat till namn med hjälp av def. Det behöver man inte nödvändigtvis göra. För enklare beräkningar kan det ibland räcka det med ett λ-uttryck (uttalas och skrivs normalt lambda). När du skriver sådana räcker det med två delar: inparametrar och utdata.

>>> lambda x,y: x + y <function <lambda> at 0x00C759C0> >>> (lambda x,y: x + y)(1, 2) 3

Lambda kan enbart innehålla uttryck (d.v.s. man kan inte ha satser som t.ex. if i ett lambda), men i gengäld behöver man inte skriva return för att skicka tillbaka något. Det sker automatiskt. Det andra exemplet ovan visar att vi kan skapa och köra ett lambda i ett enda steg.

Övning 406 Skriv ett lambdauttryck som tar ett heltal som inargument och dubblerar det.

Övning 407 Skriv ett lambdauttryck som tar två inargument och ger summan av kvadraterna på argumenten.

Övning 408 Man kan, även om det blir lite komplicerat, skriva lambdan inuti lambdan. Skriv ett lambdauttryck som tar ett tal x som argument och ger dig en anonym funktion som resultat. Denna anonyma funktion ska i sin tur ta ett argument y, och ge summan av de båda talen x och y. Om du skriver detta vid Python-prompten ska det se ut ungefär så här:

>>> (lambda <din kod här>)(5) # ger en funktion som lägger till 5 till talet y <function <lambda> at 0x00C756A8> >>> (lambda <din kod här>)(5)(3) # applicera funktion ovan med inargumentet 3 8

4.5 Funktioner som indata

Vi har sett att det går att skapa funktioner som skapar och ger funktioner som utdata. Nu går vi åt andra hållet, och skapar funktioner som tar funktioner som indata, så kallade högre ordningens funktioner.

Övning 409 Skriv en rekursiv funktion behåll_bara som har som indata ett predikat (en funktion som kontrollerar indata enligt något kriterium och ger svaret True eller False) och en textsträng. De bokstäver som ska behållas är de som uppfyller kriteriet.

>>> behåll_bara(lambda bokstav: bokstav == 'e' or bokstav == 'm', 'Vimes') 'me' >>> behåll_bara(lambda bokstav: False, 'Vimes') ''

Övning 410 Skapa en funktion för_varje som tar en funktion och en lista, och ger en lista där funktionen applicerats på varje element i listan. Använd gärna listbyggare.

>>> för_varje(lambda x: x**3, [0, 1, 2, 3]) [0, 1, 8, 27]

Övning 411 Om f och g är två matematiska funktioner kan vi kombinera dem till en ny funktion h som vi kan definiera som h(x) = f(g(x)). Här antar vi att både f och g vardera tar ett argument. Skriv en funktion sammansättning som tar två Python-funktioner och ger dig den sammansatta funktionen.

>>> def f(x): return x + 10 >>> def g(y): return 2 * y + 7 >>> h = sammansättning(f, g) >>> h(2) 21

Om du vill ha en lite större utmaning kan du försöka skriva om funktionen sammansättning så att den kan sätta samman funktioner som tar godtyckligt många argument.

Övning 412 Ibland kan man vilja kombinera en funktion med sig själv flera gånger. Detta kan vi t.ex. åstadkomma med den här funktionen:

def kör_n_gånger(fn, n, x): res = x for i in range(n): res = fn(res) return res

Funktionen kör_n_gånger tar en funktion fn, ett tal n som är antalet gånger vi ska upprepa och ett startvärde x. Vi kan t.ex. testa att upprepa kvadrering av tal så här:

>>> kör_n_gånger(lambda x: x**2, 1, 3) 9 >>> kör_n_gånger(lambda x: x**2, 2, 3) 81 >>> kör_n_gånger(lambda x: x**2, 3, 3) 6561

Att köra kvadrering en gång på talet 3 ger givetvis 9 som resultat. Att köra kvadrering två gånger innebär att vi tar resultatet av den första omgången och kvadrerar det igen, vilket ger resultatet 81.

Funktionen kör_n_gånger är i sig inte så tokig, men nu vill vi ha en funktion som kan generera nya funktioner som gör detta lite mer generellt. Definiera därför en rekursiv funktion upprepa som tar en funktion och det antal gånger den ska appliceras. Resultatet ska vara en ny funktion som applicerar funktionen rätt antal gånger på indata. Följande exempel förklarar lite tydligare vad funktionen förväntas göra:

>>> kvadrera_tre_gånger_i_rad = upprepa(lambda x: x**2, 3) >>> kvadrera_tre_gånger_i_rad(3) 6561

I exemplet ovan skapar vi först funktionen kvadrera_tre_gånger_i_rad och sedan applicerar vi den på talet 3. Detta bör ge resultatet ((3^2)^2)^2 = (9^2)^2 = 81^2 = 6561.

Övning 413 Detta är en lite svårare version av föregående övning. Antag att du har en funktion combine som den du sett i föreläsning 8. (Koden finns i combine.py). Funktionen fungerar typiskt så här: combine(f, [0, 1, 2, 3]) = f(f(f(0, 1), 2), 3). Vi kan använda combine för att definiera funktionen upprepa från föregående övning ungefär så här:

>>> def upprepa(fn, n): return combine( ... )

Skriv klart definitionen.

4.6 Rekursiva strukturer och högre ordningens funktioner

När vi behandlar rekursivt definierade strukturer är ett bra angreppssättet ofta "gör X i basfallet, gör Y annars". När vi i övning 318 i laboration 3 skrev ut nycklarna i ett (av en händelse sorterat) träd handlade det om två olika uppsättningar instruktioner:

1. Basfall
   1. Om vi kommit till ett tomt träd: gör ingenting
   2. Om vi kommit till ett löv: skriv ut nyckeln
2. Om vi kommit till en inre nod: gå vidare med vänster träd, skriv sedan ut inre nodens nyckel, gå sedan vidare med höger träd

Nu vill vi generalisera hanteringen av binära träd och definiera en funktion traversera som tar ett binärt sökträd (definierat som i laboration 3) och inte mindre än tre funktioner:

• tomt-träd-funktion som inte tar några argument
• löv-funktion som tar ett argument - nyckeln för lövet
• inre-nods-funktion som tar tre argument - nyckeln för den inre noden, samt värdet av vänster respektive höger subträd.

Funktionen traversera ska systematiskt gå igenom hela trädet och agera på följande sätt:

• Om den stöter på ett tomt träd körs tomt-träd-funktion.
• Om den stöter på ett löv körs löv-funktion på det lövet.
• Om den stöter på en inre nod körs inre-nods-funktion på den aktuella nyckeln och resultatet av att traversera vänster respektive höger subträd.

Det är kanske lättare att se hur detta fungerar genom ett exempel. Kom ihåg att trädet [6, 7, 8] är en representation av ett träd som rent strukturellt ser ut så här:

7 / \ 6 8

Vi definierar tre funktioner som vi tänker oss att köra på olika delar av av trädet. Varje tomt träd får resultatet 0, varje nyckel kommer att kvadreras och för varje inre nod summerar vi nyckelvärdet med värdet från vänster gren. Den högra grenen ignoreras.

def tomt_träd_fn(): return 0 def löv_fn(nyckel): return nyckel ** 2 def inre_nod_fn(nyckel, vänster_värde, höger_värde): return nyckel + vänster_värde

Om vi nu traverserar vårt exempelträd med dessa funktioner får vi följande resultat:

>>> traversera([6, 7, 8], inre_nod_fn, löv_fn, tomt_träd_fn) 43

I den inre noden beräknar vi alltså värdet av de två subträden. Vänster subträd visar sig vara ett löv (6), och lövfunktionen ger tillbaka värdet 36 (nyckel 6, 6^2=36). På samma sätt visar sig höger subträd vara ett löv, med följden att vi skickar tillbaka värdet 8^2 = 64. Beräkningen från den inre noden kan nu genomföras. Summan nyckel + vänster_värde blir 7 + 36 = 43.

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2012-10-03