Om tupler och strängar i hugs

Detta dokument är avsett att komplettera kapitel 2 i läroboken genom att ytterligare diskutera tupler och strängar och ge fler exempel.

Tupler

Börja med att läsa igenom avsnitt 2.10 i läroboken.

Punkter

Vi betraktar nu exemplet punkter i planet. Vi ska definiera en samling funktioner som kan vara användbara för att lösa geometriska problem.

En punkt beskrivs lämpligen med sina koordinater i det vanliga rätvinkliga koordinatsystemet. Det innebär att en punkt beskrivs av ett par av reella tal, vilket motiverar definitionen

type Point = (Float,Float)

Exempel på element i typen Point är (1.5,3.14) och (0.0,-2.5). Vi definierar några funktioner som tar punkter som argument:

xCoord :: Point -> Float
xCoord (x,y) = x

yCoord :: Point -> Float
yCoord (x,y) = y

distance :: Point -> Point -> Float
distance (x1,y1) (x2,y2) = sqrt((x1-x2)^2 + (y1-y2)^2)

I den sista funktionen har vi använt avståndsformeln för punkter i planet. Vi gör två observationer:

Funktioner som tar en eller flera punkter som argument kan definieras genom att man som argument skriver ett par vars två komponenter är variabler.
Det kan vara förvirrande att samma beteckningssätt med parenteser och kommatecken används både för en typ som (Float,Float) och ett element i denna typ som (1.5,3.14). (Vi har alltså (1.5,3.14) :: (Float,Float)). Detta måste man försöka vänja sig vid. I ett Haskellprogram är det alltid klart av sammanhanget om ett uttryck står för en typ eller ett objekt i en typ.

Definiera en funktion distanceToOrigin :: Point -> Float som givet en punkt som argument beräknar dess avstånd till origo.

En funktion kan också ge ett resultat av typen Point. Som exempel definierar vi en funktion som tar (koordinaterna för) en punkt som indata och beräknar dess spegling i x-axeln.

xMirror :: Point -> Point
xMirror (x,y) = (x,-y)

Meningen här är inte att fastna i geometriska svårigheter; om Du inte är säker på att man får speglingen i x-axeln genom att byta tecken på y-koordinaten så acceptera det och gå vidare.

Definiera en funktion

midPoint :: Point -> Point -> Point

sådan att midPoint p1 p2 är den punkt som ligger mitt emellan p1 och p2.

Relationsoperatorerna (==, /=, <, <=, > och >=) blir automatiskt definierade på tupler i hugs. Två punkter anses vara lika om och endast om både x-koordinaterna och y-koordinaterna är lika.

Undersök hur relationen < är definierad för typen Point genom att experimentera. Här är början på experimentet:

Main> (0,1) < (1,2)
True
Main>

Välj lämpliga punkter att testa med tills Du tror att Du förstår hur det fungerar. Verkar det bra?

Punkter kan ingå i sammansatta datastrukturer. Som exempel betraktar vi en lista av punkter [p₁,p₂,...p_n] som vi kan tänka på som en beskrivning av ett sätt att ta sig från punkten p₁ till punkten p_n via de övriga punkterna. Hur lång är denna väg? En funktion som besvarar detta för en given lista punkter bör ha typ

totalDistance :: [Point] -> Float

Vad bör resultatet av denna funktion bli om indatalistan innehåller a) ingen punkt b) en punkt c) två punkter?

Funktionen kan definieras med mönstermatchning över listan och användning av funktionen distance ovan.

Definiera funktionen.

Strängar

Strängar och tecken beskrivs i avsnitt 2.7. Beskrivningen där stämmer dock inte helt med den nuvarande versionen av hugs. Dessutom tycker jag att beskrivningen av specialtecken är svårbegriplig.

I Haskell finns en primitiv typ Char innehållande tecken som bokstäver, siffror och diverse övriga tecken som parenteser, frågetecken osv. Typen Char kommer till användning då man vill producera text som resultat av en beräkning. Däremot är det sällan man vill ha ett enda tecken som resultat, så mycket mer använd än Char är typen String, som består av listor av tecken.

Ett första problem med tecken är hur man ska skriva dem så att man inte blandar samman dem med variabelnamn och talkonstanter. Lösningen är att teckenkonstanter skrivs inom enkla citationstecken: 'A', '3' och '?' är tre exempel på objekt i typen Char. Obs: Man måste skilja på dessa citationstecken och de bakåtlutande som används till exempel i operatornamnet `div`.

Strängar är verkligen listor av tecken: i preluden definieras

type String = [Char]

Så ett exempel på en sträng är ['H','e','j']. Men så vill vi förstås inte läsa strängar. Därför finns en specialregel för strängar: de skrivs ut genom att man skriver de ingående tecknen i direkt följd utan sina citationstecken; i stället omsluts hela strängen av dubbla citationstecken.

Exempel:

Main> ['H','e','j']
"Hej"
Main> ['V','a','d',' ','h','e','t','e','r',' ','d','u','?']
"Vad heter du?"
Main> [] :: String
""
Main>

På detta vis blir strängar läsliga. Men man ska alltid komma ihåg att strängar är listor, så funktioner som tar listor som argument kan användas på strängar. Man kan också skriva strängar med den bekvämare notationen:

Main> length "I denna rad finns ingen bokstav med prick eller ring"
52

Argumentet till length är här en lista med 52 element (räkna!). Det är också väsentligt att det inte finns några å, ä eller ö; tyvärr klarar inte hugs att hantera dessa (dvs inte interaktivt; man kan skriva ut dessa tecken!).

Att strängar är listor betyder att operatorn ++ som slår samman (konkatenerar) två listor kan användas på strängar:

Main> "abc "++"def"
"abc def"
Main>

Gör övningarna 2.40 och 2.41 i boken, dvs definiera funktioner

spaces :: Int -> String
rJustify :: Int -> String -> String

sådana att spaces n är en sträng bestående av n blanktecken och rJustify n str är den sträng av längd n som fås genom att fylla på med blanktecken före str:

Main> spaces 8
"        "
Main> spaces 0
""
Main> rJustify 8 "Hej"
"     Hej"
Main> rJustify 3 "Too long"
"Too long"
Main>

Som antyds av det sista exemplet kan rJustify n str ha längd större än n -- om nämligen redan str innehåller fler än n tecken.

I avsnitt 2.7 beskrivs också ett antal så kallade "special characters". Jag tror inte man kan förstå detta utan att berätta något om hårdvarans historia. Gamla mekaniska utskriftsenheter från tiden före bildskärmsterminaler styrdes normalt genom att man till dem sände en lång följd av heltal i intervallet 0 till 127. Varje heltal mellan 32 och 126 svarade mot ett bestämt tecken; i den vanligaste koden ASCII betydde exempelvis 65 bokstaven 'A' och 43 plustecknet '+'. Talen 0 till och med 31 var så kallade specialtecken och var kommandon till maskinen; exempelvis betydde 10 "byt till ny rad" och 7 "plinga med den inbyggda klockan". Man kan fortfarande spåra rester av allt detta i typerna String och Char.

Det finns fortfarande funktioner som konverterar mellan Char och små heltal:
```
fromEnum :: Char -> Int
toEnum :: Int -> Char
```
Man kan testa dessa litet:
```
Main> fromEnum 'A'
65
Main> toEnum 43 :: Char
'+'
Main> 
```
Koden är fortfarande ASCII. Vi måste lägga till typinformationen :: Char då vi använder toEnum eftersom denna funktion kan koda också andra uppräkningstyper (mer om detta senare).
```
Main> toEnum 10 :: Char
'\n'
Main> toEnum 7 :: Char
'\a'
Main> 
```
Heltalen 0 till och med 31 är fortfarande koder för att styra utskrifter; hur ska man då skriva dem som tecken? Lösningen i Haskell är att skriva vissa tecken ("specialtecken") inom sina citationstecken med hjälp av flera tecken varav de första är \. Exempel på sådana tecken är '\n' (radbytestecken, på engelska newline) och '\t' tabulatortecken. De enda specialtecken vi kommer att använda är de som räknas upp på sidan 43 i boken.
Vad blir length "rad1\nrad2\nrad3\n"?
Om tecknet '\n' betyder "byt rad" så kan vi alltså hoppas på att strängen "rad1\nrad2\nrad3\n" ger en utskrift på tre rader.
```
Main> "rad1\nrad2\nrad3\n"
"rad1\nrad2\nrad3\n"
?
```
Tyvärr! Strängar presenteras av hugs med koden för specialtecken kvar utan att den effekt vi önskar uppträder. För att få se effekterna mste man använda det primitiva kommandot putStr som får xtermfönstret att bete sig som en gammal terminal:
```
Main> putStr "rad1\nrad2\nrad3\n"
rad1
rad2
rad3

Main> 
```
Hur kan man få sin arbetsstation att ge ifrån sig ett pip?
Specialtecknen och ASCII-koden är gemensamma för alla tillämpningar. Exempelvis kan vi skriva tecknet med ASCII-kod 7 direkt till Unix' kommandotolk genom att skriva Ctrl-H (dvs håll nere Control-tangenten och tryck H). Effekten blir att arbetsstationen piper. Vi kan också se att radbytestecknen fungerar inte bara i hugs genom att använda det primitiva hugs-kommandot writeFile:
```
Main> writeFile "testfil" "rad1\nrad2\n"

?
```
Effekten av detta är att det andra argumentet skrivs på filen testfil. Titta på denna fil med more eller i emacs. Vi ska i fortsättningen av denna läsperiod inte använda oss av filer från hugs, så kommandot writeFile kan man glömma tills vidare.

Vi ska nu se något på hur man skriver funktioner som kan ge "snygga" utskrifter över flera rader som resultat. Som exempel definierar vi en funktion som för givet naturligt tal n kan producera en snygg tabell över kvadrater och kuber på talen upp till n:

Main> putStr(powerTable 10)
         n       n^2       n^3
         1         1         1
         2         4         8
         3         9        27
         4        16        64
         5        25       125
         6        36       216
         7        49       343
         8        64       512
         9        81       729
        10       100      1000

Main>

För att åstadkomma detta så måste powerTable 10 vara en sträng som beskriver hela den önskade utskriften inklusive radbytestecknen. Vi noterar också att vi kommer att behöva skriva ut heltalsvärden på många ställen i denna sträng. För detta måste vi kunna konvertera ett heltal till en sträng. Detta åstadkommes av den primitiva funktionen show som fungerar på alla primitiva typer.

Main> show 12345
"12345"
Main> show pi
"3.14159"
Main> show (3>5)
"False"
Main>

Man måste lära sig att skilja på strängen "False" och det Booleska värdet False, på strängen "12345" och heltalet 12345 osv. Speciellt måste man förstå att hugs inte kan till exempel addera "12345" och "314". På strängar kan man göra operationer som har med text att göra, som att slå samman två strängar till en längre sträng, fylla ut med blanktecken i ett visst utrymme osv.

Main> "12345"++"314"
"12345314"
Main> rJustify 10 "12345"
"     12345"

Åter till potenstabellen. Vi bestämmer oss för att använda 10 teckens utrymme för varje kolumn och definierar därför en funktion

rJust :: String -> String

som fyller ut sitt argument med blanktecken så att den får längd 10.

rJust "12345"
"     12345"

Definiera denna funktion.

Vi kan nu definiera powerTable genom att observera att tabellen med n rader är precis tabellen med n-1 rader följt av en sista rad. Definitionen blir därför med primitiv rekursion över n:

powerTable :: Int -> String
powerTable 0 = rJust "n"++rJust "n^2"++rJust "n^3"++"\n"
powerTable n = powerTable (n-1) ++ line n
      where
      line n = rJust(show n)++rJust(show (n^2))++rJust(show (n^3))++"\n"

I basfallet producerar vi endast rubrikraden och i det rekursiva fallet utnyttjar vi precis observationen ovan. Pröva funktionen för några olika n.

Kom ihåg vid stränghantering att inte använda putStr annat än som ett kommando till hugs för att skriva ut en formatterad sträng. Däremot ska rekursiva funktioner som powerTable bygga upp en sträng utan att använda putStr.

Efter detta är det lämpligt att vid tillfälle läsa exemplen i avsnitt 2.9 och 2.13. Observera dock att för att få tabellen på sidan 49 måste man till hugs skriva

Main> putStr(printTable 2)

och för att få utskriften mitt på sidan 65 måste man skriva
Main> putStr(quadAnalyze 1 5 6)