我在学习函数式反应性编程时发现了这句话,来自刘海和保罗·胡达克的《用箭堵住空间泄漏》(第5页):
Suppose we wish to define a function that repeats its argument indefinitely:
repeat x = x : repeat x
or, in lambdas:
repeat = λx → x : repeat x
This requires O(n) space. But we can achieve O(1) space by writing instead:
repeat = λx → let xs = x : xs
in xs
这里的差异似乎很小,但它极大地促进了空间效率。为什么以及如何发生?我最好的猜测是手工评估:
r = \x -> x: r x
r 3
-> 3: r 3
-> 3: 3: 3: ........
-> [3,3,3,......]
如上所述,我们需要为这些递归创建无限的新thunk。然后我尝试评估第二个:
r = \x -> let xs = x:xs in xs
r 3
-> let xs = 3:xs in xs
-> xs, according to the definition above:
-> 3:xs, where xs = 3:xs
-> 3:xs:xs, where xs = 3:xs
在第二种形式中,出现了xs
,并且可以在它出现的每个地方共享,所以我想这就是为什么我们只需要O(1)
空格而不是O(n)
。但是我不确定我是对还是错。
顺便说一句:关键词“共享”来自同一篇论文的第4页:
这里的问题是,标准的按需调用评估规则无法识别函数:
f = λdt → integralC (1 + dt) (f dt)
是相同的:
f = λdt → let x = integralC (1 + dt) x in x
前一种定义导致在对f的递归调用中重复工作,而在后一种情况下,计算是共享的。
你对共享xs
的直觉是正确的。当你写作时,用重复而不是整体的方式重述作者的例子:
repeat x = x : repeat x
该语言无法识别右侧的repeat x
与表达式x:repeat x
产生的值相同。如果你写
repeat x = let xs = x : xs in xs
您显式地创建了一个结构,在计算时如下所示:
{hd: x, tl:|}
^ |
\________/
简单地说,变量是共享的,但函数应用程序不是。在里面
repeat x = x : repeat x
从语言的角度来看,(共同)递归调用repeat与同一个参数是巧合的。因此,如果没有额外的优化(称为静态参数转换),函数将被反复调用。
但是当你写作的时候
repeat x = let xs = x : xs in xs
没有递归函数调用。取一个x
,用它构造一个循环值xs
。所有的分享都是明确的。
如果你想更正式地理解它,你需要熟悉惰性评估的语义,比如惰性评估的自然语义。
用图片最容易理解:
>
第一个版本
repeat x = x : repeat x
创建一个以thunk结尾的(:)
构造函数链,它将根据您的要求用更多构造函数替换自己。因此,O(n)空间。
https://imgs.xnip.cn/cj/n/85/ba05b47a-64f9-46f8-a2a6-922c83ef3715.png" width="100%" height="100%" />
第二个版本
repeat x = let xs = x : xs in xs
使用let
来"喜结连理",创建一个引用自身的(:)
构造函数。
本文向大家介绍怎么让body高度自适应屏幕?为什么?相关面试题,主要包含被问及怎么让body高度自适应屏幕?为什么?时的应答技巧和注意事项,需要的朋友参考一下 同楼上,html,body同时设置成100%才有效,html百分比是相对于浏览器而言的,其他元素相对于父元素。 注意:这样设置会使不起作用,之前遇到过这种问题,不对的请指正。
问题内容: 在Swift中,您可以使用if let可选绑定将可选内容解包为具有相同名称的常量或变量: 对于语句中的所有内容,可选项都被包装为常规int。 同样,我可以使用保护语句来达到类似的效果 但是,我不能使用这样的代码: 为什么不? 在保护语句中,如果保护语句的条件失败,则执行else子句,然后退出当前作用域。如果条件成功,则将从保护语句的右括号到当前作用域的结尾创建一个新的变量/常量。 为什
我在Android Studio中有一个项目,通过使用,它的一部分将变得更加简单。但是,每次尝试使用var时,都会出现一个错误:。我的代码:
本文向大家介绍让网页的字体变得清晰,变细用CSS怎么做?相关面试题,主要包含被问及让网页的字体变得清晰,变细用CSS怎么做?时的应答技巧和注意事项,需要的朋友参考一下 让文字变细有两个要素: font-weight + font-family font-weight 来控制粗细还是需要看对应的字体有没有对应的变种字体。因此这就和 font-family 相关。 -webkit-font-smoot
本文向大家介绍让Java代码更高效,包括了让Java代码更高效的使用技巧和注意事项,需要的朋友参考一下 本文简单介绍一下在写代码过程中用到的一些让JAVA代码更高效的技巧。 1,将一些系统资源放在池中,如数据库连接,线程等.在standalone的应用中,数据库连接池可以使用一些开源的连接池实现,如C3P0,proxool和DBCP等,在运行在容器中的应用这可以使用服务器提供的DataSource
本文向大家介绍如何让` 测试 空格`这两个词之间的空格变大?相关面试题,主要包含被问及如何让` 测试 空格`这两个词之间的空格变大?时的应答技巧和注意事项,需要的朋友参考一下 这边有这么两种方法: 通过给标签设置,将这个属性设置成自己想要的值。 将这个空格用一个标签包裹起来,然后设置标签的或者。 我分别用和来处理了和标签: 让我们一起来看看效果: 大家可以看到效果,我用和处理标签,是会呈现不同的效