haskell - 将递归函数转换为尾递归函数。尾递归的概念
问题描述
我正在尝试在haskell中转换一些递归函数。为了获得这类函数的一些经验,我试图理解尾递归的概念。为了获得线索,我想从非常简单的函数开始来理解尾递归背后的概念。以下代码显示了我编写的一个随机递归函数。我想将其转换为尾递归变体,但在实际代码中使用理论概念时遇到问题。
h x = if x > 20 then 50 else x*x + h (x+1)
解决方案
正如 Robin Zigmond 所说,尾递归的概念在 Haskell 中的应用方式与在非惰性语言中的应用方式不同。在具有非惰性语义的语言(因此不是 Haskell)中,实现尾递归的方法是将导致堆栈使用的表达式移动到累积参数,如下所示:
h :: Int -> Int
h x = if x > 20 then 50 else x*x + h (x+1)
g :: Int -> Int
g z = g' z 50 where
g' x y
| x > 20 = y
| otherwise = g' (x+1) (x*x + y)
这里函数体的外部表达式是对其自身的调用,因此如果这是一种非惰性语言,则在解析表达式部分g'
之前,您不需要保留旧递归调用的堆栈帧。x*x + ...
但是,在 Haskell 中,这会进行不同的评估。
在微基准中比较你h
和这个,g
module Main where
import Criterion
import Criterion.Main
main :: IO ()
main = defaultMain [ bgroup "tail-recursion" [ bench "h" $ nf h 1
, bench "g" $ nf g 1
]
]
实际上,您会因此获得更差的性能g'
:
benchmarking tail-recursion/h
time 826.7 ns (819.1 ns .. 834.7 ns)
0.993 R² (0.988 R² .. 0.997 R²)
mean 911.1 ns (866.4 ns .. 971.9 ns)
std dev 197.7 ns (149.3 ns .. 241.3 ns)
benchmarking tail-recursion/g
time 1.742 μs (1.730 μs .. 1.752 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 1.742 μs (1.729 μs .. 1.758 μs)
std dev 47.44 ns (34.69 ns .. 66.29 ns)
g'
你可以通过提出严格的论点来恢复一些性能,
{-# LANGUAGE BangPatterns #-}
g2 :: Int -> Int
g2 z = g' z 50 where
g' !x !y
| x > 20 = y
| otherwise = g' (x+1) (x*x + y)
但它的外观和性能都比原来的差h
:
benchmarking tail-recursion/g2
time 1.340 μs (1.333 μs .. 1.349 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 1.344 μs (1.336 μs .. 1.355 μs)
std dev 33.40 ns (24.71 ns .. 48.94 ns)
编辑:正如 KA Buhr 指出的,我忘记了-O2
GHC 的标志;这样做会提供以下微基准测试结果:
h time: 54.27 ns (48.05 ns .. 61.24 ns)
g time: 24.50 ns (21.15 ns .. 27.35 ns)
g2 time: 25.47 ns (22.19 ns .. 29.06 ns)
在这一点上,累积参数版本确实表现得更好,而BangPatterns
版本也只是表现得一样好,但两者看起来都比原来的差。
因此,在尝试优化代码时通常是一种道德:不要过早地这样做。尤其是在尝试优化 Haskell 代码时的一个道理:在您尝试之前,您不一定知道它很重要,而且通常依赖于库函数的最抽象的解决方案表现良好。
推荐阅读
- react-native - 如何使用带有参数的scrollTo函数是ListView中的目标而不是x和y?
- c# - wpf中的数据绑定与getter中的表达式
- javascript - RegExp 仅与路径匹配包含文件名
- angular - 在 ionic 上打开推送通知时必须查看
- python-3.x - AttributeError:模块“readline”没有属性“set_completer_delims”
- python - 在正数前附加一个加号
- angular - 如何在 Angular 4 中创建 vendor.bundle.js 之前对其进行转换
- c - Linux fread() 上的预读效果
- json - WCF REST JSON 请求:格式化程序异常
- c# - 使用持久 ID 的 C# 将 XML 数据加载到现有数据库中