Generera och testa

Detta dokument beskriver en problemlösningsmetod som är tillämplig i många sammanhang och därför är värd att känna till.

Vi betraktar inledningsvis följande problem (från Svenska Dagbladets matematiktävling för gymnasister 1996):

I ett fyrsiffrigt positivt heltal är entalssiffran och tiotalssiffran inbördes lika medan hundratalssiffran är densamma som tusentalssiffran. Talet är dessutom en jämn kvadrat. Bestäm talet.
Hur ska man angripa detta problem? Först observerar vi att det är underförstått i problemet att det finns precis ett tal som uppfyller de givna villkoren. I sådana situationer är det ofta bra att inte lita på detta utan i stället lösa följande modifierade problem:
Bestäm listan bestående av alla fyrsiffriga positivt heltal n sådana att
a) i n är entalssiffran och tiotalssiffran lika samt hundratalssiffran och tusentalssiffran lika
b) n är en jämn kvadrat.
Om det verkligen är så att det ursprungliga problemet har en entydig lösning så framgår det när vi löser det modifierade problemet.

Den ide' vi ska ta fasta på här är följande. Vi finner alla lösningar genom att arbeta i två steg:

  1. Generera en lista xs som säkert innehåller alla de sökta talen (och kanske många fler).
  2. Gå igenom xs och filtrera bort de oönskade elementen, dvs de som inte har alla egenskaper som krävs.
Denna ide' kan varieras. I exemplet ovan ska de sökta talen ha fyra egenskaper; de ska vara positiva heltal, de ska vara fyrsiffriga, de ska (i decimalsystemet) ha formen AABB för några siffror A och B och de ska vara jämna kvadrater. Man kan generera och filtrera på många olika sätt:
  1. Generera listan av alla positiva heltal; filtrera sedan bort dem som inte har de övriga tre egenskaperna.
  2. Generera listan av alla fyrsiffriga positiva heltal. Filtrera sedan bort dem som inte är kvadrater och på formen AABB.
  3. Generera listan av alla fyrsiffriga jämna kvadrater. Filtrera sedan bort dem som inte är på formen AABB.
  4. ...
Vi ska nu diskutera hur man kan genomföra generering och filtrering.

Generering

Aritmetiska följder

Det enklaste sättet att generera en lista är att räkna upp dess element. Detta går förstås bara i mycket enkla fall. Listan av alla udda tal mellan 1 och 10 kan vi generera genom uppräkning: [1,3,5,7,9].

Mer användbart i allmänhet är att ha ett sätt att generera alla positiva heltal i ett visst intervall. 

enumFromTo :: Int -> Int -> [Int]
enumFromTo m n
      |n < m = []
      |True  = m:enumFromTo (m+1) n
Denna funktion är definierad i preluden, men dessutom finns en speciell syntax för användning av just denna funktion; i stället för enumFromTo a b kan man skriva [a..b]. 
? [1..8]
[1, 2, 3, 4, 5, 6, 7, 8]
? [3+5..6*4]
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
?
Hur genererar man listan av alla fyrsiffriga positiva heltal?
Förklaringen ovan verkar konstig. Vad menas med att [a..b] är en speciell syntax för enumFromTo a b? (Denna fråga och dess svar kan överhoppas av den som vill!)
Det finns också ytterligare två likartade sätt att generera listor i hugs: 
? [1..]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41, 42, 43, 44, 45, 46,^C{Interrupted!}
? [1,3..10]
[1, 3, 5, 7, 9]
? [20,17..1]
[20, 17, 14, 11, 8, 5, 2]
?
Här är [a..] den oändliga listan [a,a+1,a+2,...]. [a..] är ett bekvämare skrivsätt för funktionsapplikationen enumFrom a.
Definiera funktionen enumFrom.
Uttrycksformen [n,n'..m] betecknar en aritmetisk följd av tal med differensen n'-n. Observera att följden kan vara avtagande om n>n'. Vi lämnar som övning för den intresserade att definiera en funktion 
enumFromThenTo :: Int -> Int -> Int -> [Int]
sådan att enumFromThenTo n n' m ger det resultat som illustreras ovan för [n,n'..m].

Dessutom konstaterar vi att dessa uttryck fungerar inte bara för heltalslistor utan också för till exempel teckenlistor.

Funktionen map

Med ovanstående grundläggande sätt att generera listor av tal i aritmetisk följd samt funktionen map ur preluden kan man generera ytterligare många listor. Vi påminner om definitionen av map: 
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x:map f xs
Generera listan av alla jämna kvadrater. Förutsätt att funktionen 
square :: Int -> Int
square x = x*x
finns inladdad.
Generera listan av alla fyrsiffriga jämna kvadrater.

Filtrering

Vi övergår nu till att se hur man kan filtrera listor för att finna de element som har en viss egenskap. Detta sker med hjälp av preludens funktion 
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
     |p x  = x : filter p xs
     |True = filter p xs
För att kunna använda filter måste man ha till hands en lämplig testfunktion som blir True precis för de element man vill filtrera ut (dvs de som har den önskade egenskapen).
Definiera lämpliga testfunktioner för att testa om ett tal a) är en jämn kvadrat; b) är på formen AABB; c) har bägge dessa egenskaper.
Vi kan nu lösa det ursprungliga problemet genom att generera och filtrera på lämpligt sätt. Några kombinationer är 
? filter isAABB (map square [isqrt 1000+1..isqrt 9999])
[7744]
? filter isBoth [1000..9999]
[7744]
?
där man inser att den första är bäst -- vi har byggt in mer kunskap i genereringen, vilket betalar sig genom att det blir färre element att filtrera.
Även den andra lösningen har litet kunskap i genereringen, i och med att den inskränker sig till att testa fyrsiffriga tal. Hur går det om man försöker med 
? filter isBoth [1..]
Kan man inte tänka sig att generera alla tal på formen AABB och sedan filtrera ut kvadraterna?
Slutligen kan vi fråga oss vad som förväntades av de som deltog i matematiktävlingen. Det är i och för sig möjligt att beräkna alla kvadrater och se efter vilka som har formen AABB, men troligen avsågs någon bättre lösning.
Kan Du göra genereringen ännu bättre, (dvs generera färre tal)?
Finns det några sexsiffriga tal på formen AABBCC som är jämna kvadrater?
En palindrom är en sträng som är likadan oavsett om man läser den framlänges eller baklänges. Exempel är "apa" och "racecar". Finns det några jämna kvadrater som är palindromer när man skriver dem i decimalsystemet?

Listsammanfattningar

För användningar av funktionerna map och filter och kombinationer av dessa finns en alternativ notation som inspireras av beteckningssättet i mängdlära. Denna beskrivs i avsnitten 4.4 och (för den som vill veta mer) 13.3. Det engelska namnet på formerna är "list comprehensions". Vedertaget svenskt namn saknas. Listsammanfattningar?

Vi börjar med filter. Ett vanligt sätt att i mängdlära definiera en mängd är med uttryck av formen {x | x tillhör A och P(x)} där A är en redan känd mängd och P(x) beskriver en egenskap hos x. Vi ser att detta påminner väldigt mycket om filter där vi definierar en lista genom att välja ut de element i en redan känd lista som har en viss egenskap. Vi visar några exempel: 

filter even xs                   [y | y <- xs, even y]
filter isSquare [1000..9999]     [x | x <- [1000..9999], isSquare x]
filter isBoth ys                 [k | k <- ys, isBoth k]
På varje rad är uttrycket till höger ett bekvämare skrivsätt för det till vänster. Variablerna x, y och k är, precis som variabler i funktionsdefinitioner, lokala i respektive uttryck -- det första skulle lika gärna kunnat skrivas 
[z | z <- xs, even z]
Skrivsättet <- är ett försök att på tangentbordet efterlikna mängdlärans "tillhör"-tecken. Vi visar ytterligare två exempel: 
[y | y <- xs, y `mod` 2 == 0]
[k | k <- ys, isSquare k, isAABB k]
Det första av dessa visar att med denna notation behöver vi inte ett namn even på en funktion som testar om ett tal är jämnt eftersom vi direkt kan skriva testet här. Det andra visar att vi kan ha flera test, åtskilda av kommatecken.

Också för generering med funktionen map finns en speciell notation som många tycker är mer lättläst. Vi visar några exempel: 

? [2^n | n <- [1..5]]
[2, 4, 8, 16, 32]
? [square n | n <- [1,3..12]] 
[1, 9, 25, 49, 81, 121]
?
Med map kan det andra uttrycket också skrivas map square [1,3..12] och det första map power2 [1..5]] under förutsättning att funktionen power2 finns inladdad. Vi ser också här att vi genom att använda listsammanfattningar ibland slipper beroendet av att ha ett namn på en funktion som power2.
Skriv uttrycket [square n | n <- [1,3..12]] på ett alternativt sätt som inte är beroende av att man har laddat in funktionen square.

Detta skrivsätt påminner om definitionen i mängdlära av bilden av en mängd A under en funktion f (där A förutsätts vara en delmängd av definitionsmängden till f). Vi har då att bilden av A, betecknad f(A), är
f(A) = {f(x) | x tillhör B}.

Det verkar som om man med listsammanfattningar skulle kunna göra beräkningar i mängdlära; eller? (Kan överhoppas av den som inte är intresserad av mängdlära.)
Vi avslutar för den som har tid med ett gammalt problem:
I en lågstadieklass är 37% av eleverna pojkar och 16% bär glasögon. Hur många elever är det i klassen?
Last modified: Mon Sep 21 15:41:10 MET DST 1998