Haskell函数组合运算符的类型为(c→d) → (a→b→c) → (a→b→d)。

60

普通函数组合的类型为

(.) :: (b -> c) -> (a -> b) -> a -> c

我认为这应该适用于类似以下类型:

(.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
一个具体的例子:计算差的平方。我们可以写成 diffsq a b = (a - b) ^ 2,但是感觉上我应该能够组合 (-)(^2) 来编写类似于 diffsq = (^2) . (-) 的东西。
当然,我做不到。我能做的一件事是使用元组代替两个参数作为 (-) 的输入,通过使用 uncurry 进行转换,但这并不相同。
我想知道是否可能实现我想要的东西?如果不行,那么我误解了什么使我认为它应该是可能的?
注意:这个问题 已经在这里 被问过了,但是没有给出我怀疑必须存在的答案。

4
你所拥有的组合器是 blackbird :: (c -> d) -> (a -> b -> c) -> a -> -> b -> d。你可以将它视为对普通函数应用进行“后变换器”的应用。 - stephen tetley
1
这是一个很好的问题,因为它突显了数学中函数组合和 Haskell 中函数组合之间微妙的差别,可能会让人感到困惑。对于这个例子,我更喜欢使用 uncurry (-) 的解决方案,因为它比其他方案更简单,并指向了潜在的问题。 - George Co
6个回答

53

我偏爱的实现方式是

fmap . fmap :: (Functor f, Functor f1) => (a -> b) -> f (f1 a) -> f (f1 b)

如果仅仅因为它相当容易记住。

当将f和f1实例化为(->) c(->) d时,你会得到这个类型。

(a -> b) -> (c -> d -> a) -> c -> d -> b

这是的类型

(.) . (.) ::  (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

但是使用fmap . fmap版本更容易,而且它可以推广到其他函子。

有时候这个写成fmap fmap fmap,但是如果写成fmap . fmap,它可以更方便地扩展到允许更多参数。

fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))

fmap . fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h, Functor i) => (a -> b) -> f (g (h (i a))) -> f (g (h (i b))

通常情况下,fmap 与其本身组合 n 次可以用于实现深度为 nfmap

由于函数形成一个 Functor,这为 n 个参数的处理提供了管道。

更多信息请参见Conal Elliott的语义编辑组合器


4
此外,您可以混合其他语义组合器,例如“first”和“second”。例如:fmap.first.fmap.second ::(Functor g,Functor f)=>(b-> c)-> f(g(d1,b),d)-> f(g(d1,c),d)。这些组合非常容易编写和阅读,因为它们提供了一条路径,穿过整个被编辑的值类型到实际被修改的子值。 - Conal
1
如果我没记错的话,这里定义了组合器 .:,其定义为 .: = (.).(.) - fuz
非常正确。我发现n次组合的fmapresult组合子比.:方法更直观和有用,因为.:方法没有线性数量的实现方式。 - Edward Kmett
7
这个回答很有启发性。我不知道 (.) 实际上就是对函子 (->) c 进行特化的 fmap - Tsuyoshi Ito

42
误解在于您认为类型为 a -> b -> c 的函数是具有两个参数以及返回类型为 c 的函数,实际上它是一个具有一个参数以及返回类型为 b -> c 的函数。这是因为函数类型从右向左结合(即与 a -> (b -> c) 相同)。这使得我们无法使用标准的函数组合运算符。
要看到原因,请尝试将类型为 g :: c -> df :: a -> (b -> c) 的两个函数应用于类型为 (y -> z) -> (x -> y) -> (x -> z)(.) 运算符。这意味着我们必须将 y 统一为 c 以及 b -> c。这没有多大意义。如何让 y 同时成为 c 和返回 c 的函数呢?那将会是一个无限类型。所以这不起作用。
虽然我们不能使用标准的组合运算符,但这并不妨碍我们定义自己的组合运算符。
 compose2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
 compose2 g f x y = g (f x y)

 diffsq = (^2) `compose2` (-)

通常情况下,在这种情况下避免使用无参函数风格更好,而是选择以下方式:

 diffsq a b = (a-b)^2

6
不需要定义自己的组合函数,就可以走“半路”:sumSq a = (^2) . (+a)。通过为第一个参数命名并应用它,我们构建了一个类型为 b -> c 的函数,可与常规组合函数一起使用。 - Thomas M. DuBuisson
3
确实可以这样做,但在这种情况下很快就会变得混乱,并且会感觉不对,因为它以不同的方式处理两个参数,而函数是可交换的。 - hammar
很好的解释,谢谢。由于某些原因,编写compose2让我感到困惑。我一定会学会的。 - jameshfisher
compose2 = g f x y = g (f x y):第一个等号必须被删除。 - Tsuyoshi Ito
7
我喜欢点无关的风格(g .) . f,但我承认它与节(section)一起看起来有点令人困惑 ((^2) .) . (-) - Max
"...它必须是一个无限类型。" 注意:这不仅仅是一个单词——在Haskell中尝试构造无限类型时会出现错误。我认为,如果您可以像这样无限次扩展类型变量,即 x = [x],那么它就会出现,因此 x = [[x]] = [[[x]]] 等等。顺便提一下,这让我想起了正则公理 - LRDPRDX

24

我不知道是否有一个标准库函数可以实现这个功能,但是实现它的点号模式是组合组合函数:

(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

6
虽然这是一种有趣的技巧,但我不建议编写这种代码。 - hammar
1
我想要使用 let (f .. g) a b = f (g a b),但是 .. 是用于其他语法的。而 ... 看起来也不太对。 - dave4420
2
@hammar 确实。我也不会这样做。但它确实提供了一种不同的视角,展示了 (.) 如何与只有一个参数的函数交互。 - mightybyte
3
作曲与作曲相结合。有趣。 - Dan Burton
我喜欢它。不仅是一个可爱的技巧,我认为它非常有信息量。虽然我看到这可能不属于“最终”代码,但这是一个很好的教育练习,我认为我从中获得了一些见解。 - jon_darkstar

8

我本来想在评论中写这个,但它有点长,并且涉及到mightybyte和hammar两位作者的观点。

我建议我们在运算符上进行标准化,例如使用.*表示compose2,使用.**表示compose3。使用mightybyte的定义:

(.*) :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)
(.*) = (.) . (.)

(.**) :: (d -> e) -> (a -> b -> c -> d) -> (a -> b -> c -> e)
(.**) = (.) . (.*)

diffsq :: (Num a) => a -> a -> a
diffsq = (^2) .* (-)

modminus :: (Integral a) => a -> a -> a -> a
modminus n = (`mod` n) .* (-)

diffsqmod :: (Integral a) => a -> a -> a -> a
diffsqmod = (^2) .** modminus

是的,modminusdiffsqmod这两个函数非常随机且没有价值,但它们很快并且表明了要点。请注意,通过在另一个compose函数中组合(类似于Edward提到的链接fmap),定义下一级别是多么的容易。

(.***) = (.) . (.**)

实际上,从compose12开始,写函数名比写运算符更短。

f .*********** g
f `compose12` g

虽然数星号很繁琐,所以我们可能希望在4或5个星号处停止惯例。


[编辑] 另一个随机的想法,我们可以使用 .: 表示compose2,.:. 表示compose3,.:: 表示compose4,.::.表示compose5,.:::表示compose6,让点号的数量(除了初始点号之外)在视觉上标记需要深入的参数数目。不过我认为我还是更喜欢星号。


当我在玩Data.Aviary时,我想到了这个问题。我的结论是给组合运算符ASCII名称是浪费命名空间的,ASCII名称应该为“保留”额外的数学运算符(例如Conal Elliott的向量空间)。使用文本名称设置数学倾向代码很可怕,因此数学运算符应该首先选择名称空间。如果您无法为组合运算符想出一个好的文本名称,则最好使用有点代码。 - stephen tetley
@stephen 函数组合是一种数学运算,尽管当函数有多个参数时会变得模糊不清。我真的无法想象.*如何用作数学运算符,而这样的组合函数几乎总是以中缀样式调用。 - Dan Burton
1
如果compose2是.:,compose3是.:。,那么compose必须是“..”,但它不是!这太不公平了! - Rotsor

8

正如Max评论中指出的那样:

diffsq = ((^ 2) .) . (-)

您可以将f . g视为对g应用一个参数,然后将结果传递给f(f .) . g将两个参数应用于g,然后将结果传递给f((f .) .) . g将三个参数应用于g,以此类推。

\f g -> (f .) . g :: (c -> d) -> (a -> b -> c) -> a -> b -> d

如果我们将组合运算符与某些函数 f :: c -> d(在左侧使用 f 进行部分应用)组合,我们得到:

(f .) :: (b -> c) -> b -> d

我们有一个新的功能,它需要一个从b -> c的函数,但我们的ga -> b -> c,或等价地,a -> (b -> c)。我们需要应用一个a才能获得所需的内容。好的,让我们再迭代一次:

((f .) .) :: (a -> b -> c) -> a -> b -> d

3

我认为以下是实现你想要的优雅方式。 Functor 类型类提供了一种将函数“推入”容器中的方法,以便您可以使用 fmap 将其应用于每个元素。 您可以将函数 a -> b 视为一个容器,其中每个元素由 a 的一个元素索引,并且其值为 b。 因此,自然而然地创建此实例:

instance Functor ((->) a) where
  fmap f g = f . g

我认为您可以通过导入适当的库来实现这一点,但我记不清是哪个库了。

现在,fg 的常规组合显然是一个 fmap

o1 :: (c -> d) -> (b -> c) -> (b -> d)
f `o1` g = fmap f g

类型为a -> b -> c的函数是类型为c的元素的容器的容器。因此,我们只需要将我们的函数f向下推两次。请看下面:

o2 :: (c -> d) -> (a -> (b -> c)) -> a -> (b -> d)
f `o2` g = fmap (fmap f) g

实际上,您可能会发现您不需要o1o2,只需要使用fmap。如果您能找到我忘记位置的库,您可能会发现可以只使用fmap而无需编写任何其他代码。


o2 = fmap . fmap或者o2 = result . result,其中result在Hackage上的DeepArrow中以不同的一般形式定义。 - Conal
@Conal 是的,但我试图让代码尽可能明了。 - sigfpe
1
在这种情况下,您可能特别喜欢语义编辑器组合器,例如我上面建议的那些。它们澄清了一般情况,而不是堆积特定的特殊情况,一旦理解了正在发生的事情,它们就非常清晰和启示性。另一方面,对于仅适用于特定情况,您的o2更简单。 - Conal
“语义编辑组合器”(Semantic editor combinators)是Conal Elliott的一篇非常启发性的文章,像往常一样。 - AndrewC

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