使用 y 组合器从布尔列表中去除“FALSE”前缀？难住了

Question

给定一个列表，例如

(f: f FALSE (g: g FALSE (h: h TRUE FALSE)))

，编写一个运算符，删除所有前导

FALSE

，并仅返回以

TRUE

开头的尾部。对于此示例，运算符应仅返回

(h: h TRUE FALSE)

。

这是一个练习，实际上是一个关卡，在这个我痴迷的名为“功能”的游戏中。在上一个级别中，我们需要将 \Omega 推广到 y 组合器中，所以我想这个级别需要 y 组合器来处理任意长度的

FALSE

前缀。

我能够使用

FALSE

处理单个

(b: c: IF b (f: f b c) c)

前缀。将该运算符想象为

f

我猜答案应该类似于

(b: c: IF b (f: f b c) (Y c))

。游戏拒绝这个答案，抱怨“没有减少（变得太大）”。

我显然对 y 组合器感到困惑。有人可以告诉我如何正确使用它吗？

另外，游戏使用的疯狂语法是什么？我没有看到它在其他地方使用过。

根据要求，Steam 上的功能页面链接位于此处。我最近还在 github here 上发现了项目页面的链接。

Answer 1

试试这个：

Y(f: x: (FST x) x (f(SND x)))

。

通过使用 Y 组合器，如果头 (

x

) 为 TRUE，则返回整个列表 (

FST x

)，否则以尾 (

SND x

) 作为参数递归调用自身。

Answer 2

我在这个问题上停留了一段时间。让我解释一下为什么错误答案不起作用，然后给出解决方案。

我首先尝试“势在必行”地解决这个问题。我试图画出一个解决方案，“如果第一个元素为 TRUE，则使用列表（我们就完成了），否则通过跳过第一个元素来调用自身。”这个错误的解决方案看起来像

t: IF (FST t) t (Y (x: SND t))

看看测试用例会发生什么：

案例 1（列表=FALSE FALSE TRUE TRUE FALSE）：...失败。

情况 2 (list=TRUE FALSE)：列表中的第一个元素为 TRUE，因此

IF

语句返回整个列表。成功了。

情况 3（list=FALSE TRUE）：

IF

语句失败，这会减少到

(f: f (PAIR FALSE (PAIR TRUE FALSE))) t: IF (FST t) t (Y (x: SND t))
...
Y (x: SND (PAIR FALSE (PAIR TRUE FALSE)))
...
SND (PAIR FALSE (PAIR TRUE FALSE))
...
PAIR TRUE FALSE # single element list containing TRUE

案例 3 成功了，但纯属偶然。 Y 组合器没有做任何有用的事情。

---

让我复制问题中的一些文字：

假设您想编写一个接收两个参数并以相反顺序将 itself 应用于两个参数的函数。您可以写：

F = Y (f: x:y: f y x)

。

思考上面的例子和上面的案例3终于弄清楚了如何使用Y Combinator。您需要从 Y 组合器开始，并使用要应用于自身的函数。该函数将有一个列表参数，但或多或少遵循我第一次尝试实现的相同逻辑。正确答案：

Y (f: x: IF (FST x) x (f (SND x)))

这个解决方案说：

将此函数应用于自身。如果列表中的第一个元素为 TRUE，则返回整个列表，我们就完成了（

IF (FST x) x

部分）。

否则，将其自身应用于跳过第一个元素列表（

f (SND x)

部分）。