Understanding function with <|> operator

Question

I have the following type:

newtype Rep f a = Rep { runRep :: String -> f (String, a) }

The type Rep f a is a stateful computation that takes a String as the initial state and produces a (String, a) as the result of the computation. The result of the computation is wrapped in the functor f.

The Applicative instance for Rep is the following:

instance Monad f => Applicative (Rep f) where 
    pure x = Rep $ \s -> pure (s, x)
    Rep f <*> Rep x = Rep $ \s -> do 
        (s',rf)  <- f s 
        (s'',rx) <- x s'
        return (s'', rf rx)

And the Monad instance for Rep is the following:

instance Monad f => Monad (Rep f) where 
   return x = pure x 
   Rep a >>= f = Rep $ \s -> do
      (s', ya) <- a s
      let (Rep f') = f ya
      (s'', yf) <- f' s'
      pure (s'', yf)

The Alternative instance for Rep is the following:

instance (Monad f, Alternative f) => Alternative (Rep f) where 
    empty = Rep (const empty)
    Rep a <|> Rep b = Rep $ \s -> a s <|> b s

I have the following data types and function:

data TD = Empty | Fol TD TD | Letters [Char] | Str TD
data Res = Nil | Character Char | Cop Res Res | Special [Res]

findmatch :: (Monad f, Alternative f) => TD -> Rep f Res

findmatch (Str a) =
   frontAdd <$> findmatch a <*> findmatch (Str a)
   <|> pure (Special [])
      where
      frontAdd x (Special xs) = Special (x:xs)
      frontAdd _ _ = error "Not possible."

I am having trouble understanding the function above. The function frontAdd creates a Special value which contains a list of [Res]. findmatch returns Rep f Res. The line frontAdd <$> findmatch a <*> findmatch (Str a) applies frontAdd to the Res that is returned by findmatch a and findmatch (Str a).

However, I am not sure how this line, with the pattern matching, works: frontAdd x (Special xs) = Special (x:xs). Further, assuming that the functor f is [ ], how would the <|> in frontAdd <$> findmatch a <*> findmatch (Str a) <|> pure (Special []) work? I know that if the functor f is Maybe, then <|> makes a left-biased choice, but I don't know how <|> works specifically for lists. In the documentation it states:

instance Alternative [] where
  empty = []
  (<|>) = (++) -- length xs + length ys = length (xs ++ ys)

How exactly does the concatenation work? Am I correct in saying that the result of frontAdd <$> findmatch a <*> findmatch (Str a) is concatenated with the empty list?

Any insights are appreciated.

Answer 1

First, if f is [], then pure (Special []) is [(Special [])], which is just [Special []].

Second, list concatenation is the most natural thing, with

  [a, b, c, d, ...]  ++  [p, q, r, s, ...]
==
  [a, b, c, d, ...   ,    p, q, r, s, ...]

i.e.

(x:xs) ++ ys  =  x : (xs ++ ys)
[]     ++ ys  =             ys

which is to say,

   xs  ++ ys  =  foldr (:) ys xs

Thus

  [a, b, c]  <|>  [Special []]
==
  [a, b, c,        Special []]

and

  []         <|>  [Special []]
==
  [                Special []]

So no, <|> pure (Special []) does not concatenate with the empty list, but rather with a list of a Special wrapping the empty list.