I want to implement an instance of Applicative for my custom list.
import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes
data List a =
Nil
| Cons a (List a)
deriving (Eq, Show)
instance Eq a => EqProp (List a) where (=-=) = eq
instance Functor List where
fmap _ Nil = Nil
fmap f (Cons a Nil) = (Cons (f a) Nil)
fmap f (Cons a as) = (Cons (f a) (fmap f as))
main = do
let trigger = undefined :: List (Int, String, Int)
quickBatch $ applicative trigger
instance Arbitrary a => Arbitrary (List a) where
arbitrary = sized go
where go 0 = pure Nil
go n = do
xs <- go (n - 1)
x <- arbitrary
return (Cons x xs)
instance Applicative List where
pure x = (Cons x Nil)
Nil <*> _ = Nil
_ <*> Nil = Nil
(Cons f fs) <*> (Cons a as) = (Cons (f a) (fs <*> as))
This gives the following bugs:
λ> main
applicative:
identity: *** Failed! Falsifiable (after 3 tests):
Cons 0 (Cons (-1) Nil)
composition: *** Failed! Falsifiable (after 3 tests):
Cons <function> (Cons <function> Nil)
Cons <function> (Cons <function> Nil)
Cons 1 (Cons (-2) Nil)
homomorphism: +++ OK, passed 500 tests.
interchange: +++ OK, passed 500 tests.
functor: *** Failed! Falsifiable (after 3 tests):
<function>
Cons (-2) (Cons (-1) Nil)
First is the id law is failing:
λ> Cons id Nil <*> Cons 0 (Cons (-1) Nil)
Cons 0 Nil
How do I fix this? pure takes an a not a List a so I do not see how to match on List and preserve the nested list structure.
The composition law also fails which is not strange:
λ> (Cons "b" Nil) <*> (Cons "c" Nil)
<interactive>:295:7:
Couldn't match expected type ‘[Char] -> b’
with actual type ‘[Char]’
Relevant bindings include
it :: List b (bound at <interactive>:295:1)
In the first argument of ‘Cons’, namely ‘"b"’
In the first argument of ‘(<*>)’, namely ‘(Cons "b" Nil)’
In the expression: (Cons "b" Nil) <*> (Cons "c" Nil)
Edit: since I got great answers implementing applicative for ziplists, I have changed the question to be about ziplists.