13. Haskell in razredi tipov¶

Danes bomo spoznali programski jezik Haskell in razrede tipov (angl. type classes), ki so še en način za organizacijo kode in funkcionalnosti. Haskell je deklarativni jezik, ki se odlikuje po tem, da je tudi čist (angl. pure), kar pomeni, da v osnovi nima računskih učinkov (stanje, I/O, izjeme). O računskih učinkih in o tem, kako so implementirani z monadami, bomo govorili naslednjič.

Haskell lahko opredelimo kot programski jezik, ki je:

deklarativni jezik z leno evaluacijo
je funkcijski jezik: funkcije so vrednosti
ima koinduktivne tipe in zapise
ima parametrični polimorfizem in izpeljavo tipov
čist jezik: vsi računski učinki (stanje, I/O, izjeme) so eksplicitno zavedeni v tipu izraza
ima razrede tipov

13.1. Osnovno o Haskellu¶

Mnoge koncepte, ki nastopaj v programskem jeziku Haskell, že poznamo. Danes bomo spoznali

13.1.1. Konkretna sintaksa¶

Zamikanje¶

V Haskellu je treba kodo pravilno zamikati, podobno kot v Pythonu. V nekaterih primerih se lahko zamikanju izognemo z uporabo alternativne sintakse { ... ; ... ; ... }. Primer bomo videli kasneje.

Imena¶

Imena spremenljivk se pišejo z malo začetnico: x, y, …
Imena tipov se pišejo z veliko začetnico: Int, Bool, Char, …
Parametri v polimorfnih tipih se pišejo z malo začetnico: a, b, c, …
Imena konstruktorjev algebraičnih tipov se pišejo z veliko

Definicije¶

Vrednost t tipa A zapišemo

t :: A
t = defincija-t

Pozor: zapis t :: A pomeni »t ima tipa A« zapis x :: ℓ pa pomeni seznam z glavo x in repom ℓ (ravno obratno kot v OCamlu).

Definicija ima lahko tudi več vrstic, na primer:

f :: Int -> Int
f 0 = 1
f 1 = 1
f n = n * f (n - 1)

Definicije so lahko rekurzivne.

Tip v definiciji ni treba podati in smemo zapisati samo

t = defincija-t

V tem primeru bo Haskell izpeljal tip t. Vendar pa je v Haskellu navada, da se zapiše tip vrednosti, ki jo definiramo.

Lokalne definicije¶

Lokalno definicijo zapišemo

let x = e₁
in
  e₂

ali

e₂ where x = e₁

Določilu where lahko sledi več definicij:

e₁ where
  x = e₂
  y = e₃
  z = e₄

Seznami¶

Prazen seznam zapišemo z [], stik glave x z repom ℓ zapišemo x : ℓ, elemente lahko tudi naštejemo z [x₁, x₂, ..., xᵢ].

Seznam števil od 1 do n zapišemo [1..n] in podobno za interval [a..b].

Haskell ima izpeljane sezname (angl. list comprehension), podobno kot Python:

matematika: {f(x) | x ∈ A} je množica elementov f(x), kjer je x ∈ A
Python [f(x) for x in ℓ] je seznam elementov f(x), kjer x preteče seznam ℓ
Haskell [f x | x <- ℓ] je seznam elementov f x, kjer x preteče seznam ℓ

Podrobnosti o izpeljanih seznamih si preberite na zgornji povezavi.

Funkcije¶

Funkcijo x ↦ e zapišemo kot \ x -> e, kar nas spominja na λ x . e.

Naloga: Zakaj se ta programski jezik imenuje Haskell?

Izraz `case`¶

Izraz

case e of
  p₁ -> e₁
  p₂ -> e₂
  ...
  pⱼ -> eⱼ

primerja e z vzorci p₁, ..., pⱼ. Vrednost izraza je enaka eᵢ, kjer je pᵢ prvi vzorec, ki se ujema. Torej je case podoben izrazu match iz OCaml.

Opozorilo

OCaml opozori na manjkajoče primere v match, Haskell tega ne počne.

Primeri morajo biti pravilno zamaknjeni, lahko pa uporabimo tudi sintakso

case e of { p₁ -> e_1 ; ... ; pⱼ -> eⱼ }

ki ne zahteva zamikanja. V Haskellu velja navada, da raje zamikamo kodo, kot da bi uporabljali { ... }.

13.1.2. Tipi¶

Imena tipov pišemo z velikimi črkami

Osnovni konstruktorji tipov¶

Osnovni tipi so Int, Char, Bool, …
a -> b je tip funkcij iz a v b
(a, b) je produktni tip, ki ga v Ocamlu pišemo a * b
[a] je tip seznamov elementov tipa a, v OCamlu a list

Definicije tipov¶

Haskell poznam definicije tipov

type T = ...

in definicije koinduktivnih algebraičnih tipov

data T = ...

Definicija type uvaja okrajšavo, data pa nov podatkovni tip.

(Tipe lahko definiramo tudi z newtype, ki ga ta trenutek ne bomo obravnavali.)

Na primer, sezname lahko definiramo takole:

data List a =
    Nil
  | Cons (a, List a)

Tip Maybe je definiran z

data Maybe a =
    Nothing
  | Just a

To je pravzaprav tip a option iz OCaml.

13.1.3. Primer: AVL drevesa¶

Več podrobnosti bomo spoznali tako, da bomo iz OCaml prepisali implementacijo AVL dreves v Haskell:

-- AVL drevesa v Haskellu

module Avl where

  -- višino drevesa merimo s celim številom
  type Height = Integer

  -- koinduktivni podatkovni tip AVL dreves
  data AVLTree a =
      Empty
    | Node a Height (AVLTree a) (AVLTree a)
    deriving Show

  -- primer drevesa
  t :: AVLTree Integer
  t = Node 5 3
      (Node 3 2
       (Node 1 1 Empty Empty)
       (Node 4 1 Empty Empty))
      (Node 8 1 Empty Empty)

  height :: AVLTree a -> Height
  height Empty = 0
  height (Node _ h _ _) = h

  leaf :: a -> AVLTree a
  leaf v = Node v 1 Empty Empty

  -- pametni konstruktor, ki poskrbi za višino
  node :: a -> AVLTree a -> AVLTree a -> AVLTree a
  node v l r = Node v (1 + max (height l) (height r)) l r

  -- drevo t zapisano s pamentim konstruktorjem
  t' :: AVLTree Integer
  t' = node 5
        (node 3
         (node 1 Empty Empty)
         (node 4 Empty Empty))
        (node 8 Empty Empty)

  -- drevo t zapisano še bolje
  t'' :: AVLTree Integer
  t'' = node 5
        (node 3
         (leaf 1)
         (leaf 4))
        (leaf 8)

  -- seznam elementov v drevesu
  toList :: AVLTree a -> [a]
  toList Empty = []
  toList (Node x _ l r) = toList l ++ (x : toList r)

  search :: Ord a => a -> AVLTree a -> Bool
  search x Empty = False
  search x (Node y _ l r) =
      case compare x y of
        EQ -> True
        LT -> search x l
        GT -> search x r

  test1 = search 1 t

  test2 = search 42 t

  rotateLeft :: AVLTree a -> AVLTree a
  rotateLeft (Node x _ a (Node y _ b c)) = node y (node x a b) c
  rotateLeft t = t

  rotateRight :: AVLTree a -> AVLTree a
  rotateRight (Node y _ (Node x _ a b) c) = node x a (node y b c)
  rotateRight t = t

  imbalance :: AVLTree a -> Integer
  imbalance Empty = 0
  imbalance (Node _ _ l r) = height l - height r

  balance :: AVLTree a -> AVLTree a
  balance Empty = Empty
  balance (t @ (Node x _ l r)) =
      case imbalance t of
        2 ->  case imbalance l of
                -1 -> rotateRight (node x (rotateLeft l) r)
                _ ->  rotateRight t
        -2 -> case imbalance r of
                1 -> rotateLeft (node x l (rotateRight r))
                _ -> rotateLeft t
        _ -> t

  add :: Ord a => a -> AVLTree a -> AVLTree a
  add x Empty = leaf x
  add x (t @ (Node y _ l r)) =
      case compare x y of
        EQ -> t
        LT -> balance (node y (add x l) r)
        GT -> balance (node y l (add x r))

  remove :: Ord a => a -> AVLTree a -> AVLTree a
  remove x Empty = Empty
  remove x (Node y _ l r) =
      let removeSuccessor Empty = error "impossible"
          removeSuccessor (Node x _ Empty r) = (r, x)
          removeSuccessor (Node x _ l r) = (balance (node x l' r), y) where (l', y) = removeSuccessor l
      in
        case compare x y of
          LT -> balance (node y (remove x l) r)
          GT -> balance (node y l (remove x r))
          EQ -> case (l, r) of
                  (_, Empty) -> l
                  (Empty, _) -> r
                  _ -> balance (node y' l r') where (r', y') = removeSuccessor r

13.2. Razredi tipov¶

Razrede tipov bomo razložili v živo na predavanjih s primerom:

-- Ideja: podatki imajo neko velikost
-- Funkcionalnost: tipi, katerih vrednosti imajo "velikost"

-- Razred, ki opisuje tiste tipe a, ki so opremljeni s funkcijo "size", ki slika v Int
class Sized a where
    size :: a -> Int

-- Funkcija, ki vrne velikost svojega argumenta, povečana za 3
f :: Sized a => a -> Int
f x = size x * 3

-- Booli so veliki 1 bit
instance Sized Bool where
    size True = 1
    size False = 1

-- Chari imajo velikost 8 bitov
instance Sized Char where
    size _ = 8

-- Inti so veliki 64 bitov
instance Sized Int where
    size x = 64

-- Velikost seznamov
instance Sized a => Sized [a] where
    size [] = 0
    size (x : xs) = size x + size xs

-- Velikost parov
instance (Sized a, Sized b) => Sized (a,b) where
    size (x, y) = size x + size y

-- Primeri

-- V Haskellu so nizi seznami znakov, se pravi [Char], zato Haskell iz zgornjih
-- instanc izpelje velikost niza kot 8 * dolžina niza.
demo1 = size "This string contains forty-two characters."

-- Če napišemo samo 14, dobimo tip Num a => a, če pa napišemo 14 :: Int,
-- Haskell prislimo, da ima 14 tip Int. (Če bi napisali 14 :: Float, bi
-- ga prisilil, da bi imel tip Float).
demo2 = size [(14 :: Int), 15]

demo3 = size ("foo", (False, 42 :: Int))

13.2.1. Razredi tipov v standardni knjižnici¶

Ogledali si bomo nekatere najbolj uporabne razrede v standardni knjižnici:

Principi programskih jezikov

Haskell in razredi tipov

Vsebina

13. Haskell in razredi tipov¶

13.1. Osnovno o Haskellu¶

13.1.1. Konkretna sintaksa¶

Zamikanje¶

Imena¶

Definicije¶

Lokalne definicije¶

Seznami¶

Funkcije¶

Izraz `case`¶

13.1.2. Tipi¶

Osnovni konstruktorji tipov¶

Definicije tipov¶

13.1.3. Primer: AVL drevesa¶

13.2. Razredi tipov¶

13.2.1. Razredi tipov v standardni knjižnici¶

Principi programskih jezikov

Haskell in razredi tipov

Vsebina

13. Haskell in razredi tipov¶

13.1. Osnovno o Haskellu¶

13.1.1. Konkretna sintaksa¶

Zamikanje¶

Imena¶

Definicije¶

Lokalne definicije¶

Seznami¶

Funkcije¶

Izraz case¶

13.1.2. Tipi¶

Osnovni konstruktorji tipov¶

Definicije tipov¶

13.1.3. Primer: AVL drevesa¶

13.2. Razredi tipov¶

13.2.1. Razredi tipov v standardni knjižnici¶

Izraz `case`¶