গত গ্রীষ্মে আমি অংশ নিয়েছিলাম গুগল সামার কোড - Google এর শিক্ষার্থীদের জন্য একটি প্রোগ্রাম। প্রতি বছর, আয়োজকরা বেশ কয়েকটি ওপেন সোর্স প্রকল্প নির্বাচন করে, যার মধ্যে রয়েছে সুপরিচিত সংস্থাগুলি থেকে Boost.org и লিনাক্স ফাউন্ডেশন. Google এই প্রকল্পগুলিতে কাজ করার জন্য সারা বিশ্বের শিক্ষার্থীদের আমন্ত্রণ জানায়। 

Google Summer of Code 2019-এ একজন অংশগ্রহণকারী হিসেবে, আমি লাইব্রেরির মধ্যে একটি প্রকল্প করেছি পানা সংগঠনের সাথে Haskell.org, যা হাসকেল ভাষা বিকাশ করছে - সবচেয়ে বিখ্যাত কার্যকরী প্রোগ্রামিং ভাষাগুলির মধ্যে একটি। আলগা হল একটি লাইব্রেরি যা প্রতিনিধিত্ব করে নিরাপদ টাইপ করুন Haskell মধ্যে গ্রাফ জন্য উপস্থাপনা. এটি ব্যবহার করা হয়, উদাহরণস্বরূপ, মধ্যে শব্দার্থিক — একটি Github লাইব্রেরি যা কোডের উপর ভিত্তি করে শব্দার্থিক গাছ, কল এবং নির্ভরতা গ্রাফ তৈরি করে এবং তাদের তুলনা করতে পারে। আমার প্রকল্পটি সেই প্রতিনিধিত্বের জন্য দ্বিপক্ষীয় গ্রাফ এবং অ্যালগরিদমের জন্য একটি টাইপ-নিরাপদ উপস্থাপনা যোগ করা ছিল। 

এই পোস্টে আমি হাসকেলের দ্বিপক্ষীয়তার জন্য একটি গ্রাফ পরীক্ষা করার জন্য একটি অ্যালগরিদম বাস্তবায়নের বিষয়ে কথা বলব। যদিও অ্যালগরিদমটি সবচেয়ে মৌলিক, একটি কার্যকরী শৈলীতে এটিকে সুন্দরভাবে প্রয়োগ করা আমাকে বেশ কয়েকটি পুনরাবৃত্তি করেছে এবং বেশ অনেক কাজ করতে হয়েছে। ফলস্বরূপ, আমি মোনাড ট্রান্সফরমারগুলির সাথে একটি বাস্তবায়নে স্থির হয়েছি। 

আমার সম্পর্কে

আমার নাম ভ্যাসিলি আলফেরভ, আমি সেন্ট পিটার্সবার্গ HSE-এর চতুর্থ বর্ষের ছাত্র। আগে ব্লগে লিখেছিলাম প্যারামিটারাইজড অ্যালগরিদম সম্পর্কে আমার প্রকল্প সম্পর্কে и জুরিহ্যাক ভ্রমণ সম্পর্কে. এই মুহূর্তে আমি একটি ইন্টার্নশিপে আছি বার্গেন বিশ্ববিদ্যালয় নরওয়েতে, যেখানে আমি সমস্যার সমাধান নিয়ে কাজ করছি তালিকা রঙ. আমার আগ্রহের মধ্যে প্যারামিটারাইজড অ্যালগরিদম এবং কার্যকরী প্রোগ্রামিং অন্তর্ভুক্ত।

অ্যালগরিদম বাস্তবায়ন সম্পর্কে

ভূমিকা

প্রোগ্রামে অংশগ্রহণকারী ছাত্রদের ব্লগে দৃঢ়ভাবে উত্সাহিত করা হয়। তারা আমাকে ব্লগের জন্য একটি প্ল্যাটফর্ম দিয়েছে হাস্কেলের গ্রীষ্ম. এই নিবন্ধটি একটি অনুবাদ প্রবন্ধ, সেখানে আমার দ্বারা জুলাই মাসে ইংরেজিতে লেখা, একটি সংক্ষিপ্ত ভূমিকা সহ। 

প্রশ্নযুক্ত কোড সহ পুল রিকোয়েস্ট পাওয়া যাবে এখানে.

আপনি আমার কাজের ফলাফল সম্পর্কে পড়তে পারেন (ইংরেজিতে) এখানে.

এই পোস্টটি পাঠককে কার্যকরী প্রোগ্রামিং-এর মৌলিক ধারণাগুলির সাথে পরিচিত করার উদ্দেশ্যে করা হয়েছে, যদিও আমি সময় এলে ব্যবহৃত সমস্ত পদ স্মরণ করার চেষ্টা করব।

দ্বিপক্ষীয়তার জন্য গ্রাফ পরীক্ষা করা হচ্ছে 

দ্বিপক্ষীয়তার জন্য একটি গ্রাফ পরীক্ষা করার জন্য একটি অ্যালগরিদম সাধারণত সহজ গ্রাফ অ্যালগরিদমগুলির মধ্যে একটি হিসাবে অ্যালগরিদমের একটি কোর্সে দেওয়া হয়। তার ধারণাটি সোজা: প্রথমে আমরা বাম বা ডান ভাগে শীর্ষবিন্দু রাখি এবং যখন একটি বিরোধপূর্ণ প্রান্ত পাওয়া যায়, তখন আমরা দাবি করি যে গ্রাফটি দ্বিপক্ষীয় নয়।

একটু বিস্তারিত: প্রথমে আমরা বাম ভাগে কিছু শীর্ষবিন্দু রাখি। স্পষ্টতই, এই শীর্ষবিন্দুর সমস্ত প্রতিবেশীদের অবশ্যই ডান লোবে শুয়ে থাকতে হবে। আরও, এই শীর্ষবিন্দুর প্রতিবেশীদের সমস্ত প্রতিবেশীকে অবশ্যই বাম লোবে শুতে হবে, এবং তাই। আমরা শীর্ষবিন্দুতে শেয়ার বরাদ্দ করা চালিয়ে যাচ্ছি যতক্ষণ না শীর্ষবিন্দুর সংযুক্ত অংশে এখনও শীর্ষবিন্দু রয়েছে যা দিয়ে আমরা শুরু করেছি যেটির জন্য আমরা প্রতিবেশীদের বরাদ্দ করিনি। তারপরে আমরা সমস্ত সংযুক্ত উপাদানগুলির জন্য এই ক্রিয়াটি পুনরাবৃত্তি করি।

একই পার্টিশনের মধ্যে যদি শীর্ষবিন্দুগুলির মধ্যে একটি প্রান্ত থাকে তবে গ্রাফে একটি বিজোড় চক্র খুঁজে পাওয়া কঠিন নয়, যা একটি দ্বিপক্ষীয় গ্রাফে ব্যাপকভাবে পরিচিত (এবং বেশ স্পষ্টতই) অসম্ভব। অন্যথায়, আমাদের একটি সঠিক পার্টিশন আছে, যার মানে গ্রাফটি দ্বিপক্ষীয়।

সাধারণত, এই অ্যালগরিদম ব্যবহার করে প্রয়োগ করা হয় প্রস্থ প্রথম অনুসন্ধান বা গভীরতা প্রথম অনুসন্ধান. আবশ্যিক ভাষায়, গভীরতা-প্রথম অনুসন্ধান সাধারণত ব্যবহার করা হয় কারণ এটি কিছুটা সহজ এবং অতিরিক্ত ডেটা কাঠামোর প্রয়োজন হয় না। আমি গভীরতা-প্রথম অনুসন্ধানও বেছে নিয়েছি কারণ এটি আরও ঐতিহ্যবাহী।

এইভাবে, আমরা নিম্নলিখিত স্কিমে এসেছি। আমরা গভীরতা-প্রথম অনুসন্ধান ব্যবহার করে গ্রাফের শীর্ষবিন্দুগুলি অতিক্রম করি এবং তাদের জন্য শেয়ারগুলি বরাদ্দ করি, আমরা প্রান্ত বরাবর অগ্রসর হওয়ার সাথে সাথে ভাগের সংখ্যা পরিবর্তন করি। যদি আমরা একটি শীর্ষবিন্দুতে একটি শেয়ার বরাদ্দ করার চেষ্টা করি যাতে ইতিমধ্যে একটি ভাগ বরাদ্দ করা আছে, আমরা নিরাপদে বলতে পারি যে গ্রাফটি দ্বিপক্ষীয় নয়। যে মুহুর্তে সমস্ত শীর্ষগুলিকে একটি ভাগ দেওয়া হয়েছে এবং আমরা সমস্ত প্রান্তগুলি দেখেছি, আমাদের একটি ভাল পার্টিশন রয়েছে।

গণনার বিশুদ্ধতা

হাস্কেলে আমরা ধরে নিই যে সমস্ত গণনা পরিষ্কার যাইহোক, যদি এটি সত্যিই হয়, তাহলে আমাদের পর্দায় কিছু মুদ্রণ করার কোন উপায় থাকবে না। মোটেও, পরিষ্কার গণনা এত অলস যে একটি নেই পরিষ্কার কিছু গণনা করার কারণ। প্রোগ্রামে ঘটমান সমস্ত গণনা একরকম বাধ্য করা হয় "অশুদ্ধ" মোনাড আইও

Monads হল গণনার প্রতিনিধিত্ব করার একটি উপায় প্রভাব Haskell মধ্যে. তারা কীভাবে কাজ করে তা ব্যাখ্যা করা এই পোস্টের সুযোগের বাইরে। ইংরেজিতে একটি ভাল এবং পরিষ্কার বর্ণনা পড়া যেতে পারে এখানে.

এখানে আমি উল্লেখ করতে চাই যে কিছু মোনাড, যেমন IO, কম্পাইলার ম্যাজিকের মাধ্যমে প্রয়োগ করা হয়, অন্য প্রায় সবগুলি সফ্টওয়্যারে প্রয়োগ করা হয় এবং তাদের মধ্যে সমস্ত গণনা বিশুদ্ধ।

অনেকগুলি প্রভাব রয়েছে এবং প্রতিটির নিজস্ব মোনাড রয়েছে। এটি একটি খুব শক্তিশালী এবং সুন্দর তত্ত্ব: সমস্ত মোনাড একই ইন্টারফেস প্রয়োগ করে। আমরা নিম্নলিখিত তিনটি মোনাড সম্পর্কে কথা বলব:

• হয় ea হল একটি গণনা যা টাইপ a-এর একটি মান প্রদান করে বা টাইপ e-এর একটি ব্যতিক্রম নিক্ষেপ করে। এই মোনাডের আচরণ আবশ্যিক ভাষায় ব্যতিক্রম পরিচালনার অনুরূপ: ত্রুটিগুলি ধরা বা পাস করা যেতে পারে। প্রধান পার্থক্য হল যে মোনাড সম্পূর্ণরূপে যৌক্তিকভাবে হাসকেলের স্ট্যান্ডার্ড লাইব্রেরিতে প্রয়োগ করা হয়, যখন অপরিহার্য ভাষাগুলি সাধারণত অপারেটিং সিস্টেম প্রক্রিয়া ব্যবহার করে।
• স্টেট sa হল একটি গণনা যা টাইপ a-এর একটি মান প্রদান করে এবং s টাইপের পরিবর্তনযোগ্য অবস্থায় অ্যাক্সেস করে।
• সম্ভবত একটি. হতে পারে মোনাড এমন একটি গণনা প্রকাশ করে যা যে কোনো সময় কিছুই ফেরত দিয়ে বাধাগ্রস্ত হতে পারে। যাইহোক, আমরা হয়তো মোনাডপ্লাস ক্লাসের বাস্তবায়ন সম্পর্কে কথা বলব, যা বিপরীত প্রভাব প্রকাশ করে: এটি একটি গণনা যা একটি নির্দিষ্ট মান ফেরত দিয়ে যে কোনো সময় বাধাগ্রস্ত হতে পারে।

অ্যালগরিদম বাস্তবায়ন

আমাদের দুটি ডেটা টাইপ আছে, গ্রাফ a এবং Bigraph ab, যার মধ্যে প্রথমটি a টাইপের মান সহ লেবেলযুক্ত শীর্ষবিন্দু সহ গ্রাফগুলিকে প্রতিনিধিত্ব করে এবং দ্বিতীয়টি a এবং ডান টাইপের মান সহ লেবেলযুক্ত বাম-পাশের শীর্ষবিন্দু সহ দ্বিপক্ষীয় গ্রাফগুলিকে উপস্থাপন করে টাইপ b এর মান সহ লেবেলযুক্ত পার্শ্ব শীর্ষবিন্দু।

এগুলি আলগা লাইব্রেরির প্রকার নয়। আলগা অনির্দেশিত দ্বিপক্ষীয় গ্রাফের জন্য একটি উপস্থাপনা নেই। আমি স্বচ্ছতার জন্য এই মত ধরনের তৈরি.

আমাদের নিম্নলিখিত স্বাক্ষর সহ সহায়ক ফাংশনগুলিরও প্রয়োজন হবে:

-- Список соседей данной вершины.
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)

এটি দেখা সহজ যে গভীরতা-প্রথম অনুসন্ধানের সময় যদি আমরা একটি বিরোধপূর্ণ প্রান্ত খুঁজে পাই, তবে বিজোড় চক্রটি পুনরাবৃত্তি স্ট্যাকের উপরে থাকে। এইভাবে, এটি পুনরুদ্ধার করার জন্য, আমাদের পুনরাবৃত্ত স্ট্যাক থেকে শেষ শীর্ষবিন্দুর প্রথম উপস্থিতি পর্যন্ত সবকিছু কেটে ফেলতে হবে।

আমরা প্রতিটি শীর্ষবিন্দুর জন্য শেয়ার নম্বরগুলির একটি সহযোগী অ্যারে বজায় রেখে গভীরতা-প্রথম অনুসন্ধান বাস্তবায়ন করি। আমাদের বেছে নেওয়া মোনাডের ফাংক্টর ক্লাসের বাস্তবায়নের মাধ্যমে রিকারশন স্ট্যাকটি স্বয়ংক্রিয়ভাবে রক্ষণাবেক্ষণ করা হবে: আমাদের শুধুমাত্র রিকার্সিভ ফাংশন থেকে প্রত্যাবর্তিত ফলাফলে পাথ থেকে সমস্ত শীর্ষবিন্দু স্থাপন করতে হবে।

আমার প্রথম ধারণা ছিল Either monad ব্যবহার করা, যা আমাদের প্রয়োজনীয় প্রভাবগুলিকে বাস্তবায়িত করে বলে মনে হয়। আমি লিখেছিলাম প্রথম বাস্তবায়ন এই বিকল্পের খুব কাছাকাছি ছিল। প্রকৃতপক্ষে, আমি এক সময়ে পাঁচটি ভিন্ন বাস্তবায়ন করেছি এবং অবশেষে অন্য একটিতে স্থির হয়েছি।

প্রথমত, আমাদের শেয়ার শনাক্তকারীর একটি সহযোগী অ্যারে বজায় রাখতে হবে - এটি রাজ্য সম্পর্কে কিছু। দ্বিতীয়ত, কোনো দ্বন্দ্ব শনাক্ত হলে আমাদের থামাতে সক্ষম হতে হবে। এটি হয় মোনাড এর জন্য হতে পারে, অথবা মোনাডপ্লাস হতে পারে। প্রধান পার্থক্য হল যে হয় একটি মান ফেরত দিতে পারে যদি গণনা বন্ধ না করা হয়, এবং হয়ত এই ক্ষেত্রে শুধুমাত্র এই সম্পর্কে তথ্য প্রদান করে। যেহেতু আমাদের সাফল্যের জন্য আলাদা মান প্রয়োজন নেই (এটি ইতিমধ্যে রাজ্যে সংরক্ষিত আছে), আমরা হয়তো বেছে নিই। এবং এই মুহুর্তে যখন আমাদের দুটি মোনাডের প্রভাব একত্রিত করার প্রয়োজন হয়, তখন তারা বেরিয়ে আসে মোনাড ট্রান্সফরমার, যা এই প্রভাবগুলিকে সুনির্দিষ্টভাবে একত্রিত করে।

কেন আমি যেমন একটি জটিল টাইপ চয়ন? দুটি কারণ। প্রথমত, বাস্তবায়ন অপরিহার্য অনুরূপ হতে সক্রিয় আউট. দ্বিতীয়ত, বিজোড় লুপ পুনরুদ্ধার করার জন্য পুনরাবৃত্তি থেকে ফিরে আসার সময় বিরোধের ক্ষেত্রে আমাদের রিটার্ন মানকে ম্যানিপুলেট করতে হবে, যা হতে পারে মোনাডে করা অনেক সহজ।

এইভাবে আমরা এই বাস্তবায়ন পেতে.

{-# 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)

যেখানে ব্লক অ্যালগরিদমের মূল। আমি এর ভিতরে কি ঘটছে তা ব্যাখ্যা করার চেষ্টা করব।

• inVertex হল গভীরতা-প্রথম অনুসন্ধানের অংশ যেখানে আমরা প্রথমবার শীর্ষবিন্দু পরিদর্শন করি। এখানে আমরা শীর্ষস্থানে একটি শেয়ার নম্বর বরাদ্দ করি এবং সমস্ত প্রতিবেশীদের উপর onEdge চালাই। এখানেও আমরা কল স্ট্যাক পুনরুদ্ধার করি: যদি msum একটি মান ফেরত দেয়, আমরা সেখানে vertex v পুশ করি।
• onEdge হল সেই অংশ যেখানে আমরা প্রান্ত পরিদর্শন করি। এটি প্রতিটি প্রান্তের জন্য দুবার বলা হয়। এখানে আমরা অন্য দিকের শীর্ষবিন্দুটি পরিদর্শন করা হয়েছে কিনা তা পরীক্ষা করি এবং না হলে এটি পরিদর্শন করি। পরিদর্শন করা হলে, প্রান্তটি বিরোধপূর্ণ কিনা তা আমরা পরীক্ষা করি। যদি তা হয়, তাহলে আমরা মানটি ফেরত দিই - রিকারশন স্ট্যাকের একেবারে উপরে, যেখানে অন্য সব শীর্ষবিন্দুগুলি ফেরত দেওয়ার পরে স্থাপন করা হবে।
• প্রসেসভার্টেক্স প্রতিটি ভার্টেক্স পরিদর্শন করা হয়েছে কিনা তা পরীক্ষা করে এবং না হলে এটিতে ভার্টেক্স চালায়।
• dfs সমস্ত শীর্ষবিন্দুতে processVertex চালায়।

এখানেই শেষ.

INLINE শব্দের ইতিহাস

INLINE শব্দটি অ্যালগরিদমের প্রথম প্রয়োগে ছিল না; এটি পরে উপস্থিত হয়েছিল। যখন আমি একটি ভাল বাস্তবায়ন খুঁজে বের করার চেষ্টা করেছি, তখন আমি দেখতে পেলাম যে অ-ইনলাইন সংস্করণটি কিছু গ্রাফে লক্ষণীয়ভাবে ধীর ছিল। শব্দার্থগতভাবে ফাংশন একই কাজ করা উচিত বিবেচনা করে, এটি আমাকে ব্যাপকভাবে অবাক করেছে। এমনকি অপরিচিত, GHC এর একটি ভিন্ন সংস্করণ সহ অন্য একটি মেশিনে কোনও লক্ষণীয় পার্থক্য ছিল না।

GHC কোর আউটপুট পড়ার এক সপ্তাহ অতিবাহিত করার পরে, আমি স্পষ্ট ইনলাইনের একটি লাইন দিয়ে সমস্যাটি সমাধান করতে সক্ষম হয়েছি। GHC 8.4.4 এবং GHC 8.6.5 এর মধ্যে কিছু সময়ে অপ্টিমাইজার নিজে থেকে এটি করা বন্ধ করে দেয়।

আমি হাসকেল প্রোগ্রামিং-এ এমন ময়লার মুখোমুখি হওয়ার আশা করিনি। যাইহোক, আজও, অপ্টিমাইজাররা মাঝে মাঝে ভুল করে, এবং তাদের ইঙ্গিত দেওয়া আমাদের কাজ। উদাহরণস্বরূপ, এখানে আমরা জানি যে ফাংশনটি ইনলাইন করা উচিত কারণ এটি অপরিহার্য সংস্করণে ইনলাইন করা হয়েছে এবং এটি কম্পাইলারকে একটি ইঙ্গিত দেওয়ার একটি কারণ।

এরপরে কী হলো?

তারপরে আমি অন্যান্য মনদের সাথে হপক্রফট-কার্প অ্যালগরিদম প্রয়োগ করেছি এবং এটিই প্রোগ্রামের শেষ ছিল।

গুগল সামার অফ কোডের জন্য ধন্যবাদ, আমি কার্যকরী প্রোগ্রামিংয়ে বাস্তব অভিজ্ঞতা অর্জন করেছি, যা আমাকে শুধুমাত্র পরবর্তী গ্রীষ্মে জেন স্ট্রিটে ইন্টার্নশিপ পেতে সাহায্য করেনি (আমি নিশ্চিত নই যে এই জায়গাটি হাবরের জ্ঞানী দর্শকদের মধ্যেও কতটা পরিচিত, কিন্তু এটি একটি কয়েকটির মধ্যে যেখানে আপনি কার্যকরী প্রোগ্রামিংয়ে নিযুক্ত হতে গ্রীষ্ম করতে পারেন), তবে এই দৃষ্টান্তটি অনুশীলনে প্রয়োগ করার বিস্ময়কর জগতের সাথেও আমাকে পরিচয় করিয়ে দিয়েছে, ঐতিহ্যগত ভাষায় আমার অভিজ্ঞতা থেকে উল্লেখযোগ্যভাবে আলাদা।

উত্স: www.habr.com