instance Functor Parsa where
  fmap u (Parsa runner) =
    Parsa $ \input -> do
      (input2, x) <- runner input
      Solo (input2, u x)

instance Applicative Parsa where
  pure a = Parsa $ \s -> Solo (s, a)
  (<*>) (Parsa f) (Parsa x) = Parsa qux
    where
      qux = \s -> do
        (s2, y) <- x s
        (s3, z) <- f s2
        Solo (s3, z y)

instance Monad Parsa where
  (>>=) (Parsa x) f = Parsa quux
    where
      quux = \s -> do
        (s2, y) <- x s
        (s3, z) <- runParsa (f y) s2
        Solo (s3, z)
  return x = Parsa (\s -> Solo (s, x))