使用右折叠和差异列表的教会编码列表 [英] Church encoding of lists using right folds and difference lists

问题描述

以下是

如何存储Monoidal List功能链的数据？

和

从函数中提取数据没有数组的链条

在此我想对我的问题的贡献者表示敬意和赞赏，特别是@Aadit M Shah和@ user633183

and here I would like to express my respect and appreciation for contributors to my Questions, especially by @Aadit M Shah and @user633183

。

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

A 差异列表是一个获取列表并在其前面添加列表的函数。例如：

A difference list is a function that takes a list and prepends another list to it. For example:

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.

关于差异列表的一个很酷的事情是它们形成一个幺半群，因为它们只是内功能：

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

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

Even better, you can package them into a neat little class where function composition is the dot operator:

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 的值，如下所示：

You can use the apply method to retrieve the value of the DList as follows:

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数组）上使用差异列表的一个优点是，连接更有效，因为列表从右到左连接在一起。因此，如果您连接多个列表，它不会一遍又一遍地复制相同的值。

An advantage of using difference lists over regular lists (functional lists, not JavaScript arrays) is that concatenation is more efficient because the lists are concatenated from right to left. Hence, it doesn't copy the same values over and over again if you're concatenating multiple lists.

---

教会编码列表

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

---

Church Encoding List

As an alternative to the encoding using Church pairs, a list can be encoded by identifying it with its right fold function. For example, a list of three elements x, y and z can be encoded by a higher-order function that when applied to a combinator c and a value n returns c x (c y (c z n)).

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

user633183的解决方案太棒了它使用使用正确折叠的教会编码列表来减少延续的需要，从而产生更简单的代码，易于理解。这是她的解决方案，修改为使 foldr 看起来像 foldl ：

user633183's solution is brilliant. It uses the Church encoding of lists using right folds to alleviate the need for continuations, resulting in simpler code which is easy to understand. Here's her solution, modified to make foldr seem like 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 是到目前为止累积的Church编码列表。最初，它是空列表。调用 g 从右侧折叠。但是，我们也从右侧构建列表。因此，似乎我们正在构建列表并从左侧折叠它，因为我们编写它的方式。

Here g is the Church encoded list accumulated so far. Initially, it's the empty list. Calling g folds it from the right. However, we also build the list from the right. Hence, it seems like we're building the list and folding it from the left because of the way we write it.

---

---

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

If all these functions are confusing you, what user633183 is really doing is:

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 向后折叠向后列表。因此，看起来你正在构建并折叠列表。

As you can see, she is building the list backwards and then using reduceRight to fold the backwards list backwards. Hence, it looks like you're building and folding the list forwards.

---

什么我喜欢在差异列表中看到

---

What I like to see in Diffrence List is

1. 看起来很自然而且直截了当。


2. With concattation（flatten），它形成monoids


3. Identity元素是身份函数，不需要提供外部初始值。

我不喜欢

1. 至少，提供的示例代码取决于JavaScript数组

教会名单中我喜欢/不喜欢的事实上是上述的相反。

What I like/dislike in Church List is, in fact, the opoosite of the above.

我喜欢

1. 它独立于JavaScript数组实现，它可以自己定义操作：user633183的解决方案

1. It's indpendent of JavaScript Array implementation, and it can define operations by itself : user633183's solution

我不喜欢

1. 我不知道为什么它一定不能留下而是钻井平台ht fold？

列表可以通过识别它的右折叠函数进行编码

a list can be encoded by identifying it with its right fold function

1. 不清楚对Monoids的影响

1. Unclear for the realation to Monoids

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

Especailly, Nil is not Identity element( = identity function), and the sample code need for external initial values provided.

所以，我很好奇的是教会列表中的差异列表的任何形式化。

So, what I am curious is is there any formalization of Diffrence list like Church-list.

具体将是

• 基本上，它是一个差异列表

• Basically, it's a difference list

独立于JavaScipt数组实现

Indenpendent of JavaScipt Array implementation

初始值是内置的identety函数。

The initial value is the built-in identety function.

Thsnk you。

Thsnk you.

推荐答案

问题的根源

你的一系列问题背后的问题的根源是你坚持使用 L（1）（2）（3） 构造列表的语法。这种语法没有任何意义，人们一次又一次地告诉你放弃使用这种语法：

The Root of the Problem

The root of the problem underlying your series of questions is your insistence on using the L(1)(2)(3) syntax to construct a list. This syntax just doesn't make any sense, and people have told you time and again to forgo using this syntax:

1. < a href =https://stackoverflow.com/a/51286874/783743> user633183对你的第一个问题的回答：

函数currying和variadic参数并不能真正协同工作。一旦您意识到以下两个表达式不兼容，这是一个明显的限制

Function currying and variadic arguments don't really work together. It's a restriction made obvious once you realize that the following two expressions are incompatible

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

高于 L（1）返回一个列表，但在第二个表达式中，我们希望 L（1）是一个我们可以应用于 2 。 L（1）可以是列表或它可以是生成列表的函数;它不能同时出现。

Above L (1) returns a list, but in the second expression we expect L (1) to be a function that we can apply to 2. L (1) can be a list or it can be a function that produces a list; it cannot be both at the same time.

Bergi的评论关于你的第二个问题：

Bergi's comment on your second question:

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

First of all, if you want to embrace functional programming, avoid variadic functions or curiously mixed return types.

user633183对第三个问题的回答：

所以说到类型，让我们检查 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

Well autoCons always returns a lambda, but that lambda has a type that we cannot determine – sometimes it returns another lambda of its same kind, other times it returns a completely different result; in this case some number, 6

因此，我们无法轻松混合和组合 autoCons 表达式与我们程序的其他部分。如果你放弃这个不正常的驱动器来创建可变的curried接口，你可以创建一个 autoCons ，它是可输入的

Because of this, we cannot easily mix and combine autoCons expressions with other parts of our program. If you drop this perverse drive to create variadic curried interfaces, you can make an autoCons that is type-able

我认为没有任何理由使用 L（1）（ 2）（3）语法，当你可以简单地写 toList（[1,2,3]）：

I don't see any good reason to use the L(1)(2)(3) syntax when you could simply write 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 将新元素放在列表的开头。

Furthermore, if your only reason to use the L(1)(2)(3) syntax is to “efficiently” push an element to the end of the list, then you can do so with normal lists too. Just build the list backwards and use cons to put a new element at the beginning of the list.

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

You seem to have some unorthodox beliefs about the structure of lists:

1. 首先，您相信列表的头部应该始终为零：

1. First, you believe that the head of the list should always be nil:

构建列表的传统方式，如lisp / Scheme教科书中所解释的那样错误。 Nil不应该在列表的尾部，而应该在头部。 Lisp / Scheme带来了如此多的混乱，其中包含扭曲列表结构（尾部为0 = nil）到编程世界。

the traditional way to construct list as explained in lisp/Scheme textbook is very wrong. Nil should not be in the tail of the list, instead it should be in the head. Lisp/Scheme brought so much confusion having twisted list structure(0 =nil in the tail) to programming world.

第二，您认为您不应该为列表折叠提供初始值：

Second, you believe that you should not have to provide an initial value for list folds:

我仍然不知道你有什么理由坚持使用init值来折叠等等。看看一些库，它们不使用init，并且我认为他们更合理。 github.com/benji6/church/blob/master/src/lists。 js 确切地说，他们基本上使用Zero = Identity for init更有意义。

I still don't know any justification you stick to use "init" value for fold etc, Looking at some libraries, they don't use "init", and I think they are more reasonable. github.com/benji6/church/blob/master/src/lists.js To be precise, they basically use Zero=Identity for init that makes more sense.

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

Both of these beliefs are ill-informed. To understand why we need to look at the algebraic structure of lists:

   ┌──────────────────────────── 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 将新元素放在另一个（可能是空的）元素列表前面，形成非空列表。我们将新元素放在原始列表的前面而不是它后面，因为它更自然：

A list can either be empty or non-empty. Empty lists are represented by null. Non-empty lists are formed by putting a new element in front of another (possibly empty) list of elements by using cons. We put the new element in front of the original list instead of behind it because it's more natural:

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 定义为列出a = null | snoc（列出a，a）。但是，使用 cons 更自然。现在，取决于我们是否使用 cons 或 snoc 来定义列表数据类型，要么将新元素放在列表前面，要么将新元素放在列表后面会变得很昂贵：

Note: There's nothing inherently wrong with using snoc. We could define List as List a = null | snoc (List a, a). However, it's just more natural to use cons. Now, depending upon whether we use cons or snoc to define the List data type, either putting new elements in front of a list or putting new elements behind a list becomes expensive:

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

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

Note: Using Haskell syntax for the next two paragraphs.

差异列表用于通过延迟t来摊销昂贵操作的成本列表连接直到需要，然后以最有效的顺序连接它们。例如，假设我们将表达式设置为++ bs ++ cs ++ ds ，其中我们连接四个列表。如果我们使用 cons List 的实现，那么最有效的连接顺序是 as ++（bs ++（cs ++ ds）），这就是为什么 （++） 运算符是右关联的。另一方面，如果我们使用列表的 snoc 实现，那么最有效的连接顺序是（（as ++ bs）++ cs）++ ds 。

Difference lists are used to amortize the cost of the expensive operation by delaying the concatenation of lists until required and then concatenating them in the most efficient order. For example, suppose we have the expression as ++ bs ++ cs ++ ds where we are concatenating four lists. If we're using the cons implementation of List then the most efficient order of concatenation is as ++ (bs ++ (cs ++ ds)), which is why the (++) operator in Haskell is right associative. On the other hand, if we're using the snoc implementation of List then the most efficient order of concatenation is ((as ++ bs) ++ cs) ++ ds.

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

When using the cons implementation of List, a difference list has the form (xs ++) where xs is a regular list. We can compose them forwards using regular function composition (i.e. (as ++) . (bs ++) . (cs ++) . (ds ++)). When using the snoc implementation of List, a difference list has the form (++ xs) where xs is a regular list. We can compose them backwards using regular function composition (i.e. (++ ds) . (++ cs) . (++ bs) . (++ as)). This is another reason why using the cons implementation of List is more preferable.

现在，让我们改变方向，谈谈非空列表的部分内容。当涉及到列表时（无论我们是否使用 cons List 的实现或 snoc List 的实现），条款 head ， tail ， init 和 last 具有非常具体的含义：

Now, let's change gears and talk about parts of a non-empty list. When it comes to lists (regardless of whether we're using the cons implementation of List or the snoc implementation of List), the terms head, tail, init and last have very specific meanings:

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

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

1. 主管非空列表的 是列表的第一个元素。


2. tail 非空列表是列表的第一个元素。


3. init 非空列表是除列表最后一个元素之外的所有内容。


4. <非空列表的code> last 是列表的最后一个元素。

1. The head of a non-empty list is the first element of the list.
2. The tail of a non-empty list is everything but the first element of the list.
3. The init of a non-empty list is everything but the last element of the list.
4. The last of a non-empty list is, well, the last element of the list.

因此，取决于我们是否使用 cons 或 snoc 来定义列表数据类型， head 和 tail 或 init 并且最后变得昂贵：

Hence, depending upon whether we use cons or snoc to define the List data type, either head and tail or init and last becomes expensive:

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

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

Anyway, this is the reason why the statement, “Nil should not be in the tail of the list, instead it should be in the head,” makes no sense. The head of the list is the first element of the list. Nil is not the first element of the list. Therefore, it's illogical to state that nil should always be the head of the list.

现在，让我们进入折叠。取决于我们是否使用 cons 或 snoc 来定义列表数据类型， foldl 或 foldr 变为尾递归：

Now, let's move onto folds. Depending upon whether we use cons or snoc to define the List data type, either foldl or foldr becomes tail recursive:

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

如果语言执行 tail调优优化。但是，结构递归更多是自然，而在具有延迟评估的语言中，变得更有效率，它可以在无限数据结构上工作。说到无限的数据结构， cons 实现无限向前增长（即 cons（1，cons（2，cons（3，....） ）））而 snoc 实现无限向后增长（即 snoc（snoc（snoc（....，1） ），2），3））。另一个原因是 cons 超过 snoc 。

Tail recursion is usually more efficient if the language performs tail call optimization. However, structural recursion is more natural, and in languages with lazy evaluation it becomes more efficient and it can work on infinite data structures. Speaking of infinite data structures, the cons implementation grows infinitely forwards (i.e. cons(1, cons(2, cons(3, ....)))) whereas the snoc implementation grows infinitely backwards (i.e. snoc(snoc(snoc(...., 1), 2), 3)). Yet another reason to prefer cons over snoc.

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

Anyway, let's try to understand why the initial value of a fold is required. Suppose we have the following list, xs = cons(1, cons(2, cons(3, null))) and we fold it using foldr:

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

正如您所看到的，当我们使用 foldr 减少列表时，我们基本上会替换每个 cons with func 我们用 init null C>。这允许你通过折叠第一个列表来附加两个列表，用 cons 替换 cons 和 null 第二个列表， ys = cons（4，cons（5，cons（6，null）））：

As you can see, when we reduce a list using foldr we're essentially replacing every cons with func and we're replacing null with init. This allows you to do things like append two lists by folding the first list, replacing cons with cons and null with the second list, ys = cons(4, cons(5, cons(6, 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

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

Now, if you don't provide an initial value then you aren't preserving the structure of the list. Hence, you won't be able to append two lists. In fact, you won't even be able to reconstruct the same list. Consider:

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

使用 foldr1 您可以在不提供初始值的情况下找到列表的总和（即 foldr1（加上，xs）），但是如何在不诉诸巫术的情况下重建相同的列表？如果您愿意提供初始值，那么您可以优雅地编写 foldr（cons，null，xs）。否则，除非你违反函数式编程的原则并使用副作用从 func 本身内人为地提供初始值，否则不可能这样做。无论哪种方式，您将提供初始值，无论是通过显式指定初始值还是通过将列表的最后一个元素作为 func 中的特殊情况处理。

Using foldr1 you can find the sum of the list without providing an initial value (i.e. foldr1(plus, xs)), but how would you reconstruct the same list without resorting to witchcraft? If you're willing to provide an initial value then you can elegantly write foldr(cons, null, xs). Otherwise, it's impossible to do so unless you break the principles of functional programming and use side effects to artificially provide an initial value from within func itself. Either way, you are going to provide an initial value whether it's by explicitly specifying an initial value or by handling the last element of the list as a special case within func.

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

Choose the simpler alternative. Explicitly provide an initial value. As the Zen of Python states:

美丽胜过丑陋。

显式优于隐式。

简单比复杂更好。 />
...

特殊情况不足以违反规定。

无论如何，转到最后一部分。

Anyway, moving on to the final section.

如果不回答你的任何问题，我会告诉你是不合适的。因此：

It would be improper of me to lecture you without answering any of your questions. Hence:

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

1. With respect to difference lists, your following statement is wrong:

1. 标识元素是标识函数，不需要提供外部初始值。

1. Identity element is identity function, and no need for external initial values provided.

实际上，如果折叠差异列表，则仍需要提供初始值。有关参考，请参阅 <$ c来自Hackage上的 Data.DList 包的$ c> foldr 函数。

Actually, if you fold a difference list then you still need to provide an initial value. For reference, see the foldr function from the Data.DList package on Hackage.

关于Church编码列表，您有以下问题：

With respect to Church encoded lists, you had the following question:

1. 我不知道不知道为什么它一定不能留下而是正确的折叠？

因为你的不确定 L（1）（2）（3）语法，你只能向后建立列表（即 L（1）（2）（3）= cons （3，缺点（2，缺点（1，null））））。因此，如果你想折叠列表“ forwards”那么你必须使用 foldr 而不是 foldl 。请注意，如果我们使用 snoc 而不是 cons 那么它实际上是转发（即 L（1） ）（2）（3）= snoc（snoc（snoc（null，1），2），3））。这是因为 snoc 只是 cons ，其参数被翻转。因此，对于 cons ， foldr 相当于 foldl snoc ，反之亦然，这是user633183注意到的。

Because of your wonky L(1)(2)(3) syntax, you can only build the list backwards (i.e. L(1)(2)(3) = cons(3, cons(2, cons(1, null)))). Hence, if you want to fold the list “forwards” then you have to use foldr instead of foldl. Note that if we use snoc instead of cons then it's actually forwards (i.e. L(1)(2)(3) = snoc(snoc(snoc(null, 1), 2), 3)). This follows from the fact that snoc is just cons with the arguments flipped. Therefore, foldr for cons is equivalent to foldl for snoc and vice versa, which is what user633183 noticed.

请注意，我使用continuation的初始解决方案确实使用了 foldl for cons ，但为了做到这一点，我不得不以某种方式反转列表，因为它是向后构建的。这就是延续的目的，以扭转名单。后来才发现我根本不需要反转清单。我可以简单地使用 foldr 而不是 foldl 。

Note that my initial solution using continuations did in fact use foldl for cons, but in order to do that I had to somehow reverse the list since it was being built backwards. That's what the continuations were for, to reverse the list. It only later occurred to me that I don't need to reverse the list at all. I could simply use foldr instead of foldl.

关于你关于教会编码列表的第二点：

With respect to your second point about Church encoded lists:

1. 不清楚对Monoids的启示

所有列表都是monoids，其中identity元素是 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））相当于 foldr（cons，foldr（cons，zs，ys） ），xs）（关联性）。

All lists are monoids, where the identity element is null and the binary operation is append = (xs, ys) => foldr(cons, ys, xs). Note that foldr(cons, null, xs) = xs (left identity) and foldr(cons, ys, null) = ys (right identity). Furthermore, foldr(cons, zs, foldr(cons, ys, xs)) is equivalent to foldr(cons, foldr(cons, zs, ys), xs) (associativity).

关于教会编码列表的第三点：

With respect to your third point about Church encoded lists:

1. Especailly, Nil is not Identity element( = identity function), and the sample code need for external initial values provided.

Yes, nil is in fact the identity element for lists. If the List data type is implemented as a difference list then nil is the identity function. Otherwise, it’s something else. Nevertheless, nil is always the identity element for lists.

Yes, nil is in fact the identity element for lists. If the List data type is implemented as a difference list then nil is the identity function. Otherwise, it's something else. Nevertheless, nil is always the identity element for lists.

We’ve already discussed why external initial values are necessary. If you don’t provide them, then you can’t do certain operations like append. You have to provide the initial value to append two lists. Either you provide the initial value explicitly or you provide the initial value artificially by handling the first element (when using foldl) or last element (when using foldr) of the list as a special case (and thereby breaking the principles of functional programming).

We've already discussed why external initial values are necessary. If you don't provide them, then you can't do certain operations like append. You have to provide the initial value to append two lists. Either you provide the initial value explicitly or you provide the initial value artificially by handling the first element (when using foldl) or last element (when using foldr) of the list as a special case (and thereby breaking the principles of functional programming).

Finally, with respect to your dream interface:

Finally, with respect to your dream interface:

So, what I am curious is is there any formalization of Diffrence list like Church-list.

So, what I am curious is is there any formalization of Diffrence list like Church-list.

Why would you want to do that? What do you hope to achieve? Church encoding is only interesting in theory. It’s not very efficient in practice. Furthermore, difference lists are only useful when you’re concatenating lists haphazardly (thereby taking advantage of the monoidal structure of difference lists to flatten them). Combining the two is a really bad idea.

Why would you want to do that? What do you hope to achieve? Church encoding is only interesting in theory. It's not very efficient in practice. Furthermore, difference lists are only useful when you're concatenating lists haphazardly (thereby taking advantage of the monoidal structure of difference lists to flatten them). Combining the two is a really bad idea.

Anyway, I hope you stop asking such questions and take some time to read SICP.

Anyway, I hope you stop asking such questions and take some time to read SICP.

这篇关于使用右折叠和差异列表的教会编码列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！