۲۷ - ۱۰تمرین‌های فصل

لیست تفاضل

لیست‌ها واقعاً خوبن، اما اضافه کردنِ المان به انتها یا الحاق‌ِشون ارزون نیست. قبل‌تر ‏‎Sequene‎‏ رو به عنوانِ یه چاره برای این مشکل معرفی کردیم، اما ساختار داده ِ ساده‌تری که مشخصاً برای حلِ این مشکل طراحی شده وجود داره: لیست تفاضل!

بجای اینکه ما لیست‌های تفاضل رو توضیح بدیم، بخشی از تمرین اینه که خودتون از کاربرد و دلیل‌ش سر در بیارین (البته اگه خواستین مستندات‌ِش روی Hackage رو بخونین). قبل از اینکه برین سراغ تمرینِ آموزشی‌ای که در منابعِ پیشنهادی معرفی کردیم، اول سعی کنین خودتون این تمرین رو حل کنین. خب، تایپِ ‏‎DList‎‏ با استفاده از لیست‌های معمولی درست شده، اما یه تابع‌ست:

newtype DList a = DL { unDL :: [a] -> [a] }

کُدهای زیر بر مبنایِ API ِ دان استوارت و شان لدر نوشته شدن:

empty :: DList a
empty = undefined
{-# INLINE empty #-}

singleton :: a -> DList a
singleton = undefined
{-# INLINE singleton #-}

toList :: DList a -> [a]
toList = undefined
{-# INLINE toList #-}

-- ‎‏پیش‌افزون کن.‏‎ dlist یک المان رو به یه
-- و به معنای prepend م. پیش‌افزون معادلِ
-- ‎‏اضافه کردن به ابتدای لیست‌ه.‏‎
infixr `cons`
cons        :: a -> DList a -> DList a
cons x xs   = DL ((x:) . unDL xs)
{-# INLINE cons #-}

-- ‎‏پس‌افزون کن.‏‎ dlist یک المان رو به یه
-- و به معنای append م. پس‌افزون معادلِ
-- ‎‏اضافه کردن به انتهای لیست‌ه.‏‎
infixl `snoc`
snoc :: DList a -> a -> DList a
snoc = undefined
{-# INLINE snoc #-}

-- ‎‏کن.‏‎ append ها رو با هم dlist
append :: DList a -> DList a -> DList a
append = undefined
{-# INLINE append #-}

یکی از موارد خیلی خوبِ ‏‎DList‎‏ اینه که ‏‎cons‎‏، ‏‎snoc‎‏، و ‏‎append‎‏ همه‌شون به اندازه‌ی یکسان زمان می‌برن؛ طولِ لیستِ تفاضلی هم هر چقدر باشه فرقی نداره. به کلامِ دیگه، اون سه‌تا مقدار زمانِ ثابتی می‌برن تا اینکه با رشدِ سایزِ ساختار داده زیاد بشن.

کاری کنین این بنچمارک با عملکردی که انتظار میره اجرا بشه:

schlemiel :: Int -> [Int]
schlemiel i = go i []
  where go 0 xs = xs
        go n xs = go (n-1) ([n] ++ xs)

constructDlist :: Int -> [Int]
constructDlist i = toList $ go i empty
  where go 0 xs = xs
        go n xs =
          go (n-1)
          (singleton n `append` xs)

main :: IO ()
main = defaultMain
  [ bench "concat list" $
      whnf schlemiel 123456
  , bench "concat dlist" $
      whnf constructDlist 123456
  ]

نسخه‌ی ‏‎DList‎‏ باید حدوداً دوبرابر سریع‌تر باشه.

یه صف ِ ساده

اینجا یه ساختار داده ِ دیگه برمبنای لیست تعریف می‌کنیم، اما این بار یه جور صَف ِه. قابلیت اصلیِ صف‌ها اینه که میشه با هزینه‌ی کم به اولِ صف المان اضافه کرد، و با هزینه‌ی کم از آخرِ صف المان برداشت.

-- گرفته شده از کتاب
-- “ساختارهای داده‌ی خالصاً تابعی”
-- (Purely Functional Data Structures)
-- نوشته‌ی کریس اوکاساکی
-- (Chris Okasaki)
data Queue a =
  Queue { enqueue :: [a]
        , dequeue :: [a]
        } deriving (Eq, Show)

-- یه آیتم اضافه می‌کنه
push :: a -> Queue a -> Queue a
push = undefined

pop :: Queue a -> Maybe (a, Queue a)
pop = undefined

این بار کُدِ کمتری بهتون میدیم، وظیفه‌ی شما اینه که تابع‌های بالا رو تعریف کنین، و با یه بنچمارک، عملکرد ِ یکی‌درمیون push و pop کردن از یه صف بر مبنای یک لیستِ مجرد رو با push و pop کردن از همون لیست (بدون استفاده از تایپِ ‏‎Queue‎‏) مقایسه کنین. دلیلِ اینکه میگیم یکی‌درمیون push و pop کنین اینه که نتونین بعد از همه‌ی push‌ها لیست رو معکوس کنین تا همه‌ی pop‌ها رو بهینه اجرا کنین.

حالتی که ‏‎dequeue‎‏ خالی باشه رو فراموش نکنین، باید المان‌ها رو از ‏‎enqueue‎‏ به ‏‎dequeue‎‏ شیفت کنین. حواستون باشه که قاعده‌ی ‏‎“first come, first served”‎‏ رو رعایت کنین (م. یعنی نوبت رعایت بشه، هر کی اول رسیده، اول کارش انجام بشه).

نهایتاً در مقابلِ ‏‎Sequence‎‏ ازش بنچمارک بگیرین. خودتون چندتا تست درست کنین. اگه خواستین عملیات‌های دیگه‌ای هم به تایپِ ‏‎Queue‎‏ اضافه کنین.