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
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.
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:
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!
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 för en full dokumentation; vi behöver bara en liten liten del idag.
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.
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"]
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
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 ...
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"]
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.
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!)
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!
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...
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 ("Lots of Irritating Superfluous Parentheses", eller "LISt Processing").
Haskell, i själva verket, är ungefär som Lisp med typer.
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:
s)
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.)
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
...
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:
translate och dess hjälpfunktioner
"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"
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!
Vi ska slinka in funktioner i translate för att modifiera funktionaliteten:
Och vi ska provköra programmet med olika filer.
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.
I normaliseringen av texten ingår:
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:
isAlpha :: Char -> Bool -- is an alphabetic letter
isSpace :: Char -> Bool -- is space, tab, or newline
toLower :: Char -> Char -- convert an uppercase character to lowercase
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]
Alla uppgifter görs med hjälp av egna modifieringar till
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.
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.
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.
5. Redovisning: Räkna ut antalet olika
ord i Röda rummet med hjälp
av den vanliga, normaliserande statistiken och en Unix-pipe.
-- 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]
En kopia av 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]]
En kopia av 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