Transport eines Wolfes, einer Ziege und eines Kohls über den Fluss mit Auswirkungen in Haskell

Einmal musste ein Bauer einen Wolf, eine Ziege und einen Kohl über den Fluss transportieren. Der Bauer hat ein Boot, in das neben dem Bauern selbst nur ein Gegenstand passen kann - entweder ein Wolf, eine Ziege oder ein Kohl. Wenn der Bauer den Wolf mit der Ziege unbeaufsichtigt lässt, frisst der Wolf die Ziege; Wenn ein Bauer eine Ziege mit Kohl unbeaufsichtigt lässt, frisst die Ziege den Kohl.

In diesem Artikel werden wir versuchen, mithilfe algebraischer Effekte eine verallgemeinerte Lösung für diese Art von Rätsel zu finden.



Beginnen wir mit der einfachsten - der Reiseroute. Da wir nicht im Voraus wissen, nach welcher garantierten Anzahl von Schritten wir die Lösung erhalten, können wir eine unendliche Route erstellen, trotzdem werden wir sie träge berechnen:

data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

alter :: Direction -> Direction
alter Back = Forward
alter Forward = Back

Da wir eine verallgemeinerte Lösung erstellen werden, abstrahieren wir auch von den Zeichen. Wir werden eine nicht-transitive symmetrische Ordnungsbeziehung zwischen den Elementen eines Zeichensatzes erstellen (in den Kommentaren teilen, wenn es dafür einen gut etablierten Namen gibt):

data Character = Wolf | Goat | Cabbage deriving Eq

class Survivable a where
	survive :: a -> a -> Ordering

instance Survivable Character where
	survive Wolf Goat = GT
	survive Goat Wolf = LT
	survive Goat Cabbage = GT
	survive Cabbage Goat = LT
	survive _ _ = EQ

Warum überhaupt Effekte verwenden? Effekte helfen dabei, die Komplexität zu bekämpfen, die jeder Domäne innewohnt. Dies bedeutet, dass es sich lohnt, über die Schwierigkeiten nachzudenken, mit denen wir möglicherweise konfrontiert sind, wenn wir versuchen, die Lösung des Problems mithilfe von Code zu beschreiben, um festzustellen, welche Effekte zur Lösung des Puzzles verwendet werden sollen:

• , , . , .
• , ( , ) . type River a = ([a],[a]) c State (River a).
• - , — Maybe.

Im Code werde ich meine experimentelle gemeinsame Bibliothek verwenden (es gibt zwei Artikel über Habré, in denen das Wesentliche erläutert wird - der erste und der zweite ), aber auf Wunsch kann die Lösung auf Transformatoren oder mtl übertragen werden .



Wir haben also drei unterschiedliche Effekte: Zustand, Multiplizität, partiell. Jetzt müssen wir entscheiden, wie wir sie zusammen arrangieren wollen:

• Wenn wir in der anwendungsbezogenen / monadischen Bewertungskette für Vielleicht nichts irgendwo haben, ist das Ergebnis aller Berechnungen Nichts . Wir werden es separat lassen, da wir nicht wollen, dass wir beim Senden eines leeren Bootes (ohne Charakter, einen Bauern, den wir nicht berücksichtigen) alle Fortschritte bei der Suche nach einer Lösung verlieren.
• Jede nachfolgende Bewegungswahl (Multiplizitätseffekt) muss von der Zusammensetzung des aktuellen Ufers abhängen (Zustandseffekt), da wir den Charakter nicht in das Boot aufnehmen können, wenn er sich am anderen Ufer befindet. Daher müssen wir diese Effekte zu einem Transformator verketten: State (River a):> [] .

Eine Bewegung in einem Puzzle kann als eine Folge von Aktionen beschrieben werden:

1. Holen Sie sich die Besetzung der Charaktere am aktuellen Ufer
2. Wählen Sie das nächste zu transportierende Zeichen
3. Bewegen Sie den Charakter auf die gegenüberliegende Bank

step direction = bank >>= next >>= transport

Lassen Sie uns jeden Schritt genauer durchgehen.



Abhängig von der Bewegungsrichtung des Bootes wenden wir die Linse für die Abflugquelle auf den Zustand des gesamten Flusses an und erhalten die Zusammensetzung des aktuellen Ufers:

bank :: (Functor t, Stateful (River a) t) => t [a]
bank = view (source direction) <$> current

Die Wahl des nächsten Zeichens geht so: eine Reihe von Zeichen vom Ufer (der vorherige Ausdruck Empfangs Bank ), wir durch Hinzufügen eines leeren Boot zu diesem Raum eine Auswahl Raum bilden sich:

\xs -> Nothing : (Just <$> xs) 

Für jeden Kandidaten (ein leeres Boot ( Nothing ) ist auch ein Kandidat) prüfen wir, ob am verbleibenden Ufer keine Charaktere mehr vorhanden sind, denen es nichts ausmacht, sich gegenseitig zu essen:

valid :: Maybe a -> Bool
valid Nothing = and $ coexist <$> xs <*> xs
valid (Just x) = and $ coexist <$> delete x xs <*> delete x xs

coexist :: Survivable a => a -> a -> Bool
coexist x y = survive x y == EQ

Und wenn wir den Zeichenauswahlbereich herausgefiltert haben, erhöhen wir den Multiplizitätseffekt und geben jedes Element aus diesem Auswahlbereich zurück:

next :: (Survivable a, Iterable t) => [a] -> t (Maybe a)
next xs = lift . filter valid $ Nothing : (Just <$> xs)

Der letzte Schritt bleibt - der eigentliche Transport mit Linsen: Entfernen Sie das Zeichen aus der Versandbank und fügen Sie es der Zielbank hinzu:

leave, land :: River a -> River a
leave = source direction %~ delete x
land = target direction %~ (x :)

Wenn sich ein Charakter im Boot befand, ändern wir den Zustand des Flusses, andernfalls war die Bewegung im Leerlauf:

transport :: (Eq a, Applicative t, Stateful (River a) t) => Maybe a -> t (Maybe a)
transport (Just x) = modify @(River a) (leave . land) $> Just x where
transport Nothing = pure Nothing

Es wäre schön, das Programm in Aktion zu sehen. Um eine Lösung zu finden, müssen wir mindestens sieben Schritte entlang der Route ausführen:

start :: River Character
start = ([Goat, Wolf, Cabbage], [])

solutions = run (traverse step $ take 7 route) start

Und wir haben zwei Lösungen:







Vollständige Quellen können hier eingesehen werden .