algorithm - 如何确定 Haskell 中 "repeating"函数假定的值的数量？

Question

我有一个函数

f :: Eq a => a -> a

我知道它最终会 self 重复(我不太确定这样的函数叫什么；想到“周期性”，但这有点不同，不是吗)，我想确定有多少独特的它产生的值(value)。

天真地，像

import Data.List (nub)
length $ nub $ take n $ iterate f a0

其中 a0 是一些初始的 a 而 n 是一些我知道超过了 f 的唯一值数量的大数字，将起作用。但是，除了我必须猜测或反复试验 n 的明显缺点外，这是不切实际的(无论如何在我的情况下)，因为 f 可以是时间-消费。

在 Haskell 中查找重复应用此类“重复”(或任何正确的术语)函数产生的唯一值列表的最佳方法是什么？

Answer 1

这正是 https://en.wikipedia.org/wiki/Cycle_detection 解决的问题.该页面指定了该问题的几个众所周知的解决方案。

这是基本龟兔算法的未经测试的 Haskell 实现:

floyd :: Eq a => (a -> a) -> a -> (Int, Int)
floyd f x0 = (lam, mu) where
  hare0 = head
    [t | (h, t) <- tail $ zip (iterate f x0) (iterate (f . f) x0), h == t]
  (mu, tortoise1) = head 
    [(m, t) | (m, t, h) <- zip3 [0..] (iterate f x0) (iterate f hare0), t == h]
  lam = head [l | (l, h) <- zip [1..] (iterate f (f tortoise1)), h == tortoise1]