4. Programmering med hjälp av bibliotek
Aarne Ranta
Datorintroduktion 2009, D och DV, Chalmers & GU

%!target:html

%!postproc(html): #NEW <!-- NEW -->
%!postproc(html): #HR <HR>


#NEW

==Ett större uppdrag==

Uppgift: utifrån en text, skapa en **frekvenslista**, som anger
hur många gånger varje ord förekommer i texten:
```
  och     3247
  att     1892
  han     1694
  en      1671
  det     1633
  i       1604
  som     1526
  på      1275
  är      992
  jag     990
```
Programmet ska kunna köras som ett unix-filter, som i föregående föreläsningen:
```
  cat redRoom.txt | runghc Freq
```


#NEW

==Variationer av uppdraget==

1. Sortera listan alfabetiskt i stället för i frekvensordning.

2. Returnera antalet unika ord i texten.

3. Ange relativa frekvenser.

4. Ignorera interpunktion: ``med`` och ``med.`` ska vara samma ord.

5. Ignorera skillnaden mellan stora och små bokstaver: ``Med`` och ``med`` ska
   vara samma ord.

6. Ignorera HTML-taggar.



#NEW

==Vad har vi redan?==

Uppdraget är inte trivialt: om man skriver programmet från början krävs kanske
en sida av kod, eller mer.

Dessutom: det är lätt att //göra fel//, eller att programmet blir //oeffektivt//
(långsamt och/eller minneskrävande).

Vi ska i stället skriva ett //enkelt program//: ``translate``-funktionen blir
inte mer än tre rader kod!

Programmeringen består av två delar:
+ undersöka vilka funktioner som finns i **standardbibliotek**
+ dela upp algoritmen till delar som finns i bibliotek



#NEW

==API==

I Haskell, ett bibliotek är en modul med funktioner (och typer).

Varje funktion har, som vanligt, en typsignatur och en definition.

Exempel: sortering i biblioteket ``List``:
```
  sort :: Ord a => [a] -> [a]
  sort xs = ...


```
Definitionen av ``sort`` ser lite risig ut, och vi är glada att
vi inte behöver skriva den själva. I stället får vi den gratis
från biblioteket!


#NEW

==API==

**API** = Application Programmer's Interface. Detta är vad bibliotekets
//användare// vill se av biblioteket.

I Haskell ges APIt i form av, för varje funktion, en typsignatur och
en liten **beskrivning** (som kommentar) av vad funktionen gör:
```
  -- sort a list in ascending order
  sort :: Ord a => [a] -> [a]
```
Detta är det enda vi behöver veta om ``sort``.

Se [List API http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html]
för en full dokumentation; vi behöver bara en liten liten del idag.



#NEW

==Vad gör sort?==

Vi ska först experimentera i GHCi, och därför laddar vi biblioteket List:
```
  Prelude> :l List

  List> sort [3,1,2]
  [1,2,3]
```
Vad kan vi sortera? Typsignaturen kräver att typen av element i listan
är i klass ``Ord``; detta betyder att det är möjligt att jämföra
element och sätta dem i en storleksordning.

Det fulla APIt av Haskell-bibliotek säger vilka typer som är i Ord; nu nöjer vi
oss med att experimentera lite, för att se till att vi får det vi behöver.

#NEW

==Vad kan sorteras?==

Vi kan naturligtvis sortera heltal, flyttal, tecken och strängar:
```
  List> sort [1.0,0.999]
  [0.999,1.0]

  List> sort "abracadabra"
  "aaaaabbcdrr"

  List> sort (words "kan inte detta sorteras i haskell")
  ["detta","haskell","i","inte","kan","sorteras"]
```


#NEW

==Sortering av en fil==

Hur sorterar vi en fil? Just det: vi skriver ett textfilter:
```
  -- file Freq.hs
  module Main where
  import List

  main :: IO ()
  main = interact translate

  translate :: String -> String
  translate = sort
```
Vad händer om vi sorterar en fil med detta?
```
  $ cat ett.txt | runghc Freq
```


#NEW

==Sortering av orden i en fil==

Just det: vi får alla tecken i ordning. Först mellanslagen sedan interpunktion,
sedan stora bokstäver och till sist små, i alfabetisk ordning:
```
                                                            
                                                                       
    !,,,,,,--.....;;;;AADDDDEFGIJKLMPRRSSTTTaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbccccccccccccccdddddddddddddddddddddddddddddddddddd
dddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeefffffffffffffffffffffffggggg...
```
Låt oss sortera //ord// i stället för tecken:
```
  translate s = unwords (sort (words s))
```
Nu får vi ett resultat som ser ut så här:
```
  - De Den Det Där FÖRSTA Gråsparvarne Josefinadagen KAPITLET 
  Mosebacke Rosendal Stockholm afton allmänheten allting arbetat 
  att att att att av av av barège-lappar bersåer bjödo blivit blom, 
  blommor. bofinkarne, bon bort bygga bänkfot både början börjat de 
  de de de de! djur draga drogos där därför därinne efter ej en en 
  ett ett ett ...
```


#NEW

==Gruppering av element i en lista==

När vi sorterar en lista: inget element försvinner, inte ens duplikat.

Men alla förekomster av samma element ligger brevid varandra.

Vi kan utnyttja detta för att **gruppera** elementen.

I List-APIt hittar vi:
```
  -- take a list and return a list of lists such that the concatenation 
  -- of the result is equal to the argument. Moreover, each sublist 
  -- in the result contains only equal elements

  group :: Eq a => [a] -> [[a]]
```
Exempel:
```   
  List> group "mississippi" 
  ["m","i","ss","i","ss","i","pp","i"]

  List> group (sort "mississippi")
  ["iiii","m","pp","ssss"]
```



#NEW

==Från gruppering till frekvenser==

Hur kan vi använda gruppering för att räkna ut frekvenserna?

Jo: vi tar längden av alla listor i grupperingen
```
  List> [(head x, length x) | x <- group (sort "mississippi")]
  [('i',4),('m',1),('p',2),('s',4)]
```
Vi har valt ut ett elementet från varje lista, det första, med 
Prelude-funktionen ``head``
```
  head :: [a] -> a
```
Nu har vi frekvensen av varje tecken i "mississippi".

Men ingen sorterad frekvenstabell.


#NEW

==Sortering av frekvenstabellen==

Vi kan dock sortera en lista av par också; där sorterar man i första
had efter det första elementet, i andra hand efter det andra.

(Jfr. telefonkatalogen: ordningen följer 
i första hand efternamn, i andra hand förnamn.)
```
  List> sort [(head x, length x) | x <- group (sort "mississippi")]
  [('i',4),('m',1),('p',2),('s',4)]
```
Vi får alfabetisk sortering men ingen frekvenssortering. (Dessutom:
vi hade den ju redan från det första ``sort``!)


#NEW

==Från gruppering till frekvenssortering==

De räcker att vända om paret (ELEMENT,FREKVENS) och sortera sedan:
```
  List> sort [(length x, head x) | x <- group (sort "mississippi")]
  [(1,'m'),(2,'p'),(4,'i'),(4,'s')]
```
Hmm, detta blir från det minst till det mest frekventa, enligt "ascending order"
som APIt lovade.

Det enklaste vi kan göra nu är (om vi är i GHCi)
```
  List> reverse it
  [(4,'s'),(4,'i'),(2,'p'),(1,'m')]
```
Och nu har vi precis vad vi ville ha, förutom formatering!


#NEW

==Frekvenssortering av orden i en fil==

Det går nu att skriva en ny ``translate``-funktion som gör frekvenssortering:
```
  translate s = 
    show (reverse (sort ([(length x, head x) | x <- group (sort (words s))])))
```
Vi provkör detta:
```
  unix$ cat ett.txt | runghc Freq
  [(8,"och"),(7,"p\229"),(6,"i"),(4,"som"),(4,"ett"),(4,"de"),
  ...
```
Programmet gör rätt sak, förutom formattering. Men det ser ganska risigt ut...



#NEW

==Gruppfrekvens som en hjälpfukntion==

Titta på det här igen:
```
  translate s = 
    show (reverse (sort ([(length x, head x) | x <- group (sort (words s))])))
```
Det är en ganska snygg nestning med biblioteksfunktioner, förutom
listkomprehensionen.

Vi tar ut frekvensberäkningen till en egen hjälpfunktion:
```
  freqs :: [[a]] -> [(Int,a)]
  freqs xs = [(length x, head x) | x <- xs]
```
//Et voilà//:
```
  translate s = show (reverse (sort (freqs (group (sort (words s))))))
```
Ser ut som [Lisp http://sv.wikipedia.org/wiki/Lisp] 
("Lots of Irritating Superfluous Parentheses", eller "LISt Processing").

Haskell, i själva verket, är ungefär som Lisp med typer.



#NEW

==Funktioner och pipes==

Vi har lyckats stycka upp programmet till 7 funktioner, varav 6 kommer
från standardbibliotek (inklusive Prelude):
```
  translate s = show (reverse (sort (freqs (group (sort (words s))))))
```
Detta är mycket likt en //pipe// i Unix: sju program i sekvens, där output
från det ena skickas in som input till det nästa.

Om det fanns ett Unix-program för alla bitar (och visst skulle man kunna
skriva dem), skulle man kunna skapa frekvenstabellen med
```
  unix$ cat "ett.txt" | words | sort | group | freqs | sort | reverse | show
```
Alltså samma funktioner i baklänges ordning.

Och ännu viktigare: i en s.k. **punktfri stil**:
- man behöver ingen variabel för objektet som processeras (``s``)
- man behöver inga parenteser



#NEW

==Funktionskomposition==

Goda nyheter: pipes kan även skrivas i Haskell!

Men: de skrivs  omvänd ordning jämfört med Unix:
```
  translate = show . reverse . sort . freqs . group . sort . words
```
Ordningen är den samma som i funktionsapplikationen.

Den matematiska modellen är **funktionskomposition**:

Om //f : A -> B// och //g : B -> C//, så //g o f : A -> C//, där
//(g o f)(x) = g(f(x))//.

Precis samma regel finns i Haskells Prelude:
```
  (.) :: (b -> c) -> (a -> b) -> (a -> c)
  (g . f) x = g (f x)
```
Och funktionskompositionen får itereras så länge typerna matchar.

(I Unix är allting av typ ``String``.)



#NEW

==Utskrift av frekvenstabellen==

När programmet är snyggt indelat i funktioner som komponeras, kan
man lätt modifiera det.

Vi börjar med att ersätta ``show`` med en snyggare display:
```
  display :: [(Int,String)] -> String
  display xs = unlines [snd x ++ "  " ++ show (fst x) | x <- xs]
```
Vi har här använt två nya Prelude-funktioner, som tar ut elementen i ett par:
```
  fst :: (a,b) -> a
  snd :: (a,b) -> b
```
Och nu får vi resultat som ser snygga ut:
```
  unix$ cat ett.txt | runghc Freq
  och  8
  på  7
  i  6
  som  4
  ett  4
  ...
```


#NEW

==Hela koden==

```
module Main where
import List

main :: IO ()
main = interact translate

translate :: String -> String
translate = display . reverse . sort . freqs . group . sort . words

freqs :: [[a]] -> [(Int,a)]
freqs xs = [(length x, head x) | x <- xs]

display :: [(Int,String)] -> String
display xs = unlines [snd x ++ "  " ++ show (fst x) | x <- xs]
```
Statistik:
- 3 rader definition av ``translate`` och dess hjälpfunktioner
- 3 rader typsignaturer av dessa
- 4 rader "boilerplate" i början av modulen
- 9 funktioner från Haskells standardbibliotek (+ 1 i boilerplate)
- 3 egna funktioner (+ 1 i boilerplate)



#NEW

==Algoritmen i sammanfatting==

```
"en tusenlapp är alltid en tusenlapp"
                                                            words
"en","tusenlapp","är","alltid","en","tusenlapp"
                                                            sort
["alltid","en","en","tusenlapp","tusenlapp","är"]
                                                            group
[["alltid"],["en","en"],["tusenlapp","tusenlapp"],["är"]]
                                                            freqs
[(1,"alltid"),(2,"en"),(2,"tusenlapp"),(1,"är")]
                                                            sort
[(1,"alltid"),(1,"är"),(2,"en"),(2,"tusenlapp")]
                                                            reverse
[(2,"tusenlapp"),(2,"en"),(1,"är"),(1,"alltid")]
                                                            display
"tusenlapp 2\nen 2\när 1\nalltid 1"
```

#NEW

==Komplexiteten av algoritmen (överkurs)==

```
words    O(n)
sort     O(n log n)
group    O(n)
freqs    O(n)
sort     O(n log n)
reverse  O(n)
display  O(n)
```
Tiden det tar att skapa frekvenslistan är alltså proportionell till
//n * log n// där //n// är antalet ord i filen.

Detta är inte sämre än //den bästa möjliga algoritmen// (som dock slipper göra
så många pass).

Med bibliotek får vi ett program som är marginellt sämre än det bästa möjliga,
med en bråkdel av arbete!


#NEW

==Variationer av frekvenstabellen==

Vi ska slinka in funktioner i ``translate`` för att modifiera funktionaliteten:
- ta bort ord som endast förekommer en gång
- ignorera interpunktion och stora bokstäver
- returnera alfabetisk ordning
- ta bort HTML-taggar
- skriva ut **histogram** med relativa frekvenser


Och vi ska provköra programmet med olika filer.



#NEW

==Ta bort "hapax" ord==

Ta bort **hapax legomena**, dvs. ord som förekommer bara en gång.
```
  notHapax :: [(Int,String)] -> [(Int,String)]
  notHapax xs = [x | x <- xs, fst x > 1]
```
Uppgift: placera detta i rätt ställe i koden.

Variation: filtrera med ett annat tal än 1.


#NEW

==Normalisera texten==

I **normaliseringen** av texten ingår:
- ta bort siffror, interpunktion, HTML-tackar
- slopa distinktionen mellan stora och små bokstäver


Den första punkten kan göras med hjälp av
```
  normalize :: String -> String
  normalize s = [toLower x | x <- s, isAlpha x || isSpace x]

  -- remove HTML tags; koden finns i Translate.hs
  unHTML :: String -> String
```
Vi har använt följande funktioner från biblioteket 
[``Char`` http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Char.html]:
```
  isAlpha :: Char -> Bool  -- is an alphabetic letter
  isSpace :: Char -> Bool  -- is space, tab, or newline
  toLower :: Char -> Char  -- convert an uppercase character to lowercase
```


#NEW

==Histogram==

Ett **histogram** är en grafisk representation av numerisk data. T.ex.
```
  och       **************************************************
  det       **********************************
  han       *******************************
  att       ***************************
  en        *************************
  i         ************************
```
Där använder vi följande formeln för att beräkna antalet stjärnor:
```
  proportion :: [(Int,String)] -> Int -> Int
  proportion xs i = div (50 * i) (fst (head xs))
```
Vi skriver ut raderna med
```
  histogram :: [(Int,String)] -> String
  histogram xs = 
    unlines [snd x ++ "\t\t"++ replicate (proportion xs (fst x)) '*' | x <- xs]
```
Tabbar (``\t``) används för att pelarna ska börja från samma kolumn. 

Prelude-funktionen ``replicate`` producerar en lista av önskat antal element:
```
  replicate :: Int -> a -> [a]
```



#NEW

==Uppgifter==

Alla uppgifter görs med hjälp av egna modifieringar till
[``Freq.hs`` Freq.hs].

1. Kör ordstatistik på några filer med svensk och engelsk text, och andra
språk också om du orkar. Blir det samma top-10 i olika texter på samma språk?
Ingen redovisning.

2. Lägg till ``normalize`` och ``unHTML`` på rätt ställen i
ordstatistiken. **Redovisning**: kör statistiken på
[den här föreläsningen ./dator-04.html].

3. Modifiera ordtatistiken (med normalisering) så att den skriver ut
ett histogram (med stjärnor) av de 100 vanligaste orden.
**Redovisning**: kör programmet med [Röda rummet redRoom.txt].

4. Hur får man ut frekvensen av //ett visst ord//? Gör detta med
den vanliga, normaliserande statistiken genom att använda 
en Unix-pipe till ``grep``.
**Redovisning**: räkna ut antalet förekomster av ordet "ehuru" i
[Röda rummet redRoom.txt].

5. **Redovisning**: Räkna ut antalet //olika// 
ord i [``Röda rummet`` redRoom.txt] med hjälp
av den vanliga, normaliserande statistiken och en Unix-pipe.



#NEW

==Sammanfattning och referens==

===Prelude-funktioner===

```
  -- return the first element in a list
  head :: [a] -> a

  -- compose functions
  (.) :: (b -> c) -> (a -> b) -> (a -> c)
  (g . f) x = g (f x)

  -- return the first/second element of a pair
  fst :: (a,b) -> a
  snd :: (a,b) -> b

  -- build a list by repeating an element
  replicate :: Int -> a -> [a]
```


===Funktioner från List===

En kopia av [``List.hs`` List.hs]
```
  -- sort a list in ascending order
  sort :: Ord a => [a] -> [a]

  -- group adjacent equal elements in a list
  group :: Eq a => [a] -> [[a]]
```


===Funktioner från Char===

En kopia av [``Char.hs`` Char.hs]
```
  isAlpha :: Char -> Bool  -- is an alphabetic letter
  isSpace :: Char -> Bool  -- is space, tab, or newline
  toLower :: Char -> Char  -- convert an uppercase character to lowercase
```