Implementing `Applicative Cons`

Question

Given the following definition:

data Cons a = Cons a (Cons a) 
             | Empty 
             deriving Show

I implemented the following attempt at its Applicative instance:

instance Applicative Cons where
    pure x               = Cons x Empty
    Empty <*> _          = Empty       
    (Cons g gs) <*> x    = append (fmap g x) (gs <*> x)

append :: Cons a -> Cons a -> Cons a
append Empty x           = x
append x Empty           = x
append (Cons x Empty) ys = Cons x ys
append (Cons x xs) ys    = Cons x (append xs ys)

Please review this implementation - for correctness and whether it's idiomatic/verbose, etc.

Answer 1

As for being idiomatic, the only thing I'd change is the use of the variable g to f. Using g when f is available as a name is like using y when x is available.

There is significant redundancy in append, though. A sufficient implementation looks like this:

append :: Cons a -> Cons a -> Cons a
append Empty x           = x
append (Cons x xs) ys    = Cons x (append xs ys)

You could argue that your second pattern was an optimization in the case that the second list is empty, but the tradeoff is adding O(n) overhead every time the second list isn't empty. There's a reason (++) doesn't do that check for [a]. The third case was pure overhead, and always an improvement to remove.