如何在Haskell中编写一个恒定空间长度函数?

栏目: 编程语言 · 发布时间: 7年前

内容简介:翻译自:https://stackoverflow.com/questions/2777686/how-do-i-write-a-constant-space-length-function-in-haskell

长度:: [a] – >的规范实现Int是:

length [] = 0
length (x:xs) = 1 + length xs

这是非常漂亮但由于使用线性空间而遭受堆栈溢出.

尾递归版:

length xs = length' xs 0
  where length' [] n = n
        length' (x:xs) n = length xs (n + 1)

没有遇到这个问题,但我不明白这是如何在惰性语言中以恒定的空间运行的.

运行时是否在运行列表时累积了大量(n 1)个thunks?不应该这个函数Haskell消耗O(n)空间并导致堆栈溢出?

(如果重要的话,我正在使用GHC)

是的,你遇到了累积参数的常见陷阱.通常的做法是对累积参数进行严格评估;为此我喜欢严格的应用程序运算符$!.如果你不强制严格,GHC的优化器可能会认为这个函数是严格的,但它可能不是.肯定不是依赖它 – 有时你想要一个累积的参数来懒惰地评估和O(N)空间就好了,谢谢.

How do I write a constant-space length function in Haskell?

如上所述,使用严格的应用程序运算符强制评估累积参数:

clength xs = length' xs 0
  where length' []     n = n
        length' (x:xs) n = length' xs $! (n + 1)

$的类型!是(a – > b) – > a – > b,它强制在应用函数之前评估a.

翻译自:https://stackoverflow.com/questions/2777686/how-do-i-write-a-constant-space-length-function-in-haskell


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

网页设计创意书(卷2)

网页设计创意书(卷2)

麦克尼尔 / 图灵编辑部 / 人民邮电 / 2012-1 / 49.00元

《网页设计创意书(卷2)》是《网页设计创意书》的卷2,但并非其简单补充,而是作者基于近几年网站发展新趋势的再创作。《网页设计创意书(卷2)》先讲解了如何从他人的优秀设计中寻找灵感,接着阐述了重点、对比、平衡、对齐等网站设计的基本原则,然后将网站按类型、设计元素、风格和主题、结构样式和结构元素分类,并分章介绍了每一类的设计技巧。《网页设计创意书(卷2)》语言简练,结合作者精挑细选的网站实例,通俗易懂......一起来看看 《网页设计创意书(卷2)》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

MD5 加密
MD5 加密

MD5 加密工具