Gammalt Mästarprov Funktionell Programmering 2022

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; om du skriver med LaTeX, använd pdflatex för att göra om det till en pdf; Om du skriver i Word, välj spara som och välj filformatet pdf; inskannade handskrivna lösningar går också bra men LaTeX är bäst; det går också bra att skicka in kod i separata .hs-filer) senast Deadline. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske kort efter deadline i Zoom för någon i lärarlaget. Tidsbokningen kommer att komma upp nära uppgiftens deadline och det kommer att anslås på Canvas när de har kommit upp. Den muntliga redovisningen tar 10 minuter för dig, men de som bedömer dig har 5 minuters paus innan varje redovisning.

Boka tider i REMORES med denna länk (Länken borttagen eftersom det är ett gammalt mästarprov).

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera din implementation och de delar av Haskell och paradigmet funktionell programmering som du har använt. Alla programmeringsuppgifter ska lösas i Haskell.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om något är oklart.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas.

Som exempel på hur kod-delen av en inlämningsuppgift kan se ut, se facit och rättningsmallar från Tentaarkivet i DD1361, till exempel 2017-09-18 som gicks igenom på föreläsningen. Som exempel på hur en teorifråga kan besvaras, se facit och rättningsmallar från tentaarkivet i DD1362 till exempel juni 2021.

Lycka till!
/Marcus

1. En lista med partiklar.

I ett koordinatsystem med origo uppe i vänstra hörnet lever ett antal partiklar. Dessa partiklar är grafikpartiklar som har föjande 4 fält (fält kallas attribut för er som kommer från Python men Java och Haskell kallar dessa fält):

Din uppgift är att (1) skapa en datatyp för den här sortens partikel och (2) designa och implementera en funktion updateParticles som tar en lista med partiklar och efter applikationen av denna funktion så ska du ha en lista med partiklar efter att tiden delta_t har förflyttats. (3) Du får välja själv vilken datatyp du väljer för x, y, delta_x och delta_y men var beredd på att motivera ditt val.

Kravet på förflyttningen är att (1) x och y ska ha fått nya positioner genom att lägga till delta_x och delta_y. (2) delta_x ska ha krympt med 1 längdenhet mot 0, så om partikeln var på väg mot vänster så ska den vara mindre på väg mot vänster och tvärtom. (3) delta_y ska ha ökat med en längdenhet så att partikeln faller snabbare och snabbare mot marken.

Funktionen updateParticles ska implementeras med hjälp av minst en högre ordningens funktion.
Du får inte godkänt om du implementerar updateParticles rekursivt.
Det är tillåtet att skriva egna hjälpfunktioner utöver de funktioner som nämns här.
Det är tillåtet att importera och använda Haskells inbyggda funktioner.
Alla funktioner du skriver i uppgiften behöver ha en typsignatur som du skrivit själv. Haskells typinferens räcker inte för godkänt.
Alla funktioner behöver vara ordentligt dokumenterade. Vad tar de in för data och vad representerar en applikation av funktionen.
Redogör också ordentligt för hur immutability används av updateParticles.

Ledning: Learn You a Haskell har en guide till hur du använder Record Syntax Links to an external site..

2. Newton-Raphson

Studera detta polynom: 3x³ - 2x² + 14x + 3, exempelvis genom att plotta den hos WolframAlpha Links to an external site.. Det har en reell rot (nollpunkt) nära x = -0.2. Räkna fram nollpunkten iterativt i en Haskellfunktion som du designar och implementerar själv. Implementationen ska använda sig av Newton-Raphson:s metod. Detta ska göras utan do-notation och utan högre ordningens funktioner. Implementera denna algoritm rekursivt och förklara om dina rekursiva anrop är svansrekursiva eller inte. Utför en Newton-Raphson-iteration per rekursivt anrop. Att hårdkoda flera än så i samma funktionsanrop ger inte godkänt.

Det är tillåtet att använda hjälpfunktioner och Haskells inbyggda funktioner - så länge dessa inte är högre ordningens funktioner.
Tänk på att ange typsignaturer på alla funktioner du skriver.

Du behöver inte hitta de komplexa rötterna till polynomet.

3. Anagram

I uppgift 3 ska du skriva en funktion anagram (som precis som vanligt får ha en eller flera hjälpfunktioner). Den ska ta emot en sträng, en lista med strängar och en applikation ska ge dig en lista med de strängar ur listan som är anagram av den första strängen, sorterad i bokstavsordning utan upprepningar. Du får förutsätta att både den ensamma strängen som du matchar med och alla strängar i listan endast använder små bokstäver.

4. Referenstransparens och renhet

Leta upp de 3 krångligaste uttrycken i dina implementationer av uppgift 1 - 3 (krånglighet innebär att de har många variabler och funktionsanrop) och redogör för om de är referenstransparenta. Redogör också för om funktionerna som appliceras i uttrycken är rena eller inte.

Facit och rättningsinstruktioner.