2. Programmering med ord och strängar

Aarne Ranta
Datorintroduktion 2009, D och DV, Chalmers & GU

Vad är matematik

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...

Processning av ord och strängar

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.

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"

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" 

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']

Mera experiment med strängfunktioner

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]

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!

Ord-för-ord översättning

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.

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

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"

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.

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

Mera palindromer

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.)

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?

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
  
    <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

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

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:

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).

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.

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:

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

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.

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.

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