在Haskell中使用map时跳过异常

Question

我有以下代码返回字符串中的循环长度:

module Main where
import Data.List

detec ys n | 2*n > (length ys) = error "no cycle"
           | t == h = (2*n - n)
           | otherwise = detec ys (n+1)
            where
                t = ys !! n
                h = if n == 0 then ys !! 1 else  ys !! (n*2)
f x = detec (show x) 0
answer = map f [1/x|x<-[1..100]]

但我不知道该怎么做是让它忽略"no cycle"异常,以便生成的列表只包含循环字符串的长度.

我怎样才能做到这一点？

Answer 1

请不要error用于实现预期会出现"错误"结果的逻辑.

相反,为什么不回Maybe n,而不是只n,然后用catMaybes过滤掉NothingS'

这些变化很容易:

module Main where
import Data.List
import Data.Maybe

detec ys n | 2*n > (length ys) = Nothing
           | t == h = Just (2*n - n)
           | otherwise = detec ys (n+1)
            where
                t = ys !! n
                h = if n == 0 then ys !! 1 else  ys !! (n*2)

f x = detec (show x) 0
answer = catMaybes $ map f [1/x|x<-[1..100]]

顺便说一句,你索引超过列表的末尾; 也许你打算检查一下2*n + 1 > length ys？稍微偏离主题,我想提及它,!!并且length在大多数情况下,在应用于列表时都是低效和非惯用的,尤其是在像这样的迭代构造中.列表类型基本上是一个cons单元列表,它是一个本质上递归的数据结构,并且显然不是数组.理想情况下,您应该避免使用无法通过模式匹配轻松表达的列表执行任何操作,例如,f (x:xs) = ....

Answer 2

您是在使用Project Euler#26吗？

仅仅因为某个数字重复,并不意味着你找到了一个循环:例如,在334/999 = 0.334334334 ......中,循环不是(3),它是(334).另外,依靠浮点计算给你足够准确的数字是不明智的:#26的解决方案肯定超出了浮点数给你的范围.

无论如何,有更简单的方法来寻找周期.这将保留以前看到的元素在列表中向下移动时的列表,并在发现当前元素已被查看时返回.

findCycle :: Eq a => [a] -> Int
findCycle = findCycle' [] where
    findCycle' _ [] = 0
    findCycle' k (x:xs) = maybe (findCycle' (x:k) xs) succ $ elemIndex x k

你的乌龟和野兔算法是不完整的:它可能并不总能找到最小的循环.这个缺陷在这里得到纠正.

findCycle :: Eq a => [a] -> Int
findCycle xs = findCycle' xs (tail xs) where
    findCycle' (x:xs) (y:_:ys)
      | x == y = fromJust (elemIndex x xs) + 1
      | otherwise = findCycle' xs ys

这假设它永远不会从列表的末尾运行.如果您实现自己的十进制扩展,您可以轻松确保这是真的.