3

作为练习，我将以下组合器转换为无点表示法：

h f g x y z = f x (g y z)

f, g,h作为函数, x, y,z作为表达式的通常约定。（这不是作业问题，只是为了好玩，看看我是否理解无点转换。）

在 的帮助下进行了漫长的手动重写过程后ghci，我得到了以下结果：

h = ((flip (.)) (flip (.)) . (flip (.))) . ((.)(.))

我注意到h它只包含两个组合器， "compose"(.)和 "reverse compose" flip (.)。有了这个，原始的组合子可以简洁地写成：

c = (.) -- compose
r = flip c -- "reverse compose"
h = ((r r) . r) . (c c)
   = c(c(r r)r)(c c)

“组合”和“反向组合”操作的结构（数量和顺序）似乎与原始组合器的结构有某种关联。

我认为这与组合逻辑和 SKI 演算直接相关。我的问题是：

  1. 有更多洞察力的人可以解释这里发生了什么：无点组合器中“组合”和“反向组合”的结构与有点组合器中的函数和表达式结构有什么关系？

  2. 这可以推广到任意组合器（即，函数的数量，表达式的数量，它们的顺序是任意的）吗？更具体地说，每个组合子都可以用“compose”和“reverse compose”来表达吗，有没有一种方案可以直接从pointful combinator的结构中推导出“compose”和“reverse compose”的组合（即，没有经历完整的重写过程）？例如，是否可以直接\ f g x y z -> (f x y) g z从函数结构中得出无点版本？

  3. c和的组合逻辑叫什么名字r？

更新：

这似乎c是B组合子，r来自CBB 、C、K、W 系统。但我仍然很乐意更深入地了解我的问题，尤其是问题 1 和问题 2。

4

1 回答 1

2

首先，通过以组合形式直接操作来推导定义通常更容易：

h f g x y z = f x (g y z)
            = B(fx)(gy)z     -- B rule
            = B(B(fx))gyz    -- B rule
h f g x = B(B(fx))g          -- eta-contraction
        = BBB(fx)g           -- B rule
        = B(BBB)fxg          -- B rule
        = C(B(BBB)f)gx       -- C rule
h f = C(B(BBB)f)             -- eta-contraction
    = BC(B(BBB))f            -- B rule
h   = BC(B(BBB))             -- eta-contraction
 -- = B(B(CB(CB))(CB))(BB)   -- your expression

类型是相同的，虽然我的表达更短。这可以作为组合形式是否应该以某种方式遵循给定定义的反例吗？规则的应用方式有相当大的自由度，因此可以衍生出广泛不同的形式。我认为从给定的组合表达式中无法获得太多洞察力。

如果有的话，出现在最终翻译中的组合子更能代表所采取的推导步骤，并且可以在任何给定点从适合的那些中自由选择。

例如，显然，在推导表达式时通常会采取以下步骤：

g(fx) = Bgfx = CBfgx 

B (B (CB(CB)) (CB)) (BB) f g x y z
   = B (CB(CB)) (CB) (BB f) g x y z
   = CB (CB) (CB (BB f)) g x y z     --   and here
   = CB (BB f) (CB g) x y z          --  here
   = CB g (BB f x) y z               -- here
   = BB f x (g y) z
   = B (f x) (g y) z
   = f x (g y z)

但是，如果您优先考虑您的规则应用程序并使其具有确定性，那么您应该始终得到相同的结果——这将取决于您应用规则的顺序。

于 2014-03-16T15:47:58.087 回答