Mengangkut serigala, kambing, dan kubis melintasi sungai dengan efek di Haskell

Suatu ketika seorang petani perlu mengangkut serigala, kambing, dan kubis menyeberangi sungai. Petani memiliki perahu di mana, selain petani itu sendiri, hanya satu objek yang dapat ditampung - serigala, atau kambing, atau kubis. Jika petani meninggalkan serigala tanpa pengawasan, serigala akan memakan kambing; jika seorang petani meninggalkan kambing dengan kubis tanpa pengawasan, kambing akan memakan kubis tersebut.

Pada artikel ini, kami akan mencoba menemukan solusi umum untuk jenis teka-teki ini dengan menggunakan efek aljabar.



Mari kita mulai dengan yang paling sederhana - rute perjalanan. Karena kita tidak tahu sebelumnya berapa jaminan jumlah langkah yang akan kita dapatkan solusinya setelah itu, kita dapat membangun rute tanpa batas, bagaimanapun kita akan menghitungnya dengan malas:

data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

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

Karena kita akan membangun solusi umum, kita juga abstrak dari karakter. Kami akan membangun hubungan tatanan simetris non-transitif antara elemen-elemen dari sekumpulan karakter (bagikan di komentar jika ada nama yang mapan untuk ini):

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

Mengapa menggunakan efek sama sekali? Efek membantu memerangi kompleksitas yang melekat pada domain apa pun. Jadi, untuk menentukan efek apa yang akan digunakan untuk memecahkan teka-teki, ada baiknya memikirkan kesulitan apa yang mungkin kita hadapi ketika mencoba menjelaskan solusi untuk masalah menggunakan kode:

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

Dalam kode, saya akan menggunakan perpustakaan bersama eksperimental saya (ada dua artikel tentang Habré yang menjelaskan esensinya - yang pertama dan yang kedua ), tetapi jika diinginkan, solusinya dapat ditransfer ke transformer atau mtl .



Jadi kami memiliki tiga efek yang berbeda: keadaan, multiplisitas, dan parsial. Sekarang kita perlu memutuskan bagaimana kita akan mengaturnya bersama:

• Dalam rantai evaluasi aplikatif / monad untuk Mungkin , jika kita tidak mendapatkan apa - apa di suatu tempat, maka hasil dari semua penghitungan adalah Tidak Ada . Kami akan meninggalkannya secara terpisah, karena kami tidak ingin bahwa ketika mengirim perahu kosong (tanpa karakter, petani, kami tidak memperhitungkannya) kami akan kehilangan semua kemajuan dalam mencari solusi.
• Setiap pilihan gerakan berikutnya (efek multiplisitas) harus bergantung pada komposisi pantai saat ini (efek keadaan), karena kita tidak dapat membawa karakter ke dalam perahu jika karakter tersebut berada di pantai seberang. Oleh karena itu, kita perlu menggabungkan efek ini menjadi transformator: Keadaan (Sungai a):> [] .

Satu gerakan dalam teka-teki dapat digambarkan sebagai urutan tindakan:

1. Dapatkan pemeran karakter di pantai saat ini
2. Pilih karakter berikutnya untuk diangkut
3. Pindahkan karakter ke bank seberang

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

Mari kita bahas setiap langkah dengan lebih detail.



Bergantung pada arah pergerakan perahu, kami menerapkan lensa untuk sumber keberangkatan ke keadaan seluruh sungai dan mendapatkan komposisi tepian saat ini:

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

Pilihan karakter berikutnya berjalan seperti ini: menerima satu set karakter dari pantai ( bank ekspresi sebelumnya ), kami membentuk ruang pemilihan dengan menambahkan perahu kosong ke ruang ini sendiri:

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

Untuk setiap kandidat (perahu kosong ( Tidak ada ) juga merupakan kandidat), kami memeriksa bahwa tidak ada karakter di pantai yang tersisa yang tidak keberatan makan satu sama lain:

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

Dan ketika kami memfilter ruang pemilihan karakter, kami meningkatkan efek multiplisitas dan mengembalikan setiap item dari ruang pemilihan itu:

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

Langkah terakhir tetap - transportasi yang sebenarnya menggunakan lensa: hapus karakter dari bank pengiriman dan tambahkan ke bank tujuan:

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

Jika ada karakter di perahu, kami mengubah keadaan sungai, jika tidak, gerakan itu menganggur:

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

Akan menyenangkan melihat program ini beraksi. Untuk menemukan solusi, kita perlu mengambil setidaknya tujuh langkah di sepanjang rute:

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

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

Dan kami memiliki dua solusi:







Sumber lengkap dapat dilihat di sini .