Göm menyn

7. Abstraktion

Om (och enbart om) du har påbörjat laborationen tidigare år, besök 2012-sidan istället.

7.1. Inledning

I denna laboration kommer du att få tillgång till ett system för att hantera en personlig almanacka. Systemet är byggt i Python, och innehåller ett antal fördefinierade funktioner som kommunicerar med varandra på bestämda sätt. Du ska i denna labb reparera ett par funktioner och bygga ut systemet med ny funktionalitet. Huvudpoängen är att du ska få arbeta med- och skapa abstrakta datatyper.

Kapitel Dataabstraktion och seminarie 10 förbereder för denna laboration.

7.1.1 Datalagret, ett exempel

Vi kan illustrera hur detta fungerar genom ett exempel. I almanackan som den ser ut just nu ser en mötestid mellan 15.15 och 17:00 ut så här:

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

Vi skulle kunna ta fram själva mötesdelen - informationsmässigt det som innehåller rubriken för mötet - genom att skriva prep[1][1]. För själva textsträngen "Lab prep in Java" får vi 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 oläslig
  • det blir osmidigt att ändra representation
  • det blir svårt för utomstående att bygga vidare på din kod

Istället skapar vi ett lager av funktioner som hanterar just denna funktionalitet. Varje funktion som behöver ha reda på vad ärendet/rubriken för ett visst mötesobject (appointment), skriver bara get_subject(<ett appointment>). 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 bara ha pekare till något som gör slagningar 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.

Denna laboration handlar om att lära sig tänka i lager, och hantera detta på klokt vis.

7.1.2 Typer och typsignaturer

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 förrän 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 vi kör programmet).

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 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, Integer, m.fl.). Om vi ser på trädet från laboration 3 kan vi se att några typsignaturer är

is_tree: objekt -> sanningsvärde
key: Tree -> Heltal
create_tree: Tree x Tree -> Tree

Vad det betyder är det naturliga: "create_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.

7.2. Filerna

Almanacksystemet består av följande filer:

För att så enkelt som möjligt använda almanacksystemet bör du ladda ner alla filerna och spara dem i en och samma mapp. Om du sitter på IDA kan du komma åt filerna i katalogen ~TDDC66/src_new/alma/.

För att förstå hur funktionerna hänger ihop finns det en lista på typsignaturer för alla funktioner i almanackan (funktioner hittills, det vill säga). Använd den för att få överblick.

7.3. Att använda almanackan

Koden är uppdelad i flera olika filer, men en del filer är tyvärr inte färdigskrivna än. I en fil finns det funktioner som bryter mot abstraktionen (läs mer om detta längre fram) och som måste skrivas om, i andra filer finns det funktioner som inte ens är implmenterade, och som måste skrivas från början. Laborationsuppgifterna går i princip ut på att lösa detta, så att almanackan kan användas som väntat.

För att du ska få en liten uppfattning om hur almanackan fungerar bör du testa den. Det gör du genom att läsa in filen calendar.py på följande sätt:

>>> from calendar import *

OBS! Denna prompt får du upp genom att köra den vanliga interpretatorloopen i python3. Detta är alltså inte inbyggt i utvecklingsmiljön Eclipse.

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

>>> create("Mal") A new calendar by the name Mal has been created. >>> create("River") A new calendar by the name River has been created. >>> show_calendars() The following calendars exist: River Mal

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.

>>> create("Jayne") A new calendar by the name Peter has been created. >>> book("Jayne", 20, "sep", "12:00", "14:00", "Rob train") The appointment has been booked. >>> book("Jayne", 20, "sep", "15:00", "16:00", "Escape with loot") The appointment has been booked. >>> show("Jayne", 20, "sep") 20 september =========== 12:00-14:00 Rob train 15:00-16:00 Escape with loot

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

Användargränssnittsfunktioner

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

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 7C.
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")

7.3. Almanackans struktur

I det förra avsnittet tittade vi på almanackan från ett användarperspektiv. Nu ska vi lyfta på locket och se hur den fungerar inuti. Almanackan består av fyra källkodsfiler och du kommer att behöva utöka definitionerna i senare uppgifter.

För att hantera de olika delarna i almanackan har vi infört abstrakta datatyper. Vi kan se det som att vi har utökat språket Python med nya typer och nya funktioner som opererar på dessa. Vi kan också se det som att vi har infört flera abstraktionslager. Det understa lagret är originalspråket, i det här fallet Python. Ovanpå det har vi skapat en samling primitiva funktioner för att hantera våra abstrakta datatyper. 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.

Almanackan
Bokningar Utskrifter
Primitiver
Python

Innehållet i de olika filerna är följande:

  • calendar_ADT.py innehåller de primitiva funktioner som behövs för att kontrollera de abstrakta 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.

7.4. Almanackans representation

För att kunna skilja våra olika abstrakta 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. Etiketten talar om vilken typ av objekt det rör sig om och ä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 består av två viktiga funktioner som paketerar respektive packar upp dataobjekt. Dessa funktioner heter attach_tag och strip_tag. I praktiken så 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, dvs första värdet av tupeln. 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 abstrakta datatyper. 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_ADT.py som känner 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.

>>> month_of_january = new_month("jan") >>> month_of_january ('month', 'january') >>> month_name(month_of_january) january >>> is_hour(new_hour(14)) True >>> is_hour( 14 ) False

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 702 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.
Uppgift 7A - Laga abstraktionsbrott

I källkodsfilen calendar_ADT.py finns bland annat följande fem funktioner definierade:

  • start_time
  • end_time
  • overlap
  • new_duration
  • length_of_span

De fungerar som de ska, men deras nuvarande implementation bryter mot den modell för dataabstraktion som vi byggt almanackan kring. Din uppgift är att ändra dessa fem funktioners implementation så att de inte längre gör det.

Restriktioner Den primitiva funktionen new_duration ska som argument ta godtycklig timme och godtycklig minut. Om antalet minuter överstiger 59 ska de konverteras till timmar. Anropar man t.ex. funktionen med 3 timmar och 230 minuter så ska det resulterande objektet innehålla 6 timmar och 50 minuter.

För att kunna omimplementera dessa funktioner behöver du studera resten av källkoden. Där framgår hur primitiva funktioner ska implementeras, var dem ska skrivas och även hur fel hanteras. Utforma dina nya implementationer på samma sätt som de redan (bra) existerande implementationerna.

Vad ska funktionerna göra? Se listan på typsignaturer.

Uppgift 7B - Ny datatyp

För att enklare kunna lösa Uppgift 7D i framtiden vill vi ha en ny datatyp time_spans. Den ska bestå av en sekvens (lista) element av datatypen time_span. Elementen ska lagras i kronologisk ordning, sorterat efter tidsperiodens startklockslag. Den nya datatypen ska alltså i stort sett fungera som en calendar_day, men enbart lagra tidsperioderna. Definiera de primitiva funktioner som kan behövas för datatypen tidpsperioder. Definiera också en utskriftsfunktion som skriver ut alla tidsperioder i en sådan samling!

Notera att er insert-funktion bör heta insert_span för att fungera med testskriptet i 7D, helt analogt med hur det fungerar i calendar_day. (tillagt 161209 //Anders M.L.)

Uppgift 7C - Avbokning av möten

Denna uppgiften går ut på att lägga till funktioner som avbokar möten. Studera först hur bokning av möten går till. Vilka hjälpfunktioner anropas från gränssnittsfunktionen boka? Vilka primitiva funktioner använder dessa? Definiera gränssnittsfunktionen remove samt eventuella hjälpfunktioner och primitiva funktioner som behövs.

Funktionen avboka ska anropas på följande sätt: remove(namn, dag, månad, start). Se körexempel nedan.

>>> create("Jayne") A new calendar by the name Peter has been created. >>> book("Jayne", 20, "sep", "12:00", "14:00", "Rob train") The appointment has been booked. >>> book("Jayne", 20, "sep", "15:00", "16:00", "Escape with loot") The appointment has been booked. >>> show("Jayne", 20, "sep") 20 september =========== 12:00-14:00 Rob train 15:00-16:00 Escape with loot >>> remove("Jayne", 20, "sep", "15:00") Appointment removed. >>> book("Jayne", 20, "sep", "15:00", "16:00", "Return loot") The appointment has been booked. >>> show("Jayne", 20, "sep") 20 september =========== 12:00-14:00 Rob train 15:00-16:00 Return loot

7.5. Algoritmer och testning

De primitiva och "bra att ha"-funktionerna i calendar_ADT.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.

Uppgift 7D - Lediga tider

Du ska skapa gränssnittsfunktionen show_free, som skriver ut vilka tidsperioder som är lediga i en almanacka under ett visst intervall en dag. Definiera denna funktion samt eventuella hjälpfunktioner som behövs för att lösa uppgiften. För att lösa uppgiften ska du använda den nya datatypen time_spans från Uppgift 7B. I exemplet nedan söks de lediga tiderna mellan kl 09:00 och kl 17:00.

>>> create("Jayne") A new calendar by the name Peter has been created. >>> book("Jayne", 20, "sep", "12:00", "14:00", "Rob train") The appointment has been booked. >>> book("Jayne", 20, "sep", "15:00", "16:00", "Escape with loot") The appointment has been booked. >>>> show_free("Jayne", 20, "sep", "08:00", "19:00") 08:00-12:00 14:00-15:00 16:00-19:00

Testning OBS!: Innan du börjar skriva funktionen ledigt ska du först skriva ett antal testfall som tillsammans täcker upp alla möjliga sorters indata. Du ska också anpassa en test driver från filen test_driver.py så att den kan användas för din version av ledigt. Se på hur funktionen run_tests i test_driver gör sina anrop för att få fram lediga tidsperioder (den förutsätter att ni har skrivit en funktion free_spans).

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.

Uppgift 7E - Gemensamma lediga tider (frivillig)

Observera att denna uppgift inte behöver lämnas in för att klara laborationskursen.

Efter att ha löst problemet "hitta alla lediga tider för en person en viss dag", vill vi hitta alla tider en viss dag då två angivna personer (almanackor) båda har ledigt. Konstruera en funktion possible_appointments som skriver ut samtliga tider en viss dag som personerna båda är lediga.

Placera dina funktioner i en separat fil för att underlätta redovisning, men ange för var och en av dem i vilken av källkodsfilerna de egentligen hör hemma!

Visa med utförliga körexempel att du klarar av att ta hand om alla fall som kan uppkomma.

7.6. Typsignaturer för primitiva funktioner

Här kan du hitta de primitiva funktioner som finns tillgängliga i almanackssystemet, grupperade efter vilken datatyp de opererar på. För förklaring av typsignaturer, se ovan.

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: Python objekt -> 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: Python objekt -> 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: Python objekt -> Bool Testar om objektet är ärendet för ett möte.
new_subject: String -> subject Skapar ett möte av en sträng.
subject_text: subject -> String Omvandlar ett möte till en sträng.

duration

Tidsrymd (ej klockslag, utan en utsträckning. Till exempel 48h 15 minuter.)

is_duration: Python objekt -> Bool Testar om objektet är en tidsrymd.
new_duration: hour × minute -> duration Skapar en tidsrymd av en hour och en minut.
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: Python objekt -> 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: Python objekt -> 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: Python objekt -> 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: Python objekt -> 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: Python objekt -> 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: Python objekt -> 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: Python objekt -> 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ätt en gammal.
calendar_month: month × calendar_year -> calendar_month Returnerar calendar_month som svarar mot en given month ur en calendar_year.

Överkurs. 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: 2016-12-09