101 lines
3.6 KiB
Haskell
101 lines
3.6 KiB
Haskell
-- 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
|