Mind the Gap

Haskell-Lückentextaufgaben, alle von der Art

Ersetze  undefined  durch einen Ausdruck, 
so daß der Wert von   test  gleich   True  ist. 

Beispiel: Aufgabe:

test = let { x = undefined :: Int } in  x * x == 9

Lösung:

test = let { x = 3 :: Int } in  x * x == 9

Highscorewertung

nach möglichst kleiner Quelltextgröße (die angegebene Zahl ist die Anzahl der Knoten des Syntaxbaums der Lösung minus die der Vorgabe), im Beispiel also 0 (sowohl 3 als auch undefined sind je ein Knoten).

Benutzung autotool

Aufgaben gibt es hier: http://kernkraft.imn.htwk-leipzig.de/mind-the-gap/cgi-bin/Super.cgi

Jeder Hal-Teilnehmer kann teilnehmen. Die Hal-Anmeldenummer hat die Form hal9-1129314150-82 Matrikelnummer: die ersten fünf Ziffern (11293), Passwort: die nächsten 5 Ziffern (14150).

Dann Login (NICHT Enter), dann Vorlesung/Übungsgruppe wählen (es gibt nur eine), dann nochmal auf Vorlesung clicken, dann sieht man die Aufgaben.

Highscore-Auswertung am Nachmittag. Es ist ein virtuelles Tutorium, also gibt es auch nur virtuelle Preise.

Allgemeine Designprinzipien für die Aufgaben

• der vorgegebene Lückentext ist bereits ein syntax- und typkorrektes Haskell-Programm, d.h. der Student kann das in seinen Editor kopieren und in ghci laden (bei der Auswertung von test wird er jedoch eine Exception erhalten).
• Sollte er auch machen, weil er im eigenen ghci verschiedene Ausdrücke auswerten kann (das autotool wertet immer nur test aus und das darf der Student nicht ändern)
• es gibt keine versteckten Musterlösungen oder geheime Bewertungsfunktionen.

Explizite Tests

Bsp: multiply-peano-numbers. Testfälle werden dabei explizit angegeben.

test = and 
  [ plus (S (S Z)) Z == S (S Z)
  , plus (S (S Z)) (S (S (S Z))) == S(S(S(S(S Z))))
  , times (S (S Z)) Z == Z
  , times (S (S Z)) (S (S (S Z))) == S(S(S(S(S (S Z)))))
  ]

das reicht oft schon aus (in Zusammenhang mit einem strengen Quelltextschema)

plus :: N -> N -> N
plus x y = case x of
   Z -> undefined
   S x' -> undefined

times :: N -> N -> N
times x y = case x of
   Z -> undefined
   S x' -> plus undefined undefined

man könnte hier einen Cheat versuchen: die ersten beiden Tests besteht man auch mit

plus x y = case x of 
   Z -> undefined
   S x' -> case y of Z -> S (S Z) ; _ ->  S(S(S(S(S Z))))

aber es wird schwierig, ein dazu passendes times zu bauen. (Können die Leute gern probieren.)

Testfallgenerierung (Prinzip)

durch Smallcheck (Bsp: append-reverse), Bsp:

reverse :: List a -> List a
reverse' :: List a -> List a

spec4 = \ ( xs :: List Bool ) -> 
    reverse xs == reverse' xs

Hierbei ist der Typ im Test eingeschränkt (List Bool), aber der Student muß trotzdem polymorph imlementieren (List a).

Testfallgenerierung (Detail)

Smallcheck hat nicht genau die Testtreiber, die ich brauche, deswegen steht immer noch etwas Hilfscode in der Aufgabe

-- | first f failures from t testcases for property p
failures f t p = take f ...

Der Student sollte trotzdem in ghci einfach folgendes ausführen:

smallCheck 3 spec4 

Eindeutige Spezifikationen

(Bsp: append-reverse)

hier ist das append korrekt vorgegeben und die Spezifikation von reverse lautet

spec1 = \ ( xs :: List Bool) -> 
    reverse (reverse xs) == xs
spec2 = \ ( xs :: List Bool, ys ) -> 
       reverse (append xs ys) ==  append (reverse ys) (reverse xs)

Interessant ist die Frage, ob dadurch bereits das “richtige” reverse erzwungen wird - sowie, ob die Einschränkung des Typs im Test wirklich nichts schadet.

(Bsp: peano-symdiff) hier ist die Spec. wirklich eindeutig.

Beispiel für Tricks bei Lösungen

Ist das eine gute Aufgabenstellung?

test :: Bool
test = null $ failures 10 1000 $ \ (f, a, xs) ->
       foldr f (a :: Bool) (xs :: [Bool])
    == foldl undefined undefined (reverse xs)

Die beabsichtigter Lösung ist foldl (flip f) a xs aber da kann man mogeln und das foldl umgehen (darauf muß man aber auch erstmal kommen):

test = null $ failures 10 1000 $ \ (f, a, xs) ->
       foldr f (a :: Bool) (xs :: [Bool])
    == foldl ( \ _ _ -> foldr f a xs) a  (reverse xs)

Beispiel für Fold über binären Baum

Bsp: check-AVL-balance-via-fold

die Funktion balanced kann nicht durch fold definiert werden (weil es nicht ausreicht, in der Wurzel zu wissen, on linkes und rechtes Kind balanciert sind).

Man führt eine Hilfsfunktion ein, die berechnet ein Paar, dessen zweite Komponente enthält das gewüschte Bit und die erste Komponente liefert die Hilfsinformation, so daß man insgesamt ein fold bauen kann.

balanced :: Tree a -> Bool
balanced t = snd 
  $ fold ( \ k -> (0,True) )
    undefined
  $ t 

Welches ist die Monoid-Operation?

In vielen Haskell-Programmen werden Monaden benutzt, dann muß ja diese Aufgabe leicht sein: find-the-monoid.

Dort sieht man auch, wie Smallcheck natürliche Zahlen generiert.

Bastel-Aufgaben

• twice-id-list (leicht)
• thrice-id-list (naja)
• guess-the-impossible-number
• sort-of-sorts (nicht Haskell, aber interessant)