ylz*_*ang 6 haskell lazy-evaluation
globToRegex' (c:cs) = escape c ++ globToRegex' cs
这个函数不是尾递归的,它说答案依赖于Haskell非严格(懒惰)评估策略.该(++)运营商的简单定义在于以下这不是尾递归.
Run Code Online (Sandbox Code Playgroud)(++) :: [a] -> [a] -> [a] (x:xs) ++ ys = x : (xs ++ ys) [] ++ ys = ys在严格的语言中,如果我们评估
"foo" ++ "bar",则构造整个列表,然后返回.非严格评估在需要之前将大部分工作推迟.如果我们要求表达式的元素,
"foo" ++ "bar"函数定义的第一个模式匹配,我们返回表达式x : (xs ++ ys).因为(:)构造函数是非严格的,所以xs ++ ys可以推迟评估:我们生成更多的结果元素,无论它们需要什么速率.当我们生成更多结果时,我们将不再使用x,因此垃圾收集器可以回收它.由于我们按需生成结果元素,并且不保留我们完成的部分,因此编译器可以在恒定空间中评估我们的代码.
(重点补充.)
上面粗体的解释对Haskell来说是必不可少的,但是
x:(xs ++ ys)会在恒定的空间中评估",怎么样？这听起来像尾递归一样!请记住,这"foo"只是语法糖'f':'o':'o':[].
也就是说,String它只是一个别名,[Char]它只是一个链接的字符列表.
当客户端代码正在使用链接列表时,它会将其分解为头尾(例如x:xs),对头部执行某些操作(如果需要),然后对尾部进行递归.
当你的代码构建链表时,由于懒惰的评估,它需要做的就是返回一个thunk或者保证它会在被要求时返回一个链表.当头被解除引用时,它是按需提供的,并且尾部留作列表其余部分的承诺.
应该很容易看出,只要列表没有被复制或以其他方式存储,每个thunk将被使用一次然后被丢弃,从而整个存储空间是恒定的.
许多严格的语言暴露了一种机制(通常称为生成器)来完成相同类型的惰性列表生成,但是通过惰性求值,这些特性"免费"作为语言的一部分 - 实质上,所有Haskell列表都是生成器!
与其他FP语言相比,依赖于惰性求值而非尾递归是Haskell的一个特征.两者在限制内存使用方面发挥相关作用; 哪一个是适当的机制取决于正在产生的数据.
如果您的输出可能会逐渐消耗,那么您应该更喜欢利用延迟评估,因为输出只会在需要时生成,从而限制堆消耗.如果你急切地构造输出,那么你将自己辞去使用堆,但至少可以通过尾递归来保存堆栈.
如果您的输出无法逐步消耗 - 也许您正在计算Int- 那么懒惰可能会让您留下一堆不需要的东西,其评估会让您的筹码量减少.在这种情况下,需要严格的累加器和尾递归.
所以,如果你渴望你可能会浪费堆构建一个大数据结构.如果你是懒惰的,你可能会推迟对堆的简化(例如减少1 + 1到2),只会在支付吹笛者时最终玷污你的堆栈.
要玩硬币的两面,思考foldl'和foldr.
尾递归会使堆栈保持不变,但是在严格的语言中,堆会随着x : (xs ++ ys)计算而增长.在Haskell中,因为它是非严格的,x所以在计算下一个值之前将被释放(除非调用者x不必要地持有引用),因此堆也将是常量.