Rac*_*oob 44 recursion scheme functional-programming fold racket
在Haskell中,与许多其他函数语言一样,函数foldl被定义为例如foldl (-) 0 [1,2,3,4] = -10.
这没关系,因为foldl (-) 0 [1, 2,3,4]根据定义,((((0 - 1) - 2) - 3) - 4).
但是,在Racket中,(foldl - 0 '(1 2 3 4))是2,因为Racket"智能地"计算如下:(4 - (3 - (2 - (1 - 0)))),确实是2.
当然,如果我们定义辅助功能翻转,像这样:
(define (flip bin-fn)
(lambda (x y)
(bin-fn y x)))
然后我们可以在Racket中实现与Haskell相同的行为:而不是(foldl - 0 '(1 2 3 4))我们可以写:(foldl (flip -) 0 '(1 2 3 4))
问题是:为什么foldl球拍以这种奇怪的(非标准的,非直观的)方式定义,与其他语言不同？
Eli*_*lay 61
Haskell的定义并不统一.球拍,该功能既褶皱具有的输入顺序相同的,因此只需更换foldl由foldr并且得到同样的结果.如果你使用Haskell版本,你会得到不同的结果(通常) - 你可以在两者的不同类型中看到这一点.
(事实上,我认为为了进行适当的比较,你应该避免使用这两个类型变量都是整数的玩具数字例子.)
这有很好的副产品,鼓励您选择其中一个foldl或foldr根据其语义差异.我的猜测是,根据Haskell的顺序,您可能会根据操作选择.你有一个很好的例子:你已经习惯了,foldl因为你想减去每个数字 - 这是一个"明显"的选择,很容易忽略这个事实,这foldl在懒惰的语言中通常是一个糟糕的选择.
另一个区别是Haskell版本比通常的方式更有限于Racket版本:它只在一个输入列表上运行,而Racket可以接受任意数量的列表.这使得输入函数具有统一的参数顺序变得更加重要.
最后,假设Racket偏离"许多其他功能语言"是错误的,因为折叠远非新技巧,而且Racket的根源远远超过Haskell(或其他语言).因此,问题可能是另一种方式:为什么Haskell foldl以一种奇怪的方式定义？ (不,(-)不是一个好借口.)
由于这似乎一次又一次地打扰了人们,我做了一些腿法.这不是决定性的,只是我的二手猜测.如果您了解更多信息,甚至更好,请通过电子邮件向相关人员发送电子邮件并随时进行编辑.具体来说,我不知道做出这些决定的日期,因此以下列表是粗略的顺序.
首先是Lisp,没有提到任何类型的"折叠".相反,Lisp reduce非常不均匀,尤其是考虑到它的类型.例如,:from-end是一个关键字参数,用于确定它是左扫描还是右扫描,它使用不同的累加器函数,这意味着累加器类型取决于该关键字.这是其他黑客的补充:通常第一个值取自列表(除非您指定一个:initial-value).最后,如果你没有指定一个:initial-value,并且列表为空,它实际上将在零参数上应用该函数以获得结果.
所有这些意味着reduce通常用于其名称所暗示的内容:将值列表减少为单个值,其中两种类型通常相同.这里的结论是它为折叠提供了一种类似的目的,但它并不像折叠时通用的列表迭代结构那样有用.我猜这意味着reduce后来的折叠操作之间没有很强的关系.
Lisp之后的第一个相关语言是ML.正如下面的newacct答案中所指出的那样,那里做出的选择是采用统一类型版本(即Racket使用的版本).
下一个参考文献是Bird&Wadler的ItFP(1988),它使用不同的类型(如在Haskell中).但是,他们在附录中指出Miranda具有相同的类型(如在Racket中).
米兰达后来改变了参数顺序(即,从球拍订单转移到哈斯克尔订单).具体来说,该文字说:
警告 - foldl的这个定义与旧版Miranda的定义不同.这里的一个与Bird和Wadler(1988)中的相同.旧的定义有两个"op"颠倒了.
Haskell从Miranda那里拿走了很多东西,包括不同的类型.(但当然我不知道日期,所以米兰达的改变可能是由于哈斯克尔.)无论如何,在这一点上很明显没有达成共识,因此上面相反的问题成立.
OCaml采用Haskell方向并使用不同类型
我猜测"如何设计程序"(又名HtDP)是在大致相同的时期编写的,他们选择了相同的类型.然而,没有动机或解释 - 实际上,在练习之后,它被简单地称为内置函数之一.
当然,Racket对折叠操作的实现是这里提到的"内置插件".
然后是SRFI-1,选择使用相同类型的版本(如Racket).这个决定是约翰大卫斯通的问题,他指出SRFI的评论说
注意:MIT Scheme和Haskell为其函数
reduce和fold函数翻转F的arg顺序.
奥林后来解决了这个问题:他说的只是:
好点,但我希望两个功能之间保持一致.state-value first:srfi-1,SML state-value last:Haskell
特别要注意他对state-value的使用,这表明一致的类型可能比操作符顺序更重要.
"与任何其他语言不同"
作为一个反例,标准ML(ML是一种非常古老且有影响力的函数式语言)的foldl工作原理如下:http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL
球拍foldl和foldr(以及SRFI-1 fold和fold-right)具有的属性
(foldr cons null lst) = lst
(foldl cons null lst) = (reverse lst)
我推测因为这个原因选择了参数顺序.
从 Racket文档中，描述了foldl：
(foldl proc init lst ...+) \xe2\x86\x92 any/c\n您的问题提到了两点：
\n\n\n\n\n输入列表从左到右遍历
\n
和
\n\n\n\n\nFoldl 在恒定空间中处理 lst
\n
为了简单起见，我将推测其实现方式，并使用一个列表：
\n\n(define (my-foldl proc init lst)\n (define (iter lst acc)\n (if (null? lst)\n acc\n (iter (cdr lst) (proc (car lst) acc))))\n (iter lst init))\n正如您所看到的，满足从左到右遍历和恒定空间的要求（注意 中的尾递归iter），但描述中从未指定 的参数顺序。proc因此，调用上述代码的结果将是：
(my-foldl - 0 \'(1 2 3 4))\n> 2\nproc如果我们以这种方式指定参数的顺序：
(proc acc (car lst))\n那么结果将是：
\n\n(my-foldl - 0 \'(1 2 3 4))\n> -10\n我的观点是， 的 文档foldl不对 参数的求值顺序做出任何假设proc，它只需保证使用恒定空间，并且列表中的元素从左到右求值。
附带说明一下，您只需编写以下内容即可获得表达式所需的求值顺序：
\n\n(- 0 1 2 3 4)\n> -10\n