En första kontakt med Haskell

Detta dokument utgör det första studiematerialet i kursen Programmeringsteknik, del A. Avsikten är att Du ska läsa och arbeta med dokumentet vid terminalen. Handledare kommer att finnas tillgängliga hela tiden, men avsikten är att ni ska arbeta självständigt två och två. Fråga dock någon handledare så fort ni kör fast; det är ingen idé att sitta och planlöst försöka gissa om man inte alls förstår. Speciellt bör ni tillkalla en handledare om ni tycker att ni gör som i detta dokument men får felmeddelanden ni inte förstår. Det är omöjligt att här diskutera alla de fel man kan göra; se till att få hjälp så ni kommer vidare!

Om en av er är datorvan och den andre nybörjare, så låt den ovane sköta skrivandet och tryckandet. Man lär sig inte av att sitta bredvid och titta på!

Däremot är det troligt att ni vid flera tillfällen kommer att kunna göra saker genom att kopiera de instruktioner som ges utan att ni förstår ``hur det fungerar''. Detta är avsiktligt; meningen är att ni ska bekanta er med det program vi ska använda oss av under kursen. Närmare förklaringar ges under de kommande veckorna.

Det kan vara tröttande att läsa detta dokument om typsnittet är för litet (dvs bokstäverna för små). Om det är så, öppna Edit-menyn och välj Preferences. I det fönster som öppnas välj Fonts under kategori Appearence. Välj slutligen lämplig storlek under Size på två ställen (både Variable Width Font för löpande text och Fixed Width Font för kod). Själv tycker jag storleken 18 punkter är lagom.

Meningen är att ni ska hinna arbeta igenom materialet under en förmiddag. Den viktigaste delen av arbetet är att besvara de frågor som förekommer i stor mängd med följande utseende:

Frågorna består oftast av att man ska göra något vid datorn efter att först ha tänkt efter litet. Alla frågor har ett förslag till svar som man får fram genom att klicka på frågetecknet till vänster. Detta bör ni göra efter det att ni själva försökt besvara frågan eller göra det som föreslås. Men går det inte fortare att låta bli att tänka och kolla in svaret direkt?

Datorn som miniräknare

Ett sätt att använda en dator är som miniräknare, dvs för att interaktivt göra beräkningar. Vi ska i denna kurs använda ett sådant program med namnet hugs. Ni startar detta program genom att i ett xterm-fönster skriva dess namn:

fraggel33> hugs

Här och i fortsättningen använder vi konventionen att understruken text är användarens inmatning medan text utan understrykning har skrivits av systemet. Ni bör också efterhand som ni läser texten verkligen göra det som beskrivs. Om ni inte redan startat hugs, gör det nu! Som svar får ni se hugs' välkomsthälsning:

__   __ __  __  ____   ___      _________________________________________
||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__||  __||     Copyright (c) 1994-2001
||---||         ___||           World Wide Web: http://haskell.org/hugs
||   ||                         Report bugs to: hugs-bugs@haskell.org
||   || Version: February 2001  _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Reading file "/usr/pd/share/hugs2001/hugs/lib/Prelude.hs":
                   
Hugs session for:
/usr/pd/share/hugs2001/hugs/lib/Prelude.hs
Type :? for help
Prelude>

Vi bryr oss för tillfället inte om det som står här utan koncentrerar oss på sista raden där markören (dvs den plats där text vi skriver hamnar) finns. Först på raden finner vi texten Prelude> , vilket indikerar att hugs är beredd att ta emot ett kommando. Vad ordet Prelude betyder får vi vänta med att förklara. Det enklaste kommandot är att bara skriva ett uttryck, varvid hugs beräknar och skriver ut uttryckets värde:

Prelude> 4+5*6
34
Prelude>

Därefter är, som antyds av markören, systemet berett på ett nytt kommando. Vi kan upprepa denna interaktion hur många gånger som helst, som i nedanstående dialog.

Prelude> 4*(8-5)+3
15
Prelude> 3.5/(3+4)*4.5
2.25
Prelude> sin 1.57
1.0
Prelude>

Det första av dessa tre uttryck består av en multiplikation, en addition och en subtraktion. I vilken ordning utförs de och vilka tal är det som multipliceras, adderas respektive subtraheras?

Vad blir resultatet om man inte har parenteser i första uttrycket, dvs 4*8-5+3?

Vilka operationer utförs och i vilken ordning då det andra uttrycket beräknas?

Blir sin 1.57 precis 1?

Som man gissar av det sista uttrycket känner hugs till också de trigonometriska funktionerna, liksom exponentialfunktionen (exp), kvadratrotsfunktionen (sqrt) och många fler.

Är kvadratroten ur 1234567 större än 1111?

Det är inte alltid vi får ett värde som resultat när vi ger ett uttryck till hugs för beräkning. Det kan nämligen vara något fel i uttrycket som gör det omöjligt att beräkna något värde:

Prelude> 3+5*

ERROR: Syntax error in expression (unexpected end of input)
Prelude> 4/0

Program error: {primDivDouble 4.0 0.0}

Prelude>

I det första fallet är uttrycket syntaktiskt fel eftersom det inte finns någon högeroperand till multiplikationen. I det andra fallet försöker vi dividera med noll vilket ger fel vid beräkningen. Att känna igen olika sorters fel och förstå vad som orsakar dem tillhör det som tar mest tid i början. Vi kommer att återkomma till detta men kan inte säga mer nu.

Mer om kommandon

Nu är det dags att se något annat kommando till hugs. Ett sådant är det som avslutar programmet:

Prelude> :q
[Leaving hugs]
fraggel33>

Alla kommandon till hugs utom att ge ett uttryck för beräkning inleds med kolon. Starta hugs igen och läs igenom hälsningsmeddelandet litet noggrannare.

Vilka kommandon finns i hugs?

Två enkla exempel

Vi betraktar två små problem som kan lösas med hugs.

Säljkursen för ett engelskt pund var den 18 augusti 1997 12.7775 kronor. Hur många pund fick man den dagen för 1000 kronor?

Som bekant (?) använder man fortfarande i anglosaxiska länder Fahrenheitskalan för temperatur. 0° Celsius (C) motsvarar 32° Fahrenheit (F) och en ökning med 5° C motsvarar en ökning med 9° F. Hur många grader Fahrenheit är 28° C?

En programmerbar miniräknare!

Vi har sett hur man kan använda hugs för enkla beräkningar. Men det är bara början! Vi kan definiera funktioner som bygger ut systemets förmåga. Som ett första exempel betraktar vi växlingsproblemet ovan. Om vi många gånger vill beräkna hur många engelska pund som ett givet belopp i kronor motsvarar så kan vi definiera en funktion som uttrycker detta. Att definiera en funktion sker i flera steg:

Bestäm ett namn på funktionen. Detta bör väljas så att det antyder vad funktionen gör. Här bestämmer vi oss för namnet pund.
Bestäm vilket argument (indata) funktionen har och vilket resultat (utdata) den ska ge. I detta fall är det enkelt:
Indata: Ett tal, representerande ett belopp i kronor.
Utdata: Ett tal, representerande motsvarande belopp i pund.
Bestäm ett namn på funktionens parameter, som står för ett godtyckligt värde på argumentet. Eftersom argumentet är ett belopp i kronor, bestämmer vi oss för att använda namnet kr som parameter.
Beskriv beräkning av resultatet med hjälp av parametern. I detta fall så blir resultatet kr/12.7775 pund.
Skriv funktionsdefinitionen i Haskell. I detta fall blir det
```
pund(kr) = kr/12.7775
```

Det återstår att ge denna definition till hugs innan vi kan använda den. Men vi kan inte skriva in en funktionsdefinition direkt till hugs. I stället måste vi arbeta i två steg:

Använd emacs för att skriva funktionsdefinitionen på en fil. Gör det, dvs starta emacs, skriv in raden
```
pund(kr) = kr/12.7775
```
och spara detta i en fil med namnet ex1.hs. Se till att filen är i samma katalog som den där Du startade hugs. Gå eventuellt ur hugs, kontrollera (med Unixkommandot ls) att det finns en fil med namnet ex1.hs och kontrollera (med Unixkommandot more) att denna fil har rätt innehåll.
Ge hugs kommandot att ladda in denna fil.
```
Prelude> :l ex1.hs
Reading file "ex1.hs":
                   
Hugs session for:
/usr/pd/lib/Hugs98May/hugs/lib/Prelude.hs
ex1.hs
Main> 
```
Obs: Det fullständiga namnet på kommandot är :load så tecknet efter kolon är bokstaven l, inte siffran 1.

Vi kan nu använda definitionen:

Main> pund(1000)
78.2626
Main> pund(12345)
966.151
Main> pund(127775)
10000.0
Main>

Definiera en funktion som konverterar en temperatur i ° C till ° F. Lägg till Din definition till filen ex1.hs (på ny rad!), ladda in filen och testa Din funktion.

Definiera en funktion som givet ett tal representerande radien i en cirkel beräknar cirkelns area. Testa Din funktion med hugs. Vad händer om man ger ett negativt tal som argument?

Vi kan nu illustrera en ny typ av fel. Vad händer om man till hugs skriver pound 10 (observera felstavningen!)? Om man skriver pund kr?

Jämförelser och villkorliga ekvationer.

Hittills har de funktioner vi definierat alla definierats av en ekvation på formen
namn(par) = ett uttryck som innehåller par, tal och aritmetiska operationer

Det är inte alltid det är så lätt. Vi betraktar följande exempel.

En affär säljer potatis för 3.50 kr/kilo. För att stimulera till stora inköp så erbjuds det rabatterade priset 3 kr/kilo för den kvantitet som överstiger 10 kg vid ett och samma inköpstillfälle. Vi vill definiera en funktion som givet en vikt beräknar priset.

Låt oss kalla funktionen price och parametern v. Om v är högst 10 är det lätt: då blir priset 3.50*v. Om v är större än 10 blir det litet värre, men man kan resonera på följande sätt: De första 10 kilona kostar 35 kr och de sista v-10 kostar 3 kr/kilo, så totalt blir det 35+3*(v-10), vilket kan förenklas till 5+3*v. Vi har alltså
price(v) = 3.5*v om v<=10
price(v) = 5+3*v om v>10
Hur skriver man detta i Haskell? Först konstaterar vi att man med hugs kan jämföra tal:

Prelude> 3 < 6
True
Prelude> 3.5 <= 3
False
Prelude> circleArea(10) > 3*100
True

Resultaten av sådana jämförelser som dessa blir antingen True eller False. Observera att "mindre än eller lika med" måste skrivas <= eftersom den symbol man normalt använder i matematiken inte finns på tangentbordet. Den viktigaste användningen av jämförelser är i funktionsdefinitioner som i följande definition av price:

price(v)
   |v <= 10 = 3.5*v
   |v > 10  = 5+3*v

När man laddat in denna definition och använder funktionen på ett visst argument så gör hugs i tur och ordning (uppifrån och ner) jämförelserna till vänster om likhetstecknet tills den finner en jämförelse som blir True. Därefter används motsvarande högerled för att beräkna resultatet. Ladda in och testa funktionen price på några olika argument.

För att illustrera hur den här typen av funktionsdefinitioner fungerar, ändra sista raden i definitionen av price till

   |v > 11  = 5+3*v

Vad blir nu värdet av funktionen för argumenten 9.5, 10.5 respektive 11.5?

Ändra tillbaka och ändra i stället första raden i definitionen av price så att man får

price(v)
   |v <= 11 = 3.5*v
   |v > 10  = 5+3*v

Vad blir nu värdet av funktionen för argumenten 9.5, 10.5 respektive 11.5?

Det är vanligt att man vid definitionen av funktioner vill att sista raden ska ta hand om alla de fall som inte täckts av någon av de tidigare jämförelserna. Det kan man åstadkomma på följande sätt, illustrerat för funktionen price:

price(v)
   |v <= 10 = 3.5*v
   |True    = 5+3*v

I det sista fallet gör vi ingen jämförelse, utan skriver direkt värdet True.

Försäljningen av potatis har blivit en sådan framgång att man nu kan erbjuda priset 2.50 kr/kilo för kvantiteter över 20 kilo (och med samma priser som tidigare för övrigt). Modifiera funktionen price så den beräknar korrekt pris.

Vi ska också igen påpeka ett skrivsätt som vi i fortsättningen kommer att använda:

Main> price 7.5
26.25
Main> price 11
38.5
Main> price(4+8)
41.0
Main>

Då en funktion används på ett enkelt argument så behöver man inte sätta ut parenteser om argumentet. Däremot behövs ett mellanslag före argumentet. Om däremot argumentet är sammansatt (som 4+8) så måste det omges av parenteser.

Pröva att inte sätta dit parenteser i det sista exemplet och se vad som händer. Kan Du förklara resultatet?

Funktioner med flera argument.

Funktioner kan ha mer än ett argument. Låt oss som ett första exempel definiera en funktion som beräknar medelvärdet av två tal. Vi gör som tidigare:

Funktionens namn: Vi väljer namnet mv.
Indata: Två tal.
Utdata: Medelvärdet av de två argumenten.
Namn på parametrarna: Vi väljer x och y.
Beräkning av resultat: Medelvärdet ges av (x+y)/2
Fullständig definition:
```
mv x y = (x+y)/2
      
```

Det man observerar är att om man har flera argument så räknas de upp i tur och ordning (åtskilda av mellanslag). Likadant gör man då man vill använda funktionen sedan den laddats in:

Main> mv 5 8
6.5
Main>

Definiera en funktion som tar tre tal som argument och beräknar deras medelvärde. Skriv funktionen i emacs, ladda in och testa den i hugs.

En intressantare funktion skulle kunna ta ett variabelt antal tal som argument och ge deras medelvärde som resultat. Hur man gör det måste vänta någon vecka.

Definiera en funktion som tar två tal som argument och som resultat ger det största av dem. Skriv funktionen i emacs, ladda in och testa den i hugs.

Preluden

Många funktioner, som till exempel den i föregående övning som beräknar det största av sina två argument, kommer ofta till användning och det verkar onödigt att varje programmerare ska definiera dem själv. Därför har ett stort antal sådana användbara funktioner samlats i en fil kallad preluden, vilken laddas in automatiskt varje gång man startar hugs. Detta förklarar en del av hälsningsmeddelandet och det meddelande man får då man laddar in en egen fil; preludfilen är på våra datorer /usr/pd/lib/Hugs98May/hugs/lib/Prelude.hs. Man kan läsa denna fil, men än så länge är den svår att förstå. Men vi kan titta på en definition i denna fil:
max x y | x >= y = x | otherwise = y
Detta är en lösning på föregående övning. Den verkar obekant på två sätt:

Man har inte gjort radbyte innan man börjar med de olika fallen. Man behöver alltså inte göra det; i våra exempel hittills har vi följt lärobokens konvention.
Det sista fallet har otherwise där vi skrivit True. Förklaringen finns i preluden:
otherwise = True
Man tycker alltså bara att det ser trevligare ut att kunna skriva som ovan och har därför infört ett till namn på True.
Vi ser av detta också att man kan i sina filer definiera inte bara funktioner utan också konstanter (True är faktiskt en konstant; mer om detta följer). En annan konstant som definieras i preluden är pi, som också är av allmänt intresse.
Prelude> pi 3.14159 Prelude>

Förbättra definitionen av den funktion som ger arean av en cirkel genom att använda konstanten pi.
För att använda hugs effektivt är det viktigt att kunna använda preludens funktioner. Vi ska under de kommande veckorna bekanta oss mer med de definitioner som finns där. Just nu noterar vi bara att man inte kan själv definiera en funktion med ett namn som redan finns i preluden. Om man får ett felmeddelande av typen
ERROR "ex1.hs" (line 2): Definition of variable "max" clashes with import
är det troligt att detta är orsaken (om man inte själv gjort två olika definitioner med samma namn!).
Operatorer och funktioner av två variabler.
Funktioner som max och mv samt operatorer som +,-,* och / tar alla två tal som argument och ger ett tal som resultat. Varför används de på olika sätt (funktionerna skrivs före sina argument som i mv 3 4 medan operatorerna skrivs mellan sina argument som i 3+4)? I själva verket så finns det flera sorters namn i Haskell. Variabelnamn som vi använt för funktioner består av bokstäver och siffror (och börjar med liten bokstav). Operatorer består av ett eller flera av tecknen +-*/!#?%&$<>=|:~. Variabelnamn som är funktioner står före sina argument medan operatorer står mellan sina två argument. Man kan dock ändra på detta:
Main> 5 `mv` 4 4.5 Main> 4 `max` (5 `max` 2) 5 Main> (+) 3 4 7 Main>
Ett variabelnamn kan användas som en operator (dvs mellan sina argument) om det omsluts av ` (OBS: inte ' som också finns på tangentbordet!). En operator kan skrivas före sina argument om den omsluts av parenteser.
Olika sorters tal
Alla de funktioner vi definierat hittills arbetar med reella tal. Det finns dock många situationer där endast heltal är naturliga. Exempel är årtal och antal av olika slag (antal barn till en person, antal passagerare i en buss osv). För heltal finns två ytterligare funktioner som bägge tar två heltal som argument och returnerar ett heltal.
Funktionen div dividerar det första argument med det andra och ger ett heltal som resultat, dvs resten ignoreras:

Prelude> div 17 5 3 Prelude> div 34 8 4 Prelude> div 5 9 0 Prelude> 4 `div` 2 2 Prelude>
Observera hur vi i det sista exemplet gör en operator av namnet div.
Funktionen mod ger i stället resten vid division:
Prelude> 17 `mod` 5 2 Prelude> 34 `mod` 8 2 Prelude> 5 `mod` 9 5 Prelude> mod 4 2 0 Prelude>

Vad blir 5 `mod` 0?
Är 107139224 jämnt delbart med 11731?
Definiera en funktion som givet ett årtal ger antalet dagar under detta år med den förenklade regeln att de årtal som är jämnt delbara med fyra är skottår. (Detta är en förenkling eftersom jämna århundraden bara är skottår om också århundradet är delbart med fyra, dvs år 2000 är skottår men 1900 och 2100 är inte skottår).
För att lösa detta problem behöver ni troligen veta hur man jämför om två tal är lika: det gör man med operatorn == (ja, två likhetstecken!).

Ett större exempel
Exemplen hittills visar inte på hur man kan få hugs att göra mer omfattande beräkningar. Vi avslutar med ett exempel som illustrerar detta.
Vi betraktar följande lek med tal:
Tänk på ett heltal större än ett. Om talet är jämnt, dela det med två, annars multiplicera det med tre och lägg till ett. Om det nya talet är ett så sluta, annars upprepa förfarandet.
Som exempel, låt oss tänka på talet 10. Vi får då följande följd av tal:
10 är jämnt, så nästa tal blir 10/2 = 5
5 är udda, så nästa tal blir 3*5+1=16
16 är jämnt, så nästa tal blir 16/2 = 8
8 är jämnt så nästa tal blir 8/2 = 4
4 är jämnt så nästa tal blir 4/2 = 2
2 är jämnt så nästa tal blir 2/2 = 1. Slut!

Om vi i stället börjar med 7 så får vi följden (kontrollera!)
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Vi ska intressera oss för frågan: Givet ett tal n, hur många tal blir det i följden? För n=10 blir det 7 tal (10, 5, 16, 8, 4, 2, 1). För n=7 blir det 17 tal (se ovan). Observera att vi räknar med både n själv och den avslutande ettan.
Hur ska vi få hjälp av hugs att lösa detta problem? Vi börjar med att definiera en funktion next som givet ett heltal ger nästa tal i följden.
Gör detta!
Hur lång blir följden om vi börjar med n=6?
Vi vill definiera en funktion steps som tar ett tal n som argument och beräknar antalet tal i den följd som genereras. Vad blir steps 20? Och steps 3?
Med ledning av föregående övning observerar vi att funktionen steps uppfyller

steps n |n == 1 = 1 |otherwise = steps(next n)+1
Det förvånande är att detta faktiskt duger som definition av funktionen. Denna definition är annorlunda än alla vi sett tidigare: Vi använder funktionen själv i högerledet. Pröva att skriva in definitionen, ladda in filen och pröva att beräkna steps n för några olika n. Som ni kommer att upptäcka verkar det hela fungera utmärkt. Men samtidigt kan man undra:
Kan man vara säker på att man så småningom kommer till talet 1 vilket n man än börjar med?
Till sist så ska vi ge en antydan om ytterligare möjligheter: Kan man definiera en funktion som för givet n ger oss hela följden av tal som genereras? Svaret är, som man kanske kan gissa av den ledande frågan, ja. En funktion i hugs kan ge en hel lista av tal som resultat. Vi ger definitionen direkt:
numbers n |n==1 = [1] |otherwise = n : numbers(next n)
Laddar man in funktionen (pröva!) så får man:
Main> numbers 10 [10, 5, 16, 8, 4, 2, 1] Main> numbers 17 [17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] Main> numbers 1 [1] Main>
Vi studerar funktionsdefinitionen. Om n=1 så blir resultatet listan [1]. Annars använder vi operatorn : som kan utläsas "före" eller "följt av". Resultatet numbers n är n följt av listan numbers(next n).
När vi har definierat funktionen numbers så behöver vi inte steps eftersom det i preluden finns en funktion length som beräknar längden av en lista:
Main> length [1,6,33,8,7,14] 6 Main> length(numbers 10) 7 Main>
Men nu har vi gått alldeles för långt... Det är dags att börja gå igenom språket och dess programmeringsteknik mer systematiskt. Vi börjar imorgon!