ပြီးခဲ့တဲ့ နွေရာသီမှာ ကျွန်တော် ပါဝင်ခဲ့ပါတယ်။ Google နွေရာသီ၏ Code - Google မှ ကျောင်းသားများအတွက် ပရိုဂရမ်တစ်ခု။ နှစ်စဉ်နှစ်တိုင်း၊ ပွဲစီစဉ်သူများသည် ထိုကဲ့သို့သော နာမည်ကြီးအဖွဲ့အစည်းများမှ အပါအဝင် Open Source ပရောဂျက်များစွာကို ရွေးချယ်သည်။ Boost.org и အဆိုပါ Linux ကိုဖောင်ဒေးရှင်းမှ. Google သည် ဤပရောဂျက်များကို လုပ်ဆောင်ရန် ကမ္ဘာတစ်ဝှမ်းမှ ကျောင်းသားများကို ဖိတ်ကြားထားသည်။ 

Google Summer of Code 2019 တွင် ပါဝင်သူတစ်ဦးအနေဖြင့် စာကြည့်တိုက်အတွင်း ပရောဂျက်တစ်ခုကို လုပ်ခဲ့ပါသည်။ ရေညှိ အဖွဲ့အစည်းနှင့်အတူ Haskell.orgHaskell ဘာသာစကားကို တီထွင်ထုတ်လုပ်နေသည့် အကျော်ကြားဆုံး လုပ်ဆောင်နိုင်သော ပရိုဂရမ်းမင်းဘာသာစကားများထဲမှ တစ်ခုဖြစ်သည်။ Alga သည် ကိုယ်စားပြုသော စာကြည့်တိုက်တစ်ခုဖြစ်သည်။ လုံခြုံစွာရိုက်ပါ။ Haskell ရှိ ဂရပ်များအတွက် ကိုယ်စားပြုမှု။ ၎င်းကို ဥပမာအားဖြင့်၊ တွင် အသုံးပြုသည်။ semantic — ကုဒ်အပေါ်အခြေခံ၍ ဝေါဟာရသစ်ပင်များ၊ ခေါ်ဆိုမှုနှင့် မှီခိုမှုဂရပ်များကို တည်ဆောက်ကာ ၎င်းတို့ကို နှိုင်းယှဉ်နိုင်သည့် Github စာကြည့်တိုက်။ ကျွန်ုပ်၏ပရောဂျက်သည် ထိုကိုယ်စားပြုမှုအတွက် နှစ်ပိုင်းဂရပ်များနှင့် အယ်လဂိုရီသမ်များအတွက် အမျိုးအစား-ဘေးကင်းသောကိုယ်စားပြုမှုကို ထည့်ရန်ဖြစ်သည်။ 

ဤ post တွင် Haskell တွင် နှစ်ဘက်ညီခြင်းအတွက် ဂရပ်ကိုစစ်ဆေးခြင်းအတွက် ကျွန်ုပ်၏ အကောင်အထည်ဖော်မှုဆိုင်ရာ algorithm အကြောင်းပြောပါမည်။ algorithm သည် အခြေခံအကျဆုံးများထဲမှ တစ်ခုဖြစ်သော်လည်း၊ ၎င်းကို functional style ဖြင့် လှပစွာ အကောင်အထည်ဖော်ခြင်းသည် ကျွန်ုပ်အား ထပ်ခါထပ်ခါ အကြိမ်ပေါင်းများစွာ လုပ်ခဲ့ရပြီး အလုပ်များစွာ လိုအပ်ပါသည်။ ထို့ကြောင့် ကျွန်ုပ်သည် monad ထရန်စဖော်မာများဖြင့် အကောင်အထည်ဖော်ရန် ဆုံးဖြတ်ခဲ့သည်။ 

ကိုယ့်အကြောင်းကိုယ်

ကျွန်ုပ်အမည် Vasily Alferov ဖြစ်ပါသည်၊ ကျွန်ုပ်သည် စိန့်ပီတာစဘတ် HSE တွင် စတုတ္ထနှစ် ကျောင်းသားဖြစ်သည်။ စောစောက ဘလော့မှာ ရေးတယ်။ parameterized algorithms အကြောင်း ကျွန်ုပ်၏ ပရောဂျက်အကြောင်း и ZuriHac ခရီးစဉ်အကြောင်း. အခု ကျနော်က internship လုပ်နေတယ်။ Bergen တက္ကသိုလ် နော်ဝေးမှာ၊ ပြဿနာအတွက် ချဉ်းကပ်မှုတွေ လုပ်နေတယ်။ ဆေးရောင်ခြယ်စာရင်း. ကျွန်ုပ်၏စိတ်ဝင်စားမှုများတွင် parameterized algorithms နှင့် functional programming တို့ပါဝင်သည်။

algorithm ၏အကောင်အထည်ဖော်မှုနှင့် ပတ်သက်

စကားချီး

ပရိုဂရမ်တွင် ပါဝင်သည့် ကျောင်းသားများအား ဘလော့ဂ်သို့ ပြင်းပြင်းထန်ထန် အားပေးပါသည်။ သူတို့က ဘလော့ဂ်အတွက် ပလက်ဖောင်းတစ်ခု ပေးထားတယ်။ Haskell ၏နွေရာသီ. ဤဆောင်းပါးသည် ဘာသာပြန်တစ်ခုဖြစ်သည်။ ဆောင်းပါးများအတိုချုံးပြီး နိဒါန်းနဲ့ အင်္ဂလိပ်လို ဇူလိုင်လမှာ ရေးထားတာပါ။ 

Pull Request တွင် မေးခွန်းအတွက် ကုဒ်ဖြင့် တွေ့နိုင်သည်။ ဒီမှာ.

ကျွန်ုပ်၏အလုပ်၏ရလဒ်များအကြောင်း (အင်္ဂလိပ်ဘာသာဖြင့်ဖတ်နိုင်သည်) ဒီမှာ.

ဤ post သည် functional programming တွင်အခြေခံသဘောတရားများနှင့်စာဖတ်သူအားရင်းနှီးစေရန်ရည်ရွယ်သည်၊ သို့သော်အချိန်ရောက်သောအခါအသုံးပြုသောဝေါဟာရအားလုံးကိုပြန်လည်သိမ်းဆည်းရန်ကြိုးစားပါမည်။

နှစ်ဘက်ညီခြင်းအတွက် ဂရပ်များကို စစ်ဆေးခြင်း။ 

အရိုးရှင်းဆုံး ဂရပ်အယ်လ်ဂိုရီသမ်များထဲမှ တစ်ခုအဖြစ် algorithms ဆိုင်ရာ သင်တန်းတစ်ခုတွင် ဂရပ်နှစ်ခုပါဝင်မှုကို စစ်ဆေးခြင်းအတွက် algorithm ကို ပေးလေ့ရှိသည်။ သူ၏အကြံအစည်သည် ရိုးရိုးရှင်းရှင်းဖြစ်သည်- ပထမဦးစွာ ကျွန်ုပ်တို့သည် ဘယ်ဘက် သို့မဟုတ် ညာဖက်ဝေစုတွင် ဒေါင်လိုက်များကို တစ်နည်းနည်းဖြင့် ထည့်ကာ ကွဲလွဲနေသောအစွန်းတစ်ခုကို တွေ့ရှိသောအခါ၊ ဂရပ်သည် နှစ်ဖက်မဟုတ်ကြောင်း အခိုင်အမာဆိုသည်။

နောက်ထပ်အသေးစိတ်အချက်တစ်ချက်- ပထမဦးစွာ ကျွန်ုပ်တို့သည် ဘယ်ဘက်ဝေစုတွင် ထိပ်တန်းအချို့ကို ထည့်ထားသည်။ သိသာထင်ရှားသည်၊ ဤ vertex ၏အိမ်နီးချင်းများအားလုံးသည် ညာဘက်အမြှေးတွင် အိပ်နေရမည်ဖြစ်သည်။ ထို့အပြင်၊ ဤထိပ်တန်း၏အိမ်နီးချင်းများ၏အိမ်နီးချင်းများအားလုံးသည်ဘယ်ဘက်အမြှေးတွင်အိပ်ရမည်၊ စသည်တို့ဖြစ်သည်။ အိမ်နီးနားချင်းများကို မသတ်မှတ်ရသေးသော ဒေါင်လိုက်၏ချိတ်ဆက်ထားသောအစိတ်အပိုင်းတွင် ဒေါင်လိုက်များရှိနေသေးသရွေ့ ကျွန်ုပ်တို့သည် အစုရှယ်ယာများကို ဆက်လက်သတ်မှတ်ပေးပါသည်။ ထို့နောက် ချိတ်ဆက်ထားသော အစိတ်အပိုင်းအားလုံးအတွက် ဤလုပ်ဆောင်ချက်ကို ထပ်လုပ်ပါသည်။

တူညီသောအခန်းကန့်သို့ ကျရောက်နေသည့် ဒေါင်လိုက်များကြားတွင် အစွန်းတစ်ခုရှိနေပါက၊ bipartite ဂရပ်တွင် ကျယ်ပြန့်စွာသိရှိနိုင်သော (ထင်ရှားပြီး) မဖြစ်နိုင်သော ဂရပ်ရှိ ထူးဆန်းသောစက်ဝိုင်းကို ရှာဖွေရန် မခက်ခဲပါ။ မဟုတ်ပါက၊ ကျွန်ုပ်တို့တွင် မှန်ကန်သော partition တစ်ခုရှိသည်၊ ဆိုလိုသည်မှာ ဂရပ်သည် bipartite ဖြစ်သည်။

ပုံမှန်အားဖြင့်၊ ဤ algorithm ကို အသုံးပြု၍ အကောင်အထည် ဖော်သည်။ အကျယ်ကို အရင်ရှာပါ။ သို့မဟုတ် အနက်ကို အရင်ရှာဖွေပါ။. မရှိမဖြစ်လိုအပ်သောဘာသာစကားများတွင်၊ အနက်-ပထမရှာဖွေမှုကို များသောအားဖြင့် အနည်းငယ်ရိုးရှင်းပြီး အပိုဒေတာတည်ဆောက်ပုံများမလိုအပ်သောကြောင့် အသုံးပြုသည်။ သမားရိုးကျဆိုတော့ အနက်ပိုင်း ပထမရှာဖွေမှုကိုလည်း ရွေးချယ်ခဲ့တယ်။

ထို့ကြောင့် ကျွန်ုပ်တို့သည် အောက်ပါအစီအစဥ်သို့ ရောက်ရှိလာပါသည်။ ကျွန်ုပ်တို့သည် အတိမ်အနက်-ပထမရှာဖွေမှုကို အသုံးပြု၍ ဂရပ်များ၏ ဒေါင်လိုက်များကို ဖြတ်ကာ ၎င်းတို့ထံ မျှဝေမှုများ သတ်မှတ်ပေးကာ အစွန်းတစ်လျှောက် ရွေ့လျားသည့်အခါ မျှဝေမှုအရေအတွက်ကို ပြောင်းလဲပေးပါသည်။ အစုရှယ်ယာတစ်ခု သတ်မှတ်ပေးထားပြီးဖြစ်သော ထိပ်တန်းသို့ မျှဝေရန် ကြိုးစားပါက၊ ဂရပ်သည် နှစ်ဘက်သတ်မဟုတ်ကြောင်း လုံခြုံစွာပြောနိုင်သည်။ ဒေါင်လိုက်အားလုံးကို အစုရှယ်ယာတစ်ခု သတ်မှတ်ပြီး အစွန်းအားလုံးကို ကြည့်ရှုပြီးသည့်အခိုက်တွင်၊ ကျွန်ုပ်တို့တွင် အပိုင်းပိုင်းကောင်းတစ်ခုရှိသည်။

တွက်ချက်မှု၏သန့်ရှင်းမှု

Haskell တွင် ကျွန်ုပ်တို့သည် တွက်ချက်မှုအားလုံးဖြစ်သည်ဟု ကျွန်ုပ်တို့ယူဆသည်။ သန့်ရှင်း။ သို့သော်၊ ဤအရာသည် အမှန်တကယ်ဖြစ်ခဲ့ပါက၊ ကျွန်ုပ်တို့သည် မျက်နှာပြင်ပေါ်တွင် မည်သည့်အရာကိုမျှ ပရင့်ထုတ်ရန် နည်းလမ်းရှိမည်မဟုတ်ပါ။ လုံးဝ၊ သန့်ရှင်းသော တွက်ချက်ရတာ ပျင်းလွန်းလို့ တစ်ခုမှ မရှိဘူး။ သန့်ရှင်း တစ်စုံတစ်ခုကို တွက်ချက်ရန် အကြောင်းပြချက်များ။ ပရိုဂရမ်တွင် ဖြစ်ပေါ်နေသည့် တွက်ချက်မှုအားလုံးကို တစ်နည်းနည်းဖြင့် ခိုင်းစေပါသည်။ "မသန့်ရှင်း" monad IO။

Monads သည် တွက်ချက်မှုများကို ကိုယ်စားပြုသည့် နည်းလမ်းတစ်ခုဖြစ်သည်။ ဆိုးကျိုးများ Haskell တွင်။ သူတို့ဘယ်လိုအလုပ်လုပ်တယ်ဆိုတာကို ရှင်းပြတာက ဒီပို့စ်ရဲ့ ဘောင်ကိုကျော်လွန်ပါတယ်။ ကောင်းမွန်ရှင်းလင်းသော ဖော်ပြချက်ကို အင်္ဂလိပ်ဘာသာဖြင့် ဖတ်ရှုနိုင်ပါသည်။ ဒီမှာ.

ဤနေရာတွင် IO ကဲ့သို့ အချို့သော monads များကို compiler magic ဖြင့် အကောင်အထည်ဖော်နေသော်လည်း၊ အခြားအရာအားလုံးနီးပါးကို software ဖြင့်အကောင်အထည်ဖော်ပြီး ၎င်းတို့တွင်ရှိသော တွက်ချက်မှုအားလုံးသည် သန့်ရှင်းကြောင်းကို ဤနေရာတွင် ထောက်ပြလိုပါသည်။

အကျိုးသက်ရောက်မှုများများစွာရှိပြီးတစ်ခုစီတွင်၎င်း၏ကိုယ်ပိုင် monad ရှိသည်။ ဤသည်မှာ အလွန်အားကောင်းပြီး လှပသောသီအိုရီတစ်ခုဖြစ်သည်- monads အားလုံးသည် တူညီသောမျက်နှာပြင်ကို အကောင်အထည်ဖော်သည်။ အောက်ဖော်ပြပါ ဘုန်းကြီးသုံးပါးအကြောင်းကို ပြောပြပါမည်။

• ea သည် type a ၏တန်ဖိုးကိုပြန်ပေးသည် သို့မဟုတ် type e ၏ခြွင်းချက်တစ်ခုဖြစ်သည်။ ဤ monad ၏အပြုအမူသည် ခြွင်းချက်မရှိမဖြစ်လိုအပ်သောဘာသာစကားများဖြင့် ကိုင်တွယ်ခြင်းနှင့် အလွန်ဆင်တူပါသည်- အမှားများကိုဖမ်းမိနိုင်သည် သို့မဟုတ် ပေးပို့နိုင်ပါသည်။ အဓိကကွာခြားချက်မှာ monad သည် Haskell ရှိ စံစာကြည့်တိုက်တွင် လုံးဝယုတ္တိနည်းကျဖြင့် အကောင်အထည်ဖော်ထားပြီး၊ လိုအပ်သောဘာသာစကားများသည် ပုံမှန်အားဖြင့် လည်ပတ်မှုစနစ်ယန္တရားများကို အသုံးပြုပါသည်။
• State sa သည် အမျိုးအစား a ၏တန်ဖိုးကို ပြန်ပေးကာ အမျိုးအစား s ကို ပြောင်းလဲနိုင်သော အခြေအနေသို့ ဝင်ရောက်နိုင်သော တွက်ချက်မှုတစ်ခုဖြစ်သည်။
• ဖြစ်နိုင်တယ်။ May monad သည် Noth ကိုပြန်ပေးခြင်းဖြင့် အချိန်မရွေး အနှောက်အယှက်ဖြစ်စေနိုင်သော တွက်ချက်မှုကို ဖော်ပြသည်။ သို့သော်၊ ဆန့်ကျင်ဘက်အကျိုးသက်ရောက်မှုကိုဖော်ပြသည့် Maybe အမျိုးအစားအတွက် MonadPlus အတန်းကို အကောင်အထည်ဖော်ခြင်းအကြောင်း ကျွန်ုပ်တို့ပြောဆိုပါမည်- ၎င်းသည် တိကျသောတန်ဖိုးကို ပြန်ပေးခြင်းဖြင့် အချိန်မရွေး အနှောင့်အယှက်ဖြစ်စေနိုင်သော တွက်ချက်မှုတစ်ခုဖြစ်သည်။

algorithm ကိုအကောင်အထည်ဖော်ခြင်း။

ကျွန်ုပ်တို့တွင် ဒေတာအမျိုးအစားနှစ်မျိုးဖြစ်သည့် Graph a နှင့် Bigraph ab ရှိပြီး ပထမတစ်မျိုးမှာ a ၏တန်ဖိုးများဟု အညွှန်းတပ်ထားသော ဂရပ်များကို ကိုယ်စားပြုပြီး ဒုတိယအမျိုးအစားမှာ a နှင့် ညာဘက်တွင် တန်ဖိုးများတံဆိပ်တပ်ထားသော ဘယ်ဘက်ခြမ်းရှိ ဂရပ်ဖစ်များကို ကိုယ်စားပြုသည် အမျိုးအစား b ၏တန်ဖိုးများဖြင့်တံဆိပ်တပ်ထားသော -side vertices။

၎င်းတို့သည် Alga စာကြည့်တိုက်မှ အမျိုးအစားများမဟုတ်ပါ။ Alga တွင် လမ်းညွှန်မထားသော နှစ်ပိုင်းဂရပ်များအတွက် ကိုယ်စားပြုမှု မရှိပါ။ ဒီလိုမျိုး အမျိုးအစားတွေကို ရှင်းရှင်းလင်းလင်းဖြစ်အောင် လုပ်ထားတယ်။

အောက်ဖော်ပြပါ လက်မှတ်များဖြင့် အကူအညီပေးသည့် လုပ်ဆောင်ချက်များလည်း လိုအပ်ပါမည်။

-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]

-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
                                         -> Graph a
                                         -> Bigraph b c

-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:

type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)

နက်ရှိုင်းသော ပထမရှာဖွေမှုတွင် ကွဲလွဲနေသောအစွန်းတစ်ခုကို ကျွန်ုပ်တို့တွေ့ရှိပါက၊ ထူးဆန်းသောစက်ဝန်းသည် ပြန်လည်ကုစားမှုအစု၏ထိပ်တွင် ရှိနေသည်ကို သိမြင်ရန်မှာ လွယ်ကူပါသည်။ ထို့ကြောင့်၊ ၎င်းကို ပြန်လည်ရယူရန်၊ ကျွန်ုပ်တို့သည် ပြန်လည်ကုထုံးအစည်းမှ နောက်ဆုံးထိပ်တန်း၏ ပထမဆုံးဖြစ်ပေါ်မှုအထိ အရာအားလုံးကို ဖြတ်တောက်ရန် လိုအပ်သည်။

ကျွန်ုပ်တို့သည် ထိပ်တန်းတစ်ခုစီအတွက် ခွဲဝေကိန်းဂဏန်းများ ပေါင်းစပ်ထားသော အခင်းအကျင်းကို ထိန်းသိမ်းခြင်းဖြင့် အနက်-ပထမရှာဖွေမှုကို အကောင်အထည်ဖော်သည်။ ကျွန်ုပ်တို့ရွေးချယ်ထားသော monad ၏ Functor အတန်းအစားကို အကောင်အထည်ဖော်ခြင်းဖြင့် recursion stack သည် အလိုအလျောက်ထိန်းသိမ်းထားလိမ့်မည်- ကျွန်ုပ်တို့သည် recursive function မှ ပြန်လာသောရလဒ်အဖြစ် လမ်းကြောင်းမှ vertices အားလုံးကို ထည့်ရန်သာလိုပါမည်။

ကျွန်ုပ်၏ပထမဆုံးစိတ်ကူးမှာ ကျွန်ုပ်တို့လိုအပ်သောအကျိုးသက်ရောက်မှုများကို အတိအကျအကောင်အထည်ဖော်ပုံပေါ်သည့် Either monad ကိုအသုံးပြုရန်ဖြစ်သည်။ ကျွန်တော်ရေးခဲ့တဲ့ ပထမဆုံးအကောင်အထည်ဖော်မှုက ဒီရွေးချယ်မှုနဲ့ အရမ်းနီးစပ်ပါတယ်။ တကယ်တော့၊ တစ်ကြိမ်မှာ မတူညီတဲ့ အကောင်အထည်ဖော်မှု ငါးခုရှိခဲ့ပြီး နောက်ဆုံးမှာတော့ နောက်တစ်ခုအပေါ် အခြေချခဲ့တယ်။

ပထမဦးစွာ၊ ကျွန်ုပ်တို့သည် ခွဲဝေသတ်မှတ်ခြင်းဆိုင်ရာ ဆက်စပ်မှုခင်းများကို ထိန်းသိမ်းထားရန် လိုအပ်သည် - ၎င်းသည် နိုင်ငံတော်နှင့် ပတ်သက်သည့် အရာတစ်ခုဖြစ်သည်။ ဒုတိယအနေနဲ့၊ ပဋိပက္ခတစ်ခုကို တွေ့ရှိတဲ့အခါ ရပ်တန့်နိုင်ဖို့လိုပါတယ်။ ၎င်းသည် Monad for Either သို့မဟုတ် MonadPlus for Maybe ဖြစ်နိုင်သည်။ အဓိက ကွာခြားချက်မှာ တွက်ချက်မှု မရပ်တန့်ပါက နှစ်ခုလုံးသည် တန်ဖိုးတစ်ခုကို ပြန်ပေးနိုင်မည် ဖြစ်ပြီး ဤကိစ္စတွင် ၎င်းနှင့်ပတ်သက်သည့် အချက်အလက်ကိုသာ ပြန်ပေးနိုင်သည်။ ကျွန်ုပ်တို့သည် အောင်မြင်မှုအတွက် သီးခြားတန်ဖိုးကို မလိုအပ်သောကြောင့် (၎င်းကို နိုင်ငံတော်တွင် သိမ်းဆည်းထားပြီးဖြစ်သည်)၊ ကျွန်ုပ်တို့သည် Maybe ကို ရွေးချယ်ပါသည်။ ဘုန်းကြီးနှစ်ပါး၏ အကျိုးသက်ရောက်မှုကို ပေါင်းစပ်ရန် လိုအပ်သောအခါတွင် ၎င်းတို့သည် ထွက်ပေါ်လာသည်။ monad ထရန်စဖော်မာဤအကျိုးသက်ရောက်မှုများကို အတိအကျပေါင်းစပ်ပေးသော၊

ဒီလိုရှုပ်ထွေးတဲ့ အမျိုးအစားကို ဘာကြောင့် ရွေးချယ်ခဲ့တာလဲ။ အကြောင်းရင်းနှစ်ခု။ ပထမဦးစွာ၊ အကောင်အထည်ဖော်မှုသည် လိုအပ်ချက်နှင့် အလွန်ဆင်တူပါသည်။ ဒုတိယအနေဖြင့်၊ Maybe monad တွင်လုပ်ဆောင်ရန်ပိုမိုလွယ်ကူသည့် odd loop ကိုပြန်လည်ရယူရန်အတွက် recursion မှပြန်လာသည့်အခါ ပဋိပက္ခဖြစ်သည့်အခါ return value ကို ကိုင်တွယ်ရန် လိုအပ်ပါသည်။

ဒါကြောင့် ဒီအကောင်အထည်ဖော်မှုကို ကျွန်တော်တို့ ရရှိပါတယ်။

{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}

data Part = LeftPart | RightPart

otherPart :: Part -> Part
otherPart LeftPart  = RightPart
otherPart RightPart = LeftPart

type PartMap a = Map.Map a Part
type OddCycle a = [a]

toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
                    LeftPart  -> Left  v
                    RightPart -> Right v

type PartMonad a = MaybeT (State (PartMap a)) [a]

detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
                     (Just c, _)  -> Left  $ oddCycle c
                     (Nothing, m) -> Right $ toBipartiteWith (toEither m) g
    where
        inVertex :: Part -> a -> PartMonad a
        inVertex p v = ((:) v) <$> do modify $ Map.insert v p
                                      let q = otherPart p
                                      msum [ onEdge q u | u <- neigbours v g ]

        {-# INLINE onEdge #-}
        onEdge :: Part -> a -> PartMonad a
        onEdge p v = do m <- get
                        case v `Map.lookup` m of
                             Nothing -> inVertex p v
                             Just q  -> do guard (q /= p)
                                           return [v]

        processVertex :: a -> PartMonad a
        processVertex v = do m <- get
                             guard (v `Map.notMember` m)
                             inVertex LeftPart v

        dfs :: PartMonad a
        dfs = msum [ processVertex v | v <- vertexList g ]

        oddCycle :: [a] -> [a]
        oddCycle c = tail (dropWhile ((/=) last c) c)

block သည် algorithm ၏ core ဖြစ်သည်။ အထဲမှာ ဘာတွေဖြစ်နေလဲ ရှင်းပြဖို့ ကြိုးစားပါ့မယ်။

• inVertex သည် ပထမအကြိမ် vertex ကို ကျွန်ုပ်တို့သွားရောက်ကြည့်ရှုသည့် အနက်-ပထမရှာဖွေမှု၏ အစိတ်အပိုင်းဖြစ်သည်။ ဤနေရာတွင် ကျွန်ုပ်တို့သည် ရှယ်ယာနံပါတ်တစ်ခုကို vertex သို့သတ်မှတ်ပြီး အိမ်နီးချင်းအားလုံးတွင် onEdge ကိုဖွင့်ပါ။ ဤနေရာတွင် ကျွန်ုပ်တို့သည် ခေါ်ဆိုမှုအစုကို ပြန်လည်ရယူသည့်နေရာဖြစ်သည်၊ အကယ်၍ msum သည် တန်ဖိုးတစ်ခုကို ပြန်ပေးမည်ဆိုပါက၊ ကျွန်ုပ်တို့သည် vertex v ကို ထိုနေရာသို့ တွန်းပို့ပါသည်။
• onEdge သည် ကျွန်ုပ်တို့ အစွန်းသို့ သွားရောက်သည့် အပိုင်းဖြစ်သည်။ အစွန်းတစ်ခုစီအတွက် နှစ်ကြိမ်ခေါ်သည်။ ဤနေရာတွင် ကျွန်ုပ်တို့သည် တစ်ဖက်ရှိ ထိပ်တန်းကို ရောက်ခဲ့သည်ရှိမရှိ စစ်ဆေးပြီး မဟုတ်ပါက ၎င်းကို သွားရောက်ကြည့်ရှုပါ။ အလည်လာပါက၊ အစွန်းသည် ကွဲလွဲမှုရှိမရှိ စစ်ဆေးပါသည်။ အကယ်၍ ထိုသို့ဖြစ်ပါက၊ ကျွန်ုပ်တို့သည် တန်ဖိုးကို ပြန်ပေးသည် - ထို့နောက် အခြား ဒေါင်လိုက်များအားလုံးကို ပြန်၍ ထားရှိမည့် recursion stack ၏ ထိပ်ပိုင်း။
• processVertex သည် vertex တစ်ခုစီကို လည်ပတ်ပြီး မဟုတ်ပါက ၎င်းပေါ်တွင် Vertex တွင် အလုပ်လုပ်သည်ရှိမရှိ စစ်ဆေးသည်။
• dfs သည် ထောင့်အားလုံးတွင် processVertex ကို လုပ်ဆောင်သည်။

ဒါပါပဲ။

INLINE ဟူသော စကားလုံးသမိုင်း

INLINE ဟူသော စကားလုံးသည် အယ်လဂိုရီသမ်၏ ပထမဆုံးအကောင်အထည်ဖော်မှုတွင်မဟုတ်ပါ၊ နောက်ပိုင်းတွင်ပေါ်လာသည်။ ပိုမိုကောင်းမွန်သော အကောင်အထည်ဖော်မှုကို ရှာတွေ့သောအခါ၊ INLINE မဟုတ်သောဗားရှင်းသည် အချို့သောဂရပ်များတွင် သိသိသာသာ နှေးကွေးသွားသည်ကို တွေ့ခဲ့ရသည်။ သဘောတရားအရ လုပ်ဆောင်ချက်များသည် တူညီသင့်သည်ဟု ယူဆပါက၊ ဤအရာသည် ကျွန်ုပ်အား အလွန်အံ့သြမိပါသည်။ သူစိမ်းတောင်မှ၊ မတူညီတဲ့ GHC ဗားရှင်းရှိတဲ့ အခြားစက်မှာ သိသာထင်ရှားတဲ့ ကွာခြားမှုမရှိပါဘူး။

GHC Core ထုတ်ပေးမှုကို တစ်ပတ်ကြာဖတ်ရှုပြီးနောက်၊ ပြတ်သားသော INLINE တစ်ကြောင်းဖြင့် ပြဿနာကို ဖြေရှင်းနိုင်ခဲ့သည်။ GHC 8.4.4 နှင့် GHC 8.6.5 ကြား တစ်ချိန်ချိန်တွင် ပိုမိုကောင်းမွန်အောင်ပြုလုပ်သူသည် ၎င်းကို ၎င်း၏ကိုယ်ပိုင်လုပ်ဆောင်မှုကို ရပ်သွားခဲ့သည်။

Haskell ပရိုဂရမ်းမင်းတွင် ထိုသို့သော အညစ်အကြေးများကို ကြုံတွေ့ရမည်ဟု ကျွန်ုပ် မမျှော်လင့်ခဲ့ပါ။ သို့သော်လည်း ယနေ့တွင်ပင်၊ optimizers များသည် တစ်ခါတစ်ရံတွင် အမှားများပြုလုပ်ကြပြီး ၎င်းတို့အား အရိပ်အမြွက်ပေးရန်အတွက် ကျွန်ုပ်တို့၏အလုပ်ဖြစ်သည်။ ဥပမာအားဖြင့်၊ ၎င်းသည် imperative ဗားရှင်းတွင် မျဉ်းသားထားသောကြောင့် function ကို inline လုပ်သင့်သည်ကို ဤနေရာတွင် ကျွန်ုပ်တို့သိရပြီး၊ ၎င်းသည် compiler အား အရိပ်အမြွက်ပေးရန် အကြောင်းပြချက်တစ်ခုဖြစ်သည်။

ဘာဆက်ဖြစ်တာလဲ။

ထို့နောက် Hopcroft-Karp algorithm ကို အခြား monads များနှင့် အကောင်အထည်ဖော်ခဲ့ပြီး၊ ၎င်းသည် ပရိုဂရမ်၏ အဆုံးဖြစ်သည်။

Google Summer of Code ၏ကျေးဇူးကြောင့်၊ Functional Programming တွင် လက်တွေ့ကျသော အတွေ့အကြုံကို ရရှိခဲ့ပြီး ၎င်းသည် နောက်နွေရာသီတွင် Jane Street တွင် အလုပ်သင်ဆင်းရန် ကူညီပေးရုံသာမက (ဤနေရာသည် Habr ၏ တတ်ကျွမ်းနားလည်သူ ပရိသတ်ကြားတွင်ပင် မည်မျှလူသိများသည် မသိသော်လည်း ၎င်းမှာ တစ်ခုအပါအဝင်ဖြစ်သည်။ အလုပ်လုပ်တဲ့ ပရိုဂရမ်းမင်းမှာ ပါဝင်ဖို့ နွေရာသီမှာ သင်လုပ်နိုင်တဲ့ အနည်းငယ်ထဲက)၊ ဒါပေမယ့် ဒီပါရာဒိုင်းကို လက်တွေ့ကျင့်သုံးတဲ့ အံ့ဖွယ်ကမ္ဘာကြီးကိုလည်း မိတ်ဆက်ပေးခဲ့ပြီး၊ ကျွန်တော့်ရဲ့ ရိုးရာဘာသာစကားနဲ့ အတွေ့အကြုံနဲ့ သိသိသာသာ ကွာခြားပါတယ်။

source: www.habr.com