Saya membawa kepada Anda terjemahan dari artikel segar yang indah oleh Justin Le. Dalam blognya di Code, penulis ini berbicara dalam bahasa yang agak mudah tentang esensi matematika dari solusi fungsional yang indah dan elegan untuk masalah praktis. Artikel ini membahas secara rinci contoh bagaimana mentransfer struktur matematika yang membentuk data dalam area subjek ke sistem jenis program dapat segera, karena Gerald dan Sassman menulis "secara otomatis", mengarah pada solusi yang berfungsi.

Kode yang ditunjukkan dalam gambar adalah implementasi mandiri penuh, dapat diperluas dari pengurai ekspresi reguler, ditulis dari awal. Kelas atas, sihir tipe nyata!

Hari ini kami menerapkan ekspresi reguler dan parser (dalam semangat perpustakaan regex-aplikatif ) menggunakan struktur aljabar gratis! Struktur bebas adalah salah satu alat favorit saya di Haskell, dan saya menulis sebelumnya tentang grup gratis , variasi pada topik monad gratis dan fungsi aplikasi bebas pada monoids .

Ekspresi reguler (dan parser untuk mereka) ada di mana-mana dalam pemrograman dan ilmu komputer, jadi saya berharap bahwa dengan menunjukkan betapa mudahnya mereka diimplementasikan menggunakan struktur bebas, saya akan membantu pembaca menghargai manfaat dari pendekatan ini tanpa takut tersesat dalam detail yang tidak perlu.

Semua kode dalam artikel tersedia online sebagai "stack executable". Jika Anda menjalankannya ( ./regexp.hs ), sesi GHCi akan dimulai dengan semua definisi, sehingga Anda akan memiliki kesempatan untuk bermain-main dengan fungsi dan tipenya.

Artikel ini akan sepenuhnya dimengerti oleh "pemula tingkat lanjut", atau "spesialis pemula" di Haskell. Ini membutuhkan pengetahuan tentang konsep dasar bahasa: pencocokan pola, tipe data aljabar, dan abstraksi seperti monoids, functors, dan notasi.

Bahasa reguler

Ekspresi reguler adalah cara mendefinisikan beberapa bahasa reguler. Secara formal, ungkapan semacam itu dibangun dari tiga elemen dasar:

1. Set kosong adalah elemen yang tidak memetakan apa pun.
2. String kosong adalah elemen netral yang sepele cocok dengan string kosong.
3. Literal adalah simbol yang cocok dengan dirinya sendiri. Banyak satu elemen.

Dan juga dari tiga operasi:

1. Rangkuman: RS , urutan ekspresi. Produk set (Kartesius).
2. Alternatif: R|S , pilihan antara ekspresi. Persatuan set.
3. Baji Bintang: R* , pengulangan suatu ekspresi beberapa kali sembarang (termasuk nol).

Dan hanya itu yang membentuk ekspresi reguler, tidak lebih, tidak kurang. Dari komponen dasar ini, Anda bisa membuat semua operasi lain yang dikenal dengan ekspresi reguler - misalnya, a+ dapat dinyatakan sebagai aa* , dan kategori seperti \w dapat direpresentasikan sebagai alternatif untuk karakter yang sesuai.

Functor alternatif

Ketika Anda melihat struktur ekspresi reguler, bukankah itu tampak akrab? Ini mengingatkan saya pada banyak jenis kelas Alternative . Jika functor milik kelas ini, maka ini berarti bahwa berikut didefinisikan untuknya:

1. Elemen kosong yang terkait dengan kegagalan atau kesalahan perhitungan.
2. pure x - elemen tunggal (dari kelas Applicative ).
3. Operasi <*> , mengatur perhitungan berurutan.
4. Operasi <|> , mengatur perhitungan alternatif.
5. many fungsi adalah operasi perhitungan berulang nol atau lebih banyak kali.

Semua ini sangat mirip dengan konstruksi bahasa biasa, bukan? Mungkin functor alternatif hampir apa yang kita butuhkan, satu-satunya hal yang hilang adalah primitif yang sesuai dengan karakter literal.

Siapa pun yang baru mengenal kelas Alternative dapat menemukan pengantar yang bagus untuk Typeclassopedia . Tetapi dalam kerangka artikel kami, kelas ini hanya mewakili "monoid ganda" dengan dua cara menggabungkan <*> dan <|> , yang, dalam arti tertentu, dapat dibandingkan dengan operasi * dan + untuk angka. Secara umum, untuk menentukan functor alternatif, lima poin di atas dan beberapa undang-undang komutatif dan distributivitas tambahan sudah cukup.

 (<*>) :: Applicative f => f (a -> b) -> fa -> fb 

 (<*) :: Applicative f => fa -> fb -> fa (*>) :: Applicative f => fa -> fb -> fb 

Dengan demikian, kita dapat menganggap ekspresi reguler sebagai functor alternatif, ditambah primitif untuk karakter literal. Tapi, ada cara lain untuk melihatnya, dan itu mengarahkan kita langsung ke struktur bebas. Alih-alih "functor alternatif dengan literal", kita dapat mengubah literal menjadi turunan dari kelas Alternative .

Kebebasan

Mari kita menulis seperti itu. Jenis literal primitif:

 data Prim a = Prim Char a deriving Functor 

Perhatikan bahwa karena kami bekerja dengan functors (aplikatif, alternatif), maka dengan semua ekspresi reguler kami, "hasil" tertentu akan dikaitkan. Ini karena ketika mendefinisikan instance untuk kelas Functor , Applicative dan Alternative , kita harus memiliki tipe parameter.

Di satu sisi, Anda bisa mengabaikan jenis ini, tetapi di sisi lain, Anda harus menggunakan nilai ini sebagai hasil dari pencocokan dengan ekspresi reguler, seperti yang dilakukan dalam aplikasi industri yang bekerja dengan ekspresi reguler.

Dalam kasus kami, Prim 'a' 1 :: Prim Int akan mewakili primitif yang memetakan ke karakter 'a' dan segera ditafsirkan, menghasilkan unit.

Nah, sekarang ... mari kita beri primitif kita struktur matematika yang diinginkan menggunakan functor alternatif gratis dari perpustakaan free :

 import Control.Alternative.Free type RegExp = Alt Prim 

Itu saja! Ini adalah tipe lengkap kami untuk ekspresi reguler! Setelah mendeklarasikan tipe Alt sebagai instance dari kelas Functor , kami mendapatkan semua operasi dari kelas Applicative dan Alternative , karena dalam hal ini ada contoh Applicative (Alt f) dan Alternative (Alt f) . Sekarang kita memiliki:

• Set sepele kosong - empty dari kelas Alternative
• String kosong - pure dari kelas Applicative
• Karakter Literal - Basic Prim
• Concatenation - <*> dari kelas Applicative
• Alternatif - <|> dari kelas Alternative
• Kleene Star - many dari kelas Alternative

Dan semua ini kita dapatkan sepenuhnya "gratis", yaitu, "gratis"!

Pada dasarnya, struktur bebas secara otomatis memberikan kita hanya abstraksi untuk tipe dasar dan tidak lebih. Tapi ekspresi reguler, dengan sendirinya, juga hanya mewakili struktur: elemen dasar dan serangkaian operasi, tidak lebih dan tidak kurang, sehingga functor alternatif gratis memberi kita apa yang kita butuhkan. Tidak lebih, tetapi tidak kurang.

Setelah menambahkan beberapa fungsi pembungkus yang nyaman ... kerjakan jenisnya selesai!

 -- | charAs:   ,    charAs :: Char -> a -> RegExp a charAs cx = liftAlt (Prim cx) -- liftAlt :: fa -> Alt fa   --   Prim   RegExp -- | char:         char :: Char -> RegExp Char char c = charAs cc -- | string:         string :: String -> RegExp String string = traverse char -- , ? 

Contohnya

Baiklah, mari kita coba? Mari kita susun ekspresi (a|b)(cd)*e , yang mengembalikan, jika cocok, tipe unit () :

 testRegExp_ :: RegExp () testRegExp_ = void $ (char 'a' <|> char 'b') *> many (string "cd") *> char 'e' 

Fungsi void :: Functor f => fa -> f () dari paket Data.Functor membuang hasilnya, kami menggunakannya, karena kami hanya tertarik pada keberhasilan perbandingan. Tetapi operator <|> , *> dan many digunakan oleh kami persis seperti yang diasumsikan ketika menggabungkan atau memilih salah satu opsi.

Berikut ini contoh menarik yang lebih rumit, mari kita tentukan persamaan reguler yang sama, tetapi sekarang, sebagai hasil pencocokan, kami menghitung jumlah pengulangan dari cd substring.

 testRegExp :: RegExp Int testRegExp = (char 'a' <|> char 'b') *> (length <$> many (string "cd")) <* char 'e' 

Ada kehalusan dalam operasi operator *> dan <* : panah menunjukkan hasil yang harus disimpan. Dan karena many (string "cd") :: RegExp [String] mengembalikan daftar elemen berulang, kita dapat, tetap di dalam functor, menghitung panjang daftar ini dengan mendapatkan jumlah repetisi.

Selain itu, -XApplicativeDo kompiler GHC -XApplicativeDo memungkinkan -XApplicativeDo untuk menulis ekspresi menggunakan do-notation, yang mungkin lebih mudah dimengerti:

 testRegExpDo :: RegExp Int testRegExpDo = do char 'a' <|> char 'b' cds <- many (string "cd") char 'e' pure (length cds) 

Ini semua agak mirip dengan bagaimana kita "menangkap" hasil parsing string menggunakan ekspresi reguler, mendapatkan akses ke sana. Berikut ini adalah contoh di Ruby:

 irb> /(a|b)((cd)*)e/.match("acdcdcdcde")[2] => "cdcdcdcd" 

satu-satunya perbedaan adalah bahwa kami menambahkan beberapa post-processing untuk menghitung jumlah pengulangan.

Berikut ini adalah reguler reguler lain yang cocok dengan angka dari 0 hingga 9 dan mengembalikan nomor:

 digit :: RegExp Int digit = asum [ charAs (intToDigit i) i | i <- [0..9] ] 

Di sini, fungsi asum dari paket Control.Applicative.Alternative mewakili pilihan dari daftar item asum [x,y,z] = x <|> y <|> z , dan fungsi intToDigit didefinisikan dalam paket Data.Char . Dan, sekali lagi, kita dapat membuat hal-hal yang cukup elegan, misalnya, ekspresi \[\d\] , sesuai dengan angka dalam tanda kurung:

 bracketDigit :: RegExp Int bracketDigit = char '[' *> digit <* char ']' 

Parsing

Ya, ya, yang kami lakukan hanyalah mendeskripsikan tipe data untuk literal dengan penggabungan, seleksi, dan pengulangan. Hebat! Tapi yang benar-benar kita butuhkan adalah mencocokkan string dengan ekspresi reguler, bukan? Bagaimana functor alternatif gratis dapat membantu kami dengan ini? Bahkan, itu akan banyak membantu. Mari kita lihat dua cara untuk melakukan ini!

Bongkar functor alternatif

Apa itu kebebasan?

Cara kanonik menggunakan struktur bebas adalah dengan melipatnya menjadi struktur beton menggunakan aljabar yang sesuai. Misalnya, transformasi foldMap mengubah monoid gratis (daftar) menjadi nilai instance instance dari kelas Monoid :

 foldMap :: Monoid m => (a -> m) -> ([a] -> m) 

Fungsi foldMap mengubah transformasi a -> m menjadi transformasi [a] -> m (atau, FreeMonoid a -> m ), dengan monoid m tertentu. Gagasan umum adalah bahwa penggunaan struktur bebas memungkinkan Anda untuk menunda penggunaan spesifik "untuk nanti", memisahkan waktu pembuatan dan waktu menggunakan struktur.

Misalnya, kita dapat membuat monoid gratis dari angka:

 -- |  "" `Int`     `Int`,  `liftAlt`. liftFM :: Int -> [Int] liftFM x = [x] myMon :: [Int] myMon = liftFM 1 <> liftFM 2 <> liftFM 3 <> liftFM 4 

Dan sekarang kita dapat memutuskan bagaimana kita ingin menafsirkan operasi <> :
Mungkin tambahan ini?

 ghci> foldMap Sum myMon Sum 10 -- 1 + 2 + 3 + 4 

Atau multiplikasi?

 ghci> foldMap Product myMon Product 24 -- 1 * 2 * 3 * 4 

Atau mungkin perhitungan angka maksimal?

 ghci> foldMap Max myMon Max 4 -- 1 `max` 2 `max` 3 `max` 4 

Idenya adalah untuk menunda pemilihan monoid tertentu dengan terlebih dahulu membangun koleksi gratis angka 1, 2, 3, dan 4. Monoid bebas atas angka menentukan struktur di atas mereka yang Anda butuhkan, tidak lebih, tidak kurang. Untuk menggunakan foldMap kami menentukan "cara menerima tipe dasar" dengan meneruskan operator <> ke monoid tertentu.

Interpretasi dalam Functor State

Dalam praktiknya, memperoleh hasil dari struktur bebas terdiri dari menemukan (atau menciptakan) fungsi yang sesuai yang akan memberi kita perilaku yang diinginkan. Dalam kasus kami, kami beruntung bahwa ada implementasi spesifik dari kelas Alternative yang bekerja persis seperti yang kita butuhkan: StateT String Maybe .

Produk <*> untuk functor ini terdiri dalam mengatur urutan perubahan status. Dalam kasus kami, di bawah status, kami akan mempertimbangkan sisa string yang diuraikan, sehingga pengurutan berurutan adalah yang paling cocok untuk operasi <*> .

Dan jumlahnya <|> bekerja seperti mundur, pencarian dengan kembali ke alternatif jika terjadi kegagalan. Ia mempertahankan status sejak eksekusi parsing terakhir yang berhasil dan kembali ke sana jika alternatifnya tidak berhasil dipilih. Ini persis perilaku yang kita harapkan dari ungkapan R|S

Akhirnya, transformasi alami untuk functor alternatif gratis disebut runAlt :

 runAlt :: Alternative f => (forall b. pb -> fb) -> Alt pa -> fa 

Atau, untuk tipe RegExp:

 runAlt :: Alternative f => (forall b. Prim b -> fb) -> RegExp a -> fa 

Jika Anda tidak terbiasa dengan jenis RankN (dengan forall b. Konstruksi), Anda dapat melihat pengantar yang baik di sini . Intinya di sini adalah bahwa Anda perlu menyediakan fungsi runAlt yang bekerja dengan Prim b untuk semua b , dan bukan jenis apa pun, seperti Int dan Bool , misalnya. Yaitu, seperti pada foldMap kita hanya perlu menentukan apa yang harus dilakukan dengan tipe dasar. Dalam kasus kami, jawab pertanyaan: "Apa yang perlu dilakukan dengan tipe Prim ?"

 processPrim :: Prim a -> StateT String Maybe a processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

Ini adalah interpretasi Prim sebagai tindakan dalam konteks StateT String Maybe , di mana state adalah string yang StateT String Maybe . Biarkan saya mengingatkan Anda bahwa Prim berisi informasi tentang karakter yang cocok c dan interpretasinya dalam bentuk beberapa nilai x . Pemrosesan Prim terdiri dari langkah-langkah berikut:

• Menggunakan get status (belum diuraikan bagian dari string) dan segera mencetak karakter pertama dan sisanya. Jika garis kosong, sebuah alternatif akan kembali. ( Transformator StateT bertindak di dalam functor Mungkin, dan jika tidak mungkin untuk mencocokkan pola di sisi kanan <- operator <- di dalam blok do, perhitungan akan berakhir dengan hasil empty , yaitu, Nothing . Approx. Trans. ).
• Kami menggunakan ekspresi penjaga untuk mencocokkan karakter saat ini dengan karakter yang diberikan. Dalam hal kegagalan, empty dikembalikan, dan kami beralih ke opsi alternatif.
• Kami mengubah status dengan mengganti string yang diurai dengan "ekor", karena pada saat ini karakter saat ini sudah dapat dianggap berhasil diurai.
• Kami mengembalikan apa yang harus dikembalikan oleh primitif Prim .

Anda sudah dapat menggunakan fungsi ini untuk memetakan RegEx ke awalan string. Untuk melakukan ini, Anda harus memulai perhitungan menggunakan runAlt dan runStateT , meneruskan string yang diurai ke fungsi terakhir sebagai argumen:

 matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) 

Itu saja! Mari kita lihat bagaimana solusi pertama kami bekerja:

 ghci> matchPrefix testRegexp_ "acdcdcde" Just () ghci> matchPrefix testRegexp_ "acdcdcdx" Nothing ghci> matchPrefix testRegexp "acdcdcde" Just 3 ghci> matchPrefix testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchPrefix digit "9" Just 9 ghci> matchPrefix bracketDigit "[2]" Just 2 ghci> matchPrefix (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchPrefix (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

Tunggu, apa itu tadi?

Tampaknya semuanya terjadi sedikit lebih cepat dari yang Anda harapkan. Semenit yang lalu kami menulis primitif kami, dan kemudian lagi! dan pengurai bekerja siap. Di sini, pada kenyataannya, semua kode kunci, beberapa baris di Haskell:

 import Control.Monad.Trans.State (evalStateT, put, get) import Control.Alternative.Free (runAlt, Alt) import Control.Applicative import Control.Monad (guard) data Prim a = Prim Char a deriving Functor type RegExp = Alt Prim matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) where processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

Dan apakah kita memiliki pengurai ekspresi reguler yang berfungsi penuh? Apa yang terjadi

Ingatlah bahwa pada tingkat abstraksi yang tinggi, Alt Prim sudah mengandung pure , empty , Prim , <*> , <|> , dan many di strukturnya (ada satu kehalusan yang tidak menyenangkan dengan operator ini, tetapi lebih pada nanti). Apa runAlt adalah menggunakan perilaku functor alternatif tertentu (dalam kasus kami, StateT String Maybe ) untuk mengontrol perilaku pure , empty , <*> , <|> , dan many operator. Namun, StateT tidak memiliki operator StateT mirip dengan Prim , dan untuk ini kami perlu menulis processPrim .

Jadi, untuk tipe Prim , fungsi runAlt menggunakan runAlt , dan untuk pure , empty , <*> , <|> , dan many , contoh yang sesuai dari kelas Alternative digunakan. Dengan demikian, 83% dari pekerjaan dilakukan untuk kita oleh functor StateT , dan sisanya 17% dilakukan oleh StateT . Sebenarnya, ini agak mengecewakan. Orang mungkin bertanya: mengapa harus mulai dengan pembungkus Alt ? Mengapa tidak segera mendefinisikan tipe RegExp = StateT String Maybe dan char :: Char -> StateT String Maybe Char primitive yang sesuai char :: Char -> StateT String Maybe Char ? Jika semuanya dilakukan di func StateT, maka mengapa repot-repot dengan Alt - functor alternatif gratis?

Keuntungan utama Alt daripada StateT adalah StateT adalah ... alat yang sangat kuat. Tapi nyatanya, dia kuat, sampai-sampai absurd. Dengan itu, Anda dapat membayangkan sejumlah besar perhitungan dan struktur yang paling beragam, dan, tidak menyenangkan, mudah untuk membayangkan sesuatu yang bukan ekspresi reguler. Katakanlah sesuatu yang mendasar seperti put "hello" :: StateT String Maybe () tidak cocok dengan ekspresi reguler yang valid, tetapi jenisnya sama dengan RegExp () . Jadi, sementara kita mengatakan bahwa Alt Prim cocok dengan ekspresi reguler, tidak lebih, tetapi tidak kurang, kita tidak bisa mengatakan hal yang sama dengan StateT String Maybe . Tipe Alt Prim adalah representasi sempurna dari ekspresi reguler. Segala sesuatu yang dapat diekspresikan dengan bantuannya adalah ekspresi reguler, tetapi sesuatu yang bukan ekspresi seperti itu tidak dapat diekspresikan dengan bantuannya. Di sini, bagaimanapun, ada juga beberapa kehalusan yang tidak menyenangkan terkait dengan kemalasan Haskell, lebih lanjut tentang ini nanti.

Di sini kita dapat mempertimbangkan StateT hanya sebagai konteks yang digunakan untuk itu
interpretasi ekspresi reguler - sebagai pengurai. Tetapi Anda dapat membayangkan cara lain untuk menggunakan RegExp . Sebagai contoh, kita mungkin memerlukan representasi tekstualnya, yang tidak StateT oleh StateT .

Kita tidak bisa mengatakan bahwa StateT String Maybe adalah ekspresi reguler, hanya saja functor ini dapat mewakili pengurai berdasarkan tata bahasa reguler. Tetapi tentang Alt Prim kita dapat mengatakan dengan pasti bahwa ini adalah ekspresi reguler ( seperti yang dikatakan para ahli matematika, mereka sama dengan isomorfisme, kira-kira Trans. ).

Penggunaan langsung struktur bebas

Semua ini, tentu saja, sangat baik, tetapi bagaimana jika kita tidak ingin mengalihkan 83% pekerjaan ke kode untuk jenis yang ditulis oleh seseorang untuk kita. Apakah mungkin untuk menggunakan struktur Alt gratis secara langsung untuk menulis parser? Pertanyaan ini mirip dengan ini: bagaimana menulis fungsi yang memproses daftar (dengan mencocokkan konstruktor (:) dan [] ) alih-alih hanya menggunakan foldMap ? Bagaimana cara langsung beroperasi dengan struktur ini alih-alih mendelegasikan pekerjaan ke monoid tertentu?

Senang Anda bertanya! Mari kita lihat definisi functor alternatif gratis:

 newtype Alt fa = Alt { alternatives :: [AltF fa] } data AltF fa = forall r. Ap (fr) (Alt f (r -> a)) | Pure a 

Ini adalah tipe yang tidak biasa yang didefinisikan melalui rekursi timbal balik, sehingga dapat terlihat sangat membingungkan. Salah satu cara untuk memahaminya adalah dengan membayangkan bahwa Alt xs berisi rantai alternatif yang dibentuk menggunakan operator <|> . AltF , f , <*> ( ).

AltF fa [fr] , r . Ap (:) , fr , Pure — [] . forall r. -XExistentialQuantification .

, Alt f , . , ( ) <*> <|> , , [a] <> .

, RegExp a -> String -> Maybe a , , . : .

, Alt . , , .

 matchAlts :: RegExp a -> String -> Maybe a matchAlts (Alt res) xs = asum [ matchChain re xs | re <- res ] 

asum :: [Maybe a] -> Maybe a , Just . ( , Maybe a Alternative — Nothing , <|> . . . )

. AltF , Ap Pure :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = _ matchChain (Pure x) cs = _ 

" ": GHC "", , , . ( Haskell "" (holes) , _ , . . . ) :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = case cs of [] -> Nothing d:ds | c == d -> matchAlts (($ x) <$> next) ds | otherwise -> Nothing matchChain (Pure x) _ = Just x 

Ap ( (:) ), , - . , . Prim r , , next :: RegExp (r -> a) . , next . , "" , Nothing . , Pure x ( [] ), , , .

, , . , , " " Ap , Pure , AltF .., .

:

 ghci> matchAlts testRegexp_ "acdcdcde" Just () ghci> matchAlts testRegexp_ "acdcdcdx" Nothing ghci> matchAlts testRegexp "acdcdcde" Just 3 ghci> matchAlts testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchAlts digit "9" Just 9 ghci> matchAlts bracketDigit "[2]" Just 2 ghci> matchAlts (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchAlts (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

?

foldMap . , , foldMap, , , , ! , — , — (:) [] .

, , : , , , (:) , [] . , . , [1,2,3] <> [4] , [1] <> [2,3] <> [4] . , , .

. , :

 data RegExp a = Empty | Pure a | Prim Char a | forall r. Seq (RegExp r) (RegExp (r -> a)) | Union (RegExp a) (RegExp a) | Many (RegExp a) 

RegExp , . . , RegExp :

 -- | a|(b|c) abc1 :: RegExp Int abc1 = Prim 'a' 1 `Union` (Prim 'b' 2 `Union` Prim 'c' 3) -- | (a|b)|c abc2 :: RegExp Int abc2 = (Prim 'a' 1 `Union` Prim 'b' 2) `Union` Prim 'c' 3 

, .

Alt Prim , , , . , matchAlts , . (a|b)|c a|(b|c) . Alt . , , .

, , (a|b)|c , (a|b)|c , , , RegExp . Alt , .

, , Alt , Alt Prim . , Alt Prim a|a a . , Alt f f . , : . , , , .

, . , , . RegExp , , — .

, Haskell. , - [a] . ( , - , "" $$$\bot$, - "" . . . )

: a|aa|aaa|aaaa|aaaaa|aaaaaa|... , ( , , , . . . ). , Haskell . , Alt many . , a* a|aa|aaa|aaaa|aaaaa|aaaaaa|... , . - many (char 'a') , . Haskell Alt , .

, , , , (), . , many .

, ! "" Alt , Control.Alternative.Free.Final , many (, , ).

, , runAlt . , Alternative , many ( RE regex-applicative ) . , Haskell , , , many .

, . ( ), ( , , . . ). matchPrefix , , , . , , , , . , GHC .

, , tails ( ) mapMaybe ( ). , , listToMaybe .

 matches :: RegExp a -> String -> [a] matches re = mapMaybe (matchPrefix re) . tails firstMatch :: RegExp a -> String -> Maybe a firstMatch re = listToMaybe . matches re 

, , matchPrefix Nothing , listToMaybe , Nothing ( , . . . ).

, . , , — , . , . , , , .

Alt Prim , : , , , .

? . :

 data Prim a = Only Char a --    | Letter a --     | Digit (Int -> a) --    , | Wildcard (Char -> a) --    , | Satisfy (Char -> Maybe a) --    , --   

, . .

, , . runAlt Alt .

(). , , , , . | . ( , . . . ). , - . , MonadPlus - , , . , .

, , . , !