Haskell

Spoznali bomo funkcijski programski jezik Haskell. Standardni prevajalnik / tolmač za Haskell je GHC, ki je na voljo za vse glavne platforme, na vajah pa bomo programirali kar v brskalniku (Chrome ima občasno težave, Firefox dela). Da se izognemo sporočilu o nedefinirani spremenljivki main, v urejevalnik dodamo vrstico

main = return ()

Haskell je v osnovi podoben jeziku OCaml, z nekaterimi razlikami v sintaksi in vrsto dodatnih konstruktov. Pregled sintakse najdete tukaj.

Tipi in funkcije

Tako kot OCaml tudi Haskell samodejno izpelje tipe vseh izrazov. Ko definiramo funkcijo, najprej običajno vseeno zapišemo njen tip – to nam lahko precej pomaga pri implementaciji. Tipe zapišemo podobno kot v OCaml, le da

• za sezname pišemo [a] namesto 'a list in
• za terke pišemo (a,b) namesto a * b.

Tip Int -> Int -> [Int] tako predstavlja funkcijo, ki sprejme dve števili in vrne seznam števil, tip [(Int, Bool)] -> [[Int]] pa funkcijo, ki sprejme seznam parov (število, boolova vrednost) in vrne seznam seznamov števil. Poleg tipa Int pozna Haskell tudi tip Integer, ki podpira poljubno velika števila.

Funkcije definiramo podobno kot v OCaml:

map (\x -> x*x) [1,2,3,4,5]
=> [1,4,9,16,25]

Faktoriela

V Haskellu definirajmo funkcijo faktoriela. Najprej zapišemo njen tip – funkcija slika iz celih števil v cela števila, torej ima tip Int -> Int. Faktorielo nato rekurzivno definiramo tako:

-- funkcija, ki vzame število in vrne njegovo faktorielo
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)

Še en način, da definiramo faktorielo:

factorial :: Int -> Int
factorial n | n <= 1 = 1
            | otherwise = n * factorial (n-1)

V tej definicijo vidimo stranske pogoje ali stražarje, ki imajo splošno obliko

f x
  | p₁ = e₁
  | p₂ = e₂
  ⋮
  | pᵢ = eᵢ

To preberemo: "f x se slika v e₁ če velja pogoj p₁, sicer se slika v e₂ če velja p₂, ..., sicer se slika v eᵢ če veljapᵢ". Določilo otherwise vedno obvelja, če ne velja noben od prejšnjih pogojev.

Naloga: Fibonaccijeva števila

Definirajte funkcijo fib, ki vrne n-to Fibonaccijevo število, in zapišite njen tip.

Seznami

Kot vselej so seznami definirani kot rekurzivni podatkovni tip: prazen seznam zapišemo kot [], neprazen seznam, sestavljen iz glave x in repa xs pa kot x : xs. To definicijo je treba razumeti koinduktivno, se pravi da so lahko seznami končni ali neskončni. (V OCamlu morajo biti končni, ker je definicija induktivna.)

Definirajmo funkcijo member, ki preveri, če se število x pojavi v seznamu s:

member :: Int -> [Int] -> Bool
member x [] = False
member x (y : ys)
    | (x == y)  = True
    | otherwise = member x ys

Naloga: above

Sestavite funkcijo above, ki za dano število x in seznam s vrne True, če je x večji ali enak vsem elementom seznama s. Zapišite tudi tip funkcije.

Namig: konjunkcijo in disjunkcijo pišemo z && in ||.

Izpeljani seznami

Izpeljani seznami (angl. list comprehensions) so prikladno orodje za definiranje seznamov vrednosti, ki ustrezajo nekemu pogoju. Na primer:

prvih_dvajset = [1..20]
soda = [n | n <- prvih_dvajset, n `mod` 2 == 0]
fibonaccijeva_stevila = [fib n | n <- prvih_dvajset]

Seznam soda bi lahko definirali tudi tako, z uporabo pomožne funkcije f (kot let … in v OCaml):

soda =
    filter f [1..20] where
        f x = (mod x 2) == 0

Namesto f bi lahko uporabili neposredno funkcijo (kot fun … -> … v OCaml):

soda = filter (\x -> (mod x 2) == 0) [1..20]

Naloga: pari

Definirajte funkcijo pari, ki sprejme celo število n in vrne seznam vseh parov (i,j), kjer velja 1 ≤ i < j ≤ n. Zapišite tudi tip funkcije. Primer:

pari 4
=> [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

Neskočni seznami (tokovi)

Z neskončnimi seznami lahko elegantno programiramo. Poglejmo nekaj preprostih primerov:

• [0..] - seznam vseh naravnih števil 0, 1, 2, 3, ...
• [ k * k | k <- [0..] ] - seznam kvadratov naravnih števil 0, 1, 4, 9, ...
• [ (i, j) | i <- [0..], j <- [0..i] ] - seznam parov (i,j) kjer je i ≥ j: (0,0), (1,0), (1,1), (2,0), (2,1), (2,2), (3,0), ...
• [k | k <- [1..], k * kmod7 == 1] - seznam naravnih števil k, katerih kvadrat da pri deljenju s 7 ostanek 1: 1, 6, 8, 13, 15, ...

Če zgornje primere vnesemo v Haskell, le-ta začne izpisovati neskončen seznam. Če želimo videti le prvih 20 elementov, uporabimo funkcijo take, na primer:

take 20 [ (i, j) | i <- [0..], j <- [0..i] ]

Neskončne sezname lahko definiramo tudi rekurzivno. Na primer,

lst = 0 : [ k + 1 | k <- lst ]

je seznam lst, ki se začne z 0 in nadaljuje tako, da vsakemu elementu seznama lst prištejemo 1. Torej je drugi element 0 + 1 = 1, tretji je 1 + 1 = 2 in tako naprej. Dobimo ravno vsan naravna števila. Seznam

[1, 2, 3, 1, 2, 3, 1, 2, 3, ...]

kjer se 1, 2, 3 ponavljajo v nedogled definiramo takole:

lst = 1 : 2 : 3 : lst

Naloga

Definirajte neskončen seznam

[1, -2, 3, -4, 5, -6, ...]

Naloga

Definirajte funkcijo nedeljivi :: Int -> [Int] -> [Int] ki sprejme število k in seznam lst ter vrne seznam tistih elementov iz lst, ki niso deljivi s k. Primer uporabe:

> nedeljivi 3 [1,2,3,4,5,6,7,8,9,10]
[1,2,4,5,7,8,10]

Naloga: Eratostenovo sito

Definirajte funkcijo

eratosten :: [Int] -> [Int]

ki implementira Eratostenovo sito. Funkcija zadošča enačbi

eratosten (k : lst) = k : eratosten (nedeljivi k lst)

Nato definirajte

prastevila = eratosten [2..]

Ali ste dobili seznam vseh praštevil? Katero je 1000. praštevilo? (lst !! i vrne i-ti element seznama lst)

Problem n šahovskih dam

Spet se bomo lotili problema n šahovskih dam, tokrat v Haskellu. Za začetek si definiramo tip Square, ki predstavlja polje na šahovnici, in tip Queen, ki predstavlja položaj dame:

type Square = (Int, Int)
type Queen = Square

Tipa sta pravzaprav enaka, a je koristno med njima razločevati: Square uporabimo za koordinate polja, Qeen pa za koordinate šahovske dame. Za vse naloge spodaj najprej zapišite tip funkcije, nato pa jo definirajte.

Naloga: board

Definirajte funkcijo board n, ki vrne seznam polj na šahovnici velikosti n × n. Primer:

board 3
=> [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

Naloga: attacks

Definirajte funkcijo attacks q s, ki preveri, ali dama q napada polje s. Primer:

attacks (2,2) (4,4)
=> True
attacks (2,2) (3,4)
=> False

Naloga: attack

Definirajte funkcijo attack qs s, ki preveri, ali katerakoli dama v seznamu qs napada polje s. Primer:

attack [(1,1), (2,2), (3,3)] (4,4)
=> True
attack [(1,1), (2,2), (3,3)] (4,5)
=> False

Naloga: place1

Definirajte funkcijo place1 n x qs, ki na šahovnico velikosti n×n postavi damo v stolpec x tako, da je ne napada nobena izmed dam v seznamu qs. Funkcija naj vrne seznam vseh možnih rešitev. Primer:

place1 8 4 [(3,8),(2,5),(1,1)]
=> [(4,2),(4,6)]

Naloga: queens

Definirajte funkcijo queens, ki sprejme število n in poišče take sezname koordinat n-tih dam na šahovnici n×n, ki se med sabo ne napadajo. Funkcija naj vrne seznam vseh možnih rešitev – njen tip naj bo torej Int -> [[Queen]].

Pri definicji queens uporabite pomožno funkcijo place x qs, ki jo definirate kar znotraj funkcije queens z uporabo where. Funkcija place naj postavi dame v stolpce x do n tako, da jih ne napada nobena dama iz seznama qs in se ne napadajo med sabo. Vrne naj seznam vseh možnih rešitev, pri čemer vsako rešitev sestavlja seznam koordinat vseh dam (torej v stolpcih 1 do x).

Namig: pravi vam bo prišla funkcija concat :: [[a]] -> [a], ki seznam seznamov združi v en seznam.

Naloga: drobiz

Definirajte funkcijo drobiz bankovci vrednost, ki sprejme seznam različnih bankovcev, ki so na voljo, in vrednost, ki jo moramo izplačati, vrne pa seznam bankovcev, s katerimi lahko izplačamo to vrednost. Funkcija naj vrne seznam vseh možnih rešitev. Primer:

drobiz [10, 5, 2] 12
=> [[2,10],[2,5,5],[5,2,5],[10,2],[5,5,2],[2,2,2,2,2,2]]

Dodatna naloga: funkcija naj vrne le eno permutacijo vsake rešitve. Primer:

drobiz [10, 5, 2] 12
=> [[10,2],[5,5,2],[2,2,2,2,2,2]]