Einführende Beispiele QuickCheck
Übersicht: Einführende Beispiele QuickCheck
Formulierung einer komplexen Eigenschaft - "sortiertes Einfügen in eine Liste"
Anhand eines komplexeren Beispiels sollen allgmeine Aspekte des Testens besprochen werden.
Bei dem Beispiel handelt es sich um den Test der Operation "insertOrdered".
Die Funktion ist wie folgt definieret:
01 insertOrdered :: (Ord a) => a -> [a] -> [a] -> [a]
02 insertOrdered a [] ys = ys++[a]
03 insertOrdered a (x:xs) ys
04 | a <= x = ys ++ a:[x] ++ xs
05 | a > x = insertOrdered a xs (ys ++ [x])
|
insertOrdered.hs |
Codebeispiel 4
"insertOrdered" fügt der Ordnung des Elementtyps folgend Elemente in eine Liste. Die Funktion hat drei Paramter: das einzufügende Element, die Ausgangsliste und eine Ergebnisliste. Zeile 2 zeigt den trivialen Fall bzw. den Abbruch der Rekursion: ist die Ausgangsliste leer, so wird das Element an die Ergebnisliste angehangen und diese zurückgegeben. Der Guard in Zeile 4 der zur Definition in Zeile 3 gehört, ordnet a kleiner gleich x das a vor den Kopf der Liste x:xs und concatiniert diese an die Ergebnisliste. Der Guard in Zeile 5 bildet die Rekurison. Ist a größer x so wird insertOrdered rekurisv aufgerufen. Dabei wird das a unverändert als Element übergeben. Die Ausgangsliste wird um den Kopf reduziert und der Kopf an die Ergebnisliste concateniert.
komplexe Eigenschaften I
Für den Test erfolgt die Definition der Eigenschaft.
Es wird die Eigenschaft prop_InsertOrdered bzw. prop_InsertOrderedInt(mit Typsignatur versehene prop_InsertOrdered) definiert. Sie basieren beide auf der Funktion ordered.
01 import QuickCheck
02
03 insertOrdered :: (Ord a) => a -> [a] -> [a] -> [a]
04 insertOrdered a [] ys = ys++[a]
05 insertOrdered a (x:xs) ys
06 | a <= x = ys ++ a:[x] ++ xs
07 | a > x = insertOrdered a xs (ys ++ [x])
08
09 ordered :: (Ord a) => [a] -> Bool
10 ordered [] = True
11 ordered [x] = True
12 ordered (x1:x2:xs)
13 | x1 <= x2 = True && ordered (x2:xs)
14 | x1 > x2 = False
15
16 prop_InsertOrdered x xs = ordered (insertOrdered x xs [])
17
18 prop_InsertOrderedInt :: Integer -> [Integer] -> Bool
19 prop_InsertOrderedInt x xs = ordered (insertOrdered x xs [])
|
complexProp1.hs |
Codebeispiel 5
Die Funktion "ordered" ist ein Prädikat, welches darüber Auskunft gibt, ob eine Liste sortiert ist oder nicht. Im Falle der leeren und einelementigen Liste (Zeile 10 und 11) wird wahr zurückgegeben. Folgt auf das erste Element als zweites ein Element das nach der Ordnug des Elementtyps kleiner ist (Zeile 14), so handelt es sich um eine nicht vollständig geordnete Liste und die Funktion gibt falsch zurück. Die Zeile 13 behandelt den Fall, das die Ordnungsrelation zwischen den zwei ersten Elementen der Liste in folgender Form gegben ist x1 < x2. Hier erfolgt der rekursive Aufruf mit der am Kopf der Liste um ein Element verkürzten Liste.
Über die in Zeile 19 definierte Eigenschaft prop_InsertOrderedInt kann getestet werden, ob nach dem sortierten Einfügen über den Aufruf von insertOrdered x xs [] eine sortierte Liste vorliegt. Das erfolgt über den äusseren Aufruf von ordered ( ....).
Bei der Durchführung des Tests kommt es jedoch zu Fehlern!
Main> quickCheck prop_InsertOrderedInt
Falsifiable, after 1 tests:
3
[3,1]
(3041 reductions, 6727 cells)
Was ist falsch?
Der Fehler liegt in der Formulierung des Tests: Denn der Test kann nur dann erfolgreich verlaufen wenn die Ausgangsliste in die ein Element sortiert eingefügt werden soll, auch tatsächlich selbst sortiert ist. Dies wird von der Funktion iinsertOrdered :: (Ord a) => a -> [a] -> [a] -> [a] in keiner Weise berücksichtigt.
komplexe Eigenschaften II
An dieser Stelle führen wir die Conditional Properties - also bedingten Eigenschaften ein.
Es wird über eine erweiterte Definition der Eigenschaft der Randbedingungen bzgl. der notwendigerweise sortierten Ausgangsliste Rechenschaft geboten. In der Zeile 19 ist die erweiterte Eigenschaft formuliert. prop_InsertOrderedInt x xs = ordered xs ==> ordered (insertOrdered x xs [])
mit "ordered xs ==>" wird die Vorbedingung, die Ausgangsliste für den Test ist sortiert, formuliert.
Anwendung einer Vorbedingung - Conditional Properties
01 import QuickCheck
02
03 insertOrdered :: (Ord a) => a -> [a] -> [a] -> [a]
04 insertOrdered a [] ys = ys++[a]
05 insertOrdered a (x:xs) ys
06 | a <= x = ys ++ a:[x] ++ xs
07 | a > x = insertOrdered a xs (ys ++ [x])
08
09 ordered :: (Ord a) => [a] -> Bool
10 ordered [] = True
11 ordered [x] = True
12 ordered (x1:x2:xs)
13 | x1 <= x2 = True && ordered (x2:xs)
14 | x1 > x2 = False
15
16 prop_InsertOrdered x xs = ordered xs ==> ordered (insertOrdered x xs [])
17
18 prop_InsertOrderedInt :: Integer -> [Integer] -> Property
19 prop_InsertOrderedInt x xs = ordered xs ==> ordered (insertOrdered x xs [])
|
complexProp2.hs |
Codebeispiel 6
Die der Durchführung des Tests läuft fehlerfrei.
Main> quickCheck prop_InsertOrderedInt
OK, passed 100 tests. (550047 reductions, 1208423 cells, 5 garbage collections)
Die allgemeine Syntax der Conditional Properties
Codebeispiel 7
Was ist bei der Anwendung einer Vorbedingung (Bedingte Eigenschaften) zu beachten? Was kann an diesem Beispiel beobachtet werden?
Wir sehen das die Entwicklung einer korrekten Formulierung einer Eigenschaft und somit eines Tests eine Reihe von Schwierigkeiten birgt. Wir haben in diesem Bespiel Definition der Eigenschaft mehrfach verfeinert und parallel dazu die Eingenschaften der Funktion selbst verdeutlicht.
Als zweiten Aspekt müssen wir nach der Effizienz fragen! Wie funktionieren die Conditional Properties? Es werden zufallsbedingt Testdaten erzeugt und dann geprüft, ob diese den Bedinungen genügen. Ist dies nicht der Fall so werden die Daten verworfen. So kommt es dazu, dass viele Testdaten verworfen werden.
Code generated with AusarbeitungGenerator Version 1.1, weblink