Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to make a proper "pure" for an Applicative instance?

I've found out that there are at least 2 realizations of pure for this Applicative instance, that follow all the laws (Identity, Homomorphism, Interchange, Composition). Is one of them still wrong?

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

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

instance Applicative ZipList' where 
  ZipList' fss <*> ZipList' xss = ZipList' $ applicate fss xss
    where applicate (Cons f fs) (Cons x xs) = Cons (f x) (applicate fs xs)
          applicate Nil         _           = Nil
          applicate _           Nil         = Nil
pure x = ZipList' (Cons x Nil)

or

pure a = ZipList' as
  where as = Cons a as
like image 941
kirill fedorov Avatar asked Dec 14 '22 09:12

kirill fedorov


1 Answers

For the first pure, the identity law does not hold. Indeed, this law says that:

pure id <*> v = v

This thus means that:

ZipList' (Cons id Nil) <*> v = v

for all vs. But that does not hold. Say that v = ZipList' (Cons 1 (Cons 2 Nil)), so basically a list [1,2]. Then one expects that:

ZipList' (Cons id Nil) <*> ZipList' (Cons 1 (Cons 2 Nil)) = ZipList' (Cons 1 (Cons 2 Nil))

If we however evaluate your implementation for Applicative, we see that:

ZipList' (Cons id Nil) <*> ZipList' (Cons 1 (Cons 2 Nil))
    = ZipList' (applicate (Cons id Nil) (Cons 1 (Cons 2 Nil)))
    = ZipList' (Cons (id 1) (applicate Nil (Cons 2 Nil)))
    = ZipList' (Cons 1 Nil)

But this is not what we expect for the identity law, since here we obtain a ZipList' that basically is [1], whereas it should be [1,2].

like image 152
Willem Van Onsem Avatar answered Jan 09 '23 18:01

Willem Van Onsem