أوجه انتباهكم إلى ترجمة لمقال جديد رائع كتبه جاستن لو. في مدونته في Code ، يتحدث هذا المؤلف بلغة سهلة إلى حد ما عن الجوهر الرياضي للحلول الوظيفية الجميلة والأنيقة للمشاكل العملية. تتناول هذه المقالة بالتفصيل مثالًا على كيفية نقل البنية الرياضية التي تشكلها البيانات في مجال موضوع إلى نظام من أنواع البرامج على الفور ، كما كتب جيرالد وساسمان "تلقائيًا" ، إلى حل عملي.

الكود الظاهر في الصورة هو تطبيق كامل ومكتمل بذاته وموسع لمحلل التعبير العادي ، مكتوب من الصفر. الطبقة العليا ، نوع السحر الحقيقي!

ننفذ اليوم تعبيرات ومحللات تطبيقية منتظمة (بروح مكتبة تطبيق ريكس) باستخدام هياكل جبرية مجانية! الهياكل الحرة هي إحدى أدواتي المفضلة في Haskell ، وقد كتبت في وقت سابق عن مجموعات مجانية ، وأشكال مختلفة حول موضوع monads المجانية ومقدم الطلب "المجاني" على monoids .

إن التعبيرات المنتظمة (والمحللات بالنسبة لهم) موجودة في كل مكان في البرمجة وعلوم الكمبيوتر ، لذلك آمل أنه من خلال إظهار مدى بساطة استخدامهم للهياكل المجانية ، سوف أساعد القارئ على تقدير مزايا هذا النهج دون خوف من الضياع في التفاصيل غير الضرورية.

جميع التعليمات البرمجية في المقالة متاحة على الإنترنت باعتبارها "مكدس قابل للتنفيذ". إذا قمت بتشغيله ( ./regexp.hs ) ، فستبدأ جلسة GHCi بجميع التعاريف ، وبالتالي ستتاح لك الفرصة للتجول بالوظائف وأنواعها.

ستكون هذه المقالة مفهومة تمامًا لـ "المبتدئين المتقدمين" أو "المبتدئين المتخصصين" في هاسكل. يتطلب معرفة المفاهيم الأساسية للغة: مطابقة الأنماط ، وأنواع البيانات الجبرية ، والتجريدات مثل المونويدات ، والمولدات ، والرموز الداعمة.

اللغات العادية

التعبير العادي هو وسيلة لتعريف بعض اللغات العادية. بشكل رسمي ، يتم بناء مثل هذا التعبير من ثلاثة عناصر أساسية:

1. المجموعة الفارغة هي عنصر لا يعين أي شيء.
2. السلسلة الفارغة عبارة عن عنصر محايد يتطابق تمامًا مع سلسلة فارغة.
3. الحرفي هو رمز يطابق نفسه. الكثير من عنصر واحد.

وأيضا من ثلاث عمليات:

1. سلسلة: RS ، تسلسل التعبيرات. نتاج مجموعات (الديكارتية).
2. البديل: R|S ، الاختيار بين التعبيرات. اتحاد مجموعات.
3. Wedge Star: R* ، تكرار التعبير لعدد مرات تعسفي (بما في ذلك الصفر).

وهذا كل ما يشكل تعبيرات منتظمة ، لا أكثر ولا أقل. من هذه المكونات الأساسية ، يمكنك إنشاء جميع العمليات المعروفة الأخرى على تعبيرات منتظمة - على سبيل المثال ، يمكن التعبير عن a+ كـ aa* ، ويمكن تمثيل فئات مثل \w كبديل للحروف المناسبة.

functor البديل

عندما تنظر إلى بنية التعبيرات المنتظمة ، ألا يبدو ذلك مألوفًا؟ هذا يذكرني بالكثير من فئة النوع Alternative . إذا كان functor ينتمي إلى هذه الفئة ، فهذا يعني أن العناصر التالية محددة لها:

1. عنصر فارغ يتوافق مع خطأ الفشل أو الحساب.
2. pure x - عنصر واحد (من الطبقة Applicative ).
3. العملية <*> ، وتنظيم العمليات الحسابية المتسلسلة.
4. العملية <|> ، وتنظيم حسابات بديلة.
5. الوظيفة المتعددة هي عملية تكرار الحسابات صفر أو أكثر من المرات.

كل هذا مشابه جدا لبناء لغة عادية ، أليس كذلك؟ ربما يكون الداعم البديل هو ما نحتاجه تقريبًا ، الشيء الوحيد المفقود هو البدائية المقابلة للشخصية الحرفية.

يمكن لأي شخص جديد في الفئة Alternative العثور على مقدمة جيدة لـ Typeclassopedia . ولكن في إطار مقالتنا ، تمثل هذه الفئة ببساطة "monoid monoid" بطريقتين للجمع بين <*> و <|> ، والتي يمكن ، بالمقارنة ، مع العمليات * و + للأرقام. بشكل عام ، لتحديد جهة بديلة ، تعتبر النقاط الخمس المذكورة أعلاه وبعض القوانين الإضافية المتعلقة بتبديل البيانات والتوزيع كافية.

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

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

وبالتالي ، يمكننا النظر في التعبيرات العادية كوظيفة بديلة ، بالإضافة إلى بدائية للشخصية الحرفية. ولكن ، هناك طريقة أخرى للنظر إليها ، وهي تقودنا مباشرة إلى الهياكل الحرة. بدلاً من "المُشغل البديل ذي القيم الحرفية" ، يمكننا تحويل الحرفي إلى مثيل للفئة Alternative .

حرية

دعنا نكتب هكذا. اكتب الحرفي البدائي:

 data Prim a = Prim Char a deriving Functor 

لاحظ أنه نظرًا لأننا نعمل مع عوامل التوجيه (تطبيقية ، بديلة) ، فمع كل تعبيراتنا المعتادة ، سيتم ربط "نتيجة" معينة. هذا لأنه عند تحديد مثيل Functor و Applicative و Alternative ، يجب أن يكون لدينا نوع معلمة.

من ناحية ، يمكنك تجاهل هذا النوع ، ولكن من ناحية أخرى ، يجب عليك استخدام هذه القيمة كنتيجة للتطابق مع تعبير عادي ، كما هو الحال في التطبيقات الصناعية التي تعمل مع التعبيرات العادية.

في حالتنا ، سيمثل Prim 'a' 1 :: Prim Int بدائية تقوم بالتعيين على الحرف 'a' ويتم تفسيرها على الفور ، مما ينتج عنه وحدة.

حسنًا ، الآن ... دعنا نعطي بدائية بنية رياضية مرغوبة باستخدام عامل التوجيه البديل المجاني من المكتبة free :

 import Control.Alternative.Free type RegExp = Alt Prim 

هذا كل شئ! هذا هو نوعنا الكامل للتعبيرات العادية! بعد الإعلان عن نوع Alt Functor لفئة Functor ، حصلنا على جميع العمليات من فئتي Applicative Alternative ، حيث توجد في هذه الحالة مثيلات Applicative (Alt f) Alternative (Alt f) . الآن لدينا:

• مجموعة فارغة تافهة - empty من فئة Alternative
• سلسلة فارغة - pure من الطبقة Applicative
• الحرف الحرفي - Prim الأساسي الأساسي
• سلسلة - <*> من الطبقة Applicative
• البديل - <|> من الفئة Alternative
• كلاين ستار - many من الطبقة Alternative

وكل هذا حصلنا عليه "مجاني" تمامًا ، أي "مجانًا"!

في الأساس ، توفر لنا البنية المجانية تلقائيًا مجرد تجريد للنوع الأساسي ولا شيء أكثر من ذلك. لكن التعبيرات المنتظمة ، بحد ذاتها ، لا تمثل سوى بنية: العناصر الأساسية ومجموعة من العمليات ، لا أكثر ولا أقل ، وبالتالي فإن المشغل البديل المجاني يوفر لنا ما نحتاجه بالضبط. لا أكثر ولا أقل.

بعد إضافة بعض وظائف المجمع مريحة ... اكتمال العمل على النوع!

 -- | 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 -- , ? 

أمثلة

حسنا ، دعنا نحاول؟ لنقم ببناء التعبير (a|b)(cd)*e ، والذي يُرجع ، في حالة وجود تطابق ناجح ، نوع الوحدة () :

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

الدالة void :: Functor f => fa -> f () من حزمة Data.Functor تتجاهل النتيجة ، نحن نستخدمها ، لأننا مهتمون فقط بنجاح المقارنة. لكن عوامل التشغيل <|> ، *> many مستخدمون من قبلنا تمامًا كما هو مفترض عند وصل أو اختيار أحد الخيارات.

إليك مثال مثير للاهتمام أكثر تعقيدًا ، دعنا نحدد نفس التعبير المنتظم ، لكن الآن ، ونتيجة للمطابقة ، نحسب عدد التكرارات للقرص cd الفرعي.

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

هناك دقة في تشغيل معاملات *> و <* : تشير الأسهم إلى النتيجة التي يجب حفظها. ونظرًا لأن many (string "cd") :: RegExp [String] تُرجع قائمة بالعناصر المكررة ، فيمكننا ، في داخل المُشغل ، حساب طول هذه القائمة عن طريق الحصول على عدد التكرارات.

علاوة على ذلك ، فإن -XApplicativeDo التحويل البرمجي GHC -XApplicativeDo يسمح -XApplicativeDo بكتابة تعبيرنا باستخدام طريقة التدوين ، والتي ربما يكون من الأسهل فهمها:

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

هذا يشبه إلى حد ما كيف "نلتقط" نتيجة تحليل سلسلة باستخدام تعبير منتظم ، والوصول إليها. هنا مثال في روبي:

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

الفرق الوحيد هو أننا أضفنا بعض عمليات ما بعد المعالجة لحساب عدد التكرار.

في ما يلي عدد قياسي مناسب \d يطابق رقمًا من 0 إلى 9 ويعيد رقمًا:

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

هنا ، asum الدالة asum من الحزمة Control.Applicative.Alternative asum [x,y,z] = x <|> y <|> z عناصر القائمة asum [x,y,z] = x <|> y <|> z ، intToDigit تعريف الدالة intToDigit في حزمة Data.Char . ومرة أخرى ، يمكننا إنشاء أشياء أنيقة تمامًا ، على سبيل المثال ، التعبير \[\d\] ، المتوافق مع الرقم الوارد بين قوسين معقوفين:

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

إعراب

حسنًا ، حسنًا ، كل ما فعلناه هو وصف نوع البيانات لحرفي مع تسلسل ، اختيار ، وتكرار. ! ممتاز ولكن ما نحتاج إليه حقًا هو مطابقة سلسلة مع تعبير منتظم ، أليس كذلك؟ كيف يمكن لموظف بديل مجاني مساعدتنا في هذا؟ في الواقع ، سوف يساعد كثيرا. لنلقِ نظرة على طريقتين للقيام بذلك!

تفريغ functor البديل

ما هي الحرية؟

تتمثل الطريقة الأساسية لاستخدام الهيكل الحر في طيها في هيكل خرساني باستخدام الجبر المناسب. على سبيل المثال ، يحول تحويل foldMap (قائمة) حرة إلى قيمة أي مثيل لفئة Monoid :

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

تحول وظيفة foldMap التحويل a -> m إلى التحويل [a] -> m (أو FreeMonoid a -> m ) ، مع FreeMonoid a -> m محدد. الفكرة العامة هي أن استخدام الهيكل الحر يسمح لك بتأجيل استخدامه المحدد "لاحقًا" ، ويفصل بين وقت الإنشاء ووقت استخدام الهيكل.

على سبيل المثال ، يمكننا بناء monoid مجاني من الأرقام:

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

والآن يمكننا أن نقرر كيف نريد تفسير العملية <> :
ربما هذه الإضافة؟

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

أو الضرب؟

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

أو ربما حساب الحد الأقصى لعدد؟

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

تتمثل الفكرة في تأجيل اختيار عنصر أحادي معين عن طريق إنشاء مجموعة خالية من الأرقام 1 و 2 و 3 و 4 أولاً. يحدد العنصر الأحادي المجاني على الأرقام الهيكل الذي تحتاجه ، لا أكثر ولا أقل. لاستخدام foldMap نحدد "كيفية إدراك النوع الأساسي" عن طريق تمرير عامل التشغيل <> إلى monoid معين.

التفسير في State Functor

في الممارسة العملية ، يتمثل الحصول على نتيجة من بنية حرة في إيجاد (أو إنشاء) عامل توجيه مناسب يوفر لنا السلوك المطلوب. في حالتنا ، نحن محظوظون لوجود تطبيق محدد للفئة Alternative يعمل تمامًا كما نحتاج إليه: StateT String Maybe .

يتكون المنتج <*> لهذا المشغل من تنظيم سلسلة من تغييرات الحالة. في حالتنا ، ضمن الحالة ، سننظر في الجزء المتبقي من السلسلة التي تم تحليلها ، بحيث يكون التحليل المتسلسل هو أفضل تطابق للعملية <*> .

والمبلغ <|> يعمل مثل التراجع ، البحث مع العودة إلى البديل في حالة الفشل. يحتفظ بالحالة منذ آخر تنفيذ ناجح للتحليل ويعود إليه إذا تم اختيار البديل بنجاح. هذا هو بالضبط السلوك الذي نتوقعه من التعبير R|S

أخيرًا ، يُطلق على التحول الطبيعي runAlt بديل مجاني runAlt :

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

أو للنوع RegExp:

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

إذا لم تكن معتادًا على أنواع RankN (مع forall b. Construction) ، يمكنك رؤية مقدمة جيدة هنا . النقطة المهمة هنا هي أنك تحتاج إلى توفير وظيفة runAlt التي تعمل مع Prim b على الإطلاق لأي b ، وليس من أي نوع معين ، مثل Int و Bool ، على سبيل المثال. وهذا هو ، كما هو الحال مع foldMap نحتاج فقط إلى تحديد ما يجب القيام به مع النوع الأساسي. في حالتنا ، أجب عن السؤال التالي: "ما الذي يجب القيام به مع النوع Prim ؟"

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

هذا هو تفسير Prim كعمل في سياق StateT String Maybe ، حيث الحالة عبارة عن سلسلة StateT String Maybe . اسمح لي أن أذكرك بأن Prim تحتوي على معلومات حول الحرف المطابق c وتفسيره في شكل قيمة x . تتكون المعالجة Prim من الخطوات التالية:

• باستخدام get الحالة (لم يتم تحليل جزء منها بعد من السلسلة) ونطبع على الفور طابعها الأول والباقي. إذا كان الخط فارغًا ، فسيعود بديل. ( يعمل محوّل StateT داخل المُركِز ربما ، وإذا كان من المستحيل مطابقة النمط على الجانب الأيمن من <- عامل التشغيل <- داخل كتلة المهام ، ستنتهي الحسابات بالنتيجة empty ، أي ، Nothing . تقريبًا. Trans. ).
• نستخدم تعبير الحماية لمطابقة الحرف الحالي مع الحرف المعطى. في حالة الفشل ، empty إرجاع empty ، وننتقل إلى الخيار البديل.
• نقوم بتغيير الحالة عن طريق استبدال السلسلة التي تم تحليلها بـ "ذيلها" ، حيث أنه في هذه اللحظة يمكن اعتبار الشخصية الحالية قد تم تحليلها بنجاح.
• نعود ما يجب أن يعود البدائي البدائي.

يمكنك بالفعل استخدام هذه الوظيفة لتعيين RegEx لبادئة السلسلة. للقيام بذلك ، تحتاج إلى بدء العمليات الحسابية باستخدام runAlt و runStateT ، لتمرير السلسلة التي تم تحليلها إلى آخر وظيفة كوسيطة:

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

هذا كل شئ! دعونا نرى كيف يعمل الحل الأول لدينا:

 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 

الانتظار ، ماذا كان ذلك؟

يبدو أن كل شيء حدث أسرع قليلاً مما كنت تتوقع. منذ دقيقة كتبنا بدائية لدينا ، ثم مرة أخرى! والمحلل العامل جاهز. هنا ، في الواقع ، كل رمز المفتاح ، بضعة أسطر في هاسكل:

 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 

وهل لدينا محلل تعبير عادي كامل الوظائف؟ ماذا حدث

تذكر أنه على مستوى عالٍ من التجريد ، يحتوي Alt Prim بالفعل على pure ، empty ، Prim ، <*> ، <|> ، many في هيكلها (هناك دقة واحدة غير سارة مع هذا المشغل ، ولكن المزيد حول ذلك لاحقًا). ما تقوم به عملية runAlt هو استخدام سلوك runAlt بديل معين (في حالتنا ، StateT String Maybe ) للتحكم في سلوك StateT String Maybe <*> ، <*> ، <|> ، many العوامل. ومع ذلك ، لا يوجد لدى StateT مشغل مضمن مشابه لبرنامج Prim ، ولهذا نحتاج إلى كتابة processPrim .

لذلك ، بالنسبة إلى النوع Prim ، تستخدم الدالة runAlt ، runAlt ، empty ، <*> ، <|> ، many ، يتم استخدام مثيل مناسب للفئة Alternative . وبالتالي ، يتم تنفيذ 83٪ من العمل من قِبل جهة StateT ، بينما يتم تنفيذ الـ 17٪ المتبقية بواسطة StateT . في الحقيقة ، هذا أمر مخيب للآمال إلى حد ما. قد يتساءل المرء: لماذا كان حتى من الضروري أن تبدأ مع المجمع Alt ؟ لماذا لا تحدد على الفور نوع RegExp = StateT String Maybe البدائي المناسب char :: Char -> StateT String Maybe Char ؟ إذا تم القيام بكل شيء في StateT functor ، فلماذا تهتم Alt - وهو functor بديل مجاني؟

ميزة Alt الرئيسية على StateT هي أن StateT ... أداة قوية للغاية. ولكن في الواقع ، فهو قوي ، لدرجة العبث. يمكن استخدامه لتمثيل عدد كبير من الحسابات والهياكل الأكثر تنوعًا ، ومن غير المستحسن أن يتخيل شيئًا ما ليس تعبيرًا منتظمًا. لنفترض شيئًا أساسيًا مثل put "hello" :: StateT String Maybe () لا يتطابق مع أي تعبير منتظم صالح ، لكنه من نفس النوع مثل RegExp () . وبالتالي ، بينما نقول أن Alt Prim تطابق تعبيرًا عاديًا ، لا أكثر ، ولكن ليس أقل ، لا يمكننا قول الشيء نفسه مع StateT String Maybe . نوع Alt Prim هو التمثيل المثالي للتعبير المنتظم. كل ما يمكن التعبير عنه بمساعدته هو تعبير منتظم ، لكن لا يمكن التعبير عن أي شيء ليس مثل هذا التعبير بمساعدته. هنا ، ومع ذلك ، هناك أيضا بعض التفاصيل غير السارة المرتبطة الكسل هاسكل ، أكثر على هذا في وقت لاحق.

هنا يمكننا النظر في StateT فقط كسياق يستخدم لأحد
تفسيرات التعبير العادية - كمحلل. ولكن يمكنك تخيل طرق أخرى لاستخدام RegExp . على سبيل المثال ، قد نحتاج إلى تمثيل نصي ، وهو ما لن تسمح به StateT .

لا يمكننا القول أن StateT String Maybe عبارة عن تعبير منتظم ، فقط أن هذا العامل يمكن أن يمثل محللًا يعتمد على قواعد اللغة العادية. ولكن حول Alt Prim يمكننا أن نقول على وجه اليقين أن هذا تعبير منتظم ( كما يقول علماء الرياضيات ، إنهم متساوون في التماثل ، تقريبا Trans. ).

الاستخدام المباشر للهيكل الحر

كل هذا ، بالطبع ، جيد جدًا ، لكن ماذا لو لم نكن نريد تحويل 83٪ من العمل إلى رمز لنوع كتبه شخص ما من أجلنا. هل من الممكن استخدام الهيكل Alt المجاني مباشرة لكتابة المحلل اللغوي؟ يشبه هذا السؤال هذا: كيفية كتابة دالة تقوم بمعالجة القوائم (عن طريق مطابقة foldMap (:) و [] ) بدلاً من استخدام foldMap فقط؟ كيف تعمل مباشرة مع هذا الهيكل بدلا من تفويض العمل ل monoid معين؟

سعيد سألت! دعونا نلقي نظرة على تعريف functor بديل حر:

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

هذا نوع غير عادي يتم تعريفه من خلال التكرار المتبادل ، لذلك يمكن أن يبدو مربكًا للغاية. طريقة واحدة لفهمها هي تخيل أن Alt xs تحتوي على سلسلة من البدائل المشكلة باستخدام <|> العامل. 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 - , , . , .

, , . , !