Как правильно выполнить рекурсивный анализ?

У меня есть такой код:

-- my parser, takes a function that takes a string and gives 
-- the suffix and the answer
data Parser a = MkParser (String -> Maybe (String, a))

unParser :: Parser a -> String -> Maybe (String, a)
unParser (MkParser sf1) = sf1

-- gives `a` as the answer, never fails, doesn't change input string
pure :: a -> Parser a
pure a = MkParser (\inp -> Just (inp, a))

-- Choice... if pa fails, try pa2
(<|>) :: Parser a -> Parser a -> Parser a
MkParser sf1 <|> p2 = MkParser g
  where
    g inp = case sf1 inp of
              Nothing -> unParser p2 inp
              j -> j        -- the Just case

-- | 0 or more times, collect the answers into a list.
many :: Parser a -> Parser [a]
many p = some p <|> pure []
-- Explanation: To repeat 0 or more times, first try 1 or more
-- times!  If that fails, then we know it's 0 times, and the answer is the
-- empty list.

-- | 1 or more times, collect the answers into a list.
some :: Parser a -> Parser [a]
some p = liftA2 (:) p (many p)
-- Explanation: To repeat 1 or more times, do 1 time, then 0 or more times!

liftA2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
liftA2 op (MkParser sf1) p2 = MkParser g
  where
    g inp = case sf1 inp of
              Nothing -> Nothing
              Just (middle, a) ->
                  case unParser p2 middle of
                    Nothing -> Nothing
                    Just (rest, b) -> Just (rest, op a b)

и я тестирую код с помощью этого базового парсера, который просто дает успех, если это то char, которое я ищу:

char :: Char -> Parser Char
char wanted = MkParser sf
  where
    sf (c:cs) | c == wanted = Just (cs, c)
    sf _ = Nothing

Для запуска парсеров я использую это

runParser :: Parser a -> String -> Maybe a
runParser (MkParser sf) inp = case sf inp of
                                Nothing -> Nothing
                                Just (_, a) -> Just a

Теперь я делаю runParser (many (char '!')) "testing" и получаю Just "".

Я пытаюсь пройти через код. Сначала (many (char '!')) звонит some (char '!').

Это вызывает liftA2 (:) p (many p). И вот many p звонит liftA2 (:) p (many p) снова. Это повторяется бесконечно, верно? Я новичок в Haskell, но предполагаю, что из-за ленивых вычислений он в конечном итоге пытается вычислить p?. runParser (char '!') "testing" дает Nothing, следовательно, первый liftA2 (:) p (many p) тоже дает Nothing, верно? Это переходит ко второму случаю some p <|> pure [] и pure [] дает Just []. Поэтому ответ должен быть Just [].

Но ответ, который я получаю, когда бегу runParser (many (char '!')) "Testing", — Just "". Откуда взялся ""?

Связанный: Правильны ли эти шаги?

many (char '!') = some (char '!') <|> pure []
-- calls some p
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- here, it ways for the third argument of liftA2, or does it
-- start trying to run liftA2 with the second argument?
-- (many (char '!')) calls this:
many (char '!') = some (char '!') <|> pure []
-- which then again calls 
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- so now it looks like this:
liftA2 (:) (char '!') ( liftA2 (:) (char '!') (many (char '!')) )
-- When does it start evaluating? 
-- Because `(many (char '!')` can't technically run because
-- it needs to wait for the third argument of 
liftA2 (:) (char '!') (many (char '!'))
-- which never gives an answer since it keeps recursing right?

Если бы мне пришлось гадать:

many (char '!') = some (char '!') <|> pure []
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- run `liftA2 (:) (char '!')`, get `Nothing`
-- go to the second choice of <|>
<|> pure []
-- give Just []
Just []

Это правильно?

Еще 1 изменение: (Извините, мне следовало добавить эти вопросы в исходное сообщение, но, поскольку все они связаны, я не хочу создавать еще один вопрос)

Если я сделаю

runParser (many (char '!')) "!esting"

Шаги:

(many (char '!'))
many p = some p <|> pure []
-- calls `some p`
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- the first `char !` (second argument) runs, and it is a success.
-- the success gives Just ("esting", '!') to the third
-- argument of liftA2.
-- Now it goes to the third argument of liftA2, which is
(many (char '!')
-- which calls
many p = some p <|> pure [] -- but the string is "esting"
-- this calls
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- the string is "esting"
-- this fails, so it tries the second choice of
some p <|> pure []
-- which is `pure []` which just gives []

-- Now we go back to the first
liftA2 (:) (char '!') (many (char '!'))
-- where the first answer is '!' and the second answer is '[]'
-- and it combines it with `:`. So we have
-- Just ("sting", '!' : '[]')