Transporte de lobo, cabra e repolho pelo rio com efeitos em Haskell

Certa vez, um camponês precisava transportar um lobo, uma cabra e um repolho para o outro lado do rio. O camponês tem um barco no qual, além do próprio camponês, cabe apenas um objeto - um lobo, ou uma cabra, ou um repolho. Se o camponês deixar o lobo com a cabra sem vigilância, o lobo comerá a cabra; se um camponês deixa uma cabra com repolho sem vigilância, a cabra comerá o repolho.




Neste artigo, tentaremos encontrar uma solução generalizada para esse tipo de quebra-cabeça usando efeitos algébricos.



Vamos começar com o mais simples - a rota de viagem. Como não sabemos com antecedência qual número garantido de etapas obteremos a solução depois, podemos construir uma rota infinita, de qualquer forma, iremos calculá-la preguiçosamente:



data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

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


Visto que vamos construir uma solução generalizada, também abstraímos dos personagens. Vamos construir uma relação de ordem simétrica não transitiva entre os elementos de um conjunto de caracteres (compartilhe nos comentários se houver um nome bem estabelecido para isso):



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 que usar efeitos? Os efeitos ajudam a combater a complexidade inerente a qualquer domínio. Isso significa que, para determinar quais efeitos usar para resolver o quebra-cabeça, vale a pena pensar nas dificuldades que podemos enfrentar ao tentar descrever a solução do problema usando o código:



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


No código, usarei minha biblioteca conjunta experimental (há dois artigos sobre Habré explicando sua essência - o primeiro e o segundo ), mas se desejar, a solução pode ser transferida para transformadores ou mtl .



Portanto, temos três efeitos díspares: estado, multiplicidade e parcial. Agora precisamos decidir como vamos organizá-los juntos:



  • Na cadeia de avaliações de aplicativo / mônada para Maybe , se obtivermos Nada em algum lugar, então o resultado de todos os cálculos será Nada . Vamos deixá-lo separadamente, pois não queremos que ao enviar um barco vazio (sem personagem, um camponês, não levamos em conta) percamos todo o progresso na busca de uma solução.
  • Cada escolha subsequente de movimento (efeito de multiplicidade) deve depender da composição da costa atual (efeito de estado), uma vez que não podemos levar o personagem para dentro do barco se ele estiver na outra margem. Portanto, precisamos concatenar esses efeitos em um transformador: State (River a):> [] .


Um movimento em um quebra-cabeça pode ser descrito como uma sequência de ações:



  1. Obtenha o elenco de personagens na costa atual
  2. Escolha o próximo personagem para transportar
  3. Mova o personagem para a margem oposta


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


Vamos examinar cada etapa com mais detalhes.



Dependendo da direção do movimento do barco, aplicamos a lente da fonte de saída ao estado de todo o rio e obtemos a composição da margem atual:



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




A escolha do próximo personagem é assim: recebendo um conjunto de caracteres da costa (o banco de expressão anterior ), formamos um espaço de seleção adicionando um barco vazio a este próprio espaço:



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




Para cada candidato (um barco vazio ( Nada ) também é um candidato), verificamos se não há personagens na costa restante que não se importariam de comer uns aos outros:



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




E quando filtramos o espaço de seleção de personagem, aumentamos o efeito de multiplicidade e retornamos cada item desse espaço de seleção:



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




Resta a última etapa - o transporte propriamente dito usando lentes: retire o personagem do banco de despacho e adicione ao banco de destino:



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




Se houvesse um personagem no barco, mudamos o estado do rio, caso contrário, o movimento era inativo:



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




Seria bom ver o programa em ação. Para encontrar uma solução, precisamos realizar pelo menos sete etapas ao longo do percurso:



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

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




E temos duas soluções:







Fontes completas podem ser vistas aqui .



All Articles