Haskell：改进我的尾递归斐波那契实现 [英] Haskell: Improving my tail-recursive fibonacci implementation

问题描述

  let {
 fibo： ：积分x => [x]  - > x-> x-> x-> [x] 
 fibo lxy 0 = 1 
 fibo lxyn = fibo（l ++ [y + x] ++ [ （x + y）（y + x + y）（n-1）
} 
  

请原谅我将整个实施放在一条线上，因为我使用的是GHCi，并没有完全学会如何将它放入文件并运行（我还没有到达那里）。我想知道的是这个电话：

  fibo [0，1] 0 1 5 
  

可以得到改善。我不想通过0和1的初始列表，然后再次通过0和1的限制。我相信实施可以改变。你可以做什么样的改变？

解决方案

你的算法是尾递归的，但它看起来有其他缺点，即1）你要在结尾添加结果列表，并且它不是懒惰的。

对于1），请注意当附加两个列表 a ++ b ，你必须重新分配 a 。您的情况 a 是斐波纳契数字的增长列表， b 是接下来的两个术语。因此，每次迭代重新分配已经计算出的斐波纳契数，并添加两个更多的元素，这将导致二次运行时间。在 a 的前面加上 b 会更有效率。你将会生成斐波纳契数字，但运行时间将是线性的。然后，如果您想按升序排列序列，您可以反向最后的列表。

请注意，构建按相反顺序排列的列表可让您使用Code-Guru的模式匹配思路轻松获得序列的最后两个条件。对于2），注意在整个计算完成之前，你不能得到列表的第一个元素。比较下面这个懒惰的序列：

  fibs = 0：（go 0 1）
 where ab = b：go b（a + b）
  

即使看起来递归永不停止， code> fibs 只会根据需要进行评估。例如， fibs !! 3 只需拨打去几次。

I have come up with the following tail-recursive fibonacci generator that works:

let {
  fibo :: Integral x => [x]->x->x->x->[x]
  fibo l x y 0 = l
  fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)
}

Pardon me for the whole implementation put in one line because i am using the GHCi and haven't quite learnt how to put this in a file and run (i am yet to reach there). What i want to know is how this call:

fibo [0, 1] 0 1 5

can be improved. I do not want to pass the initial list with 0 and 1 and then pass 0 and 1 again with the limit. I believe that the implementation can be changed. What changes can be done?

解决方案

Your algorithm is tail-recursive, but it looks like it has other drawbacks, namely 1) you are building the result list by appending to the end of it, and 2) it's not lazy.

For 1), note that when you append two lists a ++ b, you essentially have to reallocate a. In your case a is the growing list of fibonacci numbers and b are the next two terms. So each iteration reallocates the fibonacci numbers that have already been computed and adds on two more elements which will result in quadratic running time. It would be more efficient to prepend b to the front of a. You'll be producing the fibonacci numbers in reverse, but the running time will be linear. You can then reverse the list at the end if you want the sequence in ascending order.

Note that building the list in reverse order allows you to easily get at the last two terms of the sequence by using Code-Guru's pattern-matching idea.

For 2), note that you can't get the first element of the list until the entire computation has completed. Compare with the following lazy generation of the sequence:

fibs = 0 : (go 0 1)
  where go a b = b : go b (a+b)

Even though it looks like the recursion never stops, fibs is only evaluated for as much as is needed. For example, fibs !! 3 only calls go a couple of times.

这篇关于Haskell：改进我的尾递归斐波那契实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！