8. Abstraktion

Gammal labb, från 2019

Studiematerial

Innan denna labb påbörjas ska följande studiematerial ha lästs:

• Dataabstraktion

Det är också till hjälp att ha gått på seminarium 10.

8.1. Inledning

Denna laboration handlar om att lära sig tänka i lager av abstraktioner och funktionalitet, och att hantera detta på ett klokt vis. Mer specifikt kommer vi att arbeta med dataabstraktion och med de lager av funktionalitet som behövs för att stödja abstraktionen.

Detta görs i 4 steg, labb 8A till 8D. När ni implementerar dessa steg måste det framgå tydligt var era egna funktioner finns och vilken del av labb 8 de tillhör. Ett bra sätt att göra detta är att lägga all egen kod i separata filer, t.ex. la8a.py, la8b.py, och så vidare. Ni demonstrerar resultatet en gång efter labb 8C och därefter en gång när hela labben är klar.

Checka in och pusha kod ofta, gärna flera gånger om dagen, även om ni inte är klara med labben. Dels är versionshantering bra för att få "kontrollpunkter" som man kan backa till vid behov, dels ger regelbundna incheckningar en tydlig logg över hur arbetet har gått till. Den loggen är inte minst bra för att demonstrera att ni har skrivit programkoden själva!

Som exempel för dataabstraktion kommer vi att använda ett system för att hantera en personlig almanacka. Någon har redan börjat utveckla detta system, och har både skapat en design och till stora delar implementerat designen i Python. Tyvärr följs inte riktigt de riktlinjer som vi har diskuterat i studiematerialet! Du ska därför ta över arbetet:

• I en av almanackans 4 filer finns det funktioner som bryter mot abstraktionen och som måste skrivas om.

• I andra filer finns det funktioner som inte ens är implementerade, och som måste skrivas från början.

Men först ska du få experimentera lite med den existerande implementationen så att du får en bättre uppfattning om hur den är tänkt att fungera.

8.1.1. Ladda ner den ursprungliga implementationen

Den ursprungliga implementationen finns i följande filer:

• calendar.py
• booking.py
• calendar_abstraction.py
• output.py

För att så enkelt som möjligt kunna testa almanacksystemet bör du ladda ner alla filerna och spara dem i en och samma mapp. Du kommer att modifiera dem senare, så spara dem i din arbetskopia för git och checka in dem!

8.1.2. Testa den ursprungliga implementationen

För att testa läser du in filen calendar.py på följande sätt:

Efter det kan du skapa nya almanackor med hjälp av funktionen create, och visa vilka almanackor som finns med funktionen show_calendars.

När man har skapat en almanacka för en person kan man även boka möten för den personen med funktionen book samt visa alla bokningar för den personen en viss dag med funktionen show.

Med funktionen save kan man även spara alla almanackor i en fil och sedan ladda in dem igen med funktionen load (se hur man anropar dessa funktioner under rubriken Användargränssnittsfunktioner nedan).

Övning 801 Ladda in almanackan och testa de användarfunktioner som finns beskrivna i listan nedan. Pröva att skapa ett par almanackor, boka möten i dem och visa vilka möten som finns bokade en viss dag. Pröva också att importera ditt eget schema och se hur det ser ut.

8.1.3. Användargränssnittsfunktioner

Nedan följer en sammanfattad förklaring på de användargränssnittsfunktioner som finns. Testa gärna!

help()

Ger en påminnelselista.

show_calendars()

Visar vilka almanackor som finns.

create(cal_name)

Skapar en ny almanacka med det angivna namnet.
Exempel: create("Kaylee")

show(cal_name, d, m)

Visar alla bokningar för den angivna dagen.
Exempel: show("Inara", 1, "jul")

book(cal_name, d, m, t1, t2, subject_text)

Bokar ett nytt möte i den angivna almanackan.
Exempel: book("Kaylee", 12, "nov", "19:00", "21:00", "Repair engine")

remove(cal_name, d, m, start)

Avbokar ett möte i almanackan. Denna implementerar du i 8C.
Exempel: remove("Kaylee", 12, "nov", "19:00")

save(filename)

Sparar samtliga existerande almanackor i en extern fil.
Exempel: save("testdata")

load(filename)

Laddar in almanackor från en extern fil. Detta ersätter alla nuvarande almanackor.
Exempel: load("testdata")

8.2. Almanackans nuvarande design och implementation

Nu ska vi titta närmare på almanackans design och implementation. Vi går därför tillbaka till början av designprocessen och börjar se på hur almanackan är strukturerad. När vi går vidare genom olika aspekter av designen kommer vi även att se på vad som blev bra, var det finns brister, och varför vi ser detta som brister.

8.2.1. Specifikation av datatyper för almanackan

Den ursprungliga utvecklaren började med att tänka genom vilka datatyper som behövs och hur dessa ska hänga ihop (se slutet av studiematerialet för dataabstraktion för mer detaljer om syntaxen för dessa beskrivningar).

  hour: integer                      # timme -- lagrar ett heltal
  minute: integer                    # minut
  time: <hour, minute>               # klockslag (absolut tid på dagen)
  time_span: <time, time>            # tidsrymd med start och slut
  duration: <hour, minute>           # varaktighet (hur länge ett time_span varar)
                                     # (det är skillnad på "2 timmar" och "klockan 02"!)

  day: integer                       # dag
  month: string                      # månad
  date: <day, month>                 # datum med dag och månad
  
  subject: string                    # ärende för ett möte
  appointment: <time_span, subject>  # möte

  calendar_day: {{appointment}}*     # kalenderdag som sekvens av möten
  calendar_month: {{calendar_day}}*  # kalendermånad
  calendar_year: {{calendar_month}}* # kalenderår

Detta fungerar bra för den funktionalitet vi vill ha och vi har just nu ingen anledning att ändra på det. Men tänk på att detta i princip bara är en designspecifikation på hög nivå: Vi vill att dessa datatyper ska existera och att de ska vara implementerade på ett lämpligt sätt. Vi har ännu inte talat om vilken övrig funktionalitet datatyperna ska ha.

8.2.2. Att konkretisera specifikationen i Python

Man kan nu tänka sig att gå vidare genom att implementera specifikationen "rakt av". Vi vet ju vad som ska lagras: Timmar är heltal, klockslag kan vara enkla tupler av (timme,minut), och så vidare. Då kan en time_span som beskriver tiden mellan 15:15 och 17:00 se ut så här:

span = ((15, 15), (17, 0))

Ett möte (av typ appointment) under denna tidsperiod kan se ut så här:

prep = (((15, 15), (17, 0)), 'Lab prep in Java')

Men vänta nu. Hur ska vi kunna testa om rätt typ skickas in till olika funktioner? Vi kan göra detta genom att lägga på en etikett på varje värde. Då blir alla värden istället till tupler som börjar med en etikett:

prep = ('appointment', (('span', (('time', (('hour', 15), ('minute', 15))), ('time', (('hour', 17), ('minute', 0))))), ('subject', 'Lab prep in Java')))

Det här fungerar faktiskt utmärkt som vår representation av möten, i alla fall för tillfället. Men hur ska vi arbeta med de här nästlade tuplerna?

8.2.3. Att använda specifikationen på fel sätt

Det är så klart alltid möjligt att låta all kod i hela almanackan gå direkt på den konkreta representationen som nästlade tupler:

• För att skapa ett möte skapar man en tupel med den önskade strukturen.

• För den senare representationen skulle man kunna ta fram själva ärendedelen – informationsmässigt det som innehåller rubriken för mötet – genom att skriva prep[1][1].

• För själva rubriken "Lab prep in Java" får man gräva i prep[1][1][1].

På liknande sätt skulle vi kunna hantera de andra delarna. I varje funktion som behöver använda denna information skulle vi sedan kunna infoga kodstycket med alla index här ovan. Det är möjligt, men har flera problem:

• Koden blir så oläslig att du inte ens själv vet om du har skrivit rätt

• Det blir svårt för utomstående att förstå och bygga vidare på din kod

• Det blir osmidigt att ändra representation

8.2.4. Att införa dataabstraktion

För att undvika de problemen skapar vi ett lager av funktioner som hanterar just datalagringen.

• För att skapa ett möte anropar man new_appointment(timespan, subject).

• För att ta fram själva ärendedelen anropar man get_subject(prep).

• För själva rubriken "Lab prep in Java" får man anropa subject_text(get_subject(prep)).

Om vi sedan bestämmer oss för att det är bättre att lagra mötestid på något annat vis (kapsla i egna objekt, göra ett dictionary eller låta get_subject() slå upp information i en SQL-databas), behöver vi bara ändra i just funktionen get_subject(). Alla de andra potentiella funktionerna – från bokning i almanackan via filtrering/sökning till eventuella mobilinterface – fortsätter fungera som de gjort tidigare.

Vi har nu börjat definiera ett abstraktionslager. Målet med detta är bland annat att almanackans gränssnitt mot terminalfönstret (create, show_calendars, ...) inte ska behöva skrivas i ren Pythonkod som bara manipulerar tupler och listor på låg nivå:

Almanackans gränssnitt mot terminalfönstret

Abstraktionslager för datatyper

Python

Vi behöver dock lite mer funktionalitet än bara de tre funktioner som vi gav exempel på ovan. Det ska vi titta på snart.

8.2.5 Typer och typsignaturer

Vi ska strax diskutera vilka funktioner (operationer) som behövs för att slutföra vårt lager av dataabstraktion i almanackan. När detta blir klart kommer vi också ett steg närmare mot att ha definierat en abstrakt datatyp, även om vi inte går så långt att vi inför matematiska specifikationer av vad varje operation gör. Men innan detta måste vi se hur vi åtminstone kan beskriva den förväntade datatypen för funktionernas parametrar och returvärden.

Till skillnad från språk som Java, Haskell och Ada är inte Python statiskt typat. Det innebär att språket inte gör någon kontroll av att data av rätt typer kommer in i funktionerna innan de körs. Vi kan exempelvis skriva kod där en funktion "väntar sig" att få in en lista, och sedan i själva anropet skicka in en textsträng. Python kommer inte stoppa det (förrän det kraschar när programmet körs och försöker göra något som man inte kan göra med textsträngar).

I denna labb kommer vi att skicka runt data av egendefinierade slag. För att hålla koll på vad funktioner gör, och inte få oväntade effekter, skriver vi själva upp vad för slags indata funktionen väntar sig, och vad den ska ge åter (en typsignaturer). Detta är ett matematiskt sätt att beskriva funktioner i allmänhet, och är inte begränsat till de datatyper som Python har inbyggt (som string, int, med flera). Om vi ser på trädet från laboration 4 kan vi se att några typsignaturer är

is_tree: objekt -> sanningsvärde

key: Tree -> Heltal

new_tree: Tree x Tree -> Tree

Vad det betyder är det naturliga: "new_tree" tar två argument. Både första och andra argumentet väntas vara träd, och det funktionen ger tillbaka är isåfall ett träd. Notationen är precis samma som i den diskreta matematiken. Formellt beskriver man en funktion från den kartesiska produkten mellan mängden Tree och mängden Tree (därav krysset - kartetisk produkt) till mängden av Tree. Rent praktiskt: har man en funktion som tar in argument av olika typer, skriver man mängderna i samma ordning som argumenten och sätter kryss mellan.

Överkurs (inte nödvändig): För den som har specialintresse, finns en motsvarande analys av traverse här.

OBS! I denna laboration används typsignaturer istället för docstrings! Även om pythonstandarden säger att docstrings ska användas säger den också att reglerna kan överskridas av lokala standader.

8.2.6 Funktionerna i dataabstraktionslagret

Den ursprungliga utvecklaren av almanackan har faktiskt också definierat typsignaturer för ett antal funktioner som hör hemma i dataabstraktionslagret. Här finns till exempel konstruktorer, igenkännare och selektorer (se studiematerialet). Här finns också annan funktionalitet som inte har att göra med just datalagringen, men som ändå kan sägas höra till datatypen – till exempel en funktion som testar om två time_span överlappar varandra.

'Bool' nedan betyder 'sanningsvärde' (True eller False).

hour – timme

is_hour: Python object -> Bool	Testar om objektet är en hour.
new_hour: Integer -> hour	Skapar en hour av ett heltal.
get_integer: minute U hour -> Integer	Omvandlar en hour/minute till ett heltal.

minute – minut

is_minute: Python object -> Bool	Testar om objektet är en minut.
new_minute: Integer -> minute	Skapar en minut av ett heltal.
get_integer: minute U hour -> Integer	Omvandlar en minut/timme till ett heltal.

day – dag

is_day: vadsomhelst -> Bool	Testar om objektet är en dag.
new_day: Integer -> day	Skapar en dag av ett heltal.
day_number: day -> Integer	Omvandlar en dag till ett heltal.

month – månad

is_month: vadsomhelst -> Bool	Testar om objektet är en month.
new_month: String -> month	Skapar en month av en textsträng (som "january").
month_name: month -> String	Omvandlar en månad till en textsträng.
month_number: month -> Integer	Omvandlar en month till ett heltal.
number_of_days: month -> Integer	Returnerar antalet dagar i en given månad.

subject – ärende (för ett möte)

is_subject: vadsomhelst -> Bool	Testar om objektet är ärendet för ett möte.
new_subject: String -> subject	Skapar ett ärende med den givna beskrivningen.
subject_text: subject -> String	Plockar fram beskrivningen ur ett ärende.

duration – tidsrymd (ej klockslag, utan en utsträckning, t.ex. 48h 15 minuter)

is_duration: vadsomhelst -> Bool	Testar om objektet är en tidsrymd.
new_duration: hour × minute -> duration	Skapar en tidsrymd av en hour och en minute.
get_hour: duration -> hour	Returnerar timdelen av en tidsrymd.
get_minute: duration -> minute	Returnerar minutdelen av en tidsrymd.

time – klockslag (till exempel 15:45)

is_time: vadsomhelst -> Bool	Testar om objektet är ett time-objekt (klockslag).
new_time: hour × minute -> time	Skapar ett klockslag av en timme och en minut.
get_hour: time -> hour	Returnerar timdelen av klockslaget.
get_minute: time -> minute	Returnerar minutdelen av klockslaget.

time_span – tidsperiod (börjar ett klockslag, slutar ett klockslag)

is_time_span: vadsomhelst -> Bool	Testar om objektet är en time span (tidsperiod).
new_time_span: time × time -> span	Skapar en tidsperiod av två klockslag.
start_time: span -> time	Returnerar det första klockslaget i tidsperioden.
overlap: span x span -> span	Returnerar den överlappande delen av från tidsperioder.
end_time: span -> time	Returnerar det sista klockslaget i tidsperioden.

date – datum

is_date: vadsomhelst -> Bool	Testar om objektet är ett datum.
new_date: day × month -> date	Skapar ett datum av en dag och en månad.
get_month: date -> month	Returnerar månaden i ett datum.
get_day: date -> day	Returnerar dagen i ett datum.

appointment – möte (har ett ärende, och en tidsperiod då det infaller)

is_appointment: vadsomhelst -> Bool	Testar om objektet är en appointment.
new_appointment: span × subject -> appointment	Skapar en appointment av en tidsperiod och ett möte.
get_span: appointment -> span	Returnerar själva tidsperioden ett möte varar i en appointment.
get_subject: appointment -> subject	Returnerar ärendet för ett möte.

calendar_day – dagalmanacka

is_calendar_day: vadsomhelst -> Bool	Testar om objektet är en calendar_day.
new_calendar_day: -> calendar_day	Skapar en tom calendar_day.
is_empty_calendar_day: calendar_day -> Bool	Testar om calendar_dayn är tom.
insert_appointment: appointment × calendar_day -> calendar_day	Ger en ny calendar_day, där indata utökats med ett möte. Inget modifieras.
first_appointment: calendar_day -> appointment	Returnerar den första appointmenten ur en calendar_day.
rest_calendar_day: calendar_day -> calendar_day	Returnerar en ny calendar_day med alla möten utom det första.

calendar_month – månadsalmanacka

is_calendar_month: vadsomhelst -> Bool	Testar om objektet är en calendar_month.
new_calendar_month: -> calendar_month	Skapar en tom calendar_month.
is_empty_calendar_month: calendar_month -> Bool	Testar om en calendar_month är tom.
insert_calendar_day: day × calendar_day × calendar_month -> calendar_month	Utökar en calendar_month med en calendar_day eller ersätter en gammal. Inget modifieras.
calendar_day: day × calendar_month -> calendar_day	Returnerar dagalmanackan (calendar day) för en given dag och en calendar_month.
actual_number_of_days: calendar_month -> Integer	Returnerar dagnumret för den sista dagen i en calendar_month som har bokningar.

calendar_year – årsalmanacka

is_calendar_year: vadsomhelst -> Bool	Testar om objektet är en calendar_year.
new_calendar_year: -> calendar_year	Skapar en tom årsalmanacka.
is_empty_calendar_year: calendar_year -> Bool	Testar om årsalmanackan är tom.
insert_calendar_month: month × calendar_month × calendar_year -> calendar_year	Utökar årsalmanackan med en calendar_month eller ersätter en gammal.
calendar_month: month × calendar_year -> calendar_month	Returnerar calendar_month som svarar mot en given month ur en calendar_year.

8.2.7. Almanackans struktur på högre nivå

Vi såg redan tidigare en illustration av almanackans struktur med ett abstraktionslager i mitten. Beroende på hur man ser det kan man faktiskt identifiera ett lager till:

• Längst ner finns Python och dess kodbibliotek.

• För att hantera de olika delarna i almanackan har vi infört ett abstraktionslager. Vi kan se det som att vi har utökat språket Python med nya typer och nya funktioner som opererar på dessa.

• I nästa lager har vi byggt en rad hjälpfunktioner, dvs funktioner för att boka möten eller visa bokade möten en viss dag. De använder sig av de primitiva funktionerna i lagret under.

• Det översta lagret består av funktioner som användaren av almanackan ska använda. De brukar också kallas för gränssnittsfunktioner, eftersom de utgör gränssnittet mellan användaren och programmet, eller högnivåfunktioner eftersom de utgör den högsta abstraktionsnivån.

Almanackans gränssnitt mot terminalfönstret
Bokningar	Utskrifter
Abstraktionslager för datatyper
Python

Denna kod lagras i 4 filer:

• calendar_abstraction.py innehåller de primitiva funktioner som behövs i abstraktionslagret för de egna datatyperna samt en rad "bra att ha"-funktioner som används för att utföra generella mindre uppgifter som t.ex. att räkna ut längden av en tidsperiod eller jämföra två klockslag.

• booking.py innehåller funktioner som tar hand om större uppgifter som att till exempel boka möten.

• output.py innehåller funktioner för att skriva ut almanacksdata på ett läsbart sätt.

• calendar.py innehåller funktioner för att hantera bokningar i olika almanackor och de gränssnittsfunktioner som användaren kommer åt.

8.3. Arbeta med almanackans abstraktionslager

Nu är det dags att börja skriva om de problematiska delarna av almanackan. Det första steget är att lära sig arbeta med almanackans abstraktionslager.

För att kunna skilja våra olika datatyper åt har vi infört en uppsättning grundläggande funktioner som hjälper oss att paketera information. Vi kan se det som att vi sätter en etikett på varje dataobjekt i almanackan. Precis som vi har sett tidigare talar etiketten om vilken typ av objekt det rör sig om. Den är samtidigt en kvalitetsstämpel som garanterar att innehållet har rätt struktur. Till exempel får inga klockslag 27:15 finnas, inte heller datumet 37 april.

Vårt typmaskineri har två viktiga funktioner som paketerar respektive packar upp dataobjekt. Dessa funktioner heter attach_tag och strip_tag. I praktiken skapar attach_tag en tupel där första värdet är en typetikett (en sträng) och andra värdet är det dataobjekt som ska märkas (t.ex. ett tal eller en lista). Funktionen strip_tag plockar ut dataobjektet. Utöver dessa finns funktionen get_tag som returnerar etiketten och ensure som används för att kontrollera parametrarnas typer och vid behov skriva ut felmeddelanden.

Med detta typmärkningssystem kan vi lättare skapa ett abstraktionslager. Vi använder oss av våra packa-funktioner för att bygga igenkänningsfunktioner, skapa-funktioner och selektor-funktioner. Det är enbart de primitiva funktionerna i filen calendar_abstraction.py som ska känna till den exakta representationen, dvs hur strukturen av den högra delen av dataobjektet ser ut! Övriga funktioner manipulerar almanacksobjekten via de primitiva funktionerna, aldrig direkt.

I exemplet ovan ser vi hur funktionen new_month returnerar ett almanacksobjekt av typen month. Den interna representationen är ('month', 'january'), men det är inget som vi ska fästa något avseende vid. När vi bygger mer abstrakta funktioner kan vi inte utgå från att månader alltid representeras på det här sättet, utan vi använder de primitiva funktionerna för att skapa objekt, känna igen dem samt plocka ut deras delar.

Övning 802 Testa de olika primitiva funktionerna och se att du kan skapa olika slags objekt. Pröva till exempel att skapa följande objekt:

• Skapa klockslaget (time) 13:15 och lagra värdet i den globala variablen t1315.
• Skapa tidsperioden (time_span) 13:15-15:00 och lagra värdet i den globala variabeln ts1315.
• Skapa en calendar_day som innehåller två möten: ett kl 8:15-9:30 för "Redovisning av uppgift", samt ett 13:15-15:00 med "Seminarium i Python". Lagra värdet i den globala variabeln cd15.

8.4. Algoritmer och testning

De primitiva och "bra att ha"-funktionerna i calendar_abstraction.py fungerar som en verktygslåda med vars hjälp vi kan bygga mer avancerade funktioner. Bokning och avbokning av möten har vi redan sett exempel på. För att kunna lösa lite större problem, till exempel hitta lediga tider i en almanacka, behöver vi dock tänka efter lite extra och konstruera algoritmer som kan använda sig av våra primitiva funktioner.

Som exempel kan vi ta en situation där två personer ska försöka bestämma ett möte någon gång under en specifik dag. För att göra detta behöver båda två ha reda på vilka tider som finns lediga så att de kan jämföra dessa med varandra. Hur hittar man de lediga tiderna i en calendar_day? Vi vet att en calendar_day består av en sekvens av mötestider ordnade i kronologisk ordning. På något sätt måste vi gå igenom dessa i tur och ordning och identifiera mellanrummen mellan mötena. Hur kan man göra det?

Samtidigt som ni tar fram en algoritm för att lösa problemet ska ni också bestämma hur algoritmen ska testas. Detta är första gången som ni har en mer komplicerad funktion att testa, där många olika fall kan uppstå. Tidsperioder kan starta, sluta och överlappa varandra på olika sätt. Därför ska ni i nästa uppgift systematisera testningen genom att studera och anppassa en så kallad test driver samt konstruera egna testfall.

OBS! Börja med att på papper beskriva de olika testfall som kan uppstå och skriv ner vad du förväntar dig att funktionen ska göra. Du får skapa ditt eget sätt att formalisera detta, till exempel genom att rita tidsperioder som intervall. När du kommit en bit med att formulera eventuella hjälpfunktioner, fundera på vad för in- och utdata de behöver, och formulera deras typsignaturer. Detta kan vara till hjälp när du sedan konstruerar funktionerna.

Överkurs: Traverse (för intresserade)

OBS! Detta avsnitt behövs inte för att klara kursen.

Vad för typ har den högre ordningens funktion traverse? Vi kan påminna om att man anropar funktionen i stil med traverse( Tree, inner_node_fn, leaf_fn, empty_tree_fn), så den kommer att vara av typ Tree × ngt × ngt × ngt -> ngt. Vi vet också att dessa andra typer "ngt" (som inte nödvändigtvis är samma) kommer att vara funktioner. Dessa har definitions- och värdemängd, och vi skriver deras typer som Df -> Vf. Om vi inte vet något om Df och Vf kan vi alltså skriva signaturen i stil med

traverse: Tree × (?? -> ??) × (?? -> ??) × (?? -> ??) -> ngt.

Vad är dessa typer? För att se det måste vi räkna ut typerna för inner_node_fn, leaf_fn och empty_tree_fn. Det är inte helt uppenbart. Vi kan skicka med funktioner som ger heltal (räkna djupet på ett träd till exempel), eller funktioner som ger sanningsvärden (finns ett element i trädet?). Vi kan alltså inte ha en enda fix Python-typ som utdatatyp för alla funktionerna vi skickar med. Låt oss istället kalla utdatatypen för empty_tree_fn för a (och på så sätt få något sätt att beskriva sambandet mellan in- och utdatatyperna, även om vi inte fixerat ett a). Det är potentiellt en typ som kan innehålla många saker - till exempel "en sträng eller en lista" (en unionstyp). Då kan vi räkna oss fram till att beteendet vi vill ha är

empty_tree_fn: -> a

leaf_fn: Tree -> a

Utifrån det ser vi att en inre-nod-funktion som indata kommer att ta ett heltal (nyckeln) och något av denna typ a (tänk dig att vi befinner oss näst längst ned i trädet och får tillbaka värden från antingen ett tomt träd eller ett löv vi behandlat). Nästa steg är att konstatera att vi borde få samma utdatatyp från alla träd, alternativt att tänka oss ett träd där vänster gren är inre nod och höger gren är ett löv. Både inre-nod och löv-funktionerna borde alltså ha samma utdatatyp, d v s a. Därmed

inner_node_fn: Integer × a × a -> a

Och därmed får vi
traverse: Tree × (Integer × a × a -> a) × (Integer -> a) × (-> a) -> a

Hoppa tillbaka.

Sidansvarig: Peter Dalenius
Senast uppdaterad: 2021-12-03