应用仿函数更有趣

Earlier我问过翻译monadic代码只使用Parsec的applicative functor实例 . 不幸的是,我得到了几个回复,回答了我真正问过的问题,但并没有给我太多的了解 . 那么让我再试一次......

总结我到目前为止的知识,一个应用函子比一个monad更受限制 . 在“少即是多”的传统中,限制代码可以做什么会增加疯狂代码操作的可能性 . 无论如何,很多人似乎相信使用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 ,基本上是 <$> . 即,给定从 xy 的函数,我们可以将 f x 映射到 f y . Applicative 添加了两个本质上新的元素 . 一个是 pure ,它与 return (以及各种类别理论类中的其他几个运算符)的类型大致相同 . 另一个是 <*> ,它使我们能够获取一个容器的容器和一个输入容器并产生一个输出容器 .

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

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

这允许我们采用N-ary函数并从N个函子中获取其参数,其方式可以容易地推广到任何N.


这个我已经明白了 . 我还有两件不太明白的事情 .

一,功能 *><*<$ . 从它们的类型来看, <* = const*> = flip const<$ 可能类似 . 据推测,这并没有描述这些功能实际上做了什么 . (?!)

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

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

由于应用程序仿函数不允许我们以这种方式将中间结果绑定到变量,所以我很困惑如何在最后阶段收集它们 . 我无法完全理解这个想法,以便理解如何做到这一点 .

回答(5)

2 years ago

<**> 函数非常简单:它们的工作方式与 >> 相同 . 除非 << 不存在, <* 的工作方式与_753124相同 . 基本上,给定 a *> b ,你首先"do" a ,然后你"do" b 并返回 b 的结果 . 对于 a <* b ,您仍然首先"do" a 然后"do" b ,但是返回 a 的结果 . (当然,"do"的适当含义 . )

<$ 函数只是 fmap const . 所以 a <$ b 等于 fmap (const a) b . 你只需丢弃"action"的结果并返回一个常量值 . 具有 Functor f => f a -> f () 类型的 Control.Monad 函数 void 可以写为 () <$ .

这三个函数对于applicative functor的定义并不重要 . ( <$ ,实际上适用于任何仿函数 . )这对于monads来说就像 >> 一样 . 我相信他们在课堂上可以更轻松地针对特定情况对其进行优化 .

当您使用applicative functors时,您不会使用仿函数来创建值 . 在一个monad中,这就是 >>= 所做的,以及 foo <- ... 的目标 . 相反,您使用 <$><*> 将包装的值直接传递给函数 . 所以你可以将你的例子重写为:

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

如果你想要中间变量,你可以使用 let 语句:

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

正如你所推测的那样, pure 只是 return 的另一个名字 . 因此,为了使共享结构更加明显,我们可以将其重写为:

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

我希望这能澄清事情 .

现在只是一点点说明 . 人们建议使用applicative functor函数进行解析 . 但是,如果它们更有意义,你应该只使用它们!对于足够复杂的东西,monad版本(特别是带有do-notation)实际上可以更清晰 . 人们推荐这个的原因是

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

比起来更简短,更易读

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

从本质上讲, f <$> a <*> b <*> c 本质上就像提升功能应用程序 . 你可以想象 <*> 是一个空间的替代品(例如函数应用程序),就像 fmap 替代函数应用程序一样 . 这也应该为您提供一个直观的概念,说明为什么我们使用 <$> - 就像 $ 的升级版本一样 .

2 years ago

我可以在这里发表一些评论,希望对你有所帮助 . 这反映了我的理解本身可能是错误的 .

pure 的名字异乎寻常 . 通常函数的命名是指它们产生的东西,但在_753169中它是 x 很纯洁 . pure x 产生一个应用函子"carries"纯 x . "Carries"当然是近似的 . 例如: pure 1 :: ZipList IntZipList ,带有纯 Int 值, 1 .

<*>*><*not functions, but methods (这回答了您的第一个问题) . f 在它们的类型中不是通用的(就像它对于函数一样),而是特定的,由特定实例指定 . 这就是为什么他们只是 $flip constconst . 专用类型 f 指定组合的语义 . 在通常的应用风格编程中,组合意味着应用 . 但是使用仿函数,会出现一个额外的维度,由"carrier"类型 f 表示 . 在 f x 中,有一个"contents", x ,但也有一个"context", f .

"applicative functors"风格试图通过效果启用"applicative style"编程 . 由仿函数,载体,背景提供者代表的效果; "applicative"指的是功能应用的正常应用风格 . Writing just f x to denote application 曾经是一个革命性的想法 . 不需要额外的语法,没有 (funcall f x) ,没有 CALL 语句,没有这些额外的东西 - 组合是应用程序......不是这样,有效果,似乎 - 再次需要特殊语法,当使用效果编程时 . 被杀的野兽再次出现了 .

所以Applicative Programming with Effects再次使组合意味着应用 - 在特殊的(可能有效的)上下文中,如果它们确实在这样的背景下 . 因此对于 a :: f (t -> r)b :: f t ,(几乎是普通的)组合 a <*> ban application of carried contents (或类型 t -> rt ), in a given context (类型为 f ) .

monad的主要区别是, monads are non-linear . 在

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

计算 b x 取决于 xc x y 取决于 xy . 这些函数是嵌套的:

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

如果 bc 不依赖于先前的结果( xy ),则可以通过使计算阶段返回 repackaged, compound data (这解决您的第二个问题)使其变平:

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

这本质上是一种应用风格( bc 事先完全知道,独立于 a 产生的值 x 等) . 因此,当您的组合创建包含进一步组合所需的所有信息的数据时,并且不需要"outer variables"(即所有计算已经完全已知,独立于任何前一阶段产生的任何值),您可以使用此样式组合 .

但是如果你的monadic链依赖于这样的"outer"变量的值(即monadic计算的前一阶段的结果),那么你就不能用它做一个线性链 . 那基本上是monadic .


作为一个例子,该论文的第一个例子显示了“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's answer的注释:在我的"terminology"这里,他的 pair 是没有申请的组合 . 它表明,Applictive Functors为简单的Functors添加的内容是结合的能力 . 然后应用程序由好老 fmap 实现 . 这表明组合仿函数可能是一个更好的名称(更新:实际上,"Monoidal Functors"是名称) .

2 years ago

你可以像这样查看仿函数,应用程序和monad:它们都带有"effect"和"value" . (请注意,术语"effect"和"value"只是近似值 - 实际上并不需要任何副作用或值 - 例如 IdentityConst . )

  • 使用 Functor ,你可以使用 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 是一个幺半体仿函数的事实 .

现在考虑一个由 pairfmappureUnit 和一些原始应用值组成的任意(有限)表达式 . 我们有几个可以使用的规则:

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)

使用这些规则,我们可以重新排序 pair ,向外推 fmap 并消除 pureUnit ,所以最终这样的表达式可以是转换成

fmap pureFunction (x1 `pair` x2 `pair` ... `pair` xn)

要么

fmap pureFunction pureUnit

确实,我们可以先使用 pair 收集所有效果,然后使用纯函数修改结果值 .

  • 使用 Monad ,效果可以取决于先前monadic值的值 . 这使他们如此强大 .

2 years ago

已经给出的答案非常好,但是's one small(ish) point I'喜欢明确拼写,它与 <*<$*> 有关 .

其中一个例子是

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

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

假设 var2 的值与 foo 无关 - 例如's just some separating whitespace. Then it also doesn'有意义让 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 . 您可以调用 foo 语义函数,该语义函数提供 parser1parser3 的结果,同时忽略 parser2 之间的结果 . 缺少 > 意味着忽视 .

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

我从来没有找到过多用于 *> ,我通常会为忽略 p1 结果的解析器编写 id <$ p1 <*> p2 而只是用 p2 解析;你可以把它写成 p1 *> p2 ,但这会增加代码读者的认知负担 .

我已经为解析器学习了这种思维方式,但后来又被推广到 Applicative ;但我认为这种符号来自the uuparsing library;至少我10年前在乌得勒支用过它 .

2 years ago

我想在现有的非常有用的答案中添加/改写一些内容:

申请人是"static" . 在 pure f <*> a <*> b 中, b 不依赖于 a ,因此可以analyzed statically . 这就是我试图在_753308中显示的内容(但我想我失败了 - 抱歉) - 因为实际上没有解析器的顺序依赖,所以不需要monad .

monad带来的关键区别是 (>>=) :: Monad m => m a -> (a -> m b) -> m a ,或者 join :: Monad m => m (m a) . 请注意,只要 x <- y 内部 do 表示法,您就使用 >>= . 这些说monad允许你使用值"inside" monad来生成一个新的monad,"dynamically" . 申请人无法做到这一点 . 例子:

-- 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提到的提升功能应用程序 . 为了了解"intermediate"结果的样子,您可以查看正常和提升函数应用程序之间的相似之处 . 假设 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的句柄 .