问题标签 [combinatory-logic]

在学习 Haskell 时，我遇到了一个挑战，要找到两个函数f和g，这样f g和f . g是等价的（和总数，所以喜欢f = undefined或f = (.) f不计算）。给定的解决方案是f和g都等于\x -> x . x（或join (.)）。

（我注意到这不是 Haskell 特有的；它可以用纯组合逻辑表示为“find fand gsuch that f g = B f g”，然后给定的解决方案将转换为f = g = W B.）

我理解为什么当我扩展给定的解决方案时它会起作用，但我不明白如果你还不知道它是如何找到它的。这是我能走多远：

• f g = f . g（给定）
• f g z = (f . g) z（两边的eta扩展）
• f g z = f (g z)（简化 RHS）

而且我不知道如何从那里开始。在尝试找到解决方案时，我接下来会做什么？

我发现使用模式匹配是eval (App x y)多余的，因为两种情况都会返回App x y. 我想知道是否eval (App x y)需要，因为我们eval x = x最后有，其中还应该包括eval (App x y)

我的任务是展示

S(KK)I = K

现在由于S需要三个参数，所以我只是一开始就卡在不知道如何解决这个问题。我看到两个论点，即(KK)和I，但没有第三个我可以“发现”。在这种情况下会发生什么？它已经对我有用了，只需省略S xyz = xz(yz)中的z，这产生了KK(I)并因此产生了K。不过这对我来说似乎是错误的，所以我想在这里问一下。这是正确的方法吗？

例如，我也不明白KI会发生什么，因为K也需要两个参数并且只得到I。我的解决方案是正确的还是我必须采取不同的方式？

我正在阅读以下关于组合逻辑的维基百科页面，并对给出的示例感到困惑：
https
://en.wikipedia.org/wiki/Combinatory_logic#Completeness_of_the_S-K_basis 使用给定的转换 T[]，该术语λx.λy.(y x)转换为滑雪组合器。

这是重写的第一步：

在哪里5.：
T[λx.λy.E] => T[λx.T[λy.E]] (if x occurs free in E)

我不明白为什么5.在这里使用。在λx.λy.(y x)中，不是x绑定变量（意味着它不会在 中自由出现E）吗？

对于函数 monad，我发现(<*>)and (>>=)/(=<<)有两种非常相似的类型。特别是，(=<<)使相似性更加明显：

因此，就像(<*>)and (>>=)/(=<<)采用二元函数和一元函数，并通过后者约束前者的两个参数之一与另一个参数确定。毕竟，我们知道对于函数 applicative/monad，

而且它们看起来非常相似（或对称，如果你愿意的话），我不禁想到标题中的问题。

至于 monad 比 applicative functors “更强大”，在LYAH 的For a Few Monads More章节的硬拷贝中，陈述如下：

[…]join不能仅通过使用仿函数和应用程序提供的功能来实现。

即join不能用(<*>),pure和来实现fmap。

但是我上面提到的函数applicative/mondad 呢？

我知道 ，join === (>>= id)对于归结为 的函数 monad \f x -> f x x，即二进制函数通过将后者的一个参数作为前者的两个参数提供而成为一元函数。

我可以用 来表达(<*>)吗？好吧，实际上我认为我可以：不flip ($) <*> f === join f正确吗？不是没有/和flip ($) <*> f的实现吗？join(>>=)(=<<)return

但是，考虑到列表 applicative/monad，我可以join在不显式使用(=<<)/(>>=)和return（甚至不是(<*>)，fwiw）的情况下表达join = concat：所以可能实现join f = flip ($) <*> f也是一种技巧，并没有真正表明我是依赖Applicative还是依赖Monad.

我的问题

我指的是一个基本上执行以下操作的函数（模const，&完美转发，或任何适当的）：

这样的功能只能通过 Boost.Hana 表达吗？

为什么我会想到它？

在Haskell中，存在这样一个函数，它被调用($)（$中缀形式），其定义如下（源码）

并且您可以将第二行简单地写为以下任一

其中第二种形式显然与(identity function)($)基本相同id

只是带有强制第一个参数是函数类型a -> b和第二个参数类型的签名a。

事实上，在 Haskell 中申请f也x可以通过编写这个来完成

即使用`id`而不是$.¹

这和韩有什么关系？

由于 Hana确实提供了一个id函数，我想知道是否可以使用它（可能与其他东西一起）来定义一个函数应用程序实用程序，而无需在本文顶部手动编写 lambda。

困难的部分

这里的难点在于，当你用f `id` xHaskell 编写代码时，争论你是传递 1 个参数还是 2 个参数并没有多大意义id，因为默认情况下所有函数都是柯里化的。

这在 C++ 中是不正确的。例如我可以这样做：

看起来很像id被咖喱并且一个接一个地而不是一起给出两个输入，但这不是真的。只是那id(plus1)正在返回plus1，它被喂养了3。我不知道如何获得以下（相当于plus1 `id` 3或id plus1 3在 Haskell 中）的工作：

谜题的真正由来

在阅读了 To Mock a Mockingbird之后，我想知道：“如何仅使用 Boost.Hana 在 C++ 中实现 Thrush？” （而 Thrush 是boost::hana::flip函数应用运算符的 ped 版本。）

¹实际上，如果要编写应用程序链，这并不完全相同，因为这两个运算符具有不同的关联性，所以f $ g $ x == f `id` (g `id` x)，但这与问题无关，我相信。