Hide

Uppvärmning

I denna labb ska du konstruera några enkla funktioner i Haskell. Alla funktioner du definierar i denna labb ska ligga i en modul som heter F1. Följande är ett kodskelett som man kan utgå ifrån, det innehåller triviala kodstubbar (som såklart inte gör rätt) för samtliga deluppgifter i labben.

module F1 where

-- Vad ska de andra funktionernas typsignaturer vara?
fib :: Integer -> Integer
fib n = 0
rovarsprak s = s
karpsravor s = s
medellangd s = 1.0
skyffla s = s

1 Fibonacci-talen

Fibonacci-talen är en talföljd som definieras så här:

\[ F(n) = \begin{cases} 0 & \text {om $n = 0$} \\ 1 & \text {om $n = 1$} \\ F(n-1) + F(n-2) & \text {om $n > 1$} \end{cases} \]
Uppgift

Skriv en funktion fib som tar ett heltal $n$ och returnerar $F(n)$. Du behöver inte hantera negativa tal. Funktionen ska klara att beräkna $F(n)$ för $n$ upp till 42 på en bråkdel av en sekund. Hur lång tid tar det att beräkna $F(35)$? $F(40)$?

Tips

Lättast är att definiera funktionen med flera ekvationer (analogt med definitionen ovan).

Exempel

fib(7) ska returnera $13$

fib(17) ska returnera $1597$

2 Rövarspråket

I rövarspråket dubblerar man alla konsonanter och lägger ett “o” emellan, se exempel nedan. (För den här uppgiften ignorerar vi de specialfall som ibland tillämpas där t.ex. “x” behandlas som “ks”.)

Uppgift

Skriv en funktion rovarsprak som tar en sträng och returnerar en ny sträng där varje konsonant $x$ har ersatts av strängen $x$o$x$. Skriv också en funktion karpsravor som gör det omvända, dvs tar en sträng på rövarspråk och “avkodar” den.

Funktionerna behöver bara hantera strängar med gemener (inga mellanslag, siffror, stora bokstäver, eller andra tecken), och behöver inte hantera åäö. Funktionen karpsravor behöver bara fungera på strängar som verkligen tillhör rövarspråket, ingen felhantering behövs för felaktig indata.

Funktionerna ska gå i linjär tid och hantera strängar på upp till $100\, 000$ tecken inom en bråkdel av en sekund.

Tips

Ni vill antagligen skriva en funktion som avgör om ett givet tecken är vokal eller konsonant. Funktionen elem kan vara en praktisk byggsten för detta.

Exempel

rovarsprak("progp") ska returnera poprorogogpop

rovarsprak("cirkus") ska returnera cocirorkokusos

karpsravor("hohejoj") ska returnera hej

karpsravor("fofunonkoktotionon") ska returnera funktion

3 Medellängd

Uppgift

Skriv en funktion medellangd som tar en text (String) som indata och returnerar ett tal (Double) med medellängden på orden i texten.

Ett ord definierar vi som en sammanhängande delsträng av bokstäver ur alfabetet, stora eller små. Alla blanka tecken, kommatering, siffror, etc, är ord-delande.

Funktionen ska gå i linjär tid och hantera texter på upp till $100\, 000$ tecken inom en bråkdel av en sekund.

Tips

Funktionen isAlpha : Char -> Bool returnerar sant på just de tecken som finns i alfabetet. För att komma åt isAlpha måste du importera modulen Data.Char.

En möjlig ansats är att först stycka upp texten i ord och sedan beräkna antal ord samt totala längden på orden.

Exempel

medellangd("No, I am definitely not a pie!") ska returnera $3.14285714$...

medellangd("w0w such t3xt...") ska returnera $1.8$

4 Listskyffling

Vi är intresserade av att kasta om elementen i en lista enligt följande: först tar vi varannat element (första, tredje, femte, etc). Vi upprepar sedan detta på elementen som återstår (dvs tar andra, sjätte, tionde, etc). Detta upprepas så länge det fortfarande finns element kvar. Om vi t.ex. börjar med listan (1, 2, 3, 4, 5, 6, 7, 8, 9) kommer vi i första vändan få (1, 3, 5, 7, 9), och elementen (2, 4, 6, 8) återstår. I andra vändan lägger vi till (2, 6), och bara (4, 8) återstår. I tredje vändan lägger vi bara till 4, och bara 8 återstår. I fjärde och sista vändan lägger vi slutligen till 8, och slutresultatet blir listan (1, 3, 5, 7, 9, 2, 6, 4, 8).

Uppgift

Skriv en funktion skyffla som tar en lista som indata och returnerar en omkastad lista enligt beskrivningen ovan.

Funktionen ska fungera på alla typer av listor.

Funktionen ska kunna hantera listor på upp till $5\, 000$ element inom en bråkdel av en sekund.

Exempel

skyffla(["kasta", "ord", "om"]) ska returnera ["kasta", "om", "ord"]

skyffla([3.4, 2.3, 5, 185, 23]) ska returnera [3.4, 5, 23, 2.3, 185]

skyffla([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]) ska returnera [1, 3, 5, 7, 9, 11, 2, 6, 10, 4, 12, 8]

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Source KTH CSC Programmeringsparadigm
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in