101 lines
3.6 KiB
Plaintext
101 lines
3.6 KiB
Plaintext
Aufgabe 4
|
|
=========
|
|
|
|
> module Aufgabe4 where
|
|
|
|
> import Control.Monad
|
|
|
|
|
|
Mighty List Monad und das Vierfarbenproblem
|
|
-------------------------------------------
|
|
|
|
In Vorlesung 2 haben Sie den Vierfarbensatz kennen gelernt. Mithilfe der
|
|
List Monade lassen sich in wenigen Zeilen Code alle gültigen Kombinationen
|
|
von Einfärbungen finden. Reicht einem eine gültige Lösungen, so kann man
|
|
getrost die gleiche Funktion verwenden und Haskells Laziness sorgt dafür,
|
|
dass nur die eine nötige Lösung berechnet wird.
|
|
|
|
|
|
> data Farbe = Rot | Gruen | Gelb | Blau
|
|
> deriving (Show, Eq, Enum)
|
|
|
|
> data Landname = Frankreich
|
|
> | Deutschland
|
|
> | Niederlande
|
|
> | Grossbritannien
|
|
> | Belgien
|
|
> | Polen
|
|
> | Oesterreich
|
|
> | Ungarn
|
|
> | Island
|
|
> | Schweiz
|
|
> | Luxemburg
|
|
> | Irland
|
|
> | Italien
|
|
> | Portugal
|
|
> | Spanien
|
|
> | Slowenien
|
|
> | Liechtenstein
|
|
> | Slowakei
|
|
> | Tschechien
|
|
> deriving (Show,Eq,Enum)
|
|
|
|
> data Land = Land Landname [Landname]
|
|
> deriving (Show,Eq)
|
|
|
|
> defaultMap = [ Land Frankreich [Schweiz, Deutschland, Luxemburg]
|
|
> , Land Deutschland [Frankreich, Schweiz, Oesterreich, Luxemburg, Polen, Niederlande, Belgien, Tschechien]
|
|
> , Land Niederlande [Deutschland, Belgien]
|
|
> , Land Belgien [Frankreich, Deutschland, Luxemburg]
|
|
> , Land Polen [Tschechien, Deutschland]
|
|
> , Land Oesterreich [Schweiz, Deutschland, Tschechien]
|
|
> , Land Schweiz [Frankreich, Oesterreich, Deutschland]
|
|
> , Land Island []
|
|
> , Land Luxemburg [Frankreich, Deutschland]
|
|
> , Land Tschechien [Oesterreich, Polen, Deutschland ]
|
|
> ]
|
|
|
|
Schreiben Sie eine Funktion `gültig :: (Farbe,Land) -> [(Farbe, Land)] -> Bool`,
|
|
die überprüft, ob eine konkrete Landeinfärbung `(Farbe,Land)` vor dem
|
|
Hintergrund bereits bestehender Einfärbungen `[(Farbe,Land)]` gültig ist.
|
|
'Gültig' bedeutet, dass keine angrenzenden Länder dieselbe Farbe haben.
|
|
|
|
> gueltig :: (Farbe,Land) -> [(Farbe, Land)] -> Bool
|
|
> gueltig (f, (Land _ ns)) xs = undefined
|
|
|
|
Exkurs: Von List comprehensions kennen Sie die Möglichkeit mit Prädikaten zu prüfen,
|
|
ob ein Wert in die Liste aufgenommen werden soll oder nicht.
|
|
|
|
listcomp xs = [ x | x <- xs , pred x ]
|
|
|
|
Wenn Sie statt dessen do-Notation verwenden (oder `>>=`...), können Sie die Funktion
|
|
`guard :: MonadPlus m => Bool -> m ()` verwenden, um Ihre Prüffunktion innerhalb eines
|
|
do-Blocks unterzubringen. Der Type constraint `MondadPlus` stellt sicher, dass die
|
|
entsprechende Monad-Instanz auch ein neutrales Element `mzero` kennt. Wenn die
|
|
Prüffunktion von `guard` zu `False` auswertet, wird die Berechnung durch ein `mzero`
|
|
unterbrochen:
|
|
|
|
doNotation xs = do
|
|
x <- xs
|
|
guard $ pred x
|
|
return x
|
|
|
|
Vervollständigen Sie nun die folgenden, rekursiven Funktionen, welche alle gültigen
|
|
Einfärbungen einer Liste von Ländern berechnet. Benutzen Sie hierfür die Ihre
|
|
`gültig-`Funktion. Beide Funktionen machen das gleiche, aber zu Übungszwecken
|
|
nutzen Sie für `einfaerbenM` do-Notation und für `einfaerbenLC` List comprehension.
|
|
|
|
> einfaerbenM :: [Land] -> [[(Farbe,Land)]]
|
|
> einfaerbenM (x:[]) = do -- alternativ: pure $ (,) <$> [Rot .. Blau] <*> [x]
|
|
> f <- [Rot .. Blau]
|
|
> return [(f,x)]
|
|
> einfaerbenM (x:xs) = undefined
|
|
|
|
|
|
> einfaerbenLC :: [Land] -> [[(Farbe,Land)]]
|
|
> einfaerbenLC (x:[]) = [ [(f,x)] | f <- [Rot .. Blau] ]
|
|
> einfaerbenLC (x:xs) = undefined
|
|
|
|
> result :: String
|
|
> result = show $ head $ einfaerbenM defaultMap
|