Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 16: Razno

v1.0

(c) 2011 Jan Šnajder

==============================================================================

> import Data.List
> import Control.Monad
> import Data.Maybe
> import System.IO

== STRIKTNOST ================================================================

Haskell je lijen i ne evaluira izraze dok ih ne treba evaluirati.

> e1 = head [1,2..]

Kako to funkcionira? Haskell ne evaluira listu, nego generira "THUNK" ili
SUSPENZIJU (vrijednost koju tek treba evaluirati). Suspenzija će se evaluirati
tek kada to bude stvarno potrebno.

Drugi primjer lijene funkcije:

  (&&) :: Bool -> Bool -> Bool
  False && _ = False
  True  && x = x

U većini slučajeva lijenost to nam odgovara, ali nekad ne. Primjer kada nam ne
odgovara:

> filesize :: FilePath -> IO Int 
> filesize f = withFile f ReadMode $ \h -> do 
>   s <- hGetContents h 
>   return $ length s

Problem je što je 'hGetContents' svoj izlaz (string) generira na lijen način,
odnosno generira ga po potrebi. Funkcija 'length' će natjerati funkciju
'hGetContents' da generira cijeli string, ali je problem što se niti 'length'
neće izvesti dok to nužno ne mora. Posljedično, samim pozivom funkcije
'filesize' neće se ništa učitati iz datoteke. Tek kada želimo na ekran ispisati
rezultat funkcije 'filesize', mora se čitati iz datoteke. Problem je u tome što
će, u trenutku kada se to dogodi, ručica datoteke već biti zatvorena i
'hGetContents' vraća prazan string.

Drugi problem:

> e2 = foldl (+) 0 [0..100]
> e2' = foldl (+) 0 [0..10000000]

Ovdje koristimo lijevo presavijanje:

  foldl :: (a -> b -> a) -> a -> [b] -> a
  foldl f z []     = z                  
  foldl f z (x:xs) = foldl f (f z x) xs

Prisjetimo se: lijevo presavijanje je dobro jer je repno rekurzivno. No unatoč
tome, ovdje imamo problem jer se 'f z x' ne evaluira, nego gradi tzv.
SUSPENZIJE (ili THUNKS):

  foldl (+) 0 [1..10] =>
  foldl (+) 0 (1:[2..10]) =>
  foldl (+) (0+1) (2:[3..10]) =>
  foldl (+) (0+1+2) (3:[4..10]) =>
  foldl (+) (0+1+2+3) (4:[5..10]) => ...

Na neki način trebamo funkciju prisiliti evaluaciju izraza 'f z x'. Za to služi
sljedeća funkcija:

  seq :: a -> b -> b

Funkcija 'seq' evaluira prvi argument prije nego što vrati drugi argument.

Npr.:

> e3 = let x = undefined in 2
> e4 = let x = undefined in x `seq` 2

Sada možemo definirati "striktnu" (nelijenu) verziju presavijanja:
  
  foldl' f z []     = z
  foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs

> e5 = foldl' (+) 0 [0..10000000]

Rješenje drugog problema:

> filesize' :: FilePath -> IO Int 
> filesize' f = withFile f ReadMode $ \h -> do 
>   s <- hGetContents h 
>   s `seq` return (length s) 

Možemo također definirati striktnu verziju operatora aplikacije ($):

  ($!) :: (a -> b) -> a -> b
  f $! x = x `seq` f x

'f $! x' će prvo evaluirati argument 'x', a onda na njega primijeniti funkciju.

Npr.

> e8 = let x = undefined in const 5 x
> e9 = let x = undefined in const 5 $! x

No treba znati da `seq` ne evaluira argument previše duboko:

> e10 = let x = undefined in x `seq` 2
> e11 = let x = Just undefined in x `seq` 2

Zapravo, 'seq' evaluira samo vanjski konstruktor (odnosno reducira izraz na
WEAK HEAD NORMAL FORM). Kada to nije dovoljno, treba se pobrinuti sa se 'seq'
primijeni dublje na podizraze. Za to se može koristiti paket 'deepseq':
http://hackage.haskell.org/package/deepseq

== MODULI ====================================================================

Program ili biblioteka u Haskellu je zbirka modula. Svi standardni moduli
Haskella definirani su u biblioteci "Haskell Hierarchical Libraries":
http://www.haskell.org/ghc/docs/latest/html/libraries/

Već znamo kako učitavamo module ili funkcije iz pojedinih modula:

  import Data.List
  import Data.List (lookup)           -- učitava samo funkciju 'lookup'
  import Data.List hiding (lookup)    -- učitava sve osim funkcije 'lookup'
  import qualified Data.Map
  import qualified Data.Map as M

Definiranje modula u Haskellu je jednostavno. Svaki modul definira se u
zasebnoj datoteci. Moduli mogu biti organizirani hijearhijski, kao npr.
'Data.List' ili 'Data.Time.Calendar'. To se postiže tako da se naprave
odgovarajući direktoriji. Npr.:

Data/List.hs           ==> modul 'Data.List'
Data/Time.hs           ==> modul 'Data.Time'
Data/Time/Calendar.hs  ==> modul 'Data.Time.Calendar'

U modulu se definiraju funkcije i podatkovne strukture (jednom riječu,
"vrijednosti"). Modul tipično eksportira samo neke funkcije i strukture (API),
dok ostale ostaju skrivene (pomoćne funkcije i pomoćne strukture).

Npr.:

--- datoteka Data/Trie.hs ---

module Data.Trie (
  Trie,
  insert, 
  lookup,
  remove,
  ... ) where

data Trie k a = 
  Leaf a | Branch [(k,Trie k a)] deriving (Eq,Ord,Show,Read)

insert :: Eq k => [k] -> a -> Trie k a -> Trie k a
...

lookup :: Eq k => [k] -> Trie k a -> Maybe a
...

remove :: Eq k => [k] -> Trie k a -> Trie k a
...

-----------------------------

U gornjem primjeru eksportira se samo tipski konstruktor 'Trie', ali ne i
podatkovni konstruktori 'Leaf' i 'Branch'. To znači da korisnik modula neće
moći koristiti te podatkovne konstruktore, pa neće moći niti sam graditi
strukturu pomoću njih niti neće moći raditi podudaranje uzorka s tom
strukturom. Na taj način smo ograničili pristup strukturi kroz naš API:
korisnik može izvoditi samo operacije nad strukturom koje mu omogućavaju naše
funkcije.

Ako želimo eksportirati sve konstruktore, pišemo:

module Data.Trie (
  Trie (..),

Ako želimo eksportirati samo neke, pišemo:
  
module Data.Trie (
  Trie (Leaf),

== PAKETI ====================================================================

Paket objedinjava jedan modul ili više njih u svrhu lakše distribucije i
instalacije. Paketi se instaliraju alatom CABAL.

http://www.haskell.org/haskellwiki/Cabal-Install

== RESURSI ===================================================================

Haskell Hierarchical Libraries
http://www.haskell.org/ghc/docs/latest/html/libraries/

Hackage
http://hackage.haskell.org

GHC
http://www.haskell.org/ghc/

Hoogle
http://www.haskell.org/hoogle/

Hayoo! (pretražuje Hackage)
http://holumbus.fh-wedel.de/hayoo/hayoo.html

Haskell Wiki
http://en.wikibooks.org/wiki/Haskell

Haskell mailing lists
http://www.haskell.org/haskellwiki/Mailing_Lists

Haskell IRC channel
http://www.haskell.org/haskellwiki/IRC_channel

Haskell Communities and Activities Report (HCAR)
http://www.haskell.org/haskellwiki/Haskell_Communities_and_Activities_Report

Haskell Weekly News
http://sequence.complete.org/

Monad Reader
http://themonadreader.wordpress.com/

Haskellers
http://www.haskellers.com/

== KAKO DALJE? ===============================================================

Što još treba znati?

- Upoznati hijerarhijsku biblioteku (osobito module Data.*)
- Upoznati važnije pakete s Hackagea
- Znati QuickCheck (provjera koda)
- Znati Haddok (pisanje dokumentacije)
- ...

Preporuka za dalje: 

- prvo pročitati:
  http://learnyouahaskell.com/

- zatim pročitati:
  http://book.realworldhaskell.org/read/