javascript - 使用右折和差异列表对列表进行教堂编码

Question

这是之后的顺序问题

How to store data of a functional chain of Monoidal List?

和

Extracting data from a function chain without arrays

在这里，我要表达我对我的问题的贡献者的敬意和赞赏，尤其是@Aadit M Shah和@ user633183的贡献

现在，打开这个问题来阐明Difference list和Church list之间的异同或关系

。



差异表

https://stackoverflow.com/a/51320041/6440264


  difference list是获取列表并在其前面添加另一个列表的函数。例如：

const concat = xs => ys => xs.concat(ys); // This creates a difference list.

const f = concat([1,2,3]); // This is a difference list.

console.log(f([])); // You can get its value by applying it to the empty array.

console.log(f([4,5,6])); // You can also apply it to any other array.

  关于差异列表的最酷的事情是它们形成一个monoid，因为它们只是 endofunctions：

const id = x => x; // The identity element is just the id function.

const compose = (f, g) => x => f(g(x)); // The binary operation is composition.

compose(id, f) = f = compose(f, id);                   // identity law
compose(compose(f, g), h) = compose(f, compose(g, h)); // associativity law

  更好的是，您可以将它们打包到一个整洁的小类中，其中函数组成是点运算符：

class DList {
    constructor(f) {
        this.f  = f;
        this.id = this;
    }

    cons(x) {
        return new DList(ys => this.f([x].concat(ys)));
    }

    concat(xs) {
        return new DList(ys => this.f(xs.concat(ys)));
    }

    apply(xs) {
        return this.f(xs);
    }
}

const id = new DList(x => x);

const cons = x => new DList(ys => [x].concat(ys));   // Construct DList from value.

const concat = xs => new DList(ys => xs.concat(ys)); // Construct DList from array.

id . concat([1, 2, 3]) = concat([1, 2, 3]) = concat([1, 2, 3]) . id // identity law

concat([1, 2]) . cons(3) = cons(1) . concat([2, 3]) // associativity law

  您可以使用 apply方法来检索 DList的值，如下所示：

class DList {
    constructor(f) {
        this.f  = f;
        this.id = this;
    }

    cons(x) {
        return new DList(ys => this.f([x].concat(ys)));
    }

    concat(xs) {
        return new DList(ys => this.f(xs.concat(ys)));
    }

    apply(xs) {
        return this.f(xs);
    }
}

const id = new DList(x => x);

const cons = x => new DList(ys => [x].concat(ys));

const concat = xs => new DList(ys => xs.concat(ys));

const identityLeft  = id . concat([1, 2, 3]);
const identityRight = concat([1, 2, 3]) . id;

const associativityLeft  = concat([1, 2]) . cons(3);
const associativityRight = cons(1) . concat([2, 3]);

console.log(identityLeft.apply([]));  // [1,2,3]
console.log(identityRight.apply([])); // [1,2,3]

console.log(associativityLeft.apply([]));  // [1,2,3]
console.log(associativityRight.apply([])); // [1,2,3]

  与常规列表（功能列表，而不是JavaScript数组）相比，使用差异列表的优势在于，由于列表是从右到左进行串联的，因此连接效率更高。因此，如果要串联多个列表，它不会一遍又一遍地复制相同的值。




Church Encoding List

作为使用教堂对进行编码的替代方法，可以通过使用右折叠功能识别列表来对列表进行编码。例如，三个元素x，y和z的列表可以由一个高阶函数编码，该函数在应用于组合器c和值n时会返回c x（c y（c z n））。

https://stackoverflow.com/a/51420884/6440264


   user633183's solution很棒。它使用 Church encoding of lists using right folds减轻了继续操作的需要，从而使代码更易于理解。这是她的解决方案，已修改为使 foldr看起来像 foldl：

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L((f, a) => f(g(f, a), x));
    case 2: return g(x, a);
    }
};

const A = L((f, a) => a);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

  这里的 g是到目前为止累积的教会编码列表。最初，它是空列表。调用 g会将其从右侧折叠。但是，我们也从右侧构建列表。因此，由于我们编写列表的方式，似乎我们正在构建列表并将其从左侧折叠。





  如果所有这些功能使您感到困惑，那么user633183真正在做什么是：

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L([x].concat(g));
    case 2: return g.reduceRight(x, a);
    }
};

const A = L([]);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

  如您所见，她正在向后构建列表，然后使用 reduceRight向后折叠向后列表。因此，您似乎正在构建并向前折叠列表。




我希望在“差异列表”中看到的是


理解似乎是自然而直接的。
带有浓淡度（展平），它会形成类体
身份元素是身份功能，不需要提供外部初始值。


我不喜欢的


至少，提供的示例代码取决于JavaScript Array


实际上，我在教堂清单中喜欢/不喜欢的是上述内容的对立面。

我喜欢


它是JavaScript数组实现的独立功能，它可以自己定义操作： user633183's solution


我不喜欢


我不知道为什么不能左折而是右折？



  可以通过使用右折叠功能对其进行识别来对列表进行编码



对于Monoid的实现不清楚
特别地，Nil不是Identity元素（=身份函数），并且示例代码需要提供外部初始值。


所以，我很好奇的是，像教堂清单这样的任何形式的差别清单都没有。

具体将是


基本上，这是一个差异列表
独立于JavaScipt Array的实现
初始值为内置身份识别功能。


谢谢你。

Answer 1

问题的根源

问题系列的根本原因是您坚持使用L(1)(2)(3)语法构造列表。这种语法没有任何意义，人们已经一次又一次告诉您放弃使用这种语法：


user633183's answer您的第一个问题：


  函数currying和可变参数不能真正一起使用。一旦意识到以下两个表达式不兼容，就会很明显地体现出这一限制
  
  

L (1)     -> [ 1 ]
L (1) (2) -> [ 1, 2 ]

  
  在 L (1)上面返回一个列表，但是在第二个表达式中，我们希望 L (1)是可以应用于 2的函数。 L (1)可以是列表，也可以是产生列表的函数；它不能同时存在。

Bergi's comment关于第二个问题：


  首先，如果要使用函数式编程，请避免使用可变参数函数或奇怪的混合返回类型。

user633183's answer您的第三个问题：


  因此，说到类型，让我们检查 autoCons的类型–
  
  

autoCons (1)                  // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2)              // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3)          // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3) (add, 0) // 6

  
   autoCons总是返回一个lambda，但是该lambda具有我们无法确定的类型-有时它返回另一个相同类型的lambda，有时返回一个完全不同的结果。在这种情况下， 6
  
  因此，我们无法轻松地将 autoCons表达式与程序的其他部分混合和组合。如果删除此错误驱动器以创建可变参数的咖喱界面，则可以使 autoCons可输入类型



当您可以简单地编写 L(1)(2)(3)时，我认为没有任何理由使用 toList([1,2,3])语法：

// null :: List a
// cons :: (a, List a) -> List a
const cons = (head, tail) => ({ head, tail });

// xs :: List Number
const xs = cons(1, cons(2, cons(3, null))); // You can either construct a list manually,

// toList :: Array a -> List a
const toList = array => array.length ? cons(array[0], toList(array.slice(1))) : null;

// ys :: List Number
const ys = toList([1,2,3]); // or you can construct a list from an array.

console.log(xs);
console.log(ys);

此外，如果使用 L(1)(2)(3)语法的唯一原因是“有效地”将元素推到列表的末尾，那么您也可以使用普通列表来这样做。只需向后构建列表，然后使用 cons在列表的开头放置一个新元素。

列表的代数结构

您似乎对列表的结构有一些非正统的信念：


首先， you believe列表的开头应始终为nil：


  Lisp / Scheme教科书中解释的构造列表的传统方法是非常错误的。 Nil不应该在列表的末尾，而应该在列表的头。 Lisp / Scheme给程序世界带来了如此多的混乱，它们具有扭曲的列表结构（0 =尾无）。

其次， you believe不必为列表折叠提供初始值：


  我仍然不知道您坚持使用“ init”值进行折叠等任何理由，看看某些库，他们不使用“ init”，我认为它们更合理。 github.com/benji6/church/blob/master/src/lists.js确切地说，他们基本上将Zero = Identity用于更有意义的初始化。



这两种信念都是不明智的。要了解为什么我们需要查看列表的代数结构：

   ┌──────────────────────────── A List of a
   │   ┌──────────────────────── is
   |   |   ┌──────────────────── either null
   |   |   |  ┌───────────────── or
   |   |   |  |   ┌───────────── cons of
   |   |   |  |   |   ┌───────── an a and
   │   |   |  |   |   |     ┌─── another List of a.
┌──┴─┐ │ ┌─┴┐ | ┌─┴┐  |  ┌──┴─┐
List a = null | cons (a, List a)

列表可以为空或非空。空列表由 null表示。通过使用 cons将新元素放在另一个（可能为空）元素列表之前，可以形成非空列表。我们将新元素放在原始列表的前面而不是它的后面，因为它更自然：

cons(1, cons(2, cons(3, null))); // This is easier to read and write.

snoc(snoc(snoc(null, 1), 2), 3); // This is more difficult to read and write.

注意：使用 snoc并没有本质上的错误。我们可以将 List定义为 List a = null | snoc (List a, a)。但是，使用 cons更自然。现在，根据是否使用 cons或 snoc定义 List数据类型，将新元素放在列表前面或将新元素放在列表后面变得很昂贵：

       in front of     behind
     ┌─────────────┬─────────────┐
cons │ Inexpensive │  Expensive  │
     ├─────────────┼─────────────┤
snoc │  Expensive  │ Inexpensive │
     └─────────────┴─────────────┘

注意：接下来的两段使用Haskell语法。

Difference lists用于通过延迟列表的串联直到需要，然后以最有效的顺序将它们串联来分摊昂贵操作的成本。例如，假设我们有一个表达式 as ++ bs ++ cs ++ ds，在其中连接了四个列表。如果我们使用 cons的 List实现，则串联的最有效顺序是 as ++ (bs ++ (cs ++ ds))，这就是Haskell中 (++)运算符正确关联的原因。另一方面，如果我们使用 snoc的 List实现，则串联的最有效顺序是 ((as ++ bs) ++ cs) ++ ds。

使用 cons的 List实现时，差异列表的形式为 (xs ++)，其中 xs是常规列表。我们可以使用常规函数组合（即 (as ++) . (bs ++) . (cs ++) . (ds ++)）将它们向前组合。使用 snoc的 List实现时，差异列表的形式为 (++ xs)，其中 xs是常规列表。我们可以使用常规函数组合（即 (++ ds) . (++ cs) . (++ bs) . (++ as)）向后组合它们。这是为什么更优选使用 cons的 List实现的另一个原因。

现在，让我们换一下齿轮，谈谈非空列表的一部分。关于列表（无论我们使用的是 cons的 List实现还是 snoc的 List实现），术语 head， tail， init和 具有非常具体的含义：

   head          tail
     │  ┌──────────┴─────────┐
cons(1, cons(2, cons(3, null)));
└──────┬─────┘       │
     init          last

              init         last
     ┌──────────┴─────────┐  │
snoc(snoc(snoc(null, 1), 2), 3);
                     │   └─┬─┘
                   head  tail

非空列表的 last是列表的第一个元素。
非空列表的 head是列表的第一个元素以外的所有内容。
非空列表的 tail是列表的最后一个元素以外的所有内容。
非空列表的 init是列表的最后一个元素。


因此，根据我们是使用 last还是 cons定义 snoc数据类型， List和 head或 tail和 init变得昂贵：

       head / tail   init / last
     ┌─────────────┬─────────────┐
cons │ Inexpensive │  Expensive  │
     ├─────────────┼─────────────┤
snoc │  Expensive  │ Inexpensive │
     └─────────────┴─────────────┘

无论如何，这就是为什么声明“ Nil不应该在列表的末尾，而应该在列表的头”的原因是没有意义的。列表的开头是列表的第一个元素。 Nil不是列表的第一个元素。因此，声明nil应该始终是列表的头是不合逻辑的。



现在，让我们继续前进。根据我们使用 last还是 cons定义 snoc数据类型， List或 foldl都将成为尾递归：

               foldl                  foldr
     ┌──────────────────────┬──────────────────────┐
cons │    Tail Recursion    │ Structural Recursion │
     ├──────────────────────┼──────────────────────┤
snoc │ Structural Recursion │    Tail Recursion    │
     └──────────────────────┴──────────────────────┘

如果语言执行 tail call optimization，则尾递归通常会更有效。但是，结构化递归更多地 natural，在具有延迟评估的语言中，它 becomes more efficient，并且可以在无限数据结构上工作。说到无限数据结构， foldr实现无限向前扩展（即 cons），而 cons(1, cons(2, cons(3, ....)))实现无限向前扩展（即 snoc）。与 snoc(snoc(snoc(...., 1), 2), 3)相比更喜欢 cons的另一个原因。

无论如何，让我们尝试理解为什么需要折叠的初始值。假设我们有以下列表 snoc，并使用 xs = cons(1, cons(2, cons(3, null)))折叠它：

  cons                                         func
 /    \                                       /    \
1    cons                                    1    func
    /    \      -> foldr(func, init, xs) ->      /    \
   2    cons                                    2    func
       /    \                                       /    \
      3    null                                    3    init

如您所见，当我们使用 foldr减少列表时，实际上是用 foldr替换每个 cons，并且用 func替换 null。这样，您可以通过折叠第一个列表，将 init替换为 cons，用第二个列表 cons替换 null来追加两个列表：

  cons                                       cons
 /    \                                     /    \
1    cons                                  1    cons
    /    \      -> foldr(cons, ys, xs) ->      /    \
   2    cons                                  2    cons
       /    \                                     /    \
      3    null                                  3    cons
                                                     /    \
                                                    4    cons
                                                        /    \
                                                       5    cons
                                                           /    \
                                                          6    null

现在，如果您不提供初始值，那么您就不会保留列表的结构。因此，您将无法追加两个列表。实际上，您甚至无法重建相同的列表。考虑：

  cons                                    func
 /    \                                  /    \
1    cons                               1    func
    /    \      -> foldr1(func, xs) ->      /    \
   2    cons                               2    func
       /    \                                  /
      3    null                               3

使用 ys = cons(4, cons(5, cons(6, null)))可以找到列表的总和而不提供初始值（即 foldr1），但是如何在不借助 witchcraft的情况下重建相同的列表呢？如果您愿意提供初始值，则可以优雅地编写 foldr1(plus, xs)。否则，除非您违反了函数式编程的原理，并使用副作用从 foldr(cons, null, xs)自身内部人为地提供初始值，否则不可能这样做。无论哪种方式，无论是通过显式指定初始值还是通过将列表的最后一个元素作为 func中的特例处理，您都将提供初始值。

选择更简单的选择。明确提供初始值。如 Zen of Python所述：


  美丽胜于丑陋。
  显式胜于隐式。
  简单胜于复杂。
  ...
  特殊情况还不足以打破规则。


无论如何，请转到最后一节。

您正在寻找的答案（以及更多）

如果我不回答您的任何问题给您讲课，那将是不合适的。因此：


关于差异列表，您的以下陈述是错误的：


  
  身份元素是身份功能，不需要提供外部初始值。
  


实际上，如果折叠差异列表，则仍然需要提供初始值。作为参考，请参见Hackage中 func包中的 foldr函数。
关于教会编码列表，您有以下问题：


  
  我不知道为什么不能左折而是右折？
  


由于 Data.DList语法不正确，因此只能向后构建列表（即 L(1)(2)(3)）。因此，如果要“向前”折叠列表，则必须使用 L(1)(2)(3) = cons(3, cons(2, cons(1, null)))而不是 foldr。请注意，如果我们使用 foldl而不是 snoc，那么它实际上是转发的（即 cons）。这是因为 L(1)(2)(3) = snoc(snoc(snoc(null, 1), 2), 3)只是 snoc且参数已翻转。因此， cons的 foldr等同于 cons的 foldl，反之亦然，这是user633183注意到的。

请注意，我最初使用延续的解决方案实际上确实将 snoc用于 foldl，但是为此，由于列表是向后构建的，因此我不得不以某种方式反转该列表。这就是延续的目的，以反转列表。直到后来我才意识到我根本不需要撤消这份清单。我可以简单地使用 cons而不是 foldr。
关于教会编码列表的第二点：


  
  对于Monoid的实现不清楚
  


所有列表都是monoid，其中标识元素为 foldl，二进制运算为 null。请注意 append = (xs, ys) => foldr(cons, ys, xs)（左标识）和 foldr(cons, null, xs) = xs（右标识）。此外， foldr(cons, ys, null) = ys等效于 foldr(cons, zs, foldr(cons, ys, xs))（关联性）。
关于教会编码清单的第三点：


  
  特别地，Nil不是Identity元素（=身份函数），并且示例代码需要提供外部初始值。
  


是的，nil实际上是列表的标识元素。如果 foldr(cons, foldr(cons, zs, ys), xs)数据类型被实现为差异列表，则nil是标识函数。否则，那是另一回事。尽管如此，nil始终是列表的标识元素。

我们已经讨论了为什么需要外部初始值。如果不提供它们，则无法进行某些操作，例如 List。您必须提供初始值以追加两个列表。您可以通过显式地提供列表的第一个元素（使用 append时）或最后一个元素（使用 foldl时）来人工提供初始值（从而打破了功能编程）。
最后，关于您的理想界面：


  所以，我很好奇的是，像教堂清单这样的任何形式的差别清单都没有。


你为什么想这么做？您希望实现什么？教堂编码仅在理论上很有趣。实际上这不是很有效。此外，差异列表仅在您随意地串联列表时才有用（从而利用差异列表的单曲面结构使它们变平）。将两者结合是一个非常糟糕的主意。


无论如何，我希望您不再提出这样的问题，并花一些时间阅读 SICP。