list - 用<|>运算符了解功能

我有以下类型：

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

类型Rep f a是有状态计算，将String作为初始状态，并产生(String, a)作为计算结果。计算结果包装在函子f中。

Rep的适用实例如下：

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)

Rep的Monad实例如下：

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)

Rep的Alternative实例如下：

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

我具有以下数据类型和功能：

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."

我在理解上面的功能时遇到了麻烦。函数frontAdd创建一个Special值，其中包含[Res]的列表。 findmatch返回Rep f Res。 frontAdd <$> findmatch a <*> findmatch (Str a)行将frontAdd应用于Res和findmatch a返回的findmatch (Str a)。

但是，我不确定具有模式匹配的这一行如何工作：frontAdd x (Special xs) = Special (x:xs)。此外，假设函子f是[ ]，<|>中的frontAdd <$> findmatch a <*> findmatch (Str a) <|> pure (Special [])将如何工作？我知道如果函子f是Maybe，那么<|>会做出左偏选择，但是我不知道<|>如何专门用于列表。在文档中指出：

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

串联究竟如何工作？我是否正确地说frontAdd <$> findmatch a <*> findmatch (Str a)的结果与空列表连接在一起？

任何见解均表示赞赏。

最佳答案

首先，如果f是[]，则pure (Special [])是[(Special [])]，即[Special []]。

其次，列表串联是最自然的事情，

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

即

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

就是说

   xs  ++ ys  =  foldr (:) ys xs

从而

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

和

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

因此，不，<|> pure (Special [])不与空列表连接，而是与Special的列表包装空列表。