Funktsionaalprogrammeerimine 2025/26 sügis

Kodutöö 3

Listikomprehensioon

Konspekt

Lisalugemine (vabatahtlik):

Raamatust:

• konstandid
• listikomprehensioon

lõik Idris2 tutorialis:

• List comprehension

Praktikumi ja kodutöö ülesanded

1. Konstantidega {$\lambda$}-arvutus

Videos nägite järgnevaid näiteid reduktsioonist {$\lambda$}-arvutuses:

• {$\textsf{add}\ (\textsf{mul}\ 2\ 3)\ 1 \to \textsf{add}\ 6\ 1 \to 7$}
• {$(\lambda x.\ x\ 3\ 2)\ \textsf{mul} \to \textsf{mul}\ 3\ 2 \to 6$}

Redutseeri järgnevad termid:

1. {$ \textsf{mul}\ (\textsf{add}\ 1\ 2)\ 3 $}
2. {$ \textsf{mul}\ (\textsf{add}\ \textsf{true}\ \textsf{true})\ 3 $}
3. {$ \textsf{cond}\ (\textsf{iszero}\ (\textsf{sub}\ 3\ 2))\ 0\ 4 $}
4. {$ \textsf{add}\ (\textsf{cond}\ (\textsf{iszero}\ 0)\ 0\ 4)\ 3 $}
5. {$ \textsf{cond}\ (\textsf{cond}\ \textsf{true}\ 3\ 4)\ 0\ 3$}

2. Vabade muutujate leidmine

Leia termidest vabad muutujad!

1. {$ \text{FV}(\lambda{}f.\ (\lambda{}g.\ g\ x)\ (\lambda{}x.\ f\ x))$}
2. {$ \text{FV}((\lambda{}x.\ (\lambda{}g.\ g\ x))\ x)$}
3. {$ \text{FV}(\lambda{}g.\ (\lambda{}f.\ f\ x)\ (\lambda{}x.\ g\ x))$}
4. {$ \text{FV}((\lambda{}y.\ y)\ (\lambda{}f\ x.\ y\ x)\ (\lambda{}x.\ g\ x))$}
5. {$ \text{FV}(z\ \lambda{}h\ x.\ (\lambda{}f.\ h\ f)\ x)$}

3. Substitutsioon

Leia substitutsiooni tulemus!

1. {$ (\lambda{}f.\ f\ y(\lambda{} x. x))[y \to \lambda{}x\ y.\ f\ x] $}
2. {$ (\lambda{}x.\ f\ (x\ x))(\lambda{}x.\ f\ (x\ x))[f\to \lambda{}x\ y.\ y] $}
3. {$ (\lambda{}x\ g\ y. x\ g\ y)[g\to x\ g\ y] $}

4. Väikesed, seitsmega jaguvad arvud

Kasutades listikomprehensiooni, leia kõik naturaalarvud mis on väiksemad kui 1000 ja jaguvad seitsmega. Mitu neid on?

mod7 : List Int
mod7 = ?rhs_mod7

Näide:

  Main> length mod7
  143

5. tähtede loendamine sõnes

Kasutades listikomprehensiooni, kirjuta funktsioon mis loendab etteantud sõnes esimese parameetrina antud tähe leidumiste arvu. Vihje: funktsioon unpack teisendab sõne tähtede listiks.

count : Char -> String -> Nat
count c s = ?rhs_count

näiteks:

  Main> count 's' "Mississippi"
  4

6. listide lamendamine

Kasutades listikomprehensiooni, kirjuta funktsioon mis teisendab listide listid listideks hoides alles kõik elemendid samas järjekorras.

concat' : List (List a) -> List a
concat' xss = ?rhs_concat

näiteks:

  Main> concat' [ [1,2,3], [4,5], [6], [] ]
  [1, 2, 3, 4, 5, 6]

7. arvu faktorid

Kasutades listikomprehensiooni, kirjuta funktsioon mis leiab parameetrina antud arvu n täisarvulised faktorid s.t. arvud, millega n-i jagades ei teki jääki.

factors : Int -> List Int
factors n = ?rhs_factors

näiteks:

  Main> factors 15
  [1, 3, 5, 15]
  Main> factors 18
  [1, 2, 3, 6, 9, 18]

8. väikeste algarvude leidmine

Algarvud on täisarvud, mille faktoriteks on üks ja arv ise.

isPrime : Int -> Bool
isPrime n = factors n == [1,n]

Kasutades listikomprehensiooni, kirjuta funktsioon mis leiab parameetrina antud arvust n kõik väiksemad algarvud.

primes : Int -> List Int
primes n = ?rhs_primes

näiteks:

  Main> primes 14
  [2, 3, 5, 7, 11, 13]

9. Funktsioon zip'

Kirjuta lihtrekursiivne funktsioon, mis teisendab listide paarid paaride listiks.

zip' : List a -> List b -> List (a,b)
zip' = ?rhs_zip

näiteks:

  Main> zip' [] [1,2,3]
  [] 
  Main> zip' [1,2,3] ['a', 'b', 'c', 'd']
  [(1, 'a'), (2, 'b'), (3, 'c')]

10. järjestikuste elementide paarid

Kasutades funktsiooni zip', kirjuta funktsioon mis leiab parameetrina antud listist kõik järjestikuste elementide paarid.

pairs : List a -> List (a,a)
pairs xs = ?rhs_pairs

näiteks:

  Main> pairs [1..6]
  [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]

11. Funktsioon and'

Kirjuta lihtrekursiivne funktsioon, mis kontrollib kas kõik listis olevad väärused on tõesed.

and' : List Bool -> Bool
and' = ?rhs_and

näiteks:

  Main> and' [True, True, True]
  True
  Main> and' [True, True, False]
  False

12. sorteerituse kontrollimine

Kasutades listikomprehensiooni ja eelnevalt defineeritud abifunktsiooni and' ning pairs, et kontrollida, kas parameetrina antud list on sorteeritud -- elemendid mittekahanevas järjekorras .

sorted  : List Int -> Bool
sorted = ?rhs_sorted

näiteks:

  Main> sorted [1..10]
  True
  Main> sorted [1,2,4,3]
  False
  Main> sorted [3,2,1]
  False

13. Pythagorase kolmikud

Positiivsete täisarvude kolmik {$(a,b,c)$} on Pythagorase kolmik, kui kehtib võrdus {$a^2+b^2=c^2$}.

Kasutades listikomprehensiooni, leia kõik Pythagorase kolmikud, mille komponendid on võrdsed või väiksemad kui etteantud parameeter.

pyths : Int -> List (Int,Int,Int)
pyths n = ?rhs_pyths

näiteks:

  Main> pyths 10
  [(4, (3, 5)), (3, (4, 5)), (8, (6, 10)), (6, (8, 10))]

Tärnülesanded

Täiuslikud arvud

Täisarv {$n$} on täiuslik kui kõik tema täisarvuliste faktorite (v.a. arv ise) summa on arv {$n$}. Näiteks 6 saab jagada kolmega, kahega ja ühega ning 3+2+1=6.

Kasutades listikomprehensiooni, leia kõik täiuslikud arvud, mis on võrdsed või väiksemad kui etteantud parameeter.

perfects : Int -> List Int
perfects n = ?rhs_perfects

näiteks:

  Main> perfects 30
  [6, 28]

Optimeeritud Pythagorase kolmikud

Optimeeri Pythagorase kolmikute ülesande lahendust selliselt, et arvutatakse vaid kolmikud {$(a,b,c)$} kus {$a<b$}. Pane tähele, et lisakontrolli lisamine pole optimieerimine -- see teeb lahenduse ju aeglasemaks. Mõelge, kuidas saaks piirata proovitavate kolmikute arvu.

näiteks:

  Main> pythsOpt 10
  [(3, (4, 5)), (6, (8, 10))]