Göm menyn

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.

Kapitel 19-20 i studiematerialet förbereder för denna laboration.

OBS! Från och med den här laborationen ska ni laborera i par. För att bli tilldelad en grupp behöver ni först registrera er i Webreg. OBS! Registrera er först när ni är färdiga med labb 3 i TDDC66 om ni läser den kursen.

  • Logga in på Webreg och skriv upp dig i någon av grupperna under fliken KLAR MED LABB 3.
  • Skriv upp dig i den klassen vars labbpass du vill gå på under TDDD73, det spelar inte någon roll för kursen vilken ni väljer men tänk på att om ni väljer er egna minimerar ni risken för schemakrockar. Det behöver inte vara samma grupp som under de första laborationerna.

Om något blir fel i anmälan, kontakta din labbassistent. Börja inte med laborationen förrän du har hittat någon att jobba med.

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 kapitlet funktionell programmering och du kan läsa mer om det i dokumentationen för Python 3.

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

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

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

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

Övning 403 Skapa en funktion distribute 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.

>>> distribute('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, fMaMaö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.

Uppgift 4A - Potensmängd

Potensmängden för en mängd är mängden av alla möjliga delmängder. Potensmängden av {tiger, lejon} är alltså {{}, {tiger}, {lejon}, {tiger, lejon}}. Observera att den tomma mängden alltid kommer att vara med i potensmängden, eftersom den tomma mängden är delmängd till varje mängd.

Din uppgift är att skriva en funktion powerset som tar en godtyckligt stor mängd och genererar dess potensmängd. För enkelhets skull ska mängderna representeras som listor, både i in- och utdata.

>>> powerset([]) [[]] >>> powerset(["ridcully"]) [[], ['ridcully']] >>> powerset(["ridcully", "librarian"]) [[], ['ridcully'], ['librarian'], ['ridcully', 'librarian']] >>> powerset(["ridcully", "librarian", "rincewind"]) [[], ['ridcully'], ['librarian'], ['ridcully', 'librarian'], ['rincewind'], ['ridcully', 'rincewind'], ['librarian', 'rincewind'], ['ridcully', 'librarian', 'rincewind']]

Det spelar ingen roll om din lösning har elementen eller listorna i en annan ordning. Huvudsaken är att du får med rätt mängder.

I det första exemplet ovan är potensmängden en mängd som bara innehåller den tomma mängden. Det är alltså en mängd i en mängd.

Vi vet från kursen i diskret matematik att om en mängd har n element, är antalet element i potensmängden precis 2n och detta håller alltid, även för tomma mängder. Notera att 20 = 1, och att det faktiskt är ett element i potensmängden för den tomma mängden. En första kontroll kan vara att se om din funktion ger rätt antal delmängder, innan du kollar att de innehåller rätt element.

Du får, men behöver inte, använda listbyggare i din lösning. Du får inte importera någon modul som du inte har skrivit själv. Du får inte heller använda några iterativa strukturer (vanliga for-loopar eller liknande), utan alla former av upprepning ska lösas antingen med hjälp av listbyggare eller med rekursiva funktioner. Observera att användande av nyckelordet for i en listbyggare är tillåtet. (förtydligande 161102 //Anders M.L.)

Börja som vanligt med ett basfall, försök sedan se mönstret för hur resultatet ändras när antalet element ändras.

Testning För att se till att din funktion klarar av uppgiften finns det ett pythonprogram som kör automatisk testning på din kod. Programmet kan antingen hämtas (test_4.py) om du inte befinner dig på datorerna i SU-salarna eller köras direkt från filsystemet (~TDDC66/tester/test_4.py) om du befinner dig på en av datorerna i ovannämnda salar. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 4A.

OBS! Från och med den här laborationen sker redovisning genom versionshanteringsverktyget Subversion. Läs mer om hur det fungerar rent praktiskt i vår introduktion.

Läs mer i reglerna för redovisning om hur ni ska checka in koden.

Vi kommer även att ställa betydligt högre krav på kodkvalitet, så se till att den koden som ni skickar in är väldokumenterad, har docstrings för alla funktioner och så vidare.

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 create_ad(business): def actual_ad(): print("Ät mat från", business) return actual_ad

Här har vi nu en def inuti en def. Funktionen create_ad 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 actual_ad utan använder den som returvärde.

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

>>> advertise_dibbler = create_ad("CMOT Dibbler's") >>> advertise_dibbler <function actual_ad at 0x00C75A08> >>> business = "Harga's House of Ribs" >>> advertise_dibbler() Ä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 advertise_dibbler 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 create_ad definierar den lokala funktionen actual_ad. Denna funktion skickar vi sedan som utdata, så när anropet är klart är advertise_dibbler bundet till en funktion. Så långt är allt väl. Nu är frågan vad advertise_dibbler kommer att skriva ut när den anropas. Där funktionen skapades var business = "CMOT Dibbler's", men den anropas från topploopen i Python, där business = "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 create_ad.

>>> advertise_harga = create_ad("Harga's House of Ribs") >>> advertise_dibbler = create_ad("CMOT Dibbler's") >>> advertise_harga() Ät mat från Harga's House of Ribs >>> advertise_dibbler() Ät mat från CMOT Dibbler's

Övning 405 Skriv en funktion create_lock 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.

>>> my_lock = create_lock(42, 'Lita inte på Lupine!') >>> my_lock <function lock at 0x00C75E40> >>> my_lock(123) Fel kod! >>> my_lock(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

Uppgift 4B

Du har en kompis Daniel som är fysiker. Han arbetar med att simulera raketbanor i Python och behöver din hjälp. Daniel är inte så bra på Python, men desto bättre på fysik.

Daniel vill simulera en rakets färd genom tre faser (start, motor slås av, fallet börjar). Vi kan uttrycka hur högt upp raketen befinner sig vid en tidpunkt t om vi vet fyra saker: när fasen inleddes (tidpunkten t0), hur högt upp den hunnit i början av fasen (h0), dess aktuella hastighet (v0) och hur snabbt raketen accelererar (konstanten a). Sambandet är följande:

h(t) = h0 + v0(t - t0) + 0.5a(t - t0)2

Detta kanske ser ut som en hemskt komplicerad formel, men för att lösa den här uppgiften behöver du inte egentligen förstå hur den funkar. Du behöver bara kunna översätta den till Python.

Daniel har ett simuleringsprogram i Python som tar en funktion av en variabel, och numeriskt försöker hitta när vissa villkor uppfylls. Till exempel kan det svara på frågan när raketen börjar falla, givet en funktion h(t), d.v.s. när är h(t+dt) < h(t)). Problemet är att varje fas har en egen unik h(t)-funktion. Konstanternas värden i fas 2 av en viss simulering vet vi inte innan vi fått utdata från fas 1 (och så vidare), så det går inte att hårdkoda. Här behöver fysikern Daniel din hjälp.

Din uppgift är att skriva en funktion generate_height som tar de fyra konstanterna som indata och ger dig en anonym funktion h(t), som gäller för just denna fas. Daniel vill använda generate_height för att skapa funktioner som han kan skicka in till sin simulator (som du tyvärr inte har tillgång till). Så här ska det fungera:

>>> h_fas_ett = generate_height(0, 0, 0, 290) # (h0, v0, t0, a) >>> h_fas_ett(5) # Vad är höjden, fem sekunder efter start? 3625.0 >>> h_fas_ett # Den inre funktionen ska vara anonym! <function <lambda> at 0x00C75E88>

Alternativt kan det se ut på fölajnde sätt (det viktigaste är att det står <lambda>):

>>> h_fas_ett = generate_height(0, 0, 0, 290) # (h0, v0, t0, a) >>> h_fas_ett(5) # Vad är höjden, fem sekunder efter start? 3625.0 >>> h_fas_ett # Den inre funktionen ska vara anonym! <function generate_height.<locals>.<lambda> at 0x7f4768aede18>

Testning För att se till att din funktion klarar av uppgiften finns det ett pythonprogram som kör automatisk testning på din kod. Programmet kan antingen hämtas (test_4.py) om du inte befinner dig på datorerna i SU-salarna eller köras direkt från filsystemet (~TDDC66/tester/test_4.py) om du befinner dig på en av datorerna i ovannämnda salar. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 4B.

OBS! Från och med den här laborationen sker redovisning genom versionshanteringsverktyget Subversion. Läs mer om hur det fungerar rent praktiskt i vår introduktion.

Läs mer i reglerna för redovisning om hur ni ska checka in koden.

Vi kommer även att ställa betydligt högre krav på kodkvalitet, så se till att den koden som ni skickar in är väldokumenterad, har docstrings för alla funktioner och så vidare.

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 keep_if 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.

>>> keep_if(lambda bokstav: bokstav == 'e' or bokstav == 'm', 'Vimes') 'me' >>> keep_if(lambda bokstav: False, 'Vimes') ''

Övning 410 Skapa en funktion foreach 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.

>>> foreach(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 compose 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 = compose(f, g) >>> h(2) 21

Om du vill ha en lite större utmaning kan du försöka skriva om funktionen compose så att den kan sätta samman funktioner där den andra funktionen g tar godtyckligt antal argument (så exempelvis compose(lambda x: x**2, lambda y,z: y+z)).

Ö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 apply_repeatedly(fn, n, x): res = x for i in range(n): res = fn(res) return res

Funktionen apply_repeatedly 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:

>>> apply_repeatedly(lambda x: x**2, 1, 3) 9 >>> apply_repeatedly(lambda x: x**2, 2, 3) 81 >>> apply_repeatedly(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 apply_repeatedly ä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 repeat 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:

>>> square_thrice = repeat(lambda x: x**2, 3) >>> square_thrice(3) 6561

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

Ledning Hur ser de olika fallen ut?

Om vi tar en funktion f och repeterar den 1 gång, modell square_once = repeat(lambda x: x**2, 1), bör resultatet bli själva funktionen. Vad bör skilja mellan detta och den som repeterats 2 gånger? Mer allmänt, mellan den som repeterats p gånger och den som repeterats p+1 gånger?

Tips I övning 411 skrev du förmodligen funktionen compose. Den kan vara användbar här!

Ö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 kapitlet funktionell programmering. (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 repeat_fold (combine är en så kallad "foldning") från föregående övning ungefär så här:

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

Skriv klart definitionen.

Uppgift 4C

Deluppgift (i) Begreppet glättning (eng. smoothing) är viktigt bl.a. vid signalbehandling. Om f är en funktion och dx ett litet tal, då är den glättade versionen av f den funktion vars värde vid en punkt x är medelvärdet av f(x-dx), f(x) och f(x+dx). Definiera en funktion smooth som tar en funktion av en variabel, innehåller ett steg dx, och ger en glättad version av funktionen. För dessa två uppgifter antar vi att dx = 0.001, vilket är fixt.

Notera att (jämförelsevis små) skillnader relativt körexempel kan uppstå beroende på vilken ordning ni utför additioner. Se exemplet under Wikipedias Floating point accuracy-artikel för förklaring. Här bryr vi oss inte om just denna aspekt.

>>> smoothed_square = smooth(lambda x: x**2) >>> smoothed_square(10) 100.00000066666666 >>> import math >>> smoothed_sin = smooth(math.sin) >>> math.sin(0.456) 0.44036035495318304 >>> smoothed_sin(0.456) 0.44036020816641025

Deluppgift (ii) Skriv funktioner twice_smoothed_square och twice_smoothed_sin, som ger versionerna som glättats två gånger. (Notera skillnaderna bland decimalerna i körexemplen för de en- och två gånger glättade funktionerna.)

>>> twice_smoothed_square(10) 100.00000133333333 >>> twice_smoothed_sin(0.456) 0.4403600613796865

Deluppgift (iii) Ibland vill man glätta en funktion flera gånger, d.v.s. glätta den glättade funktionen. Om man upprepar detta kan man tala om den n-falt glättade funktionen. Definiera en funktion repeatedly_smoothed som tar två argument: en funktion f och ett heltal n. Funktion ska med hjälp av smooth och repeat beräkna den n-falt glättade versionen av f. (fetstil tillagd 161129 //Anders M.L)
Se övningsuppgift 412 för mer information om repeat (tillagd 161201 // Erik Hansson)

>>> fivefold_smoothed_square = repeatedly_smoothed(lambda x: x**2, 5) >>> fivefold_smoothed_square(10) 100.00000333333332 >>> fivefold_smoothed_sin = repeatedly_smoothed(math.sin, 5) >>> fivefold_smoothed_sin(0.456) 0.4403596210198086

Testning För att se till att din funktion klarar av uppgiften finns det ett pythonprogram som kör automatisk testning på din kod. Programmet kan antingen hämtas (test_4.py) om du inte befinner dig på datorerna i SU-salarna eller köras direkt från filsystemet (~TDDC66/tester/test_4.py) om du befinner dig på en av datorerna i ovannämnda salar. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 4C.

OBS! Från och med den här laborationen sker redovisning genom versionshanteringsverktyget Subversion. Läs mer om hur det fungerar rent praktiskt i vår introduktion.

Läs mer i reglerna för redovisning om hur ni ska checka in koden.

Vi kommer även att ställa betydligt högre krav på kodkvalitet, så se till att den koden som ni skickar in är väldokumenterad, har docstrings för alla funktioner och så vidare.

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:

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

Funktionen traverse 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 empty_tree_fn.
  • Om den stöter på ett löv körs leaf_fn på det lövet.
  • Om den stöter på en inre nod körs inner_node_fn 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 empty_tree_fn(): return 0 def leaf_fn(key): return key**2 def inner_node_fn(key, left_value, right_value): return key + left_value

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

>>> traverse([6, 7, 8], inner_node_fn, leaf_fn, empty_tree_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.

Uppgift 4D - Att traversera träd

Deluppgift (i) Definiera funktionen traverse enligt ovan. Du kan anta att användaren alltid ger dig giltiga binära sökträd, som följer beskrivningen i laboration 3. Använd dig av de primitiva hjälpfunktionerna som t.ex. left_subtree istället för att leta i listorna med hjälp av index. Saknas någon sådan funktion, definiera den. (förtydl. av Anders M.L. 161122).

Deluppgift (ii) Använd nu traverse för att definiera en sökfunktion contains_key som söker efter en nyckel i ett binärt träd (inte nödvändigtvis ett väl sorterat sådant). Uppgiften är alltså i praktiken att definiera de tre funktionerna som ska skickas in till traverse - inre-nod, löv och tomt-träd - för att åstadkomma en sökning.

>>> contains_key(6, [6, 7, 8]) True >>> contains_key(2, [6, 7, [[2, 3, 4], 0, []]]) True >>> contains_key(2, [[], 1, 5]) False

Deluppgift (iii) Använd traverse för att definiera en funktion tree_size som beräknar storleken av ett binärt sökträd, d.v.s. det totala antalet löv och inre noder.

>>> tree_size([2, 7, []]) 2 >>> tree_size([]) 0 >>> tree_size([[1, 2, []], 4, [[], 5, 6]]) 5

Deluppgift (iv) Använd traverse för att definiera en funktion tree_depth som beräknar djupet av ett binärt sökträd, d.v.s. antalet noder i den längsta vägen från roten till ett löv.

>>> tree_depth(9) 1 >>> tree_depth([1, 5, [10, 7, 14]]) 3

Testning För att se till att din funktion klarar av uppgiften finns det ett pythonprogram som kör automatisk testning på din kod. Programmet kan antingen hämtas (test_4.py) om du inte befinner dig på datorerna i SU-salarna eller köras direkt från filsystemet (~TDDC66/tester/test_4.py) om du befinner dig på en av datorerna i ovannämnda salar. Öppna filen och läs instruktionerna för hur man för att se hur man kör programmet och kör det sedan för att testa labb 4D.

Feedback För att ständigt förbättra undervisningen uppskattar vi om ni individuellt fyller i följande formulär. Notera att det är friviligt och inte påverkar betygen på något sätt.

OBS! Från och med den här laborationen sker redovisning genom versionshanteringsverktyget Subversion. Läs mer om hur det fungerar rent praktiskt i vår introduktion.

Läs mer i reglerna för redovisning om hur ni ska checka in koden.

Vi kommer även att ställa betydligt högre krav på kodkvalitet, så se till att den koden som ni skickar in är väldokumenterad, har docstrings för alla funktioner och så vidare.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-12-09