Infinite loop when calling many on custom Parser

Question

I'm loosely following Stephen Diehl's Write you a Haskell for implementing my own parser. However, I'm stuck at a point where calls to many and some will go into an infinite loop. I have pinpointed the loop to my parser's fmap function using trace, but I can't figure out why the loop is occurring. Looking at the source for some and many, it seems that the only other functions that are called are <*> (through liftA2), pure and <|>; I've tried putting calls to trace on all of those, but none of those show up on stdout.

The essential parts of my parser look like this:

data Parser a = Parser { runParser :: String -> [(a, String)] }

item :: Parser Char
item = trace "item" Parser $ \s ->
  case s of
    [] -> []
    (x:xs) -> pure (x, xs)

instance Functor Parser where
  fmap f (Parser p) = trace "fmap" Parser $ fmap (first f) . p

instance Applicative Parser where
  (Parser p1) <*> (Parser p2) = trace "<*>" Parser $ 
    \s1 -> [(f x, s3) | (f, s2) <- p1 s1, (x, s3) <- p2 s2]
  pure x = trace "pure" Parser $ \s -> pure (x, s)


instance Alternative Parser where
  empty = trace "empty" Parser $ const mempty
  (Parser p1) <|> (Parser p2) = trace "<*>" Parser $ \s -> case p1 s of
    [] -> p2 s
    x  -> x

Calling many or some shows the following output:

> runParser (many item) "abcd"
item
fmap
fmap
fmap
(and so forth)

As far as I can tell, my functions are correctly implemented. Why would this infinite loop on fmap occur?