haskell - 检测 Haskell 中的循环行为

Question

我正在做另一个 projecteuler Haskell 中的问题，我必须在其中确定数字中每个数字的阶乘之和是否等于原始数字。如果没有重复该过程，直到达到原始数字。下一部分是找出具有 60 个非重复单元的 100 万以下的起始数字的数量。我做到了这一点:

prob74 = length [ x | x <- [1..999999], 60 == ((length $ chain74 x)-1)]

factorial n = product [1..n]

factC x = sum $ map factorial (decToList x)

chain74 x  | x == 0 = []
           | x == 1 = [1]
           | x /= factC x = x : chain74 (factC x)

但我不知道如何在 x 的值变成循环后让它停止。当 chain74 恢复到原来的数字时，我该如何停止？

Answer 1

当您遍历可能包含循环的列表时，您的函数需要跟踪已经看到的元素以便能够检查重复项。每个新元素都与已经看到的元素进行比较。如果已经看到新元素，则循环完成，如果还没有看到，则检查下一个元素。

所以这计算了列表的非循环部分的长度:

uniqlength :: (Eq a) => [a] -> Int
uniqlength l = uniqlength_ l []
   where uniqlength_ [] ls = length ls
         uniqlength_ (x:xs) ls
            | x `elem` ls = length ls
            | otherwise   = uniqlength_ xs (x:ls)

(使用集合而不是列表时性能可能更好，但我还没有尝试过。)