Transporter un loup, une chèvre et un chou à travers la rivière avec des effets à Haskell

Autrefois, un paysan avait besoin de transporter un loup, une chèvre et un chou à travers la rivière. Le paysan a un bateau dans lequel, à part le paysan lui-même, un seul objet peut tenir - soit un loup, ou une chèvre, ou un chou. Si le paysan laisse le loup avec la chèvre sans surveillance, le loup mangera la chèvre; si un paysan laisse une chèvre avec du chou sans surveillance, la chèvre mangera le chou.

Dans cet article, nous allons tenter de trouver une solution généralisée pour ce type de puzzle en utilisant des effets algébriques.



Commençons par le plus simple - l'itinéraire de voyage. Comme on ne sait pas à l'avance quel nombre de pas garanti on obtiendra une solution après, on peut construire un itinéraire infini, de toute façon on va le calculer paresseusement:

data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

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

Puisque nous allons construire une solution généralisée, nous faisons également abstraction des personnages. Nous allons construire une relation d'ordre symétrique non transitive entre les éléments d'un ensemble de caractères (partage dans les commentaires s'il existe un nom bien établi pour cela):

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

Pourquoi utiliser des effets? Les effets aident à combattre la complexité inhérente à tout domaine. Cela signifie que pour déterminer les effets à utiliser pour résoudre le casse-tête, il convient de réfléchir aux difficultés auxquelles nous pourrions être confrontés lorsque nous essayons de décrire la solution du problème à l'aide de code:

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

Dans le code, j'utiliserai ma bibliothèque commune expérimentale (il y a deux articles sur Habré expliquant son essence - le premier et le second ), mais si vous le souhaitez, la solution peut être transférée vers des transformers ou mtl .



Nous avons donc trois effets disparates: état, multiplicité et partiel. Nous devons maintenant décider comment nous allons les organiser ensemble:

• Dans la chaîne d'évaluations applicatives / monades pour Maybe , si nous n'avons rien quelque part, alors le résultat de tous les calculs sera Rien . Nous le laisserons séparément, puisque nous ne voulons pas que lors de l'envoi d'un bateau vide (sans personnage, un paysan, nous ne prenons pas en compte) nous perdrons tout progrès dans la recherche d'une solution.
• Chaque choix de mouvement ultérieur (effet de multiplicité) doit reposer sur la composition du rivage actuel (effet d'état), car on ne peut pas emmener le personnage dans le bateau s'il est sur l'autre rive. Par conséquent, nous devons concaténer ces effets dans un transformateur: State (River a):> [] .

Un mouvement dans un puzzle peut être décrit comme une séquence d'actions:

1. Obtenez le casting de personnages sur le rivage actuel
2. Choisissez le prochain personnage à transporter
3. Déplacer le personnage vers la rive opposée

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

Passons en revue chaque étape plus en détail.



En fonction du sens de déplacement du bateau, nous appliquons la lentille de la source de départ à l'état de l'ensemble du fleuve et obtenons la composition de la rive actuelle:

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

Le choix du caractère suivant se déroule comme suit: recevant un jeu de caractères du rivage (la banque d' expressions précédente ), nous formons l'espace de sélection en ajoutant un bateau vide à cet espace lui-même:

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

Pour chaque candidat (bateau vide ( Rien ) est également candidat), nous vérifions qu'il ne reste plus de personnages sur le rivage restant qui ne craindraient pas de se manger:

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

Et lorsque nous avons filtré l'espace de sélection des caractères, nous augmentons l'effet de multiplicité et renvoyons chaque élément de cet espace de sélection:

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

La dernière étape reste - le transport proprement dit à l'aide de lentilles: retirez le personnage de la banque d'expédition et ajoutez à la banque de destination:

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

S'il y avait un personnage dans le bateau, nous changeons l'état de la rivière, sinon le mouvement était ralenti:

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

Ce serait bien de voir le programme en action. Pour trouver une solution, nous devons effectuer au moins sept étapes le long du parcours:

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

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

Et nous avons deux solutions: les







sources complètes peuvent être consultées ici .