Functional Programming 2023/24 fall

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

1. Funktsioon fst - paari esimene element

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

2. Funktsioon length - listi pikkuse arvutamine

-- varjame sisseehitatud listi pikkuse arvutuse
%hide Prelude.List.length

length : List a -> Int
length = ?rhs_length

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

3. Funktsioon ++ - kahe listi konkateneerimine

-- varjame sisseehitatud konkateneerimise arvutuse
%hide Prelude.Types.List.(++) 

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

Redutseeri avaldis K2.(++) [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

--peidame sisseehitatud funktsiooni
%hide Prelude.Types.List.reverse

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

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 otsi

Tagastab True, kui arv leidub listis, muidu False.

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

Näiteks:

otsi 3 [1, 2, 3, 4, 5, 6] ==> True
otsi 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 P2.ipkg ning faili sisuks kirjuta:

package P2

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.

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", ""]