今天我找到了Haskell中斐波那契数列的定义:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
在探索中,我将“tribonacci”数字写成了以下形式:
tribs = 0 : 0 : 1 : zipWith (+) (zipWith (+) tribs (tail tribs)) (drop 2 tribs)
这个方法很好用,所以我尝试使用相同的基本思路来概括任何“斐波那契类型”的序列:
nbonacci n = (take n (repeat 0)) ++ [1] ++ (z n)
where z 1 = zipWith (+) (nbonacci n) (drop 1 (nbonacci n))
z x = zipWith (+) (z (x-1)) (drop x (nbonacci n))
下面这种方法也可以:它能正确给出我想要的数列。不幸的是,这种方法速度非常慢,甚至比生成相同的斐波那契和Tribonacci数列时还要慢很多。有什么方法可以用更高的性能来表达相同的想法吗?
go
,这个列表在所有相互调用的函数之间是共享的,避免了一直重新计算它的情况。你原来的代码中到处都有nbonacci n
,这是一个函数应用,这些结果默认情况下是不共享的。 - Ørjan Johansen