理解 Haskell 中无参函数中的 `ap`

22

我能理解 Haskell 中无点函数的基础知识:

addOne x = 1 + x

由于方程两侧都有x,我们对其进行简化:

addOne = (+ 1)

令人难以置信的是,原来在不同位置使用相同参数的函数可以被写成无参函数!

让我们以基本示例 average 函数为例:

average xs = realToFrac (sum xs) / genericLength xs

虽然简化xs看起来似乎是不可能的,但http://pointfree.io/提供了以下内容:

average = ap ((/) . realToFrac . sum) genericLength

没问题。

据我理解,这意味着将average作为两个函数的调用结果,这两个函数是(/) . realToFrac . sumgenericLength的组合。

不幸的是,ap函数对我来说完全没有意义,文档http://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html#v:ap中写道:

ap :: Monad m => m (a -> b) -> m a -> m b

In many situations, the liftM operations can be replaced by uses of ap,
which promotes function application.

      return f `ap` x1 `ap` ... `ap` xn

is equivalent to

      liftMn f x1 x2 ... xn

但是写作:

let average = liftM2 ((/) . realToFrac . sum) genericLength

无法运行,(会出现一个非常长的类型错误消息,如果需要我可以包含它),所以我不明白文档试图表达什么。


表达式 ap ((/) . realToFrac . sum) genericLength 如何工作?您能以比文档更简单的方式解释 ap 吗?


let average = liftM2 ((/) . realToFrac) sum genericLength 的代码有效。 - Ørjan Johansen
@ØrjanJohansen 很有趣,你能在回答中解释一下吗? - Caridorc
1
请查看函数的Monad实例的“ap”实现。 - Bergi
作为一项有趣的练习,可以将ap定义为(. ((. (return .)) . (>>=))) . (>>=)。 :-) - awllower
3个回答

13
任何 lambda 表达式都可以被重写为使用一组合适的 组合子 而不需要 lambda 抽象等效的表达式。这个过程称为 抽象消除。在这个过程中,您希望从内到外删除 lambda 抽象。因此,在一步中,您有一个 λx.M,其中 M 已经没有 lambda 抽象,并且您想摆脱 x
  • 如果 Mx,则用 id (在组合逻辑中通常用 I 表示)替换 λx.x
  • 如果 M 不包含 x,则用 const M (在组合逻辑中通常用 K 表示)替换该术语。
  • 如果 MPQ,也就是说该项是 λx.PQ,则要将 x 推入函数应用的两个部分中,以便可以递归地处理这两个部分。这可以通过使用定义为 λfgx.(fx)(gx)S 组合子来实现,即它接受两个函数并将 x 传递给它们,然后将结果应用在一起。您可以轻松验证 λx.PQ 等同于 S(λx.P)(λx.Q),我们可以递归处理两个子项。

    如其他答案所述,在 Haskell 中,S 组合子作为针对 reader monad 特化的 ap(或 <*>)可用。

阅读器单子的出现并非偶然:当解决用等效函数替换λx.M任务时,基本上是将M :: a提升到阅读器单子r -> a中(实际上,阅读器应用部分就足够了),其中rx的类型。如果我们修改上述过程:

  • 唯一与读取器单子实际相关的情况是当 Mx 时。然后我们将 x 提升到 id,以摆脱变量。下面的其他情况只是将表达式提升到应用函子的机械应用:
  • 另一种情况是 λx.M,其中 M 不包含 x,它只是将 M 提升到读取器应用程序中,即 pure M。事实上,对于 (->) rpure 等价于 const
  • 在最后一种情况中,<*> :: f (a -> b) -> f a -> f b 是将函数应用程序提升到单子/应用程序。这正是我们所做的:我们将两个部分 PQ 都提升到读取器应用程序中,然后使用 <*> 将它们绑定在一起。
这个过程可以通过添加更多的组合器进一步改进,从而使结果术语更短。最常用的是组合器BC, 在 Haskell 中对应于函数(.)flip。而且,(.)只是读取器应用程序的fmap/<$>。 (我不知道是否有这样一个内置函数来表示flip,但它将被视为读取器应用程序的f(a -> b)-&gt; a -&gt; f b的特化。)
一段时间以前,我写了一篇短文:The Monad Reader Issue 17,《Reader Monad and Abstraction Elimination》。

1
它不是“内置的”,但 lens 有广义的 flip,表示为 (??)。我觉得这是 Data.Functor 中的一个小漏洞。 - Ørjan Johansen

10

当单子 m(->) a 时,就像您的情况一样,您可以定义ap如下:

ap f g = \x -> f x (g x)

我们可以看到,在您的无点示例中,这确实“起作用”。

average = ap ((/) . realToFrac . sum) genericLength
average = \x -> ((/) . realToFrac . sum) x (genericLength x)
average = \x -> (/) (realToFrac (sum x)) (genericLength x)
average = \x -> realToFrac (sum x) / genericLength x

我们还可以从一般定律得出ap

ap f g = do ff <- f ; gg <- g ; return (ff gg)

也就是说,将do符号转化为基本语法。

ap f g = f >>= \ff -> g >>= \gg -> return (ff gg)

如果我们替换单子方法的定义

m >>= f = \x -> f (m x) x
return x = \_ -> x

我们得到了以前定义的ap(对于我们特定的单子(->) a)。确实:

app f g 
= f >>= \ff -> g >>= \gg -> return (ff gg)
= f >>= \ff -> g >>= \gg -> \_ -> ff gg
= f >>= \ff -> g >>= \gg _ -> ff gg
= f >>= \ff -> \x -> (\gg _ -> ff gg) (g x) x
= f >>= \ff -> \x -> (\_ -> ff (g x)) x
= f >>= \ff -> \x -> ff (g x)
= f >>= \ff x -> ff (g x)
= \y -> (\ff x -> ff (g x)) (f y) y
= \y -> (\x -> f y (g x)) y
= \y -> f y (g y)

1
那么定义ap' f g = \ x-> f x(g x)会使它拥有比普通的ap更小的一部分权力吗? - Caridorc
1
@Caridorc:是的,普通的ap适用于所有单子,而你的ap'只适用于函数。 - Bergi
ap'. 有相似之处吗?虽然 . 是将两个都只接受一个参数的函数组合起来,但是 ap' 则是将一个接受两个参数的函数和一个接受一个参数的函数组合起来。 - Caridorc
@Caridorc 只知道一点。在 lambda 演算和组合逻辑中,它被称为“S 组合子”。https://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E9%80%BB%E8%BE%91#%E7%BB%84%E5%90%88%E5%AD%90%E4%BE%8B%E5%AD%90 - chi
@chi 的确如此!Applicative 可以被视为 SKI 演算法的一般化:(<*>) 是 S,pure 是 K,而 I = S K K。 - Rein Henrichs

4

简单易懂的修复liftM2方法:

原始示例中的问题在于ap函数与liftM函数有些不同。 ap函数接受一个被封装在单子中的函数,并将其应用于一个被封装在单子中的参数。但是,liftMn函数接受一个“正常”的函数(即未被封装在单子中的函数),并将其应用于被封装在单子中的参数。

我将在下面更详细地解释这意味着什么,但要点是,如果您想使用liftM2函数,则必须将(/)拿出来,使其成为一个独立的参数放在开头。(因此,在这种情况下,(/)是“普通”函数。)

let average = liftM2 ((/) . realToFrac . sum) genericLength -- does not work
let average = liftM2 (/)   (realToFrac . sum) genericLength -- works

如原问题中所发帖的,调用liftM2应该涉及三个参数:liftM2 f x1 x2。这里的f(/)x1(realToFrac . sum)x2genericLength
问题中发布的版本(不起作用的版本)试图仅使用两个参数来调用liftM2
解释
我将分几个阶段逐步构建起来。我将从一些具体的值开始,并建立一个可以接受任何一组值的函数。TL:DR请跳到最后一节。
在本示例中,假设数字列表为[1,2,3,4]。这些数字的总和为10,列表长度为4。平均数是10/42.5
为了强行将其转换成正确的ap形式,我们要将其拆分为一个函数、一个输入和一个结果。
ourFunction =  (10/)    -- "divide 10 by"
ourInput    =    4
ourResult   =    2.5 

三种函数应用方式

aplistM 都涉及到单子。在解释此处之前,您可以将单子视为一个值可以“封装在其中”的东西。下面我会给出更好的定义。

普通函数应用将普通函数应用于普通输入。liftM将普通函数应用于封装在单子中的输入,ap将封装在单子中的函数应用于封装在单子中的输入。

        (10/) 4          -- returns 2.5
liftM   (10/) monad(4)   -- returns monad(2.5)
ap monad(10/) monad(4)   -- returns monad(2.5)

(请注意,以下为伪代码。monad(4)实际上不是有效的Haskell代码)
(请注意,liftM是与之前使用的liftM2不同的函数。 liftM接受一个函数和仅一个参数,这更适合我所描述的模式。)
在上面定义的average函数中,单子是函数,但是“函数作为单子”可能很难谈论,因此我将从更简单的例子开始。
那么什么是单子?
单子的更好描述是“包含值或生成值或可以从中提取值的东西,但还具有更复杂的功能”。
那是非常模糊的描述,但必须这样,因为“更复杂的事情”可能是许多不同的事情。
单子可能很困惑,但它们的重点在于当您使用单子操作(如apliftM)时,它们将为您处理“更复杂的事情”,因此您只需专注于值。
这可能仍然不是很清楚,因此让我们进行一些例子:
Maybe 单子
ap (Just (10/)) (Just 4)   -- result is (Just 2.5)

最简单的单子之一是 'Maybe'。值就是包含在 Just 中的任何内容。因此,如果我们调用 ap 并给它 (Just ourFunction)(Just ourInput),那么我们会得到 (Just ourResult)

"更加复杂的" 是可能根本没有值存在,您必须允许 Nothing 的情况。

正如前面提到的,使用像 ap 这样的函数的意义在于它为我们处理这些额外的复杂性。对于 Maybe 单子,ap 通过在 Maybe 函数或 Maybe 输入为 Nothing 时返回 Nothing 来处理这个问题。

ap (Just (10/)) Nothing    -- result is Nothing
ap Nothing (Just 4)        -- result is Nothing

列表单子

ap [(10/)] [4]    -- result is [2.5]

对于列表单子,其值始终是列表内的内容。因此,ap [我们的函数] [我们的输入]返回[我们的结果]

“更复杂的事情”在于列表中可能有多个内容(或者完全没有内容、只有一个内容)。

对于列表来说,这意味着ap接受零个或多个函数以及零个或多个输入的列表。它通过返回一个结果列表来处理:每种可能的函数和输入组合都有一个结果。

ap [(10/), (100/)] [5,4,2]  -- result is [2.0, 2.5, 5.0, 20.0, 25.0, 50.0]

函数作为单子

genericLength这样的函数被认为是单子,因为它有一个值(函数的输出),还有一个“更加复杂”的东西(你必须提供输入才能获得值)。

这就是让人有些困惑的地方,因为我们处理多个函数、多个输入和多个结果。虽然所有内容都很明确,但我们必须小心使用术语。

让我们从列表[1,2,3,4]开始,并将其称为我们的“原始输入”。这就是我们要找到平均数的列表。在原始的average函数中,它是xs参数。

如果我们将原始输入([1,2,3,4])传递给genericLength,那么我们会得到一个值为'4'。

我们的另一个函数是((/) . realToFrac . sum)。它获取我们的列表[1,2,3,4],找到总和(10),将其转换为分数值,然后将其作为第一个参数馈送给(/)。结果是一个不完整的除法函数,正在等待另一个参数。也就是说,它以[1,2,3,4]为输入,以(10/)为输出。

所有这些都符合函数定义的ap方式。对于函数,ap需要两个东西。第一个是读取原始输入并生成新函数的函数。第二个是读取原始输入并生成新输入的函数。最终结果是一个函数,它接受原始输入,并返回如果将新函数应用于新输入所得到的相同结果。

你可能需要多读几次才能理解。或者,这里有伪代码:

average = 
  ap
    (functionThatTakes [1,2,3,4] and returns "(10/)" )
    (functionThatTakes [1,2,3,4] and returns "  4  " )

-- which means:

average = 
    (functionThatTakes [1,2,3,4] and returns "2.5"  )

与前面更简单的例子相比,您会发现这个示例仍然具有我们的函数(10/),输入4和结果2.5。每个元素再次被包装在“更加复杂的东西”中。在这种情况下,“更加复杂的东西”是“接受[1,2,3,4]并返回...”的函数。
当然,由于它们是函数,它们不必将[1,2,3,4]作为它们的输入。如果它们使用了不同的整数列表(例如[1,2,3,4,5]),那么我们将获得不同的结果(例如新函数:(15/),新输入5和新值3)。
其他例子:
minPlusMax = ap ((+) . minimum) maximum
-- a function that adds the minimum element of a list, to the maximum element


upperAndLower = ap ((,) . toUpper) toLower
-- a function that takes a Char and returns a tuple, with the upper case and lower case versions of a character

这些也都可以使用liftM2来定义。

average       = liftM2 (/) sum genericLength
minPlusMax    = liftM2 (+) minimum maximum
upperAndLower = liftM2 (,) toUpper toLower

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接