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 ()
```