Alapok, nyelvi konstrukciók

Az alábbi feladatok teljes implementálása saját munka: tiltottak a rövidített kifejezések, generátorok, stb (pl. [1..N]). Használjatok rekurziót és mintaillesztést.

1. Kifejezések kiértékelése
(1 pont)

Írjunk egy függvényt, mely egy pozitív N-re kiszámolja a számok összegét 1től N-ig. Például:
sum 5 ⇒ 15

Írjuk meg ennek egy kétparaméteres változatát mely N-től M-ig összeadja a számokat. Például:
sum 1 3 ⇒ 6
sum 6 6 ⇒ 6

2. Listák készítése
(1 pont)

Írjunk egy függvényt mely előállít egy listát 1-től N-ig a természetes számokból.
create_list 3 ⇒ [1, 2, 3]

Írjunk egy függvényt mely fordított sorrendben állítja elő az előző listát.
reverse_create 3 ⇒ [3, 2, 1]

3. Mellékhatások
(1 pont)

Írjunk függvényt, mely kiírja az összes természetes számot 1-től N-ig a képernyőre.
Tipp: putStrLn-al lehet kiíratni, s ugye show-al String-gé alakítani.

Írjunk egy függvényt, mely csak a párosakat írja ki.
Tipp: Őrkifejezéseket használjatok.

4. Egyszerű "adatbázis" listákkal
(3 pont)

Írjunk függvényeket adatbázis kezelésére: az adatbázist létrehozzák, lehetővé teszik elemek beszúrását, keresést az adatok között, illetve elemek törlését.
Implementáljuk az összes függvényt/rekurziót!

Az adatbázis interfész legyen az alábbi:

new ⇒ db 
write db key value  ⇒ newdb 
delete db key ⇒ newdb 
read db key ⇒ ("ok", value) | ("error", "not found") 
match db value ⇒ [key1, key2, ..., keyN]

Példa:

> :l db.hs
[1 of 1] Compiling Main( db.hs, interpreted )
Ok, modules loaded: Main.
> let db = new
[]
> let db1 = write db "karesz" "java"
[("karesz", "java")]
> let db2 = write db1 "hz" "haskell"
[("hz", "haskell"), ("karesz", "java")]
> read db2 "karesz"
("ok", "java")
> let db3 = write db2 "darvay" "java"
[("darvay", "java"), ("hz", "haskell"), ("karesz", "java")]
> read db3 "agoston"
("error", "not found")
> match db3 "java"
["darvay", "karesz"]
> let db4 = delete db3 "karesz"
[("darvay", "java"), ("hz", "haskell")]
> match db4 "haskell"
["hz"]

Segítség:
Mivel a read két lehetséges típust téríthet vissza, használjátok az Either típusosztályt.

5. Listakezelés
(2 pont)

Írjunk függvényt, mely egy listából kiválogatja azon elemeket melyek kisebbek, mint egy adott szám.

filter [1, 2, 3, 4, 5, 3, 0] 4 ⇒ [1, 2, 3, 3, 0]

Írjunk függvényt, mely egy lista elemeinek sorrendjét megfordítja.

reverse [1, 2, 3] ⇒ [3, 2, 1]

Írj egy függvényt mely egy listákból álló listából egy egyszerű listát készít.

concatenate [[1, 2, 3], [4], [5, 6]] ⇒ [1, 2, 3, 4, 5, 6]

6. Rendezések
(2 pont)

Implementáljuk az alábbi két rendező algoritmust:

Quicksort
A lista feje a pivot/osztó elem. A listát kettéosztjuk aszerint, hogy az elemek kisebbek vagy nagyobbak az osztóelemnél. Mindkét listát rekurzívan rendezzük, majd összefűzzük a két eredménylistát, az osztó elemet helyezve középre.

Mergesort
Az eredeti listát kettéosztjuk fele-fele arányban, mindkét részlistát rekurzívan rendezzük, majd a kettőt összefésüljük.