无限列表中的周期性(Fibonacci mod序列)Haskell

Question

我需要在Haskell中创建一个函数,其工作方式如下

periodicity ::[Integer] ->[Integer]
periodicity [1,2,3,3,4,1,2,3,3,4...] = [1,2,3,4]
periodicity [0,1,2,2,5,4,3,3,0,1,2,5,4...] = [0,1,2,5,4,3]

也就是说,从列表中你得到的部分总是重复,数学科学中的部分将被称为函数的周期.

我已经尝试过这个,但是因为我想要与无限列表一起工作,我没有像我想要的那样工作

periodicty :: Eq a => [a] -> [a]
periodicity xs = take n xs
    where l = length xs
          n = head [m | m <- divisors l, 
                        concat (replicate (l `div` m) (take m xs)) == xs]

我发现这个函数给了我句号的长度,我本可以解决问题,但我不明白代码在哪里:

periodo 1 = 1
periodo n = f 1 ps 0
  where
   f 0 (1 : xs) pi = pi
   f _ (x : xs) pi = f x xs (pi + 1)
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps 

Answer 1

正如你所说,你想要的功能是不可能的¹.

但既然你说你真的追随的是Pisano时期,那么足以注意到两个连续的数字足以确定斐波那契序列的其余部分(mod n或其他).所以你真的在寻找相邻对的第一次重现,例如

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0
^^^^                    ^^^^
[--------- 8 -----------)

我不是为他们编码人们的问题,但我可以草拟我解决这个问题的方式.要记住的一件事是周期性可能有一个不重复的前缀 - 我不知道这是否实际发生在Fibonacci序列mod n中,但它通常发生.所以我们需要准备扔掉一个前缀.

首先,zip列表及其尾部以获取相邻对的列表

    [ 0,     1,     1,     2,     0,     2,    2,     1 ...]
 -> [(0,1), (1,1), (1,2), (2,0), (0,2), (2,2), (2,1), ... ]

从这里,折叠通过列表构建一个Data.Map键在这一对上,其中值是它首次出现的索引.你可以这样做,foldr但我可能只是使用累加器的递归函数.对于上面的示例,每个步骤的地图如下所示:

{(0,1): 0}
{(0,1): 0, (1,1): 1}
{(0,1): 0, (1,1): 1, (1,2): 2}
{(0,1): 0, (1,1): 1, (1,2): 2, (2,0): 3}
...

当您到达列表中已存在该键的点时,您可以从地图中的一个点中减去当前索引,这是您的句点.

¹这是一个证明.假设您有图灵机的规范,并列出steps其执行步骤.如果它停止,该列表将是有限的,否则无限.现在构建这个列表:

bad = zipWith const (cycle [1,2,3]) steps ++ cycle [1,2,3,4]

只要机器运行,该列表就以周期3循环,之后的周期为4.因此,如果图灵机停止periodicity bad = 4,否则periodicity bad = 3.也就是说,periodicity可以决定暂停问题,这是不可能的.