使用 <|> 运算符理解函数

Question

我有以下类型：

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 的替代实例如下：

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] 的列表。 findmatchreturnsRep f Res。 frontAdd <$> findmatch a <*> findmatch (Str a) 行将 frontAdd 应用于 findmatch a 和 findmatch (Str a).

返回的 Res

但是，我不确定这一行与模式匹配如何工作：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) 的结果与空列表连接是否正确？

如有任何见解，我们将不胜感激。

Answer 1

首先，如果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 列表连接。

使用 <|> 运算符理解函数

Understanding function with <|> operator

monads

haskell

list

concatenation

alternative-functor