haskell - 应用函子更有趣

Question

之前我问过翻译一元代码以仅使用 Parsec 的应用函子实例。不幸的是，我收到了几个答复，这些答复回答了我真正提出的问题，但并没有真正给我太多的见解。所以让我再试一次......

总结我到目前为止的知识，应用函子比单子更受限制。在“少即是多”的传统中，限制代码可以做的事情增加了疯狂代码操作的可能性。无论如何，很多人似乎认为使用 applicative 代替 monad 是一个可能的更好的解决方案。

该类Applicative在中定义Control.Applicative，其 Haddock 的列表有助于将类方法和实用程序函数与它们之间的大量类实例分开，从而难以同时快速查看屏幕上的所有内容。但是相关的类型签名是

pure ::    x              -> f x
<*>  :: f (x -> y) -> f x -> f y
 *>  :: f  x       -> f y -> f y
<*   :: f  x       -> f y -> f x
<$>  ::   (x -> y) -> f x -> f y
<$   ::    x       -> f y -> f x

完全有道理，对吧？

嗯，Functor已经给我们了fmap，基本上就是<$>。即，给定一个函数 from xto y，我们可以将 an 映射f x到 an f y。Applicative添加了两个本质上新的元素。一个是，它与（以及各种范畴论类中的其他几个运算符）pure具有大致相同的类型。return另一个是<*>，它使我们能够获取一个函数容器和一个输入容器，并产生一个输出容器。

使用上面的运算符，我们可以非常巧妙地做一些事情，比如

foo <$> abc <*> def <*> ghi

这允许我们采用 N 元函数并从 N 个函子中获取其参数，这种方式很容易推广到任何 N。

这点我已经明白了。有两件主要的事情我还不明白。

首先，*>函数<*和<$。从它们的类型来看<* = const，*> = flip const、和<$可能是相似的。大概这并没有描述这些功能实际上做了什么。（？？！）

其次，在编写 Parsec 解析器时，每个可解析实体通常最终看起来像这样：

entity = do
  var1 <- parser1
  var2 <- parser2
  var3 <- parser3
  ...
  return $ foo var1 var2 var3...

由于应用函子不允许我们以这种方式将中间结果绑定到变量，我对如何为最后阶段收集它们感到困惑。为了理解如何做到这一点，我一直无法完全围绕这个想法。

score 26 · Accepted Answer

和函数非常简单：它们的工作方式<*与. 的工作方式与except不存在相同。基本上，给定，您首先“做” ，然后“做”并返回. 对于，您仍然先“做” ，然后“做” ，但您返回的结果。（当然，对于“do”的适当含义。）*>>><*<<<<a *> babba <* baba

功能<$只是. fmap const所以a <$ b等于fmap (const a) b。您只需丢弃“动作”的结果并返回一个常量值。具有类型的Control.Monad函数可以写成。voidFunctor f => f a -> f ()() <$

这三个函数不是应用函子定义的基础。( <$, 事实上, 适用于任何函子。) 这又一次, 就像>>单子一样。我相信他们在课堂上可以更轻松地针对特定实例优化它们。

当您使用应用函子时，您不会从函子中“提取”值。在 monad 中，这是做什么>>=的，也是foo <- ...去糖的。相反，您将包装的值直接使用<$>and传递给函数<*>。因此，您可以将示例重写为：

foo <$> parser1 <*> parser2 <*> parser3 ...

如果你想要中间变量，你可以只使用一个let语句：

let var1 = parser1
    var2 = parser2
    var3 = parser3 in
foo <$> var1 <*> var2 <*> var3

正如您正确推测的那样，pure它只是return. 因此，为了使共享结构更加明显，我们可以将其重写为：

pure foo <*> parser1 <*> parser2 <*> parser3

我希望这可以澄清事情。

现在只是一个小提示。人们确实建议使用应用函子函数进行解析。但是，只有在它们更有意义时才应该使用它们！对于足够复杂的事情，monad 版本（尤其是 do-notation）实际上可以更清晰。人们推荐这个的原因是

foo <$> parser1 <*> parser2 <*> parser3

比

do var1 <- parser1
   var2 <- parser2
   var3 <- parser3
   return $ foo var1 var2 var3

本质上，f <$> a <*> b <*> c它本质上就像提升功能的应用程序。您可以想象它<*>是一个空间（例如功能应用程序）的替代品，其方式与fmap功能应用程序的替代品相同。这也应该让您直观地了解我们为什么使用<$>- 它就像$.

score 13 · Accepted Answer

可以在这里说几句，希望对大家有帮助。这反映了我的理解，这本身可能是错误的。

pure被异常命名。通常函数的命名是指它们产生的东西，但pure x它x是纯的。pure x产生一个“携带” pure 的应用函子x。“携带”当然是近似的。一个例子：pure 1 :: ZipList Int是一个ZipList，带有一个纯Int值，1。

<*>,*>和<*不是函数，而是方法（这回答了您的第一个问题）。f它们的类型不是一般的（就像函数一样），而是具体的，由特定实例指定。这就是为什么它们确实不只是$和。专门的类型指定了组合的语义。在通常的应用风格编程中，组合意味着应用。但是对于函子，存在一个额外的维度，由“载体”类型表示。在中，有一个“内容”，，但也有一个“上下文”，。flip constconstfff xxf

“applicative functors”风格试图启用“applicative style”编程，具有效果。由函子、载体、上下文提供者代表的效果；“applicative”指的是函数式应用的正常应用风格。写作只是f x为了表示应用曾经是一个革命性的想法。不再需要额外的语法，没有(funcall f x)，没有CALL语句，这些额外的东西都没有 -组合是应用程序......不是这样，似乎有效果 - 当使用效果进行编程时，再次需要特殊语法。被杀的野兽再次出现。

因此，带有效果的应用程序编程再次使组合意味着只是应用程序——在特殊的（也许是有效的）上下文中，如果它们确实在这样的上下文中。因此，对于a :: f (t -> r)and b :: f t，（几乎简单的）组合a <*> b是在给定上下文（类型）中承载内容（或类型t -> rand t）的应用。f

与 monad 的主要区别在于，monad 是非线性的。在

do {  x        <-  a
   ;     y     <-  b x
   ;        z  <-  c x y
   ;               return 
     (x, y, z) }

计算b x取决于x，并且c x y取决于x和y。函数是嵌套的：

a >>= (\x ->  b x  >>= (\y ->  c x y  >>= (\z ->  .... )))

如果b并且c不依赖于先前的结果（x, y），则可以通过使计算阶段返回重新打包的复合数据来实现这一点（这解决了您的第二个问题）：

a  >>= (\x       ->  b  >>= (\y-> return (x,y)))       -- `b  ` sic
   >>= (\(x,y)   ->  c  >>= (\z-> return (x,y,z)))     -- `c  `
   >>= (\(x,y,z) ->  ..... )

这本质上是一种应用风格（b,c是预先完全知道的，独立于x产生的值a等）。因此，当您的组合创建包含进一步组合所需的所有信息的数据时，并且不需要“外部变量”（即所有计算都已经完全已知，独立于任何先前阶段产生的任何值），您可以使用这种风格的组合。

但是，如果您的单子链具有依赖于此类“外部”变量的值的分支（即单子计算的前一阶段的结果），那么您无法从中创建线性链。那么它本质上是一元的。

作为说明，该论文中的第一个示例显示了“monadic”函数

sequence :: [IO a] → IO [a]
sequence [ ] = return [ ]
sequence (c : cs) = do
  {  x       <-  c
  ;      xs  <-  sequence cs  -- `sequence cs` fully known, independent of `x`
  ;              return 
    (x : xs) }

实际上可以用这种“扁平、线性”的方式编码为

sequence :: (Applicative f) => [f a] -> f [a]
sequence []       = pure []
sequence (c : cs) = pure (:) <*> c <*> sequence cs
                  --     (:)     x     xs

这里没有用 monad 对先前结果进行分支的能力。

关于出色的 Petr Pudlák 答案的注释：在我的“术语”中，他pair是无应用的组合。它表明 Applictive Functor 添加到普通 Functor 的本质是组合的能力。应用则由好老实现。这表明组合仿函数可能是一个更好的名称（更新：事实上，“Monoidal Functors”就是这个名称）。fmap

score 8 · Accepted Answer

您可以这样查看函子、应用程序和单子：它们都带有一种“效果”和一种“值”。（请注意，术语“效果”和“价值”只是近似值 - 实际上不需要任何副作用或值 - 就像 inIdentity或Const。）

你可以在Functorusing 中修改可能的值fmap，但你不能对里面的效果做任何事情。
使用Applicative，您可以创建一个没有任何效果的值，pure您可以对效果进行排序并在其中组合它们的值。但是效果和值是分开的：在排序效果时，效果不能依赖于前一个效果的值。这反映在<*,<*>和*>: 它们对效果进行排序并组合它们的值，但是您不能以任何方式检查其中的值。

您可以Applicative使用这组替代函数进行定义：
```
fmap     :: (a -> b) -> (f a -> f b)
pureUnit :: f ()
pair     :: f a -> f b -> f (a, b)
-- or even with a more suggestive type  (f a, f b) -> f (a, b)
```
（其中pureUnit不产生任何影响）并定义pure它们<*>（反之亦然）。这里pair对两个效果进行排序并记住它们的值。Applicative这个定义表达了一个单曲面函子的事实。

pair现在考虑一个由、fmap和pureUnit一些原始应用值组成的任意（有限）表达式。我们有几个可以使用的规则：
```
fmap f . fmap g           ==>     fmap (f . g)
pair (fmap f x) y         ==>     fmap (\(a,b) -> (f a, b)) (pair x y)
pair x (fmap f y)         ==>     -- similar
pair pureUnit y           ==>     fmap (\b -> ((), b)) y
pair x pureUnit           ==>     -- similar
pair (pair x y) z         ==>     pair x (pair y z)
```
使用这些规则，我们可以对 s 重新排序，将s 向外pair推，并消除s，因此最终可以将这样的表达式转换为fmappureUnit
```
fmap pureFunction (x1 `pair` x2 `pair` ... `pair` xn)
```
或者
```
fmap pureFunction pureUnit
```
因此，确实，我们可以首先使用将所有效果收集在一起pair，然后使用纯函数在内部修改结果值。
使用Monad，效果可以取决于先前的单子值的值。这使他们如此强大。

score 6 · Accepted Answer

已经给出的答案非常好，但有一点我想明确说明，它与<*,<$和*>.

其中一个例子是

do var1 <- parser1
   var2 <- parser2
   var3 <- parser3
   return $ foo var1 var2 var3

也可以写成foo <$> parser1 <*> parser2 <*> parser3。

假设的值与- 例如它只是一些分隔空格var2无关。那么接受这个空格只是忽略它foo也是没有意义的。foo在这种情况下foo应该有两个参数，而不是三个。使用do-notation，您可以将其写为：

do var1 <- parser1
   parser2
   var3 <- parser3
   return $ foo var1 var3

如果您只想使用它来编写它<$>，<*>它应该类似于以下等效表达式之一：

(\x _ z -> foo x z) <$> parser1 <*> parser2 <*> parser3
(\x _ -> foo x) <$> parser1 <*> parser2 <*> parser3
(\x -> const (foo x)) <$> parser1 <*> parser2 <*> parser3
(const  . foo) <$> parser1 <*> parser2 <*> parser3

但这有点棘手，要正确处理更多的论点！

但是，您也可以编写foo <$> parser1 <* parser2 <*> parser3. 您可以调用以andfoo为结果的语义函数，同时忽略两者之间的结果。没有的意思是表示忽略。parser1parser3parser2>

如果您想忽略的结果parser1但使用其他两个结果，您可以类似地编写foo <$ parser1 <*> parser2 <*> parser3，使用<$而不是<$>。

我从来没有发现 ; 有太多用处*>，我通常会id <$ p1 <*> p2为忽略结果的解析器p1编写p2; 你可以这样写，p1 *> p2但这会增加代码读者的认知负担。

我已经为解析器学习了这种思维方式，但后来它被推广到Applicatives; 但我认为这个符号来自uuparsing 库；至少我 10 多年前在 Utrecht 使用过它。

score 3 · Accepted Answer

我想在非常有用的现有答案中添加/改写几件事：

应用程序是“静态的”。中pure f <*> a <*> b，b不依赖a，所以可以静态分析。这就是我在对您之前的问题的回答中试图展示的内容（但我想我失败了——抱歉）——因为实际上没有解析器的顺序依赖，所以不需要 monad。

monad 带来的主要区别是(>>=) :: Monad m => m a -> (a -> m b) -> m a，或者，join :: Monad m => m (m a)。请注意，只要您有x <- y内部do符号，您就在使用>>=. 这些说单子允许您使用单子“内部”的值来“动态地”生成新的单子。这不能通过 Applicative 完成。例子：

-- parse two in a row of the same character
char             >>= \c1 ->
char             >>= \c2 ->
guard (c1 == c2) >>
return c1

-- parse a digit followed by a number of chars equal to that digit
--   assuming: 1) `digit`s value is an Int,
--             2) there's a `manyN` combinator
-- examples:  "3abcdef"  -> Just {rest: "def", chars: "abc"}
--            "14abcdef" -> Nothing
digit        >>= \d -> 
manyN d char 
-- note how the value from the first parser is pumped into 
--   creating the second parser

-- creating 'half' of a cartesian product
[1 .. 10] >>= \x ->
[1 .. x]  >>= \y ->
return (x, y)

最后，Applicatives 启用了 @WillNess 提到的提升功能应用程序。要尝试了解“中间”结果是什么样的，您可以查看普通函数应用程序和提升函数应用程序之间的相似之处。假设add2 = (+) :: Int -> Int -> Int：

-- normal function application
add2 :: Int -> Int -> Int
add2 3 :: Int -> Int
(add2 3) 4 :: Int

-- lifted function application
pure add2 :: [] (Int -> Int -> Int)
pure add2 <*> pure 3 :: [] (Int -> Int)
pure add2 <*> pure 3 <*> pure 4 :: [] Int

-- more useful example
[(+1), (*2)]
[(+1), (*2)] <*> [1 .. 5]
[(+1), (*2)] <*> [1 .. 5] <*> [3 .. 8]

不幸的是，您无法有意义地打印结果，pure add2 <*> pure 3原因与您无法add2...令人沮丧的原因相同。您可能还想查看Identity及其类型类实例以了解 Applicatives。

haskell - 应用函子更有趣

5 回答 5

Related

Reference