Aufgabe 4 ========= ```haskell 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. ```haskell 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. ```haskell 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. ```haskell 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 mit `mzero` unterbrochen: ```haskell 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. ```haskell 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 ```