Funktsionaalprogrammeerimine - Kursused

Kodutöö 5

Selles praktikumis õpime ja harjutame andmestruktuuride kasutamist.

Lisalugemine (vabatahtlik):

Type-Driven development with Idris peatükid:

Andmestruktuurid:

Chapter 4. User-defined data types, sissejuhatus ja alampeatükid:
- 4.1. Defining data types
  - 4.1.1. Enumerations
  - 4.1.2. Union types
  - 4.1.3. Recursive types
- 4.3. Type-driven implementation of an interactive data store
  - 4.3.1. Representing the store
Chapter 6. Programming with first-class types, alampeatükid:
- 6.3. Enhancing the interactive data store with schemas, alampeatükid:
  - 6.3.1. Refining the DataStore type
  - 6.3.2. Using a record for the DataStore

Liidesed:

Chapter 7. Interfaces: using constrained generic types, sissejuhatus ja alampeatükid:
- 7.1. Generic comparisons with Eq and Ord
  - 7.1.1. Testing for equality with Eq
  - 7.1.2. Defining the Eq constraint using interfaces and implementations
  - 7.1.3. Default method definitions
  - 7.1.4. Constrained implementations
  - 7.1.5. Constrained interfaces: defining orderings with Ord

Praktikumi ja kodutöö ülesanded

1. Reduktsioon

Redutseeri väärtuseks (s.t. nii palju kui saab) a) normaaljärjekorras ja b) aplikatiivjärjekorras.

$(\lambda{}f.\ f f) ((\lambda{}x.b) (\lambda{}x.x))$
$(\lambda{}f.\ (\lambda{}g. f) f) ((\lambda{}x.\ b) (\lambda{}x.\ x))$
$((\lambda{}x.\ x) (\lambda{}x.\ (\lambda{}y.\ x\ w) r) (\lambda{}x.\ y))$

2. E-maili andmestruktuur

        
              data Email = E String String
 
varmo     : Email
kalmer    : Email
karoliine : Email
varmo     = E "varmo.vene"       "ut.ee"
kalmer    = E "kalmer.apinis"    "ut.ee"
karoliine = E "karoliine.holter" "ut.ee"

Implementeerige e-maili andmestruktuuri jaoks show funktsioon (liideses Show) nii, et ülaldefineeritud aadressid näidataks standardsel kujul: show kalmer == "kalmer.apinis@ut.ee"

        
              Show Email where
  show (E nimi domeen) = ?rhs_kiri_show

NB! Liidestest räägime järgnevates praksides pikemalt.

3. Kirja (kirje) andmestruktuur

record on ainult ühe konstruktoriga andmetüüp, millele genereeritakse automaatselt funktsioonid, mis selle väljasid projetseerivad.

        
              record Kiri where
  constructor MkKiri
  saatja   : Email
  saajad   : List Email
  pealkiri : String
  sisu     : String

Kirjutage Kiri tüüpi väärtus, mis tähistaks kirja teilt arvutiteaduse instituudi juhatajale.

        
              testkiri : Kiri
testkiri = ?rhs_testkiri

Kirjuta funktsioon pealkiriSisu, mis tagastab kirja kujul pealkiri: sisu.

        
              pealkiriSisu : Kiri -> String
pealkiriSisu = ?rhs_pealkiriSisu

4. Puu andmestruktuur

        
              data Tree a = Leaf | Branch (Tree a) a (Tree a)

Defineerige puude võrdsuskontroll (==) (defineerides puudele liidese Eq).

        
              Eq a => Eq (Tree a) where
    x == y = ?rhs_Eq_tree

Näiteks:

(==) (Branch Leaf 1 Leaf) (Branch Leaf 1 Leaf) == True
(==) (Branch Leaf 1 Leaf) (Branch Leaf 1 (Branch Leaf 2 Leaf)) == False

Eq a => tähendab siin, et puid tüübiga Tree a saame võrrelda ainult eeldusel, et tüübil a on juba Eq liides defineeritud ehk oskame juba a tüüpi elemente omavahel võrrelda.

5. Funktsioon `height`

Defineerige puu kõrguse funktsioon height.

        
              height : Tree a -> Int
height = ?rhs_height

Näiteks:

height Leaf == 0
height (Branch Leaf 'x' Leaf) == 1
height (Branch (Branch Leaf "2" Leaf) "1" (Branch (Branch Leaf "4" Leaf) "3" (Branch Leaf "5" Leaf))) == 3

Vihje

Idrises on sisseehitatud funktsioon max, mis võtab kaks argumenti ja tagastab neist suurima.

6. Funktsioon `fold`

Püüdke aru saada, kuidas on puu fold-i tüüp tuletatud. Seejärel defineerige puule fold funktsioon.

        
              fold : (a -> b -> a -> a) -> a -> Tree b -> a 
fold = ?rhs_fold

Näiteks:

fold (\ a, b, c => a+b+c) 0 (Branch Leaf 1 (Branch Leaf 2 Leaf)) == 3

Vihje

See fold peaks asendama Leaf konstruktori teise argumendiga ja Branch konstruktori esimese argumendiga s.t. näidet peaks arvutama nii ((\ a, b, c => a+b+c) 0 1 ((\ a, b, c => a+b+c) 0 2 0))

7. Funktsioon `size`

Defineerige Tree a andmetüübi jaoks elementide arvu funktsioon size.

        
              size : Tree a -> Nat
size = ?rhs_size

size Leaf == 0
size (Branch (Branch (Branch Leaf 1 Leaf) 7 Leaf) 8 Leaf) == 3

8. Funktsioon `heightFold`

Defineerige puu kõrguse funktsioon heightFold, kasutades fold-i.

        
              heightFold : Tree a -> Int
heightFold = ?rhs_heightFold

heightFold Leaf == 0
heightFold (Branch Leaf 'x' Leaf) == 1
heightFold (Branch (Branch Leaf "2" Leaf) "1" (Branch (Branch Leaf "4" Leaf) "3" (Branch Leaf "5" Leaf))) == 3

9. Funktsioon `memberOf`

Defineerige Tree a andmetüübi jaoks sisalduvusoperaator memberOf.

        
              memberOf : Eq a => a -> Tree a -> Bool
memberOf = ?rhs_memberOf

memberOf 7 Leaf == False
memberOf 7 (Branch (Branch (Branch Leaf 1 Leaf) 7 Leaf) 8 Leaf) == True
memberOf 3 (Branch (Branch (Branch Leaf 1 Leaf) 7 Leaf) 8 Leaf) == False

10. Funktsioon `balanced`

Defineerige predikaat balanced : Tree a -> Bool, mis kontrollib et harude kõrgused ei erineks rohkem kui ühe võrra.

        
              balanced : Tree a -> Bool
balanced = ?rhs_balanced

balanced Leaf == True
balanced (Branch (Branch Leaf 'x' Leaf) 'x' (Branch Leaf 'x' Leaf)) == True
balanced (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) == True
balanced (Branch Leaf 'x' (Branch Leaf 'x' Leaf)) == True
balanced (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf) == False
balanced (Branch (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf) 'x' (Branch (Branch (Branch Leaf 'x' Leaf) 'x' Leaf) 'x' Leaf)) == False

Vihje

Idrises on sisseehitatud funktsioon abs, mis võtab ühe argumendi ja tagastab selle absoluutväärtuse.

11. Funktsioon `gen`

Defineerige funktsioon gen mis tagastab mittenegatiivse täisarvu jaoks täpselt sellise kõrgusega täieliku kahendpuu, mis koosneb ainult elementidest a.

        
              gen : Int -> a -> Tree a
gen = ?rhs_gen

Näiteks:

gen 0 'x' == Leaf
gen 1 'x' == Branch Leaf 'x' Leaf
gen 2 'x' == Branch (Branch Leaf 'x' Leaf) 'x' (Branch Leaf 'x' Leaf)
         . . .

12. Funktsioon `tree2list`

Defineerige funktsioon tree2list mis teisendab puu listiks keskjärjestuses.

        
              tree2list : Tree a -> List a
tree2list = ?rhs_tree2list

Näiteks:

tree2list Leaf == []
tree2list (Branch Leaf 1 Leaf) == [1]
tree2list (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)) == [1,2,3]
 . . .

13. Funktsioon `bOrs`

Idrises on tüübid esimest klassi väärtused, mis sisuliselt tähendab seda, et saame defineerida näiteks funktsiooni f : Bool -> Type, mis tagastab mingi tüübi, näiteks Int. Defineerige funktsioon bOrs, mis tagastab tüübi Int, kui sisend on False ja tüübi String, kui sisend on True.

        
              bOrs : Bool -> Type 
bOrs b = ?rhs_bOrs

Näiteks:

bOrs False == Int

14. Funktsioon `hundred`

Defineerige funktsioon hundred, mis tõese sisendi korral tagastab sõne "hundred" (tüüpi String) ning väära sisendi korral arvu 100 (tüüpi Int). Funktsiooni tagastustüübi pead seekord ise välja mõtlema.

        
              hundred : (isString : Bool) -> ?rhs_Type
hundred b = ?rhs_hundred

Näiteks:

hundred False == 100
hundred True == "hundred"

15. Funktsioon `add_all`

Defineerige funktsiooni reprodT abil funktsioon add_all, mis saab sisendiks naturaalarvu k (k on argumentide arv), akumulaatori acc ning nii mitu naturaalarvulist argumenti, kui arv k lubab. Kokkuvõttes liidab add_all kõik argumendid kokku.

        
              reprodT : Nat  -> Type
reprodT 0  = Nat
reprodT (S k)  = Nat -> reprodT k
 
add_all : (k : Nat) -> (acc : Nat) -> reprodT k
add_all k acc = ?rhs_add_all

Näiteks:

add_all 5 0 1 2 3 4 5 == 15
add_all 3 0 10 10 10 == 30
add_all 1 0 509 == 509

Tärnülesanded

Funktsioon `list2tree`

Defineerige funktsioon list2tree, mis teisendab listi puuks. Püüdke lahendada ülesanne nii, et tagastatud puu oleks balansseeritud.

        
              list2tree : List a -> Tree a
list2tree = ?rhs_list2tree

Näiteks:

list2tree []  == Leaf 
list2tree [1] == (Branch Leaf 1 Leaf)
list2tree [1,2,3] == (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf))

Vihje 1

Võite kasutada Idrisesse sisse ehitatud funktsiooni splitAt, selleks peate aga importima mooduli import Data.List. Abiks tuleb mustrisobitus case-of või with süntaksiga.

Vihje 2

Naturaalarvude jagamiseks kasuta infix operaatori / asemel funktsiooni div, selleks lisa ka import import Data.Nat.

Funktsionaalprogrammeerimine 2024/25 sügis

Kodutöö 5

Lisalugemine (vabatahtlik):

Praktikumi ja kodutöö ülesanded

1. Reduktsioon

2. E-maili andmestruktuur

3. Kirja (kirje) andmestruktuur

4. Puu andmestruktuur

5. Funktsioon height

6. Funktsioon fold

7. Funktsioon size

8. Funktsioon heightFold

9. Funktsioon memberOf

10. Funktsioon balanced

11. Funktsioon gen

12. Funktsioon tree2list

13. Funktsioon bOrs

14. Funktsioon hundred

15. Funktsioon add_all

Tärnülesanded

Funktsioon list2tree

5. Funktsioon `height`

6. Funktsioon `fold`

7. Funktsioon `size`

8. Funktsioon `heightFold`

9. Funktsioon `memberOf`

10. Funktsioon `balanced`

11. Funktsioon `gen`

12. Funktsioon `tree2list`

13. Funktsioon `bOrs`

14. Funktsioon `hundred`

15. Funktsioon `add_all`

Funktsioon `list2tree`