Mästarprov i 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, Google Gemini 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 . Skriv i så fall koden och texten som en akademisk uppsats och illustrera elegant och begripligt. Använd till exempel noweb . 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 . 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. Om ni har svårt för LaTeX-syntax så har vi här ett litet undantag från generativ AI: Det är tillåtet att slå upp LaTeX-syntax med generativ AI eftersom detta också är tillåtet på mästarproven i ADK. Exempel på godkända prompter är "How do I write a new paragraph in LaTeX?", "How do I make Haskell code look good in a LaTeX document" och "Please write a boilerplate template for a handin in LaTeX".
Det tredje bästa är att använda Markdown 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 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å uppgifterna:

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. I lambdafunktioner är typsignaturer valfria om ej annat anges.
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 de biblioteksfunktioner som följer med ghc Links to an external site. bortsett från när det strider mot regel nummer 2.
4. Alla programmeringsuppgifter kan lösas med hjälp av rena funktioner och referenstransparenta uttryck. Gör det och var beredd på att redogöra på redovisningen vad som menas med begreppen och vad som gör att din kod är implementerad på detta sätt.
5. Exempelkörningar ges på programmeringsuppgifterna. Era lösningsförslag behöver fungera på samma sätt som exemplen i dessa fall, men även uppfylla uppgiftslydelsen som helhet.
6. Ni behöver inte tänka på Integer Overflow.

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, så länge de har typsignaturer. 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 i kurs-PM under examination -> mästarprov. Kurs-PM finns länkat från årets förstasida.. 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. REMORES-tiderna kommer att anslås i nära anslutning till deadline för mästarprovet.

Lycka till!

1. Initialer. Skriv en Haskellfunktion som heter initialer som tar in en lista med strängar med namn och som utdata ger en lista med initialer, det vill säga den första bokstaven i varje del av namnet, oavsett om de olika namnen är separerade av bindestreck eller mellanslag.
Exempelkörningar:

ghci> initialer ["Alice","Bob","Charlie"]
["A","B","C"]
ghci> initialer ["Anna-Lena","Tonima Afroze ","Carl-Erik"]
["AL","TA","CE"]
ghci> initialer ["eLAK iNDATA","mer--- -- ---krånglig---- - -   -    -        indata","","-- -- - --  --- -- "]
["EI","MKI","",""]

Problemet kan med fördel lösas med högre ordningens funktioner, men rekursiva lösningar accepteras också.

2. Skriv en Haskellfunktion som heter targetSumPairs som tar som indata:

• En lista med positiva heltal.
• Ett positivt heltal som utgör målet.

Utdata ska bestå av:

• En lista med par av heltal, plockade ur indatalistan, utan återläggning. Varje par av heltal ska summera till målet. Ordningen spelar ingen roll.
• En separat lista med omatchade heltal som inte kan ingå i en summa.

Exempelkörningar:

ghci> targetSumPairs [1, 2, 3, 4, 5] 5
([(2,3),(1,4)],[5])
ghci> targetSumPairs [3, 3, 3, 3, 3] 6
([(3,3),(3,3)],[3])
ghci> targetSumPairs [] 1
([],[])
ghci> targetSumPairs [1] 2
([],[1])
ghci> targetSumPairs [1, 0, 1, 2] 2
([(0,2),(1,1)],[])
ghci>

Krav på lösningen:

• Din lösning behöver vara rekursiv och inte använda högre ordningens funktioner (exempel inkluderar men är inte begränsade till map, filter eller reduce).
• Det är tillåtet och rekommenderat att använda en eller flera hjälpfunktioner.
• Funktionen behöver inte ta hänsyn till Integer overflow vid summan.
• Du får utgå från att indata inte innehåller några negativa tal.
• Var beredd på att redogöra för basfall och rekursiva anrop under redovisningen.

3. Prefixsummor.
Skriv en funktion som heter prefixSums som tar in en lista med heltal och som utdata ger en lista som är lika lång, men det i:te talet innehåller summan av de första i talen i indatalistan.

Exempelkörningar:

ghci> prefixSums [1, 2, 3, 4, 5]
[1, 3, 6, 10, 15]
ghci> prefixSums []
[]
ghci> prefixSums [1]
[1]
ghci>

4. Skriv en funktion som heter processStrings som tar som indata en lista med strängar. Utdata från funktionen ska vara en tupel med två listor där den första listan är de strängar som har högst 3 tecken eller innehåller bokstaven 'R' (som också kan vara lowercase). Den andra listan i tupeln ska innehålla de strängar som inte uppfyllde kravet. Du får internt konvertera strängarna men i slutresultatet ska strängarna i de båda listorna vara samma strängar som i ursprungslistan. Ordningen för varje lista i utdatan ska vara samma som i indatalistan. Det här låter lite liknande uppgift 2, men nu är kravet att du använder minst en högre ordningens funktion och att du på en central plats använder en anonym funktion skriven med lambdanotation.
Exempelkörningar:

ghci> processStrings ["ABCDE", "AF", "ABBA", "aber", "VR headset"]
(["AF","aber","VR headset"],["ABCDE","ABBA"])
ghci> processStrings []
([],[])
ghci> processStrings ["a", "aa", "aaa", "aaaa", "aaaaa"]
(["a","aa","aaa"],["aaaa","aaaaa"])
ghci>