Funktsionaalprogrammeerimine 2024/25 sügis

Kodutöö 7

Selles praktikumis harjutame kursuse esimeses pooles õpitut. Esmalt teeme läbi harjutusi {$\lambda$}-termide väärtustamisest ning seejärel implementeerime kahendpuid ja hulkasid töötlevaid funktsioone.

{$\lambda$}-termide väärtustamine

1. Churchi numbritega arvutamine

Väärtusta normaalkujule järgnevad termid:

1. {$\text{add}\ \underline{1}\ \underline{1}$}
2. {$\text{add}\ \underline{0}\ \underline{0}$}
3. {$\text{mul}\ \underline{2}\ \underline{0}$}
4. {$\text{mul}\ \underline{2}\ \underline{3}$}
5. {$\text{exp}\ \underline{2}\ \underline{2}$}
6. {$\text{exp}\ \underline{2}\ \underline{0}$}

Definitsioonid slaidilt:

{$ \begin{array}{lcl} \underline{n} & \equiv & \lambda f\ x.\ f^n\ x \\ \text{succ} & \equiv & \lambda n.\ \lambda f\ x.\ n\ f\ (f\ x) \\ \text{add} & \equiv & \lambda m\ n.\ \lambda f\ x.\ m\ f\ (n\ f\ x) \\ \text{mul} & \equiv & \lambda m\ n.\ \lambda f\ x.\ m\ (n\ f)\ x \\ \text{exp} & \equiv & \lambda m\ n.\ \lambda f\ x.\ n\ m\ f\ x \end{array} $}

Kahendpuud ja hulgad

Vaatame kahendpuid

import Data.List 

data Tree k v = E | T (Tree k v) k v (Tree k v)

test124 : Tree Int String
test124 = T (T E 1 "\252ks" (T E 2 "kaks" E)) 4 "neli" E

treeToList : Tree k v -> List (k,v)
treeToList E = []
treeToList (T x y z w) = (y,z) :: treeToList x ++ treeToList w

Puu on kas tühi leht E või kaheks hargnemine T l k v r, kus

• k on võti,
• v on võtmele vastav väärtus,
• l ning r on (vastavalt) vasak ja parem alampuu.

NB! Mõeldud on nii, et vasakus alampuus on vaid k-st rangelt väiksema võtmega seotud väärtused ja paremas alampuus vaid suuremad.

Näiteks on toodud puu test124, kus arvule 1 vastab sõne "üks", arvule 2 vastab "kaks" ja arvule 4 vastab "neli".

Näidete ja automaatkontrolli jaoks on laetud standardteegi pakett Data.List ning antud listiks tegemise funktsioon treeToList. Testimiseks võite hiljem vaadata, kas kehtib järgnev võrdsus:

  sort (treeToList test124) == [(1, "\252ks"), (2, "kaks"), (4, "neli")]

2. Implementeeri puudele võrdsuskontroll

Testimiseks võib kasutada järgnevaid võrdsusi

  the (Tree Int Int) E == the (Tree Int Int) E
  T E 1 100 E == T E 1 100 E
  E /= T E 1 100 E

3. Implementeeri puudest võtme järgi otsimine

lookup : Ord k => k -> Tree k v -> Maybe v
lookup = ?rhs_lookup

Testimiseks võib kasutada järgnevaid võrdsusi

  lookup 1 test124 == Just "\252ks" 
  lookup 2 test124 == Just "kaks"
  lookup 3 test124 == Nothing
  lookup 4 test124 == Just "neli"

4. Implementeeri puudsse andmete lisamine

insert : Ord k => k -> v -> Tree k v -> Tree k v
insert = ?rhs_insert

Testimiseks võib kasutada järgnevaid võrdsusi

  insert 1 "1" E  == T E 1 "1" E
  insert 1 "1" (T E 1 "yks" E)  == T E 1 "1" E
  insert 2 "2" (insert 1 "1" E) == T E 1 "1" (T E 2 "2" E)
  insert 0 "0" (insert 1 "1" E) == T (T E 0 "0" E) 1 "1" E

5. Implementeeri puude jaoks fold f a

Operatsioonide järjekord ei ole tähtis, aga kõik puus olevad andmed (võtmed k koos vastava väärtusega v) peavad lõpuks saama funktsiooni f-ga (f k v ?t-ga) akumulaatorisse lisatud.

fold : Ord k => (k -> v -> a -> a) -> a -> Tree k v -> a
fold = ?rhs_fold

Testimiseks võib kasutada järgnevaid võrdsusi

  fold (\x,y,xs=>(x,y)::xs) [] (the (Tree Int Int) E) == []
  sort (fold (\x,y,xs=>(x,y)::xs) [] test124) == sort (treeToList test124)

6. Implementeeri puude jaoks listis olevate andmete lisamine

Soovitame kasutada foldr-i.

insertAll : Ord k => List (k,v) -> Tree k v -> Tree k v
insertAll = ?rhs_insertAll

Testimiseks võib kasutada järgnevaid võrdsusi

  sort (treeToList (insertAll [(2,"2"), (1,"1")] E)) == [(1, "1"), (2, "2")]

7. Implementeeri puust võtme eemaldamine -- remove

Eemaldamine pole väga keeruline, kui puu on tühi, või juhtudel, kui puu ei ole tühi, aga eemaldatav võti on puu juures olevast võtmest rangelt suurem või rangelt väiksem.

Raskem on juht, kui puus T l x v r ongi vaja eelmaldada x (ja v). Selleks implementeeri abifunktsioon combine, et väiksemate võtmetega alampuu l ja suuremate võtmetega alampuu r ühendada. Üks lahendus on asetada l alampuu r sisse kõige vasakpoolsema lehe asemele.

combine : Ord k => Tree k v -> Tree k v -> Tree k v
combine = ?rhs_combine

remove : Ord k => k -> Tree k v -> Tree k v
remove = ?rhs_remove

Testimiseks võib kasutada järgnevaid võrdsusi

  combine (T E 1 "1" E) E == T E 1 "1" E
  combine (T E 1 "1" E) (T E 2 "2" E) == T (T E 1 "1" E) 2 "2" E
  sort (treeToList (remove 1 test124)) == [(2, "kaks"), (4, "neli")]
  sort (treeToList (remove 2 test124)) == [(1, "\252ks"), (4, "neli")]
  sort (treeToList (remove 3 test124)) == [(1, "\252ks"), (2, "kaks"), (4, "neli")]

8. Implementeeri puude üldine ühendamine

Kui võtmele k vastab mingi väärtus v puus r, siis peab peab ka union l r-s võtmele k vastama v. Kui võtmele k vastab mingi väärtus v puus l aga puus r sellele väärtust ei leidu, siis peab peab union l r-s võtmele k vastama v.

Soovitame kasutada eelnevalt implementeeritud fold-i.

NB! Siin ei saa funktsiooni combine kasutada, kuna me ei tea, et esimese argumendi sees olevad võtmed oleksid väiksemad kui teises argumendis olevad võtmed.

union : Ord k => Tree k v -> Tree k v -> Tree k v
union = ?rhs_union

Testimiseks võib kasutada järgnevaid võrdsusi

  union (the (Tree Int Int)E) E == E
  union (T E 1 "1" E) E == T E 1 "1" E
  union (T E 1 "y" E) (T E 1 "1" E) == T E 1 "1" E
  sort (treeToList (union test124 (T E 3 "3" E))) == [(1, "\252ks"), (2, "kaks"), (3, "3"), (4, "neli")]

9. Kasutades puid, implementeeri elemendi hulka lisamine

Esmalt, hulgad on puud, kus väärtuste tüüp on (). Seega:

Set : Type -> Type
Set a = Tree a ()

empty : Set a
empty = E

setToList : Ord a => Set a -> List a
setToList = fold (\x,(),xs=>x::xs) []

Nüüd implementeerime uue elemendi hulka lisamise funktsiooni:

add : Ord a => a -> Set a -> Set a
add = ?rhs_add

Testimiseks võib kasutada järgnevaid võrdsusi

  setToList (add 1 empty) == [1]
  sort (setToList (add 1 (add 2 empty))) == [1, 2]

10. Implementeeri hulga lahutamine

delete : Ord a => Set a -> Set a -> Set a
delete = ?rhs_delete

Testimiseks võib kasutada järgnevaid võrdsusi

  delete (T (T E 1 () E) 2 () E) (T E 1 () E) == T E 2 () E
  delete (T (T E 1 () E) 2 () E) (T E 2 () E) == T E 1 () E
  delete (T (T E 1 () E) 2 () E) (T E 3 () E) == T (T E 1 () E) 2 () E

11. Implementeeri hulkade ühisosa operatsioon

intersect : Ord a => Set a -> Set a -> Set a
intersect x = ?rhs_intersect

Testimiseks võib kasutada järgnevaid võrdsusi

  intersect (T (T E 1 () E) 2 () E) E == E
  intersect (T (T E 1 () E) 2 () E) (T E 1 () E) == T E 1 () E
  intersect (T (T E 1 () E) 2 () E) (T E 2 () E) == T E 2 () E

---

Kontrolltööks valmistumine

Näidiskontrolltöö siin (ja lahendus siin)