Funktsionaalprogrammeerimine 2024/25 sügis

Kodutöö 2

Selles praktikumis harjutame funktsioonide kirjutamist, mis tegelikult on Idrise standardteegis olemas. Näeme, kuidas Idrise listidega fundamentaalsel tasandil opereerida; näeme, et need standardfunktsioonid pole mingi sisseehitatud maagia, ning selle käigus õpime ära mõned lihtsamad standardteegi funktsioonid.

Lisalugemine (vabatahtlik):

Type-Driven development with Idris peatükid:

• Chapter 2. Getting started with Idris, alampeatükid:
  • 2.2. Functions: the building blocks of Idris programs, alampeatükid:
    • 2.2.3. Writing generic functions: variables in types
  • 2.3. Composite types
    • 2.3.1. Tuples
    • 2.3.2. Lists
    • 2.3.3. Functions with lists

Praktikumi ja kodutöö ülesanded

Implementeerige järgnevad funktsioonid vastavalt etteantud tüübile ja ülesandepüstitusele. Pidage meeles, et Moodle automaatkontroll sisaldab teste kõikide selle kodutöö ülesannete jaoks.

Standardteegi funktsioonid

Et nimesid mitte segamini ajada, on kodutöös funktsiooninimedele lisatud ülakoma. S.t. standardteegis on funtksioonid ilma ülakomata.

1. Funktsioon fst' - paari esimene element

fst' : (a, b) -> a
fst' = ?rhs_fst

Katseta erinevat tüüpi paaridega: näiteks fst' ('x', True) ja fst' (8, "Tere").

2. Funktsioon length' - listi pikkuse arvutamine

length' : List a -> Int
length' = ?rhs_length

Redutseeri avaldis length' [2, 3, 4] .

3. Funktsioon +++ - kahe listi konkateneerimine

Standardteegis on listide konkateneerimiseks operaator ++. (Ülakomad pole operaatorite nimedes lubatud)

infixr 7 +++
(+++) : List a -> List a -> List a
(+++) = ?rhs_kon

Redutseeri avaldis [1] +++ [2].

4. Funktsioon replicate' - n-st elemendist x koosneva listi konstrueerimine

replicate' : Int -> a -> List a
replicate' = ?rhs_replicate

replicate' 1 True  ==> [True]
replicate' 3 False ==> [False, False, False]
replicate' 0 True  ==> []

5. Funktsioon take' - listist algusosa võtmine

take' : Int -> List a -> List a
take' = ?rhs_take

Näiteks:

take' 3 [1,2,3,4,5] ==> [1,2,3]
take' 5 [2,4]       ==> [2,4]
take' 0 [1,2,3]     ==> []

6. Funktsioon sum' - listi elementide summa

Kirjutada funktsioon sum', mis leiab täisarvude listi summa.

sum' : List Integer -> Integer
sum' = ?rhs_sum

Näiteks:

sum' [1..10]   ==>   55
sum' [3, 1, 2] ==>   6
sum' [2]       ==>   2
sum' []        ==>   0

Redutseeri avaldis sum' [100, 76, 24].

7. Funktsioon drop' - listi algusosa eemalejätmine

drop' : Int -> List a -> List a
drop' = ?rhs_drop

Näiteks:

drop' 0 [1, 2, 3, 4]    ==> [1, 2, 3, 4]
drop' 1 [1, 2, 3, 4]    ==> [2, 3, 4]
drop' 3 [1, 2, 3, 4]    ==> [4]
drop' 100 [1, 2, 3, 4]  ==> []

8. Funktsioon reverse' - listi ümberpööramine

reverse' : List a -> List a
reverse' = ?rhs_reverse

Näiteks:

reverse' [1, 2, 3]     ==> [3, 2, 1]
reverse' [True, False] ==> [False, True]
reverse' []            ==> []

9. Funktsioon esimesed

Nüüd vaatame mõningaid funktsioone, mida sellisel kujul standardteegis ei ole. (Näiteks, kuna seda saab teha mitme kõrgemat järku funktsiooniga, mida vaatame järgnevates praksides.)

Funktsioon tagastab paaride listi esimesed elemendid (samas järjekorras).

esimesed : List (a, b) -> List a
esimesed ps = ?rhs_esimesed

Näiteks:

esimesed [] ==> []
esimesed [(2, 3), (6, 4), (9, 9)] ==> [2, 6, 9]

10. Funktsioon leidub

Tagastab True, kui arv leidub listis, muidu False.

leidub : Integer -> List Integer -> Bool
leidub n xs = ?rhs_otsi

Näiteks:

leidub 3 [1, 2, 3, 4, 5, 6] ==> True
leidub 8 [1, 2, 3, 4, 5, 6] ==> False

11. Funktsioon dropLast

Eemaldab listi viimase elemendi.

dropLast : List a -> List a
dropLast xs = ?rhs_dropLast

Näiteks:

dropLast []           ==> []
dropLast [1, 2, 3]    ==> [1, 2]
dropLast [3, 2, 1, 0] ==> [3, 2, 1]

12. Funktsioon lisa

Lisab tähe sõnesse. Kusjuures nulli või negatiivse indeksiga pannakse täht algusse, suurema indeksiga, kui sõne pikkus, lõppu.

lisa : Int -> Char -> String -> String
lisa i x ys = ?rhs_lisa

Näiteks:

lisa (-1) 'a' "xyz" ==> "axyz"
lisa 1    'a' "xyz" ==> "xayz"
lisa 3    'a' "xyz" ==> "xyza"
lisa 2    'a' "xyz" ==> "xyaz"
lisa 400  'a' "xyz" ==> "xyza"

Defineeri abimeetod lisa' : Int -> Char -> List Char -> List Char.

Sõne ja tähemärkide listi vahel teisendamiseks kasuta funktsioone unpack ja pack.

13. Funktsioon arvuta

Väärtustab polünoomi kohal x. Iga listi element (a, n) tähistab polynoomi liidetavat a*x^n.

arvuta : List (Double, Nat) -> Double -> Double
arvuta ps x = ?rhs_arvuta

Näiteks: [(4.0,2),(1.0,1),(30.0,0)] tähendab 4*x^2 + x + 30 ja

arvuta [(4.0, 2), (1.0, 1), (30.0, 0)] 5 ==> 135.0
arvuta [(4.0, 2), (1.0, 1), (30.0, 0)] 2 ==> 48.0
arvuta []                              5 ==> 0

Selles ülesandes sisseehitatud operaatori ^ kasutamiseks lisa faili päisesse import Data.Monoid.Exponentiation. Et VScode-is ei oleks import punane, loo käsureal uus fail: touch K2.ipkg ning faili sisuks kirjuta:

package K2
depends = contrib

Käsurealt käivita siis nii rlwrap idris2 --find-ipkg K2.idr või nii rlwrap idris2 -p contrib K2.idr.

Tärnülesanded

Funktsioon lines

Kirjuta funktsioon lines, mis võtab sisse sõne ja tagastab sõnede listi, mille elemendid on sisendi (reavahetusega eraldatud) teksitread.

(Standardteegis on lines moodulis Data.String .)

lines : String -> List String
lines = ?rhs_lines

Näiteks:

lines ""           ==> []
lines "asfd"       ==> ["asfd"]
lines "asfd\n"     ==> ["asfd"]
lines "as\nfd\n"   ==> ["as", "fd"]
lines "as\nfd\n\n" ==> ["as", "fd", ""]