かつて農民はオオカミ、ヤギ、キャベツを川を渡って運ぶ必要がありました。農民は、農民自身のほかに、オオカミ、ヤギ、またはキャベツのいずれか1つのオブジェクトのみが収まるボートを持っています。農民がヤギと一緒にオオカミを離れると、オオカミはヤギを食べます。農民がキャベツを持ってヤギを放置すると、ヤギはキャベツを食べます。
この記事では、代数的効果を使用して、このタイプのパズルの一般化された解決策を見つけようとします。
最も単純なもの、つまり移動ルートから始めましょう。解決策が得られる保証されたステップ数が事前にわからないため、無限のルートを構築できます。とにかく、それを怠惰に計算します。
data Direction = Back | Forward
route :: [Direction]
route = iterate alter Forward
alter :: Direction -> Direction
alter Back = Forward
alter Forward = Back
一般化されたソリューションを構築するので、文字からも抽象化します。文字セットの要素間に非遷移的な対称順序関係を構築します（これに十分に確立された名前がある場合は、コメントで共有してください）。
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
なぜエフェクトを使用するのですか？エフェクトは、あらゆるドメインに固有の複雑さに対抗するのに役立ちます。これは、パズルを解くためにどの効果を使用するかを決定するために、コードを使用して問題の解決策を説明しようとするときに直面する可能性のある困難について考える価値があることを意味します。
- , , . , .
- , ( , ) . type River a = ([a],[a]) c State (River a).
- - , — Maybe.
コードでは、実験的な共同ライブラリを使用します（Habréにはその本質を説明する2つの記事があります-最初と2番目）が、必要に応じて、ソリューションをトランスフォーマーまたはmtlに転送できます。
したがって、状態、多重度、部分的という3つの異なる効果があります。次に、それらをどのように一緒に配置するかを決定する必要があります。
- たぶん、アプリケーション/モナドの評価チェーンで、どこかに何も得られなかった場合、すべての計算の結果は何もありません。空のボートを送るときに（キャラクター、農民なし、私たちは考慮しません）、解決策を見つけるためのすべての進歩を失うことを望まないので、それを別々に残しておきます。
- キャラクターが他の海岸にいる場合はボートに乗ることができないため、その後の移動の選択（多重効果）はそれぞれ、現在の海岸の構成（状態効果）に依存する必要があります。したがって、これらの効果をトランスフォーマーに連結する必要があります：State（River a）：> []。
パズルの1つの動きは、一連のアクションとして説明できます。
- 現在の海岸でキャラクターのキャストを取得する
- 転送する次の文字を選択してください
- キャラクターを反対側のバンクに移動します
step direction = bank >>= next >>= transport各ステップをさらに詳しく見ていきましょう。
ボートの移動方向に応じて、出発元のレンズを川全体の状態に適用し、現在の銀行の構成を取得します。
bank :: (Functor t, Stateful (River a) t) => t [a]
bank = view (source direction) <$> current
次のキャラクターの選択は次のようになります。海岸（前のエクスプレッションバンク）からキャラクターのセットを受け取り、このスペース自体に空のボートを追加して選択スペースを形成します。
\xs -> Nothing : (Just <$> xs)
候補者ごとに（空のボート（Nothing）も候補者です）、残りの海岸にお互いを食べても構わないキャラクターが残っていないことを確認します。
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
そして、文字選択スペースを除外すると、多重度効果が上がり、その選択スペースから各アイテムが返されます。
next :: (Survivable a, Iterable t) => [a] -> t (Maybe a)
next xs = lift . filter valid $ Nothing : (Just <$> xs)
最後のステップは残ります-レンズを使用した実際の輸送：ディスパッチバンクからキャラクターを削除し、デスティネーションバンクに追加します：
leave, land :: River a -> River a
leave = source direction %~ delete x
land = target direction %~ (x :)
ボートにキャラクターがいた場合は、川の状態を変更します。それ以外の場合、移動はアイドル状態でした。
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
プログラムが実際に動作しているのを見るのは素晴らしいことです。解決策を見つけるには、ルートに沿って少なくとも7つのステップを踏む必要があります。
start :: River Character
start = ([Goat, Wolf, Cabbage], [])
solutions = run (traverse step $ take 7 route) start
そして、2つの解決策
があります。完全なソースはここで表示できます。