0 javascript arrays functional-programming list church-encoding
这是之后的顺序问题
和
在这里，我想表达我对我的问题的贡献者的尊重和赞赏，尤其是@Aadit M Shah 和@user633183
.
一个差异列表是一个函数，它接受一个列表，并预置另一个列表吧。例如：
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
更好的是，您可以将它们打包成一个整洁的小类，其中函数组合是点运算符：
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 对进行编码的替代方法，可以通过使用右折叠函数识别列表来对列表进行编码。例如，一个包含三个元素 x、y 和 z 的列表可以由一个高阶函数编码，当应用于组合器 c 和值 n 时，返回 cx (cy (czn))。
user633183 的解决方案很棒。它使用使用右折叠的Church 列表编码来减轻对延续的需求，从而产生更简单的代码，易于理解。这是她的解决方案，修改后
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是迄今为止累积的 Church 编码列表。最初，它是空列表。调用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向后折叠向后列表。因此，看起来您正在构建并向前折叠列表。
我喜欢在差异列表中看到的是
我不喜欢什么
事实上，我在Church List 中喜欢/不喜欢的是上述内容的反面。
我喜欢
我不喜欢
一个列表可以通过用它的右折叠功能识别它来编码
对 Monoids 的关系不清楚
特别是Nil不是Identity元素（=identity function），示例代码需要提供外部初始值。
所以，我很好奇的是有没有像 Church-list 这样的差异列表的形式化。
规范是
基本上，这是一个差异列表
独立于 JavaScipt 数组实现
初始值是内置的identety 函数。
谢谢你。
您的一系列问题背后的问题根源在于您坚持使用L(1)(2)(3)语法来构建列表。这种语法没有任何意义，人们一次又一次地告诉你放弃使用这种语法：
user633183对您的第一个问题的回答：
函数柯里化和可变参数不能真正一起工作。一旦您意识到以下两个表达式不兼容，这是一个显而易见的限制
Run Code Online (Sandbox Code Playgroud)L (1) -> [ 1 ] L (1) (2) -> [ 1, 2 ]上面
L (1)返回一个列表，但在第二个表达式中，我们希望L (1)是一个可以应用于 的函数2。L (1)可以是一个列表，也可以是一个生成列表的函数；它不能同时存在。
首先，如果您想拥抱函数式编程，请避免可变参数函数或奇怪的混合返回类型。
user633183对你的第三个问题的回答：
说到类型，让我们来看看类型
autoCons——Run Code Online (Sandbox Code Playgroud)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在列表的开头放置一个新元素。
您似乎对列表的结构有一些非正统的看法：
首先，您认为列表的头部应该始终为零：
lisp/Scheme 教科书中解释的构建列表的传统方法是非常错误的。Nil 不应该在列表的尾部，而应该在头部。Lisp/Scheme 扭曲了列表结构（尾部为 0 = nil）给编程世界带来了很多混乱。
其次，您认为您不必为列表折叠提供初始值：
我仍然不知道您坚持使用“init”值进行折叠等的任何理由，查看一些库，他们不使用“init”，我认为它们更合理。github.com/benji6/church/blob/master/src/lists.js准确地说，他们基本上使用 Zero=Identity 作为更有意义的 init。
这两种信念都是不明智的。要理解为什么我们需要查看列表的代数结构：
????????????????????????????? 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 of a
? ????????????????????????? is
| | ????????????????????? either null
| | | ?????????????????? or
| | | | ?????????????? cons of
| | | | | ?????????? an a and
? | | | | | ???? another List of a.
?????? ? ???? | ???? | ??????
List a = null | cons (a, List a)
注意：使用snoc. 我们可以定义List为List a = null | snoc (List a, a)。但是，使用cons. 现在，取决于我们是否使用cons或snoc定义List数据类型，将新元素放在列表前面或将新元素放在列表后面变得昂贵：
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.
注意：接下来的两段使用 Haskell 语法。
差异列表用于分摊昂贵操作的成本，方法是将列表的连接延迟到需要时，然后以最有效的顺序连接它们。例如，假设我们有as ++ bs ++ cs ++ ds连接四个列表的表达式。如果我们使用 的cons实现，List那么最有效的连接顺序是as ++ (bs ++ (cs ++ ds))，这就是(++)Haskell 中的运算符是右结合的原因。另一方面，如果我们使用 的snoc实现，List那么最有效的连接顺序是((as ++ bs) ++ cs) ++ ds。
使用 的cons实现时List，差异列表的形式为(xs ++)wherexs是常规列表。我们可以使用常规函数组合（即(as ++) . (bs ++) . (cs ++) . (ds ++)）将它们向前组合。使用 的snoc实现时List，差异列表的形式为(++ xs)wherexs是常规列表。我们可以使用常规函数组合（即(++ ds) . (++ cs) . (++ bs) . (++ as)）向后组合它们。这是使用 的cons实现List更可取的另一个原因。
现在，让我们换个角度谈谈非空列表的部分内容。当涉及到列表（无论我们使用cons的实现List或snoc实施List）的条款head，tail，init并last有非常具体的含义：
in front of behind
?????????????????????????????
cons ? Inexpensive ? Expensive ?
?????????????????????????????
snoc ? Expensive ? Inexpensive ?
?????????????????????????????
head一个非空列表的是列表的第一个元素。tail一个非空列表的是一切，但该列表的第一个元素。init一个非空列表的是一切，但在列表的最后一个元素。last一个非空列表的是，好了，列表的最后一个元素。因此，取决于我们是使用cons还是snoc定义List数据类型，headandtail或initandlast变得昂贵：
head tail
? ??????????????????????
cons(1, cons(2, cons(3, null)));
?????????????? ?
init last
init last
?????????????????????? ?
snoc(snoc(snoc(null, 1), 2), 3);
? ?????
head tail
无论如何，这就是为什么“Nil 不应该在列表的尾部，而应该在头部”这句话没有任何意义的原因。列表的头部是列表的第一个元素。Nil 不是列表的第一个元素。因此，声明 nil 应该始终是列表的头部是不合逻辑的。
现在，让我们转向折叠。取决于我们是否使用cons或snoc定义List的数据类型，可以是foldl或foldr变成尾递归：
head / tail init / last
?????????????????????????????
cons ? Inexpensive ? Expensive ?
?????????????????????????????
snoc ? Expensive ? Inexpensive ?
?????????????????????????????
如果语言执行尾调用优化，尾递归通常更有效。然而，结构递归更自然，并且在具有惰性求值的语言中它变得更高效并且可以处理无限数据结构。说到无限数据结构，cons实现无限向前增长（即cons(1, cons(2, cons(3, ....)))），而snoc实现无限向后增长（即snoc(snoc(snoc(...., 1), 2), 3)）。还有一个理由，更喜欢cons了snoc。
不管怎样，让我们试着理解为什么需要折叠的初始值。假设我们有以下列表，xs = cons(1, cons(2, cons(3, null)))我们使用 折叠它foldr：
foldl foldr
???????????????????????????????????????????????
cons ? Tail Recursion ? Structural Recursion ?
???????????????????????????????????????????????
snoc ? Structural Recursion ? Tail Recursion ?
???????????????????????????????????????????????
如您所见，当我们使用 using 来减少列表时，我们foldr实际上是将 each 替换为with cons，func而我们正在替换null为init。这允许您通过折叠第一个列表，免去做事喜欢追加两个列表cons与cons和null与第二列表，ys = cons(4, cons(5, cons(6, null)))：
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr(func, init, xs) -> / \
2 cons 2 func
/ \ / \
3 null 3 init
现在，如果您不提供初始值，那么您就不会保留列表的结构。因此，您将无法附加两个列表。事实上，您甚至无法重建相同的列表。考虑：
cons cons
/ \ / \
1 cons 1 cons
/ \ -> foldr(cons, ys, xs) -> / \
2 cons 2 cons
/ \ / \
3 null 3 cons
/ \
4 cons
/ \
5 cons
/ \
6 null
使用foldr1您可以在不提供初始值（即foldr1(plus, xs)）的情况下找到列表的总和，但是如何在不诉诸巫术的情况下重建相同的列表？如果您愿意提供初始值，那么您可以优雅地编写foldr(cons, null, xs). 否则，除非您违反函数式编程的原则并使用副作用来人为地从其内部提供初始值，否则不可能这样做func。无论哪种方式，您都将提供一个初始值，无论是通过显式指定初始值还是将列表的最后一个元素作为func.
选择更简单的替代方案。显式提供初始值。正如Python之禅所说：
美丽总比丑陋好。
显式优于隐式。
简单胜于复杂。
...
特殊情况不足以打破规则。
无论如何，进入最后一部分。
我不回答你的任何问题就给你讲课是不合适的。因此：
关于差异列表，您的以下陈述是错误的：
- 标识元素是标识函数，不需要提供外部初始值。
实际上，如果您折叠差异列表，那么您仍然需要提供一个初始值。为了参考，见foldr从功能Data.DList包上Hackage。
关于 Church 编码列表，您有以下问题：
- 我不知道为什么它必须不是左折叠而是右折叠？
由于您的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颠倒了论点。因此，foldrforcons等价于foldlfor snoc，反之亦然，这是 user633183 注意到的。
请注意，我使用延续的初始解决方案实际上确实使用了foldlfor cons，但为了做到这一点，我必须以某种方式反转列表，因为它是向后构建的。这就是延续的目的，以反转列表。后来我才意识到我根本不需要反转列表。我可以简单地使用foldr而不是foldl.
关于你关于 Church 编码列表的第二点：
- 对 Monoids 的关系不清楚
所有列表都是幺半群，其中单位元素是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)（结合性）。
关于你关于 Church 编码列表的第三点：
- 特别是Nil不是Identity元素（=identity function），示例代码需要提供外部初始值。
是的， nil 实际上是列表的标识元素。如果List数据类型实现为差异列表，则 nil 是标识函数。否则，它是别的东西。尽管如此， nil 始终是列表的标识元素。
我们已经讨论了为什么需要外部初始值。如果您不提供它们，那么您将无法执行某些操作，例如append. 您必须提供初始值才能附加两个列表。要么显式提供初始值，要么通过将列表的第一个元素（使用时foldl）或最后一个元素（使用时foldr）作为特殊情况（从而破坏函数式编程的原则）来人为地提供初始值。
最后，关于你梦想中的界面：
所以，我很好奇的是有没有像 Church-list 这样的差异列表的形式化。
你为什么想这么做？你希望达到什么目标？教会编码只是在理论上有趣。在实践中效率不是很高。此外，差异列表仅在您随意连接列表时才有用（从而利用差异列表的幺半群结构将它们展平）。将两者结合起来是一个非常糟糕的主意。
不管怎样，我希望你不要问这样的问题，花点时间阅读SICP。
| 归档时间： |
|
| 查看次数： |
1007 次 |
| 最近记录： |