Haskell中的S组合子

Question

能否用仅使用标准函数（不通过方程定义）和不使用lambda（匿名函数），在Haskell中表达S combinator的类比？我期望它的类型为(a -> b -> c) -> (a -> b) -> a -> c。

例如，K combinator的类比就是const。

事实上，我正在尝试使用标准函数来表达函数\f x -> f x x，但无法想到任何标准的非线性函数来开始（即使用其参数多次的函数）。

- Alexey

---

\f x -> f x x 在函数单子中被称为 join。 - duplode

我写了一篇博客，介绍了SK组合子演算和应用函子之间的联系，并且得到了一些有趣的读者评论，你可能会想看一下。此外，还有更多有趣的评论可以在这个答案里找到。 - jberryman

@duplode 我想知道这是否算作通过方程式定义它。 - Sassa NF

@SassaNF，我指的是任何相当标准的东西，比如(.)，($)，可能还有flip :)。 - Alexey

参见The Monad Reader Issue 17：阅读器monad与抽象消除。 - Petr

Answer 1

s = (<*>) 是指为了 ((->) r)类型的 Applicative 实例。

- David Young

---

抱歉，((->) r) 是什么意思？ - Alexey

@Alexey 它是所有类型的 r ->。不幸的是，您无法像使用普通运算符一样使用类型运算符进行部分操作。因此，尽管您可以做像 (10*) 这样的事情，但这不是有效的 Haskell (r ->)。不过，幸运的是，我们有一种语法可以给我们等效的结果：((->) r)。然而，请注意，我们不能对第二个参数执行相同的操作。这实际上是故意禁止的（我认为在某些情况下可能会使类型推断变得不可能），这就是为什么我们不能有类型运算符部分的原因。 - David Young

@Alexey，如果我们有一个类型同义词 type Function a b = a -> b，那么 ((->) r) 等同于 Function r。 - David Young

那么，r 只是一个类型变量吗？ - Alexey

有没有可能像(-> Int)这样的东西是不可能的，是因为Haskell不允许反变函子吗？ - Alexey

@Alexey：是的，r是一个类型变量。实际上，Haskell有（或可以有）反变函子 (http://hackage.haskell.org/package/contravariant)。它不允许像`(-> Int)`这样的东西，是因为如果允许你通过部分类型应用程序随意重新排列类型参数，你本质上将在类型级别上拥有完整的λ演算。这将使类型推断成为不可能。 - David Young

Answer 2

尽管乍一看并不是这样，但ap是S组合子（而join则是你真正需要的组合子）。

- Daniel Wagner

---

谢谢，这很有帮助。不过，考虑到我的问题标题以及 Applicative 似乎比 Monad 更通用，我想我会接受其他答案。 - Alexey

事实上，也许Monad比Applicative更加严格，你的答案实际上更好。 - Alexey

Answer 3

它还可以使用(=<<), (>>=)。

它们也包含在Prelude中。

instance Monad ((->) r) where  
    return = const
    f >>= k = \ r -> k (f r) r  

- Daishi Nakajima