۱۷ - ۸مانویدِ ZipList

مانوید ِ پیش‌فرض برای لیست در ‏‎Prelude‎‏، الحاق ِه، اما یه راه دیگه برای ترکیب ِ مانویدی ِ لیست‌ها وجود داره. ‏‎mappend‎‏ ِ پیش‌فرض برای لیست این کار رو می‌کنه:

[1, 2, 3] <> [4, 5, 6]

-- تبدیل میشه به

[1, 2, 3] ++ [4, 5, 6]

[1, 2, 3, 4, 5, 6]

اما مانوید ِ ‏‎ZipList‎‏ مقادیرِ لیست رو به صورتِ موازی، با استفاده از مانوید ِ خودشون ترکیب می‌کنه:

[1, 2, 3] <> [4, 5, 6]

-- تبدیل میشه به

[
  1 <> 4
, 2 <> 5
, 3 <> 6
]

احتمالاً یادِ توابعی مثلِ ‏‎zip‎‏ یا ‏‎zipList‎‏ انداخته‌تون.

اگه بخوایم مثالِ بالا کار کنه، می‌تونیم یه تایپی مثلِ ‏‎Sum Integer‎‏ برای مقادیرِ ‏‎Num‎‏ تعیین کنیم تا ‏‎Monoid‎‏ داشته باشن.

Prelude> import Data.Monoid
Prelude> 1 <> 2

No instance for (Num a0) arising
  from a use of ‘it’
The type variable ‘a0’ is ambiguous
Note: there are several potential
  instances:
  ... Num شلوغی مرتبط با ...

Prelude> 1 <> (2 :: Sum Integer)
Sum {getSum = 3}

‏‎Prelude‎‏ اون ‏‎Monoid‎‏ رو نداره، پس خودمون باید تعریف کنیم:

module Apl1 where

import Control.Applicative
import Data.Monoid
import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes

چندتا نمونه ِ یتیم و مظلوم اینجا تعریف کردیم. برای کُدی که می‌خواین نگه دارین یا منتشر کنین اینطوری ننویسین.

-- این درست کار نمی‌کنه

instance Monoid a
      => Monoid (ZipList a) where
  mempty  = ZipList []
  mappend = liftA2 mappend


instance Arbitrary a
      => Arbitrary (ZipList a) where
  arbitrary = ZipList <$> arbitrary

instance Arbitrary a
      => Arbitrary (Sum a) where
  arbitrary = Sum <$> arbitrary

instance Eq a
      => EqProp (ZipList a) where
  (=-=) = eq

اگه این رو بیاریم تو REPL و صحت‌ش برای ‏‎Monoid‎‏ رو تست کنیم، شکست می‌خوره:

Prelude> let zl = ZipList [1 :: Sum Int]
Prelude> quickBatch $ monoid zl

monoid:
  left  identity: 
   *** Failed! Falsifiable (after 3 test):
ZipList [ Sum {getSum = -1} ]
  right identity:
   *** Failed! Falsifiable (after 4 tests):
ZipList [ Sum {getSum = -1}
        , Sum {getSum = 3}
        , Sum {getSum = 2} ]
  associativity:  +++ OK, passed 500 tests.

مشکل اینه که ‏‎ZipList‎‏ ِ خالی، صفر ِه نه همانی!

صفر و همانی

-- صفر
n * 0 == 0

-- همانی
n * 1 == n

خوب حالا همانی ِ ‏‎ZipList‎‏ چی میشه؟

Sum 1 `mappend` ??? -> Sum 1

instance Monoid a
      => Monoid (ZipList a) where
  mempty  = pure mempty
  mappend = liftA2 mappend

وقتی خودتون برای ‏‎ZipList‎‏ نمونه ِ ‏‎Applicative‎‏ بنویسین، متوجهِ نقشِ ‏‎pure‎‏ در اینجا میشین.

تمرینِ اپلیکتیو ِ ‏‎List‎‏

برای ‏‎List‎‏ نمونه ِ ‏‎Applicative‎‏ بنویسین. حداقل متود‌های لازم برای ‏‎Applicative‎‏ که باید تعریف کنین، ‏‎pure‎‏ و ‏‎<*>‎‏ هستن. یه کم راهنمایی می‌کنیم. با کتابخونه ِ checkers نمونه ِ ‏‎Applicative‎‏ ِتون رو تست کنین.

data List a =
    Nil
  | Cons a (List a)
  deriving (Eq, Show)

‏‎Functor‎‏ای که برای ‏‎List‎‏ نوشتین رو به خاطر بیارین:

instance Functor List where
  fmap = undefined

نمونه ِ ‏‎Applicative‎‏ هم مشابهِ همونه:

instance Applicative List where
  pure = undefined
  (<*>) = undefined

نتیجه‌ی مورد نظر:

Prelude> let f = Cons (+1) (Cons (*2) Nil)
Prelude> let v = Cons 1 (Cons 2 Nil)
Prelude> f <*> v
Cons 2 (Cons 3 (Cons 2 (Cons 4 Nil)))

اگه گیر کردین، از تابع‌ها و راهنمایی‌های زیر استفاده کنین.

append :: List a -> List a -> List a
append Nil ys = ys
append (Cons x xs) ys =
  Cons x $ xs `append` ys

fold :: (a -> b -> b) -> b -> List a -> b
fold _ b Nil        = b
fold f b (Cons h t) = f h (fold f b t)

concat' :: List (List a) -> List a
concat' = fold append Nil

-- concat' این رو با
-- تعریف کنین fmap و
flatMap :: (a -> List b)
        -> List a
        -> List b
flatMap f as = undefined

با استفاده از کُدهای بالا، سعی کنین بدونِ تطبیقِ الگو ِ صریح روی سلول‌های cons از ‏‎flatMap‎‏ و ‏‎fmap‎‏ استفاده کنین. ولی حالت‌های ‏‎Nil‎‏ رو باید تطبیق الگو کنین.

تابع ‏‎flatMap‎‏ ساده‌تر از چیزیه که به نظر میرسه. این کار رو می‌کنه: "‏‎fmap‎‏، بعد لِه."

Prelude> fmap (\x -> [x, 9]) [1, 2, 3]
[[1,9],[2,9],[3,9]]

Prelude> let toMyList = foldr Cons Nil
Prelude> let xs = toMyList [1, 2, 3]
Prelude> let c = Cons

Prelude> let f x = x `c` (9 `c` Nil)
Prelude> flatMap f xs
Cons 1 (Cons 9 (Cons 2
        (Cons 9 (Cons 3 (Cons 9 Nil)))))

برخلافِ ‏‎Functor‎‏‌ها، تضمینی برای یکتا بودنِ نمونه‌های ‏‎Applicative‎‏ نیست.

تمرینِ اپلیکتیو ِ ‏‎ZipList‎‏

برای ‏‎ZipList‎‏ نمونه‌ ِ ‏‎Applicative‎‏ بنویسین. بعد هم با کتابخونه checkers، نمونه ِ ‏‎Applicative‎‏ ِتون رو تست کنین. نمونه ِ ‏‎EqProp‎‏ رو براتون تعریف کردین (یه کم عجیب‌غریب‌ه... کمی جلوتر توضیح میدیم).

data List a =
    Nil
  | Cons a (List a)
  deriving (Eq, Show)

take' :: Int -> List a -> List a
take' = undefined

instance Functor List where
  fmap = undefined

instance Applicative List where
  pure = undefined
  (<*>) = undefined


newtype ZipList' a =
  ZipList' (List a)
  deriving (Eq, Show)

instance Eq a => EqProp (ZipList' a) where
  xs =-= ys = xs' `eq` ys'
    where xs' = let (ZipList' l) = xs
                in take' 3000 l
          ys' = let (ZipList' l) = ys
                in take' 3000 l

instance Functor ZipList' where
  fmap f (ZipList' xs) =
    ZipList' $ fmap f xs

instance Applicative ZipList' where
  pure = undefined
  (<*>) = undefined

ایده‌ی کلی اینه که یه لیست از تابع‌ها و یه لیست از مقادیر رو بذاریم روی هم، طوری که تابعِ اول به مقدار اول اعمال شه، تابع دوم به مقدار دوم، و الی آخر. این نمونه باید با لیست‌های بینهایت کار کنه. چندتا مثال:

Prelude> let zl' = ZipList'
Prelude> let z = zl' [(+9), (*2), (+8)]
Prelude> let z' = zl' [1..3]
Prelude> z <*> z'
ZipList' [10,4,11]
Prelude> let z' = zl' (repeat 1)
Prelude> z <*> z'
ZipList' [10,2,9]

دقت کنین که ‏‎z'‎‏ ِدوم یه لیستِ بینهایت‌ه. تو ‏‎Prelude‎‏ دنبال تابع‌هایی بگردین که راهنمایی‌تون کنن. اسمِ یکی از این تابع‌ها با ‏‎z‎‏ شروع میشه، یکی دیگه‌شون با ‏‎r‎‏. چون از تایپِ لیستِ ‏‎Prelude‎‏ استفاده نمی‌کنین، این تابع‌ها فقط نقش راهنمایی می‌تونن داشته باشن.

توضیح و توجیهِ اون ‏‎EqProp‎‏ ِعجیب

چنین چیزی ناشی از تستِ تساوی بین لیست‌های بینهایت‌ه... یعنی شدنی نیست. اگه با یه نمونه ِ ‏‎EqProp‎‏ معمولی، هومومورفیسم ِ نمونه ِ ‏‎Applicative‎‏ ِتون رو تست کنین، تا ابد لیست‌های بینهایت رو طی می‌کنه. نتیجه‌ای که از ‏‎QuickCheck‎‏ می‌گیریم، کلاً "به اندازه‌ی کافی،" صحت رو نشون میده؛ پس بررسیِ تعدادِ زیادی از المان‌های لیست (در این مورد ۳۰۰۰ تا) بجای کلِ لیست بینهایت، با طرز کارِ ‏‎QuickCheck‎‏ هم‌راستا ِه. اگه حرف ما رو باور نمی‌کنین، بیانیه‌ی زیر رو توی REPL امتحان کنین.

repeat 1 == repeat 1

اپلیکتیو ِ ‏‎Either‎‏ و ‏‎Validation‎‏

باز میریم سراغ تایپ‌ها:

اختصاصی‌سازی تایپ‌ها

-- f ~ Either e

type E = Either
  (<*>) ::   f (a -> b) ->   f a ->   f b
  (<*>) :: E e (a -> b) -> E e a -> E e b

pure :: a ->   f a
pure :: a -> E e a

مقایسه‌ی ‏‎Either‎‏ و ‏‎Validation‎‏

معمولاً مانوید، بخش جذابِ یه ‏‎Applicative‎‏ ِه. ولی باعث میشه همونطور که برای یه نوع‌داده میشه چندتا ‏‎Monoid‎‏ ِ معتبر داشت، چندتا ‏‎Applicative‎‏ ِ معتبر و قانونمند هم میشه داشت (بر خلافِ ‏‎Functor‎‏).

در زیر اپلیکتیو ِ ‏‎Either‎‏ رو با چندتا مثال نشون دادیم:

Prelude> pure 1 :: Either e Int
Right 1

Prelude> Right (+1) <*> Right 1
Right 2
Prelude> Right (+1) <*> Left ":("
Left ":("
Prelude> Left ":(" <*> Right 1
Left ":("
Prelude> Left ":(" <*> Left "sadface.png"
Left ":("

قبلاً مزایای ‏‎Either‎‏ رو گفتیم، و نشون دادیم که چطور اپلیکتیو ِ ‏‎Maybe‎‏ می‌تونه کمک کنه کُدمون رو تروتمیزتر بنویسیم، پس دیگه تکرار نمی‌کنیم. یه جایگزین برای ‏‎Either‎‏ هست، به اسمِ ‏‎Validation‎‏، که تنها تفاوت‌ش در نمونه ِ ‏‎Applicative‎‏ ِشه:

data Validation err a where
    Failure err
  | Success a
  deriving (Eq, Show)

این نوع‌داده دقیقاً عینِ ‏‎Either‎‏ ِه، حتی یه جفت تابع هم داریم که می‌تونن مقادیر این دو تایپ رو به هم تبدیل کنن. یادتون هست تبدیلات طبیعی رو گفتیم؟ هردوی این تابع‌ها تبدیلات طبیعی هستن:

validToEither :: Validation e a
              -> Either e a 
validToEither (Failure err) = Left err
validToEither (Success a) = Right a

eitherToValid :: Either e a
              -> Validation e a 
eitherToValid (Left err) = Failure err
eitherToValid (Right a) = Success a

eitherToValid . validToEither == id
validToEither . eitherToValid == id

خوب ‏‎Validation‎‏ چه فرقی داره؟ اساساً فرق‌ش در کاریه که نمونه ِ ‏‎Applicative‎‏ ِش با خطاها می‌کنه. در مواقعی که دوتا مقدار خطا وجود دارن، بجای اتصال کوتاه، از تایپکلاسِ ‏‎Monoid‎‏ برای ترکیب‌شون استفاده می‌کنه. این کار معمولاً با یه لیست یا مجموعه‌ای از خطاها انجام میشه، ولی هرکاری که دوست دارین می‌تونین انجام بدین.

data Errors =
    DividedByZero
  | StackOverflow
  | MooglesChewedWires
  deriving (Eq, Show)

success =   Success (+1)
        <*> Success 1

success == Success 2

failure =   Success (+1)
        <*> Failure [StackOverflow]

failure == Failure [StackOverflow]

failure' =   Failure [StackOverflow]
         <*> Success (+1)

failure' == Failure [StackOverflow] 

failures =   Failure [MooglesChewedWires]
         <*> Failure [StackOverflow]

failures == Failure [MooglesChewedWires
                   , StackOverflow]

در مقدارِ ‏‎failures‎‏، تمایز بینِ ‏‎Either‎‏ و ‏‎Validation‎‏ رو می‌بینیم: حالا میشه همه‌ی شکست‌هایی که اتفاق افتادن رو نگه داریم، نه فقط اولی رو.

تمرین: تنوع‌های ‏‎Either‎‏

‏‎Validation‎‏ در ظاهر مثلِ ‏‎Either‎‏ ارائه میشه، اما ممکنه تفاوت‌هایی داشته باشه. ‏‎Functor‎‏ ِش رفتار یکسانی داره، اما ‏‎Applicative‎‏ ِش فرق می‌کنه. از مثالِ بالا رفتارِ ‏‎Validation‎‏ رو ببینین. با کتابخونه ِ checkers تست کنین.

data Validation e a where
    Failure e
  | Success a
  deriving (Eq, Show)

-- Either عینِ
instance Functor (Validation e) where
  fmap = undefined

-- این فرق می‌کنه
instance Monoid e =>
         Applicative (Validation e) where
  pure  = undefined
  (<*>) = undefined