如何组合这两个函数

Question

我知道标题有点不清晰，问题是：

假设我有一个类型为 a -> c 的函数，另一个类型为 b -> d 的函数，如何获得一个类型为 (a -> b) -> (c -> d) 的函数，或者这在一般情况下是否不可能？

---

也许我应该提供一些背景信息。我之所以提出这个问题，是因为我在解决幽灵类型的乐趣论文中的第9个练习时遇到了困难。

data Type t where
  ...
  RFun :: Type a -> Type b -> Type (a -> b)

而且tequal函数

tequal :: Type t -> Type u -> Maybe (t -> u)
...
tequal (RFun a b) (RFun c d) = -- should do something with (tequal a c) (tequal b d)

所以问题归结为将 a -> c 和 b -> d 组合成 (a -> b) -> (c -> d)。

- Jeremy Bi

---

那是什么？一个接受函数并返回函数的函数？你真的是指第一个参数将是 (a -> b) 吗？ - m0nhawk

是的，它是一个接受函数并返回另一个函数的函数，只需从类型中阅读即可。 - Jeremy Bi

仅返回类型是完全无意义的，因为您在那里有一些不同的函数。 - m0nhawk

在Haskell中，函数可以接受另一个函数作为参数。现在，您想返回一个函数以在其他地方应用吗？ - Xaphanius

只是一个提示，因为我认为这就是你所需要的。你有除了在“tequal a c”，“tequal b d”上进行递归之外的其他选择。其中一种选择将给你正确形状的碎片，以便组合成“(a -> b) -> (c -> d)”。 - Reid Barton

Answer 1

这是不可能的。

假设你有一个期望的函数 f :: (a -> b) -> (c -> d)。

你可以将它的类型简化为 (a -> b) -> c -> d（参见这里）。

f的实现会是什么样子呢？它有一个类型为 a -> b 的第一个参数和一个类型为 c 的第二个参数：

f ab c = ...

您可以通过 ab 做什么呢？它是一个函数，但您不能使用它，因为您没有类型为 a 的任何内容（除了 _|_）。即使您有函数 g :: a -> c 和 h :: b -> d，它们也没有用，因为您没有类型为 a 或 b 的任何内容，无法组合它们。

所以，唯一有效的实现方式类似于：

f ab = undefined

或者

f = undefined

关于你问题的第二部分，似乎可以使用递归方式使用 tequal 检查函数类型是否相等: 类型 a -> c 和 b -> d 仅在 a = b 和 c = d 时相等（这是有效的，因为该论文中的玩具类型系统没有类型变量）。

这里是一个实现的草图：

tequal (RFun a c) (RFun b d)
  = liftM2 func (tequal a b) (tequal c d)

您可以注意到，此代码与RPair的情况几乎相同。这与柯里化有关。

- max taldykin

Answer 2

作为max taldykin回答的小补充，

鉴于

f :: (a -> c) -> (b -> d) -> (a -> b) -> (c -> d)
f ac bd ab = ???

组合参数的方法实际上只有一种

bd . ab :: a -> d

但现在我们陷入了困境！我们无法从任何组合的a->c、b->d、a->b或a->d中构建c->d。

另一方面，如果我们有一个c->a，那么我们就可以构建一个

f :: (c -> a) -> (b -> d) -> (a -> b) -> (c -> d)
f ca bd ab = bd . ab . ca

顺便说一下，拿出笔和纸画一些箭头并尝试将它们连接成图表可能非常有帮助：

如果您尝试为 f :: (a -> c) -> (b -> d) -> (a -> b) -> (c -> d) 做同样的事情，那么您会发现无法绘制连接 c -> d 的图表：

现在我们没有办法连接这些点。

- Rein Henrichs

Answer 3

我相信你正在寻找高阶函数，它基本上是一个将函数作为参数或返回其他函数的函数。

例如，为了说明高阶函数，你可以定义以下函数：

f0 :: Int -> Int
f0 x = 0

f1 :: a -> a
f1 x = x

f2 :: (a -> a) -> a -> a
f2 f a = f(a)

f3 :: (a -> a) -> (a -> a)
f3 f = f1

请注意，f2接受一个函数并将其应用于第二个参数，而f3接受一个函数并返回函数f1。

如果您执行f2（f3（f0））5，则会返回5。 步骤： 1- f2（f3（f0））5 f3接受一个函数（f0）并返回f1。 2- f2（f1）5 f2接受一个函数（f1）并将其应用于第二个参数（5） 3- f1（5） f1被应用于5。

- Xaphanius

---

我非常熟悉高阶函数。我的问题是如何按照我指定的类型组合它们。无论如何，谢谢！ - Jeremy Bi

我明白了。在你编辑答案之前，我已经开始写作了，这是我的错误。现在我正在寻找其他解决方法。 - Xaphanius