Programming Languages 2020/21 fall

4. Haskelli kodutöö

Lahenda järgmised ülesanded Haskelli moodulisse Kt4.

Moodle'ist leiad ka lahendusfaili malli Kt4.hs.

1. ülesanne (1p)

Olgu kahendpuud defineeritud järgnevalt:

data BinTree a = Leaf (Maybe a) | Node (BinTree a) a (BinTree a)
  deriving (Show, Eq)

Näiteks:

     Node
    /  | \
Leaf   2  Node
  |      /  | \      = Node (Leaf (Just 1)) 2 (Node (Leaf Nothing) 4 (Leaf (Just 5)))
Just Leaf   4  Leaf
  |    |         |
  1  Nothing   Just
                 |
                 5

1a. ülesanne (0.3p)

Kirjuta funktsioon, mis loob listist "vasakule kaldu" oleva puu.

Näiteks:

                           Node
                          /  | \
                      Node   1  Leaf
vasak [1,2,3] =      /  | \       |
                 Leaf   2  Leaf Nothing
                   |         |
                 Just      Nothing
                   |
                   3

             Leaf
vasak [] =     |
             Nothing

vasak :: [Int] -> BinTree Int
vasak xs = undefined

1b. ülesanne (0.3p)

Kirjuta funktsioon, mis leiab puust suurima arvu (kui see leidub).

Näiteks:

maks (Node (Leaf (Just 3)) 1 (Leaf (Just 2))) ==> Just 3
maks (Leaf Nothing) ==> Nothing

maks :: BinTree Int -> Maybe Int
maks t = undefined

1c. ülesanne (0.4p)

Kirjuta Foldable tüübiklassi instants BinTree tüübile, mis võimaldaks mittetühjadel kahendpuudel kasutada standardset maximum funktsiooni.

Näiteks:

maximum (Node (Leaf (Just 3)) 1 (Leaf (Just 2))) ==> 3

instance Foldable BinTree where
  foldMap f t = undefined

Standardne maximum funktsioon ei tööta tühjadel struktuuridel, sest selle tagastustüüp ei kasuta Maybe-t.

foldMap asemel võib implementeerida ka foldr.

2. ülesanne (1p)

Kasutame State monaadi rahakoti esitamiseks ja opereerimiseks, kus seisundiks on praegu rahakotis olev summa. Olgu selleks defineeritud järgmised tüübid:

type Raha = Integer
type RahakottSeisund = Raha
type RahakottArvutus a = State RahakottSeisund a
data RahakottViga = NegatiivneArgument | LiigaVäheRaha
  deriving (Show, Eq)
type RahakottTulemus = Either RahakottViga ()

State monaadi kasutamiseks lisa faili päisesse import Control.Monad.State.

2a. ülesanne (0.3p)

Kirjuta protseduur, mis tagastab praegu rahakotis oleva summa.

saldo :: RahakottArvutus Raha
saldo = undefined

2b. ülesanne (0.3p)

Kirjuta protseduur, mis lisab rahakotti antud summa (ja tagastab Right ()). Kui antud summa on negatiivne, siis summat ei muuda ja tagastab Left NegatiivneArgument.

sisse :: Raha -> RahakottArvutus RahakottTulemus
sisse n = undefined

2c. ülesanne (0.4p)

Kirjuta protseduur, mis eemaldab rahakotist antud summa (ja tagastab Right ()). Kui antud summa on negatiivne, siis summat ei muuda ja tagastab Left NegatiivneArgument. Kui rahakotis piisavalt raha pole, siis summat ei muuda ja tagastab Left LiigaVäheRaha.

välja :: Raha -> RahakottArvutus RahakottTulemus
välja n = undefined

3. ülesanne (1p)

Vaatleme avaldispuid, mis koosnevad täisarvulistest konstantidest, mündivisetest (tulemusega 0 või 1), liitmistest ja jagamistest. Olgu selleks defineeritud järgmine tüüp:

data Expr = Const Int | Coin | Add Expr Expr | Div Expr Expr
  deriving (Show, Eq)

Näiteks:

expr1 = Div (Add (Const 3) (Const 1)) (Const 2)
expr2 = Add (Const 1) (Div (Const 1) (Add (Const 1) (Const (-1))))
expr3 = Add Coin Coin
expr4 = Div (Add (Const 3) Coin) (Const 2)
expr5 = Add (Add Coin Coin) (Div (Const 1) (Add Coin (Const (-1))))

Kirjuta funktsioon, mis tagastab antud avaldise kõikvõimalikud väärtused. Nulliga jagamised tuleb võimalike tulemuste listist välja arvata. Kui mingi tulemus tekib mitmel moel, siis tuleb see korduvalt listi jätta, kuid järjekord pole oluline.

Näiteks:

evalExpr (Const 5) ==> [5]
evalExpr Coin ==> [0, 1]
evalExpr (Add (Const 5) Coin) ==> [5, 6]
evalExpr (Add Coin Coin) ==> [0, 1, 1, 2]
evalExpr expr4 ==> [1, 2]
evalExpr expr5 ==> [-1, 0, 0, 1]

evalExpr :: Expr -> [Int]
evalExpr e = undefined

Analoogilisele praktikumiülesande lahendusele piisab lisada vaid üks rida!