list - How do I create an applicative instance for ziplist? -

i want implement instance of applicative custom list.

import test.quickcheck import test.quickcheck.checkers import test.quickcheck.classes   data list =   nil   | cons (list a)   deriving (eq, show)  instance eq => eqprop (list a) (=-=) = eq  instance functor list   fmap _ nil = nil   fmap f (cons nil) = (cons (f a) nil)   fmap f (cons as) = (cons (f a) (fmap f as))  main =   let trigger = undefined :: list (int, string, int)   quickbatch $ applicative trigger   instance arbitrary => arbitrary (list a)    arbitrary = sized go     go 0 = pure nil           go n =             xs <- go (n - 1)             x  <- arbitrary             return (cons x xs)  instance applicative list   pure x = (cons x nil)   nil <*> _ = nil   _ <*> nil = nil  (cons f fs) <*> (cons as) = (cons (f a) (fs <*> as)) 

this gives 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 id law failing:

λ> cons id nil <*> cons 0 (cons (-1) nil) cons 0 nil 

how fix this? pure takes a not list a not see how match on list , preserve nested list structure.

the composition law fails not strange:

λ> (cons "b" nil) <*> (cons "c" nil)  <interactive>:295:7:     couldn't match expected type ‘[char] -> b’                 actual type ‘[char]’     relevant bindings include       :: list b (bound @ <interactive>:295:1)     in first argument of ‘cons’, namely ‘"b"’     in first argument of ‘(<*>)’, namely ‘(cons "b" nil)’     in expression: (cons "b" nil) <*> (cons "c" nil) 

edit: since got great answers implementing applicative ziplists, have changed question ziplists.

for ziplist-like approach expect following left-identity hold:

pure id <*> somelist = somelist 

for this, pure cannot return single-element list, since stop immediately:

(cons id nil) <*> cons 1 (cons 2 nil)   = cons (id 1) (nil <*> cons 2 nil)   = cons 1 nil 

which isn't expected result left-identity. if pure cannot return single element list, how many should return? answer is: infinite:

repeatlist :: -> list repeatlist x = let c = cons x c in c 

why did call ziplist approach? because it's same behaviour in control.applicative.ziplist, can motivated zipwith:

zipwithlist :: (a -> b -> c) -> list -> list b -> list c zipwithlist f (cons x xs) (cons y ys) = cons (f x y) (zipwithlist f xs ys) zipwithlist _ _           _           = nil 

now instance is

instance applicative list   pure  = repeatlist   (<*>) = zipwithlist ($) 

however, checkers cannot check instance either due eqprob instance, since pure f <*> pure x == pure (f x) (homomorphism) results in check on infinite lists. can provide alternative one, though. example, can take arbitrary number of elements , compare them:

prop_samelist :: eq => (int, int) -> list -> list -> property prop_samelist bounds xs ys = forall (choose bounds) $ \n ->    takelist n xs `eq` takelist n ys  takelist :: int -> list -> list takelist _ nil = nil takelist n (cons x xs)  | n <= 0    = nil  | otherwise = cons x (takelist (n - 1) xs) 

then, if want compare @ least 1000 , @ 10000 elements, can use:

instance eq => eqprob (list a)   (=-=) = prop_samelist (1000, 10000) 

after all, we're trying find list our property not hold.