Transportar un lobo, una cabra y un repollo a través del río con efectos en Haskell

Una vez, un campesino necesitaba transportar un lobo, una cabra y un repollo a través del río. El campesino tiene un bote en el que, además del campesino mismo, solo cabe un objeto: un lobo, una cabra o un repollo. Si el campesino deja desatendido al lobo con la cabra, el lobo se comerá la cabra; si un campesino deja desatendida una cabra con repollo, la cabra se comerá el repollo.

En este artículo, intentaremos encontrar una solución generalizada para este tipo de acertijos mediante el uso de efectos algebraicos.



Comencemos con el más simple: la ruta de viaje. Dado que no sabemos de antemano qué número garantizado de pasos obtendremos una solución después, podemos construir una ruta infinita, aún así la calcularemos perezosamente:

data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

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

Dado que vamos a construir una solución generalizada, también abstraemos de los personajes. Construiremos una relación de orden simétrico no transitivo entre los elementos de un conjunto de caracteres (comparta los comentarios si hay un nombre bien establecido para esto):

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

¿Por qué utilizar efectos? Los efectos ayudan a combatir la complejidad inherente a cualquier dominio. Entonces, para determinar qué efectos usar para resolver el rompecabezas, vale la pena pensar en las dificultades que podemos enfrentar cuando tratamos de describir la solución al problema usando código:

• Para encontrar una solución en la que todos los personajes sean transportados a la orilla opuesta, es necesario clasificar muchas opciones de permutaciones. Para ello utilizaremos el efecto de multiplicidad que se puede conseguir con una lista regular.
• , ( , ) . type River a = ([a],[a]) c State (River a).
• - , — Maybe.

En el código, usaré mi biblioteca conjunta experimental (hay dos artículos sobre Habré que explican su esencia, el primero y el segundo ), pero si lo desea, la solución se puede transferir a transformers o mtl .



Entonces tenemos tres efectos dispares: estado, multiplicidad y parcial. Ahora tenemos que decidir cómo los vamos a organizar juntos:

• En la cadena aplicativa / mónada de evaluaciones para Quizás , si tenemos Nada en alguna parte, entonces el resultado de todos los cálculos será Nada . Lo dejaremos por separado, ya que no queremos que al enviar un bote vacío (sin un personaje, un campesino, no lo tenemos en cuenta) perdamos todo avance en la búsqueda de una solución.
• Cada elección posterior de movimiento (efecto de multiplicidad) debe depender de la composición de la orilla actual (efecto de estado), ya que no podemos llevar al personaje al barco si está en la otra orilla. Por lo tanto, necesitamos concatenar estos efectos en un transformador: Estado (Río a):> [] .

Un movimiento en un rompecabezas se puede describir como una secuencia de acciones:

1. Obtén el elenco de personajes en la orilla actual
2. Elige el siguiente personaje para transportar
3. Mueve el personaje a la orilla opuesta

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

Repasemos cada paso con más detalle.



Dependiendo de la dirección de movimiento del barco, aplicamos la lente de la fuente de salida al estado de todo el río y obtenemos la composición de la orilla actual:

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

La elección del siguiente carácter es la siguiente: obteniendo un conjunto de caracteres de la orilla (el banco de expresiones anterior ), formamos el espacio de selección agregando un bote vacío a este espacio en sí:

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

Para cada candidato (un bote vacío ( Nada ) también es un candidato), verificamos que no haya personajes en la orilla restante que no les importe comerse unos a otros:

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

Y cuando filtramos el espacio de selección de caracteres, aumentamos el efecto de multiplicidad y devolvemos cada elemento de ese espacio de selección:

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

Queda el último paso: el transporte real con lentes: elimine el personaje del banco de despacho y agréguelo al banco de destino:

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

Si había un personaje en el bote, cambiamos el estado del río, de lo contrario el movimiento estaba inactivo:

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

Sería bueno ver el programa en acción. Para encontrar una solución, debemos dar al menos siete pasos a lo largo de la ruta:

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

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

Y tenemos dos soluciones: las







fuentes completas se pueden ver aquí .