Gammalt Mästarprov Funktionell Programmering

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. Nytt för 2023 är att det inte är tillåtet att använda verktyg baserade på AI/maskininlärning i arbetet med lösningarna. Exempel på förbjudna verktyg är Github Copilot och ChatGPT.

Skriftliga lösningar ska lämnas in i Canvas.
Det bästa formatet för inlämningar är litterär programmering (literate programming) i en stil som liknar Physically Based Rendering. Bokens tredje utgåva finns gratis på nätet här Links to an external site.. Skriv i så fall koden och texten som en akademisk uppsats och illustrera elegant och begripligt. Använd till exempel noweb Links to an external site.. Lämna in resultatet som pdf.
Det näst bästa formatet (och fortfarande kanonbra) är att använda LaTeX för att skapa texten. De flesta som använder LaTeX gör det via ett webbgränssnitt som till exempel Overleaf Links to an external site.. Om du bygger lokalt, tänk på att använda pdflatex så att resultatet blir en pdf-fil. Assistenterna ska inte behöva bygga LaTeXfiler själva och framför allt inte installera externa bibliotek.
Det tredje bästa är att använda Markdown Links to an external site. som är enklare än LaTeX och ger nästan lika bra resultat.
Resterande: Om ni använder Microsoft Word eller liknande - tänk på att spara som pdf så att alla kan läsa texten som det är tänkt utan att ha Word installerat.
Skicka inte in nedpackade arkivfiler utan använd Ctrl-klick för att lägga till var och en av filerna i inlämningen.

Krav på koden:

1. I varje uppgift krävs typsignaturer. Detta gäller även på hjälpfunktioner som du skriver till stöd för huvuduppgiften. De automatiskt genererade räcker inte för godkänt. Undantag ges för anonyma funktioner som skrivits med lambdanotation. Här är typsignaturer valfria.
2. Vissa uppgifter kräver en viss metodik, till exempel svansrekursion eller högre ordningens funktioner.
3. Det är alltid tillåtet att använda Haskells standardbibliotek bortsett från när det strider mot regel nummer 2.

Skriv ditt namn och KTH-mailadress överst på framsidan av varje pdf, markdownfil och/eller kodfil i 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 mellan varje par av redovisningar.

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. Det är alltid tillåtet att använda hjälpfunktioner. Det är alltid tillåtet att använda nästlade typer.

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ågon formulering är oklar.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas. Tänk på att mästarprovet bedöms efter sin sämst lösta uppgift så överarbeta inte en uppgift förräns alla är OK.

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. Det finns också lösningsförslag på gamla mästarprov. Titta under uppgifter i vänstermarginalen och längst ner finns en länk till ett Gitubrepo. Som exempel på hur en teorifråga kan besvaras, se facit och rättningsmallar från tentaarkivet i DD1362 till exempel juni 2021.

Mästarproven behöver redovisas både skriftligt och muntligt. Om du har lämnat in den skriftliga biten i tid så behöver du för att få godkänt även boka in dig på en muntlig redovisning med hjälp av REMORES. Välj en anonym assistent, välj först inom vilket 2h-intervall som du vill redovisa och välj sist en 10-minuterstid då du faktiskt redovisar. Det finns 4 tider per timme eftersom assistenterna behöver ställtid mellan redovisningarna. Lycka till. Här är länken:
 https://www.csc.kth.se/cgi-bin/bokning/remores1.4/server/decoder?request:overview=yes&repository=mpfunk20231

1. En lista med heltal.
Implementera en funktion i Haskell som tar in en lista av heltal och returnerar en lista där varje element är kvadraten av det ursprungliga elementet, förutom de element som är negativa eller 0. Icke-positiva element ska istället ignoreras och inte finnas med i den resulterande listan.
Exempelkörningar:


Implementationen av squarePositive behöver uppfylla följande krav:

1. Du behöver använda högre ordningens funktioner för att implementera funktionen.

Dokumentationen av squarePositive behöver uppfylla följande krav:

1. Redogör för vilka högre ordningens funktioner som du använder och förklara varför dessa är högre ordningens funktioner.
2. Redogör för hur funktionen använder immutability.

2. Resmål

Definiera ett Record för enskilda personer kallat Person som har namn, ålder och en lista över strängar som representerar resmål. Skriv sedan en funktion som läser in en lista över Person och returnerar en lista över alla resmål som de tillsammans har besökt med alla resmål som besökts av minst en person i listan. Kravet på listan är att alla resmål ska vara unika.
Uppgiften går att lösa effektivt men det är inget krav. En lösning som är O(n^3) ger godkänt.

Dokumentationskrav: Dokumentera utförligt hur man skapar en instans av Person.

Ledning: Learn You a Haskell har en guide till hur du använder Record Syntax .

3. Svansrekursiv sifferkedja

En sifferlek går till på följande sätt. Du börjar på ett heltal current och ska nå ett heltal goal. Dina två tillåtna drag är:

1. Att lägga till 2 till talet
2. Att dra ifrån 3 från talet.

Leken tar slut då du når goal. Leken ställer krav på att du loggar alla delresultat på vägen. Det finns alltid minst en giltig lösning. Exempelkörningar:

Du behöver också kunna hantera negativa tal. Gör detta genom att skriva talet inom parentes så att Haskell förstår att det är unärt minus.

Ledning:

1. En girig algoritm som alltid går mot målet när den kan och sedan antingen backar eller skjuter över målet ger en optimal lösning.

Krav på implementationen:

1. Du behöver använda en hjälpfunktion.
2. Högre ordningens funktioner är förbjudna här.
3. Hjälpfunktionen behöver vara implementerad med hjälp av svansrekursion.
4. Din lösning får inte använda slump.

Krav på dokumentationen:

1. Skriv vad som gör din implementation svansrekursiv.

4. Kortaste vägen

Skriv en funktion totalDistance som tar in en lista med koordinater i planet och beräknar den kortaste vägen som går igenom alla punkter i den ordning som de var givna i listan. Exempelkörning:

Tänk också på dessa specialfall:

Ledning:

1. Avståndet mellan två punkter kan beräknas med Pythagoras sats.
2. Testa med exemplet ovan, som ges i lättpastead text här: [(1.3,2.4), (5.3, -1.3), (-4.2, -3.4), (5.2, 8.0)]

Dokumentations- och implementationskrav:

1. Impementera uppgiften med rena funktioner och dokumentera vad som gör dem rena.
2. Implementera uppgiften med referenstransparens och dokumentera vad som gör koden referenstransparent.

Det var alla uppgifter. Testa din kod och kolla alla checklistor innan du lämnar in. Lycka till önskar lärarlaget i progp23!