２６問目

http://projecteuler.net/index.php?section=problems&id=26
1000未満の数dに対して1/dを循環小数で表したときに循環する部分の長さの最大値を求める。
下のコードが最初に書いたものです。間違いはないし処理時間も問題ないのですが、明示的に再帰しているところがHaskellっぽくないなぁと思って、別の書き方に挑戦しました。

main = print $ euler026 999

euler026 :: Int -> Int
euler026 n = (+ 1) $ length $ takeWhile (< (maximum lens)) lens
    where lens = map (cycleLength [1]) [1..n]

cycleLength :: [Int] -> Int -> Int
cycleLength rems n
    | (rem == 0) = 0
    | (elem rem rems) = (length $ takeWhile (/= rem) rems) + 1
    | otherwise = cycleLength (rem : rems) n
    where rem = mod ((head rems) * 10) n

で、できたのが下のコード。
一応動くのですが、無限リストから循環する部分を取り出すロジック（cyclePart）がいまいち複雑で、処理時間も上のコードより長くかかります。
もっと簡潔で、速く動くコードが書けないものでしょうか。
思いついた方は、ぜひコメントください。

main = print $ euler026 999

euler026 :: Int -> Int
euler026 n = (+ 1) $ length $ takeWhile (< (maximum lens)) lens
  where lens = map cycleLength [1..n]

cycleLength :: Int -> Int
cycleLength n = length $ cyclePart $ rems n

cyclePart :: [Int] -> [Int]
cyclePart xs = dropPrefix $ dropSuffix xs
  where
    dropPrefix xs
      | (last xs == 0) = []
      | otherwise = init $ dropWhile (/= last xs) xs
    dropSuffix xs = head $ dropWhile notDuplicate $ map (flip take xs) [1..]
    notDuplicate xs = notElem (last xs) (init xs)

rems :: Int -> [Int]
rems n = iterate next 1
  where next rem = mod (rem * 10) n

コメントでいいアルゴリズムを教えていただいたので、修正したものを載せておきます。詳しい説明はこちら。→どう書く？org 6144
文句無しに最速です。

cyclePart :: [Int] -> [Int]
cyclePart xs
  | (t' == 0) = []
  | otherwise = t' : (takeWhile (/= t') $ fst $ unzip ys)
  where
    ((t', r') : ys) = dropWhile (\ (t, r) -> t /= r) $
      zip xs $ map head $ iterate (drop 2) $ tail xs