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

کایندها رو تشخیص بدین

۱.

کایند ِ ‏‎a‎‏ چیه؟

id :: a -> a

۲.

کایندهای ‏‎a‎‏ و ‏‎f‎‏ چی‌اند؟

r :: a -> f a

پردازشِ نوشته

این تمرین از اونجور کارهایی ِه که زبان‌شناس‌ها برا سرگرمی انجام میدن.

۱.

یه تابعِ بازگشتی به اسمِ ‏‎replaceWith‎‏ بنویسین که یه ‏‎String‎‏ می‌گیره، لغات‌ش رو جدا می‌کنه و هر جا the هست، با a جایگزین می‌کنه. این تابع قراره فقط the رو جایگزین کنه. تابعِ ‏‎notThe‎‏ یه تابعِ کمکی ِ پیشنهادی‌ه.

-- GHCi نمونه جلسه‌ی

-- >>> notThe "the"
-- Nothing
-- >>> notThe "blahtheblah"
-- Just "blahtheblah"
-- >>> notThe "woot"
-- Just "woot"
notThe :: String -> Maybe String
notThe = undefined

-- >>> replaceThe "the cow loves us"
-- "a cow loves us"
replaceThe :: String -> String
replaceThe = undefined

۲.

یه تابعِ بازگشتی بنویسین که یه ‏‎String‎‏ می‌گیره، لغات‌ش رو جدا می‌کنه و تعداد دفعاتی که بعد از the یه کلمه که با حرف صدادار شروع میشه اومده رو می‌شماره.

-- >>> countTheBeforeVowel "the cow"
-- 0
-- >>> countTheBeforeVowel "the evil cow"
-- 1
countTheBeforeVowel :: String -> Integer
countTheBeforeVowel = undefined

۳.

تعداد حروف صدادار در یه کلمه رو بشمارین.

راهنمایی: اگه مسئله رو ریز ریز کنین بهتون کمک می‌کنه. هر چقدر تابعِ کمکی لازم دارین بنویسین.

a)

صدادار بودن رو بررسی کنین.

b)

حروف صدادارِ یه نوشته رو برگردونین.

c)

تعداد المان‌های خروجی رو بشمارین.

-- >>> countVowels "the cow"
-- 2
-- >>> countVowels "Mikolajczak"
-- 4
countVowels :: String -> Integer
countVowels = undefined

کلمه رو تأیید کنین

با استفاده از تایپِ ‏‎Maybe‎‏ تابعی بنویسین که تعدادِ حروف صدادار و حروف بی‌صدا در یه نوشته رو بشماره. اگه تعداد حروف صدادار از حروف بی‌صدا بیشتر شد، تابع باید ‏‎Nothing‎‏ برگردونه. در اکثر زبان‌ها خیلی کم پیش میاد حروف صدادار از حروف بی‌صدا در یه لغت بیشتر باشن، پس هر وقت این اتفاق بیوفته، شاید ورودی لغت نباشه (یا به عبارتِ دیگه، ورودیِ معتبری نباشه):

newtype Word' =
  Word' String
  deriving (Eq, Show)

vowels = "aeiou"

mkWord :: String -> Maybe Word'
mkWord = undefined

پیش میاد، طبیعی‌ه

یه نوع‌داده برای ارائه‌ی اعدادِ طبیعی بهتون میدیم. تنها اعدادی که با اعدادِ طبیعی میشه نشون داد اعدادِ صفر تا بینهایت‌اند. برای این تمرین توابعی بنویسین که ‏‎Natural‎‏ ها رو به ‏‎Integer‎‏، و ‏‎Integer‎‏ها رو به ‏‎Natural‎‏ تبدیل می‌کنن. تبدیلِ ‏‎Natural‎‏ به ‏‎Integer‎‏ لازم نیست ‏‎Maybe‎‏ برگردونه، چون ‏‎Integer‎‏ سوپرمجموعه ِ ‏‎Natural‎‏ ِه. هر ‏‎Natural‎‏ ای رو میشه با ‏‎Integer‎‏ نشون داد، اما برعکس‌ش برای هر ‏‎Integer‎‏ ای صادق نیست.

-- طبیعی، مثل هیکل
-- یه بدنساز حرفه‌ای
data Nat =
    Zero
  | Succ Nat
  deriving (Eq, Show)

-- >>> natToInteger Zero
-- 0
-- >>> natToInteger (Succ Zero)
-- 1
-- >>> natToInteger (Succ (Succ Zero))
-- 2
natToInteger :: Nat -> Integer
natToInteger = undefined

-- >>> integerToNat 0
-- Just Zero
-- >>> integerToNat 1
-- Just (Succ Zero)
-- >>> integerToNat 2
-- Just (Succ (Succ Zero))
-- >>> integerToNat (-1)
-- Nothing
integerToNat :: Integer -> Maybe Nat
integerToNat = undefined

یه کتابخونه ِ کوچیک برای ‏‎Maybe‎‏

توابعِ زیر رو تعریف کنین. شاید یه کم وقت ببره.

۱.

بررسیِ بولیَن برای مقادیرِ ‏‎Maybe‎‏.

-- >>> isJust (Just 1)
-- True
-- >>> isJust Nothing
-- False
isJust :: Maybe a -> Bool

-- >>> isNothing (Just 1)
-- False
-- >>> isNothing Nothing
-- True
isNothing :: Maybe a -> Bool

۲.

کاتامورفیسم ِ ‏‎Maybe‎‏. هر مقدارِ ‏‎Maybe‎‏ رو به می‌تونه به هر چیزِ دیگه تبدیل کنه.

-- >>> mayybee 0 (+1) Nothing
-- 0
-- >>> mayybee 0 (+1) (Just 1)
-- 2
mayybee :: b -> (a -> b) -> Maybe a -> b

۳.

برای مواقعی که فقط یه مقدارِ پشتیبان لازم دارین.

-- >>> fromMaybe 0 Nothing
-- 0
-- >>> fromMaybe 0 (Just 1)
-- 1
fromMaybe :: a -> Maybe a -> a

-- سعی کنین با استفاده از
-- بنویسین maybe کاتامورفیسم

۴.

تبدیلِ لیست به ‏‎Maybe‎‏ و برعکس. 

-- >>> listTMaybe [1, 2, 3]
-- Just 1
-- >>> listToMaybe []
-- Nothing
listToMaybe :: [a] -> Maybe a

-- >>> maybeToList (Just 1)
-- [1]
-- >>> maybeToList Nothing
-- []
maybeToList :: Maybe a -> [a]

۵.

حذفِ مقادیرِ ‏‎Nothing‎‏ از لیستِ ورودی.

-- >>> catMaybes [Just 1, Nothing, Just 2]
-- [1, 2]
-- >>> let xs = take 3 $ repeat Nothing
-- >>> catMaybes xs
-- []
catMaybes :: [Maybe a] -> [a]

۶.

بعداً این تابع رو به اسمِ ‏‎sequence‎‏ می‌بینین.

-- >>> flipMaybe [Just 1, Just 2, Just 3]
-- Just [1, 2, 3] 
-- >>> flipMaybe [Just 1, Nothing, Just 3]
-- Nothing
flipMaybe :: [Maybe a] -> Maybe [a]

یه کتابخونه ِ کوچیک برای ‏‎Either‎‏

هر کدوم از توابعِ زیر رو بنویسین. اگه برای هر تایپ بیشتر از یک تابعِ یکتا وجود داشت، خودتون قضاوت کنین چه کاری باید انجام بده.

۱.

تابعِ زیر رو هرطور خواستین تعریف کنین، ولی سعی کنین بالاخره به جوابی برسین که با ‏‎foldr‎‏ نوشته شده.

lefts' :: [Either a b] -> [a]

۲.

مثلِ تمرینِ قبل. باز هم سعی کنین به ‏‎foldr‎‏ برسین.

rights' :: [Either a b] -> [b]

۳.

partitionEithers' :: [Either a b]
                  -> ([a], [b])

۴.

eitherMaybe' :: (b -> c)
             -> Either a b 
             -> Maybe c

۵.

این تابع یه کاتامورفیسم ِ عمومی برای مقادیرِ ‏‎Either‎‏ ِه.

either' :: (a -> c)
        -> (b -> c) 
        -> Either a b 
        -> c

۶.

مثلِ تمرینِ ۴، فقط اینبار با استفاده از ‏‎either'‎‏ که الان تعریف کردین بنویسین.

eitherMaybe'' :: (b -> c) 
              -> Either a b 
              -> Maybe c

بیشترِ توابعی که الان دیدین، در ‏‎Prelude‎‏، ‏‎Data.Maybe‎‏، یا ‏‎Data.Either‎‏ وجود دارن، اما باید سعی کنین بدونِ نگاه کردن به تعاریفِ اونها خودتون بنویسین. اگه تقلب کنین، به خودتون کم‌لطفی کردین.

آنفولد

با اینکه تازه کاتامورفیسم‌ها رو یاد گرفتیم، یه نگاه به دوگان ِ اونها، یعنی آنامورفیسم‌ها بندازیم. با فولد (یا کاتامورفیسم) میشد ساختارهای داده رو تخریب کنیم، در مقابل با آنامورفیسم میشه اونها رو بسازیم. مثلِ فولدها، چند راه برای آنفولد کردنِ یه ساختار داده وجود داره. هم میشه ساختارهای داده‌ی متناهی بسازیم، و هم نامتناهی.

-- مثل یه آنفولدِ محدود iterate تابع
-- می‌مونه که هیچ‌وقت تموم نمیشه
Prelude> :t iterate
iterate :: (a -> a) -> a -> [a]

-- به همین خاطر که تمومی نداره،
-- یه لیست متناهی بگیریم take باید با
Prelude> take 10 $ iterate (+1) 0
[0,1,2,3,4,5,6,7,8,9]

-- جامع‌تره unfoldr تابع
Prelude> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

-- برای unfoldr استفاده از
-- iterate بازنویسی
Prelude> take 10 $ unfoldr (\b -> Just (b, b+1)) 0
[0,1,2,3,4,5,6,7,8,9]

خب چه فایده؟

این همون فایده رو داره که با فولد، خوداتکایی ِ مستقیم رو در تابع‌هایی مثل ‏‎sum‎‏، ‏‎product‎‏، و ‏‎concat‎‏ انتزاعی کردیم.

import Data.List

mehSum :: Num a => [a] -> a
mehSum xs = go 0 xs
  where go :: Num a => a -> [a] -> a
        go n [] = n
        go n (x:xs) = (go (n+x) xs)

niceSum :: Num a => [a] -> a
niceSum = foldl' (+) 0

mehProduct :: Num a => [a] -> a
mehProduct xs = go 1 xs
  where go :: Num a => a -> [a] -> a
        go n [] = n
        go n (x:xs) = (go (n*x) xs) 

niceProduct :: Num a => [a] -> a
niceProduct = foldl' (*) 1

mehConcat :: [[a]] -> [a]
mehConcat xs = go [] xs
  where go :: Num a => a -> [a] -> a
        go xs' [] = xs'
        go xs' (x:xs) = (go (xs' ++ x) xs) 

niceConcat :: [[a]] -> [a]
niceConcat = foldr (++) []

شاید سردرد گرفته باشین، اما شاید هم متوجه شده باشین که اینطور انتزاعی کردنِ الگوهای رایج و اسم دادن به اونها، همونطور که برای فولدها فایده داره برای آنفولدها هم فایده داره.

نسخه‌ی ‏‎iterate‎‏ و ‏‎unfoldr‎‏ ِ خودتون رو بنویسین

۱.

تابعِ ‏‎myIterate‎‏ رو با خوداتکایی ِ مستقیم بنویسین. برای اطمینان از صحت جواب‌تون با ‏‎iterate‎‏ ِ موجود مقایسه کنین. تعریفِ تابعِ ‏‎iterate‎‏ در منبع، یا مثال‌های مشابه‌ش رو نخونین که مجبور شین خودتون حل کنین.

myIterate :: (a -> a) -> a -> [a]
myIterate = undefined

۲.

تابعِ ‏‎myUnfoldr‎‏ رو با خوداتکایی ِ مستقیم بنویسین. برای اطمینان از صحتِ جواب‌تون با ‏‎unfoldr‎‏ ِ موجود مقایسه کنین. باز هم تعاریفِ ‏‎unfoldr‎‏ رو نخونین تا خودتون حل کنین.

myUnfoldr :: (b -> Maybe (a, b))
          -> b
          -> [a]
myUnfoldr = undefined

۳.

تابعِ ‏‎myIterate‎‏ رو با استفاده از ‏‎myUnfoldr‎‏ به اسمِ ‏‎betterIterate‎‏ بازنویسی کنین. یه راهنمایی – بالاتر، از ‏‎unfoldr‎‏ استفاده کردیم تا همون جوابِ ‏‎iterate‎‏ رو بدست بیاریم. همین کار رو با توابع مختلف انجام بدین و ببینین آیا می‌تونین ساختار رو انتزاعی کنین.

-- تایپ جلوی چشم‌تون باشه کمک می‌کنه
-- myUnfoldr :: (b -> Maybe (a, b))
--           -> b
--           -> [a]

betterIterate :: (a -> a) -> a -> [a]
betterIterate f x = myUnfoldr ...?

یادتون باشه که ‏‎betterIterate‎‏ باید همون جوابِ ‏‎iterate‎‏ رو بده.

Prelude> take 10 $ iterate (+1) 0
[0,1,2,3,4,5,6,7,8,9]

Prelude> take 10 $ betterIterate (+1) 0
[0,1,2,3,4,5,6,7,8,9]

بالاخره یه چیزی غیر از لیست!

با ‏‎BinaryTree‎‏ از فصلِ قبل، تمرین‌های زیر رو کامل کنین. اینجا دوباره نوع‌داده رو نوشتیم: 

data BinaryTree a = 
    Leaf
  | Node (BinaryTree a) a (BinaryTree a)
  deriving (Eq, Ord, Show)

۱.

برای ‏‎BinaryTree‎‏ تابعِ ‏‎unfold‎‏ بنویسین.

unfold :: (a -> Maybe (a,b,a))
       -> a
       -> BinaryTree b
unfold = undefined

۲.

یه درخت‌ساز تعریف کنین. با استفاده از تابعِ ‏‎unfold‎‏ که برای ‏‎BinaryTree‎‏ تعریف کردین، تابعِ زیر رو بنویسین:

treeBuild :: Integer -> BinaryTree Integer
treeBuild = undefined

چنین جواب‌هایی باید بده:

Prelude> treeBuild 0
Leaf
Prelude> treeBuild 1
Node Leaf 0 Leaf
Prelude> treeBuild 2
Node (Node Leaf 1 Leaf)
     0
     (Node Leaf 1 Leaf)
Prelude> treeBuild 3
Node (Node (Node Leaf 2 Leaf)
           1
           (Node Leaf 2 Leaf))
     0
     (Node (Node Leaf 2 Leaf) 
           1
           (Node Leaf 2 Leaf))

یا یه جور دیگه نشون بدیم:

    0

    0
   / \
  1   1

    0
   / \
  1   1
 /\   /\
2  2 2  2

آفرین.