haskell - 斐波那契序列奇怪的输出形式(Haskell)

Question

当我在数字的 optput 中意识到一些“奇怪”的形式时，我正在观看我在 Haskell 中的斐波巴契序列实现的结果。

首先，这是我想出的 Haskell 代码:

fib :: Integer -> [Integer]
fib 0 = [0]
fib 1 = [0, 1]
fib a = (fib' 0 1 [0,1] 1 a)

fib' :: Integer -> Integer -> [Integer] -> Integer -> Integer -> [Integer]
fib' n1 n2 l cont n 
        | cont == n = l
        | otherwise = (fib' n2 n3 (l++[n3]) (cont+1) n)
             where n3 = n2 + n1

对于像 fib 10 这样的输出将是:[0,1,1,2,3,5,8,13,21,34,55]
然后我想尝试类似 fib 1000 之类的东西，虽然数字非常大，而且所有......我看到的是一些由“，”形成的奇怪省略号，这些省略号会在列表中的每个整数之间打印出来，例如:

example1

所以我已经最大化了输出窗口的大小，看看这个奇怪的模式是否还会重复，答案是肯定的:

example2

我的问题是:

有谁知道为什么在列表中的整数之间的“，”中出现这种模式？
它不应该更随机，更不像省略号吗？

Answer 1

斐波那契数 grow as an exponential function n.

十进制数的长度本质上是以 10 为底的对数。因此，斐波那契的长度像 n 的线性函数一样增长，因为对数和指数相互抵消。

因此，如果您将它们打印在一列中，您会看到一条直线。但是您一个接一个地打印它们，因此位置会累积。如果您正在获取线性序列的累积和，则会得到一个二次序列。

在本地，每一行都包含大约相同数量的斐波那契数，我们称之为 k。这意味着两件事:

行号随 n 线性变化。

为了计算逗号的实际位置(相对于窗口的左边缘)，我们需要将累积的“绝对位置”的余数取模行长度。这相当于(平均)每增加一个 n 减去 1/k。这种调整是线性的，不会改变位置的二次行为。

所以你看到的是抛物线——二次函数的图形。