2. Programmering med ord och strängar Aarne Ranta Datorintroduktion 2009, D och DV, Chalmers & GU %!target:html %!postproc(html): #NEW %!postproc(html): #HR
#NEW ==Vad är matematik== Siffror? Tal? Funktioner? Geometriska figurer? Allt som man kan göra **exakta resonemang** om: - definiera precist - ge slutgiltiga bevis - beräkna i mekaniska steg Om man vill skriva datorprogram om något, krävs precis detta: - matematisk modellering - formalisering (i ett programspråk) Det är genom matematisk modellering vi kan skriva program som handlar inte bara om tal, utan även ord, texter, bankkonton, mobila nätverk, anställda i ett företag... #NEW ==Processning av ord och strängar== Viktiga tillämpningar av datorer - ordprocessning (Microsoft Word) - typsättning - textstatistik - sökmotorer (Google) - maskinöversättning Idag ska vi lära grunderna till **strängprocessning** i Haskell. Nästa gång ska vi tillämpa kunskapen till större texter. #NEW ==Strängar och tecken== En sträng (``String``) i Haskell är en lista av **tecken** (``Char``): i Prelude definieras typen ``` type String = [Char] ``` Ett tecken anges i enkelfnuttar: ``` 'a' ``` En sträng kan således anges med de kända notationerna för listor: ``` ['k','o','r','k'] ``` Men det bekvämaste är specialnotationen med dubbelfnuttar: ``` "kork" ``` #NEW ==Funktioner med strängar== Mycket av kraften ligger i att alla listoperationer fungerar med strängar: ``` ['a' .. 'z'] [x | x <- "kork", x /= 'k'] ['a','a' ..] length "kork" take 2 "kork" ``` Vi ska sitta ner och beräkna dessa. Men vissa listoperationer är speciellt användbara med strängar: t.ex. **konkatenation**, ``++``: ``` "kork" ++ "skruv" == "korkskruv" ``` #NEW ==Experiment med strängfunktioner== Konkatenera två strängar med ett mellanslag emellan. ``` "hello" ++ " " ++ "world" ``` Ta bort alla mellanslag från en sträng ``s``. ``` unspace :: String -> String unspace s = [c | c <- s, c /= ' '] ``` Räkna hur många gånger bokstaven //k// förekommer i en sträng ``s``. ``` number_k :: String -> Int number_k s = length [c | c <- s, c == 'k'] ``` #NEW ==Mera experiment med strängfunktioner== Eliminera fyrbokstavsord (["four-letter words" http://en.wikipedia.org/wiki/Four-letter_word]) från en ordlista ``ws``. ``` unfour :: [String] -> [String] unfour ws = [w | w <- ws, length w /= 4] ``` Ta ut initialerna av en lista till en sträng. ``` initials :: [String] -> [String] initials ws = [take 1 w | w <- ws] ``` #NEW ==Strängar och ord== En sträng kan delas upp i ord vid avgränsande mellanslag och nyradstecken. Detta görs med Prelude-funktionen ``words``: ``` words "till och med" == ["till","och","med"] ``` Låt oss ta initialerna från varje ord i en sträng: ``` initials s = [take 1 w | w <- words s] ``` När vi har hanterat färdigt varje ord, kan vi skriva tillbaka den nya strängen med ``unwords``: ``` unwords (initials (words "till och med")) == "t o m" ``` Obs. ``unwords`` skapar inget mellanslag efter det sista ordet. Förresten: är det alltid så att ``` unwords (words s) == s ``` Ge bevis eller motexempel! #NEW ==Ord-för-ord översättning== Idé: ersätt varje ord i en text med ett något annat ord - svenska ord med norska ord (maskinöversättning) - fula ord med anständiga ord (censur) - Apple-ord med Microsoft-ord (texttvättning) Det finns ett generellt mönster i programmen: ``` translate :: String -> String translate s = unwords [replace w | w <- words s] ``` där ``replace :: String -> String``. #NEW ==Mönstermatchning== Vi kan definiera en ersättningsfunktion med **fallanalys**, med hjälp av **mönstermatchning**: ``` replace :: String -> String replace "inte" = "ikke" replace "jag" = "jeg" replace w = w ``` Funktionen beräknas genom matchning av mönstren i samma ordning. Det första mönster som matchar tillämpas. Mönster kan vara - konstanta värden, som endast matchar det samma värdet: ``"jeg"`` - variabler, som matchar vad som helst: ``w`` Nu fångas alltså alla ord som inte behöver ändras med variabeln ``w``, och samma ord returneras som värde. ``` translate "jag kommer inte med" == "jeg kommer ikke med" ``` #NEW ==Om maskinöversättning== Ord-för-ord metoden är inte så jättebra: se t.ex. den svenska versionen av [den här sidan http://www.cs.chalmers.se/~rjmh/]. #NEW ==Reversering== Funktionen som returnerar en lista i omvänd ordning: ``` reverse :: [a] -> [a] ``` Exempel: ``` reverse [1,2,3] == [3,2,1] reverse "en korkskruv" == "vurkskrok ne" ``` Exempel: testa om en sträng är en palindrom, dvs. samma baklänges (t.ex. "rotor"). ``` palindrome :: String -> Bool palindrome s = reverse s == s ``` #NEW ==Mera palindromer== Det finns en samling i t.ex. [Wikipedia http://sv.wikipedia.org/wiki/Palindrom]; //I Reval sitta ni alla i natt i slaveri// Observera att mellanslag ignoreras i palindromtestet: ``` palindrome :: String -> Bool palindrome s = unspace (reverse s) == unspace s ``` (Det här kunde göras effektivare förstås.) #NEW ==Formateringsproblemet== På första föreläsningen skapade vi tabeller, t.ex. kvadrattabellen ``` [(x,x*x) | x <- [0 .. 10]] ``` Tyvärr blev utseendet lite tråkigt: ``` [(0,0),(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100)] ``` Vi skulle vilja skriva ut varje par som en rad, där talen är separerade med mellanslag. Hur gör vi? #NEW ==Från tal till strängar== Låt oss börja med hur man skriver //ett// par av tal med ett mellanslag emellan. ``` Prelude> 3 ++ " " ++ 5 :1:0: No instance for (Num [Char]) arising from the literal `3' at :1:0 ... ``` Någon sorts **typfel**. Poängen är att ``" "`` bara kan konkateneras med en sträng, inte med ett heltal. Vi måste **konvertera** heltal till strängar. Konvertering till strängar görs (för de flesta typer) med funktionen ``show``. Alltså: ``` show 12 == "12" -- Int show 3.14 == "3.14" -- Float show [1,2,3] == "[1,2,3]" -- [Int] show "hello" == "\"hello\"" -- String ``` #NEW ==Formatering av tabeller== Nu vet vi att vi ska skriva så här: ``` Prelude> show 3 ++ " " ++ show 5 "3 5" ``` Återstår att hantera listan av alla rader: ``` [show x ++ " " ++ show (x*x) | x <- [0 .. 10]] ``` Vi vill skriva ut listan som en sträng, med nyradstecken mellan varje element. Analogt med ``words`` och ``unwords`` har Prelude - ``lines``, som delar upp en sträng till en lista av strängar, vid varje nyradstecken (``\n``) - ``unlines``, som tar en lista av strängar och returnerar en sträng där varje element ur listan slutar med ett nyradstecken #NEW ==Skriva utt en sträng== Det här ser inte alls bra ut: ``` Prelude> unlines [show x ++ " " ++ show (x*x) | x <- [0 .. 10]] "0 0\n1 1\n2 4\n3 9\n4 16\n5 25\n6 36\n7 49\n8 64\n9 81\n10 100\n" ``` Problemet: GHCi visar **stränguttrycket**, i ett format som skulle kunna användas i en Haskell-fil. Det vi skulle vilja i stället är att strängen **skrivs ut**. Utskriften är en effekt utanför den rena funktionella matematiska världen. Men i Haskell kan man programmera utskrift av en sträng med Prelude-funktionen ``putStr``: #NEW ==Utskrift av kvadrattabellen== ``` Prelude> putStr (unlines [show x ++ " " ++ show (x*x) | x <- [0 .. 10]]) 0 0 1 1 2 4 3 9 4 16 5 25 6 36 7 49 8 64 9 81 10 100 ``` Obs: ``print x`` är samma som ``putStr (show x ++ "\n")``. Nästa gång: mer om utskrift och andra **IO-funktioner** (Input-Output). #NEW ==Vad får man skriva och var?== I en //Haskell-fil//: **definitioner**, som består av ``` FUNKTIONSNAMN VARIABLER = UTTRYCK ``` Detta betyder att funktionsnamnet får användas i samma fil eller när filen laddas i GHCi eller importeras i en annan fil. Till //GHCi-prompten//: uttryck, dvs. högerled av definitioner. ``` Module> UTTRYCK ``` Detta betyder att GHCi ska beräkna värdet av uttrycket och visa det. Man kan //inte// skriva ett ensamt uttryck i en fil. //Inte heller// kan man skriva en definition till prompten. #NEW ==Definitioner i GHCi== Det //är// faktiskt möjligt att skriva definitioner direkt i GHCi. Man måste använda nyckelordet ``let``: ``` Prelude> let fac n = product [1 .. n] Prelude> fac 6 720 ``` Alltså: till prompten skriver man **kommandon**: - ett bart uttryck är kommandot att beräkna dess värde - ett ``let`` är kommandot att lägga till en definition i miljön där senare kommandon ges Obs: varje uttryck som beräknas definierar i själva verket om funktionen ``it``: de följande raderna har samma effekt: ``` Prelude> 2+2 Prelude> let it = 2+2 ``` #NEW ==Uppgifter== ===Redovisning=== Uppgifterna ska redovisas i en fil ``Ex2.hs``, som erhålls genom att ersätta alla ``undefined`` i följande: ``` module Main where main = do print ex2 print ex3 putStr ex4 ex2 = lengths "i en bra film finns alltid droider" lengths :: String -> [Int] lengths s = undefined ex3 = abbreviation "Very Superior Old Pale" abbreviation :: String -> String abbreviation s = undefined ex4 :: String ex4 = undefined ``` **Obs**: om du kopierar koden, se till att den första raden (med ordet ``module``) och varje rad som börjar från samma position flyttas till början av raden. #NEW ==Uppgifterna== 1. Kör minst fem exempel ur denna föreläsning, med minst en egen variationer av varje. 2. Skriv en funktion ``` lengths :: [String] -> Int ``` som läser en sträng och returnerar listan av längderna på varje ord. Uttrycket ``ex3`` definieras som tillämpning av denna funktion till "i en bra film finns alltid droider". 3. Skriv en funktion ``` abbreviation :: String -> String ``` som tal initialerna av alla ord i en sträng och skriver dem tillbaka i en sträng med en punkt och ett mellanslag: ``` abbreviation "till och med" == "t. o. m." ``` Uttrycket ``ex3`` definieras som tillämpning av denna funktion till "Very Superior Old Pale". 4. Skriv om Fahrenheit-tabellen från övning 1.2 på ett sådant sätt att varje talpar kommer på en egen rad, med två mellanslag mellan talen. T.ex. ``` 120.0 48.888888888888886 ``` Svaret ges i uttyck ``ex4``. 5. Skriv en ord-till-ord översättare med egen ``replace``-funktion. Behöver inte redovisas. #NEW ==Sammanfattning och referens== ===Definitioner i GHCi=== Man kan skriva en definition till prompten: ``` Prelude> let fac n = producs [1 .. n] ``` Evaluering av ett uttryck t.ex. ``2+2`` tolkan som en definition av ``it``: ``` Prelude> let it = 2+2 ``` ===Mönstermatchning=== En funktion kan definieras med en sekvens av definitioner, där varje definition hanterar ett fall med ett mönster. T.ex. ``` replace :: Char -> Char replace 'v' = 'w' replace c = c ``` En variabel som möster hanterar allt som inte hanterats av tidigare mönster. ===Tecken och strängar=== ``` type String = [Char] "kork" == ['k','o','r','k'] ``` ===Preludfunktioner=== ``` -- konkatenera listor (++) :: [a] -> [a] -> [a] -- ta fram orden/raderna i en sträng words :: String -> [String] lines :: String -> [String] -- använd strängarna som ord/rader i en sträng unwords :: [String] -> String unlines :: [String] -> String -- returnera motsatsen not :: Bool -> Bool -- listan baklänges reverse :: [a] -> [a] -- konvertera värde till sträng show :: (Show a) => String -- skriv ut en sträng putStr :: String -> IO () ```