Mencoba menyusun skema docking yang tidak dapat dikomposisikan

Pendahuluan

Di Haskell, sudah lazim untuk bekerja dengan efek sebagai functors yang objeknya adalah beberapa ekspresi yang kita minati saat ini.

Ketika kita melihat jenis ekspresi Mungkin a , kita abstrak dari keberadaan aktual dari beberapa, memusatkan semua perhatian kita pada ini. Kisah yang sama dengan Daftar a - nilai jamak dari; Status sa - a , tergantung pada beberapa kondisi saat ini; Baik ea - a , yang mungkin mengembalikan beberapa kesalahan e .

Sebelum melanjutkan, artikel ini akan menggunakan beberapa definisi:

type (:=) ta = ta -- |   type (:.) tua = t (ua) -- |   type (~>) tu = forall a . ta -> ua -- |   

Misalnya: Daftar : . Mungkin: = a - ungkapan ini mudah dibayangkan, ini adalah daftar nilai yang keberadaannya dipertanyakan.

Lebih lanjut, sebagai contoh, kita akan menggunakan empat tipe umum: Reader , State , Either , Maybe .

Komposisi dan Transformer

Cara yang paling jelas untuk menerapkan lebih dari satu efek ke ekspresi adalah dengan hanya menanamkan satu ke yang lain, ini adalah komposisi fungsi yang biasa. Dalam komposisi, efek tidak berpengaruh satu sama lain (kecuali metode Traversable digunakan di atasnya). Dan untuk menggabungkan banyak efek menjadi satu, transformer digunakan. Setiap metode memiliki kelebihan dan kekurangan:

Komposisi:

• Tidak diperlukan jenis tambahan untuk membuatnya
• Tidak ada metode umum untuk menggabungkan efek dengan kelas Functor / Applicative / Monad
• Semuanya menyusun luar biasa sampai datang ke monads

Transformer:

• Memungkinkan Anda menggabungkan beberapa efek menjadi satu
• Tetapi Anda memerlukan jenis yang terpisah (paling sering beberapa jenis baru )
• Dengan menggunakan lift, Anda dapat melakukan perhitungan pada setiap lapisan tumpukan transformasi.
• Tetapi Anda tidak dapat memperhitungkan efek secara terpisah, meskipun ada fungsi khusus

Transformer berbeda dari komposisi kopling (saya tidak tahu harus menyebutnya apa secara berbeda). Memiliki komposisi, Anda dapat mengubahnya menjadi transformator dan sebaliknya. Skema docking akan membantu kita dengan ini.

Skema Docking

Jika kita melihat lebih dekat pada tipe untuk transformator monad, kita dapat mengidentifikasi beberapa pola:

 newtype ReaderT rma = ReaderT { runReaderT :: r -> ma } newtype MaybeT ma = MaybeT { runMaybeT :: m (Maybe a) } newtype ExceptT ema = ExceptT { runExceptT :: m (Either ea)) } newtype StateT sma = StateT { runStateT :: s -> m (a,s) } 

Transformer menggambarkan kasus khusus tentang bagaimana efek pasti dan tidak pasti saat ini harus bertautan.

Biarkan t menjadi pasti dan Anda tidak terbatas, coba:

 Reader: r -> ua ===> (->) r :. u := a ===> t :. u := a -- t ~ (->) r Maybe: u (Maybe a) ===> u :. Maybe := a ===> u :. t := a -- t ~ Maybe Either: u (Either ea) ===> u :. Either e := a ===> u :. t := a -- t ~ Either e 

Beberapa efek cukup kompleks dan dapat didefinisikan melalui komposisi efek lain yang lebih sederhana:

 State: s -> u (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t' := a -- t ~ (->) s, t' ~ (,) s newtype State sa = State ((->) s :. (,) s := a) 

Jika kita melihat lebih dekat pada 3 contoh pertama, kita dapat melihat pola umum: jika di Reader , efek tertentu membungkus yang tidak terbatas (membawanya ke tanda kurung, menjadi objek dari functor), kemudian dengan Either dan Maybe itu sebaliknya - efek tidak terbatas merangkum yang spesifik. Dalam kasus State, kami bahkan menempatkan functor antara dua efek yang didefinisikan lebih sederhana.

Mari kita coba untuk mengekspresikan pola-pola ini dalam tipe:

 newtype TU tua = TU (t :. u := a) newtype UT tua = UT (u :. t := a) newtype TUT tut' a = TUT (t :. u :. t' := a) 

Kami baru saja menetapkan skema docking - ini adalah komposisi fungsi dalam bungkus yang menunjukkan posisi efek spesifik dan tidak terbatas.

Pada kenyataannya, metode untuk transformer yang namanya dimulai dengan menjalankan cukup menghapus pembungkus transformator, mengembalikan komposisi functors. Kami menggambarkan kelas jenis tersebut:

 class Composition t where type Primary ta :: * run :: ta -> Primary ta 

Sekarang kita memiliki cara universal untuk menjalankan sirkuit ini:

 instance Composition (TU tu) where type Primary (TU tu) a = t :. u := a run (TU x) = x instance Composition (UT tu) where type Primary (UT tu) a = u :. t := a run (UT x) = x instance Composition (TUT tu t') where type Primary (TUT tu t') a = t :. u :. t' := a run (TUT x) = x 

Bagaimana dengan transformer? Di sini Anda juga akan memerlukan kelas tipe di mana skema docking ditentukan untuk jenis tertentu, metode penanaman dinyatakan untuk meningkatkan efek tidak terbatas ke tingkat transformator dan membangun untuk membangun efek tertentu menjadi transformator:

 class Composition t => Transformer t where type Schema (t :: * -> *) (u :: * -> *) = (r :: * -> *) | r -> tu embed :: Functor u => u ~> Schema tu build :: Applicative u => t ~> Schema tu type (:>) tua = Transformer t => Schema tua 

Sekarang tinggal mendeklarasikan instance, mulai dengan Maybe and Either :

 instance Transformer Maybe where type Schema Maybe u = UT Maybe u embed x = UT $ Just <$> x build x = UT . pure $ x instance Transformer (Either e) where type Schema (Either e) u = UT (Either e) u embed x = UT $ Right <$> x build x = UT . pure $ x 

Kami akan membuat tipe kami sendiri untuk Pembaca , karena tidak ada di pangkalan . Dan dia juga membutuhkan turunan dari kelas Komposisi , karena ini adalah pembungkus untuk functor panah:

 newtype Reader ea = Reader (e -> a) instance Composition (Reader e) where type Primary (Reader e) a = (->) ea run (Reader x) = x instance Transformer (Reader e) where type Schema (Reader e) u = TU ((->) e) u embed x = TU . const $ x build x = TU $ pure <$> run x 

Lakukan sesuatu yang mirip dengan Negara :

 newtype State sa = State ((->) s :. (,) s := a) instance Composition (State s) where type Primary (State s) a = (->) s :. (,) s := a run (State x) = x instance Transformer (State s) where type Schema (State s) u = TUT ((->) s) u ((,) s) embed x = TUT $ \s -> (s,) <$> x build x = TUT $ pure <$> run x 

Sebagai contoh

Masih untuk menguji ini pada masalah dunia nyata - sebagai contoh, kami akan menulis sebuah program yang menghitung penempatan berbagai jenis kurung yang benar.

Tentukan jenis untuk tanda kurung: mereka dapat membuka dan menutup; dan juga memiliki gaya yang berbeda:

 data Shape = Opened | Closed data Style = Round | Square | Angle | Curly 

Simbol lain dari program kami tidak menarik:

 data Symbol = Nevermind | Bracket Style Shape 

Kami juga menetapkan daftar kesalahan yang mungkin ditemui program kami:

 data Stumble = Deadend (Int, Style) --     | Logjam (Int, Style) --     | Mismatch (Int, Style) (Int, Style) --       

Apa efek yang dibutuhkan oleh program kami? Kami harus menyimpan daftar tanda kurung yang menunggu verifikasi dan kami harus berhenti pada kesalahan pertama yang ditemui. Kami membuat transformator:

 State [(Int, Style)] :> Either Stumble := () 

Algoritma ini sederhana: kita melalui struktur dengan tanda kurung yang diindeks, jika setelah bagian kita tidak menemukan kesalahan dan kita masih memiliki tanda kurung di negara bagian, maka braket terbuka tidak memiliki yang tertutup:

 checking :: Traversable t => t (Int, Symbol) -> Either Stumble () checking struct = run (traverse proceed struct) [] >>= \case (s : _, _) -> Left . Logjam $ s where ([], _) -> Right () 

Kami ingat setiap braket terbuka, bandingkan yang tertutup dengan yang terakhir diingat terbuka:

 proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := () proceed (_, Nevermind) = pure () proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style) procceed (n, Bracket closed Closed) = build get >>= \case []-> embed $ Left . Deadend $ (n, closed) ((m, opened) : ss) -> if closed /= opened then embed . Left $ Mismatch (m, opened) (n, closed) else build $ put ss where 

Kesimpulan

Menggunakan skema docking, memiliki beberapa komposisi fungsi, kita dapat mengubahnya menjadi transfomers dan sebaliknya. Sayangnya, trik seperti itu tidak akan berhasil dengan ibu dari monad - sekuel. Dan semuanya karena mereka tidak dapat dibayangkan sebagai komposisi dari para pelaku, tetapi itu mungkin sebagai komposisi dari para ahli ... ... Namun, ini adalah kisah yang sama sekali berbeda.

Kode Perpustakaan tentang Github | Dokumentasi Hackage | Contoh parenthesis