问题的根源
你这一系列问题的根源在于你坚持使用L(1)(2)(3)
构造列表的语法。这种语法没有任何意义,人们一次又一次地告诉你不要使用这种语法:
-
用户633183的回答 https://stackoverflow.com/a/51286874/783743对于你的第一个问题:
函数柯里化和可变参数并不能真正协同工作。一旦您意识到以下两个表达式不兼容,这个限制就会变得显而易见
L (1) -> [ 1 ]
L (1) (2) -> [ 1, 2 ]
Above L (1)
返回一个列表,但在我们期望的第二个表达式中L (1)
成为我们可以应用的函数2
. L (1)
可以是一个列表or它可以是一个生成列表的函数;它不能同时是两者。
-
贝尔吉的评论 https://stackoverflow.com/questions/51297054/how-to-store-data-of-a-functional-chain-of-monoidal-list#comment89595300_51297054关于你的第二个问题:
首先,如果您想拥抱函数式编程,请避免可变参数函数或奇怪的混合返回类型。
-
用户633183的回答 https://stackoverflow.com/a/51460654/783743关于你的第三个问题:
说到类型,让我们检查一下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
Well 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
将新元素放在列表的开头。
列表的代数结构
您似乎对列表的结构有一些非正统的信念:
-
First, 你相信 https://stackoverflow.com/questions/51418212/extracting-data-from-a-function-chain-without-arrays/51460654#comment89918805_51460654列表的头部应该始终为零:
lisp/Scheme 教科书中解释的构建列表的传统方法是非常错误的。 Nil 不应该位于列表的尾部,而应该位于列表的头部。 Lisp/Scheme 扭曲的列表结构(尾部 0 =nil)给编程世界带来了很多混乱。
-
Second, 你相信 https://stackoverflow.com/users/6440264/bayesian-study您不必为列表折叠提供初始值:
我仍然不知道您坚持使用“init”值进行折叠等的任何理由,查看一些库,他们不使用“init”,我认为它们更合理。github.com/benji6/church/blob/master/src/lists.js https://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
。我们将新元素放在原始列表的前面而不是后面,因为这样更自然:
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.
Note:使用本质上没有什么问题snoc
。我们可以定义List
as List a = null | snoc (List a, a)
。然而,使用起来更自然cons
。现在,取决于我们是否使用cons
or snoc
定义List
数据类型,将新元素放在列表前面或将新元素放在列表后面都会变得昂贵:
in front of behind
┌─────────────┬─────────────┐
cons │ Inexpensive │ Expensive │
├─────────────┼─────────────┤
snoc │ Expensive │ Inexpensive │
└─────────────┴─────────────┘
Note:接下来的两段使用 Haskell 语法。
差异列表 https://en.wikipedia.org/wiki/Difference_list用于通过将列表的串联延迟到需要时然后以最有效的顺序串联它们来分摊昂贵操作的成本。例如,假设我们有表达式as ++ bs ++ cs ++ ds
我们正在连接四个列表。如果我们使用cons
实施List
那么最有效的串联顺序是as ++ (bs ++ (cs ++ ds))
,这就是为什么(++) http://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:-43--43-Haskell 中的运算符是右结合的。另一方面,如果我们使用snoc
实施List
那么最有效的串联顺序是((as ++ bs) ++ cs) ++ ds
.
当使用cons
实施List
,差异列表的形式为(xs ++)
where xs
是一个常规列表。我们可以使用常规函数组合将它们向前组合(即(as ++) . (bs ++) . (cs ++) . (ds ++)
)。当使用snoc
实施List
,差异列表的形式为(++ xs)
where xs
是一个常规列表。我们可以使用常规函数组合向后组合它们(即(++ ds) . (++ cs) . (++ bs) . (++ as)
)。这是使用的另一个原因cons
实施List
是更优选的。
现在,让我们换个话题来讨论非空列表的各个部分。当涉及到列表时(无论我们是否使用cons
实施List
or the snoc
实施List
), 条款head
, tail
, init
and last
有非常具体的含义:
head tail
│ ┌──────────┴─────────┐
cons(1, cons(2, cons(3, null)));
└──────┬─────┘ │
init last
init last
┌──────────┴─────────┐ │
snoc(snoc(snoc(null, 1), 2), 3);
│ └─┬─┘
head tail
- The head http://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:head非空列表的第一个元素是列表的第一个元素。
- The tail http://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:tail非空列表的 是除了列表的第一个元素之外的所有内容。
- The init http://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:init非空列表的内容是列表中除最后一个元素之外的所有内容。
- The last http://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:last非空列表的 是列表的最后一个元素。
因此,取决于我们是否使用cons
or snoc
定义List
数据类型,要么head
and tail
or init
and last
变得昂贵:
head / tail init / last
┌─────────────┬─────────────┐
cons │ Inexpensive │ Expensive │
├─────────────┼─────────────┤
snoc │ Expensive │ Inexpensive │
└─────────────┴─────────────┘
不管怎样,这就是为什么“Nil 不应该在列表的尾部,而应该在头部”这样的说法毫无意义的原因。列表的头是列表的第一个元素。 Nil 不是列表的第一个元素。因此,声明 nil 应该始终是列表的头部是不合逻辑的。
现在,让我们转向折叠。取决于我们是否使用cons
or snoc
定义List
数据类型,要么foldl
or foldr
变成尾递归:
foldl foldr
┌──────────────────────┬──────────────────────┐
cons │ Tail Recursion │ Structural Recursion │
├──────────────────────┼──────────────────────┤
snoc │ Structural Recursion │ Tail Recursion │
└──────────────────────┴──────────────────────┘
如果语言执行,尾递归通常会更有效尾调用优化 https://stackoverflow.com/questions/310974/what-is-tail-call-optimization。然而,结构递归更natural https://stackoverflow.com/q/32260444/783743,并且在具有惰性求值的语言中变得更有效率 https://stackoverflow.com/q/3429634/783743它可以处理无限的数据结构。说到无限数据结构,cons
实施无限向前增长(即cons(1, cons(2, cons(3, ....)))
)而snoc
实现无限向后增长(即snoc(snoc(snoc(...., 1), 2), 3)
)。另一个选择的理由cons
over snoc
.
无论如何,让我们尝试理解为什么需要折叠的初始值。假设我们有以下列表,xs = cons(1, cons(2, cons(3, null)))
我们用它来折叠它foldr
:
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr(func, init, xs) -> / \
2 cons 2 func
/ \ / \
3 null 3 init
正如你所看到的,当我们使用foldr
我们基本上正在替换每一个cons
with func
我们正在替换null
with init
。这允许您通过折叠第一个列表来执行诸如附加两个列表之类的操作,替换cons
with cons
and null
与第二个列表,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
现在,如果您不提供初始值,那么您就不会保留列表的结构。因此,您将无法附加两个列表。事实上,您甚至无法重建相同的列表。考虑:
cons func
/ \ / \
1 cons 1 func
/ \ -> foldr1(func, xs) -> / \
2 cons 2 func
/ \ /
3 null 3
Using foldr1
您可以在不提供初始值的情况下找到列表的总和(即foldr1(plus, xs)
),但是如何在不诉诸于的情况下重建相同的列表巫术 https://stackoverflow.com/a/51433691/783743?如果您愿意提供初始值,那么您可以优雅地编写foldr(cons, null, xs)
。否则的话,是不可能做到的,除非你打破函数式编程的原则,利用副作用从内部人为地提供一个初始值func
本身。无论哪种方式,您都将提供一个初始值,无论是通过显式指定初始值还是通过将列表的最后一个元素作为特殊情况处理func
.
选择更简单的替代方案。明确提供初始值。作为Python之禅 https://www.python.org/dev/peps/pep-0020/ states:
美丽总比丑陋好。
显式的比隐式的好。
简单总比复杂好。
...
特殊情况还不足以违反规则。
无论如何,继续最后一部分。
您正在寻找的答案(以及更多)
我不回答你的任何问题就给你讲课是不合适的。因此:
-
关于差异列表,您的以下说法是错误的:
- 单位元是单位函数,并且无需提供外部初始值。
实际上,如果您折叠差异列表,那么您仍然需要提供初始值。作为参考,请参阅foldr https://hackage.haskell.org/package/dlist-0.8.0.4/docs/Data-DList.html#v: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
论点翻转了。所以,foldr
for cons
相当于foldl
for snoc
反之亦然,这是 user633183 注意到的。
请注意,我最初使用延续的解决方案实际上使用了foldl
for cons
,但为了做到这一点,我必须以某种方式反转列表,因为它是向后构建的。这就是延续的目的,颠倒列表。后来我才意识到我根本不需要颠倒列表。我可以简单地使用foldr
代替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))
相当于foldr(cons, foldr(cons, zs, ys), xs)
(关联性)。
-
关于你关于教会编码列表的第三点:
- 特别是,Nil不是Identity元素(=恒等函数),并且示例代码需要提供外部初始值。
是的,nil 实际上是列表的单位元素。如果List
数据类型被实现为差异列表,然后 nil 是恒等函数。否则,那就是另外一回事了。尽管如此,nil 始终是列表的标识元素。
我们已经讨论了为什么外部初始值是必要的。如果您不提供它们,那么您将无法执行某些操作,例如append
. You have提供附加两个列表的初始值。要么显式提供初始值,要么通过处理第一个元素(当使用foldl
)或最后一个元素(当使用foldr
)作为一个特例(从而打破了函数式编程的原则)。
-
最后,关于您梦想的界面:
所以,我很好奇的是,是否有像 Church-list 这样的 Diffrence 列表的形式化。
你为什么想这么做?您希望实现什么目标?教会编码仅在理论上有意义。在实践中效率不是很高。此外,差异列表仅在您随意连接列表时才有用(从而利用差异列表的幺半群结构来展平它们)。将两者结合起来是一个非常糟糕的主意。
无论如何,我希望你停止问这样的问题并花一些时间阅读SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html.