Siffror? Tal? Funktioner? Geometriska figurer?
Allt som man kan göra exakta resonemang om:
Om man vill skriva datorprogram om något, krävs precis detta:
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...
Viktiga tillämpningar av datorer
Idag ska vi lära grunderna till strängprocessning i Haskell.
Nästa gång ska vi tillämpa kunskapen till större texter.
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"
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"
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']
Eliminera fyrbokstavsord
("four-letter words")
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]
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!
Idé: ersätt varje ord i en text med ett något annat ord
Det finns ett generellt mönster i programmen:
translate :: String -> String translate s = unwords [replace w | w <- words s]
där replace :: String -> String
.
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
"jeg"
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"
Ord-för-ord metoden är inte så jättebra: se t.ex. den svenska versionen av den här sidan.
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
Det finns en samling i t.ex. Wikipedia;
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.)
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?
Låt oss börja med hur man skriver ett par av tal med ett mellanslag emellan.
Prelude> 3 ++ " " ++ 5 <interactive>:1:0: No instance for (Num [Char]) arising from the literal `3' at <interactive>: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
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
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
:
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).
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.
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:
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
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.
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.
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
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.
type String = [Char] "kork" == ['k','o','r','k']
-- 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 ()