algorithm - Haskell中的简单链表循环检测

Question

我尝试在 Haskell 中实现一个简单的链表...

data List a = Nil | Cons a (List a) deriving (Show, Eq)

...和它的循环检测算法:

listNext :: List a -> List a
listNext Nil          = Nil
listNext (Cons _ xs) = xs

loopDetecting' :: (Eq a) => List a -> List a -> Bool
loopDetecting' current next
      | current == Nil || next1 == Nil || next2 == Nil  = False
      | current == next1 || current == next2            = True
      | otherwise = loopDetecting' (listNext current) next2
      where
          next1 = listNext next
          next2 | next1 == Nil  = Nil
                | otherwise     = listNext next1

loopDetecting :: (Eq a) =>  List a -> Bool
loopDetecting Nil         = False
loopDetecting (Cons _ xs) = loopDetecting' xs xs

但是，我得到了无限递归。怎么了？

完整代码在这里:https://gist.github.com/mrLSD/03381a277c336c1902f9d78b79a131b0

Answer 1

      | current == next1 || current == next2            = True

此行在两个未知列表上使用了 ==。要确定两个列表是否相等，== 必须遍历它们的元素。如果列表是无限的，== 只会在找到差异后返回。如果它们相等，== 将永远不会停止。

至于为什么 == 这样做:编译器为您的类型生成的 Eq 实例(由 deriving (Eq) 提供)看起来像这样:

instance (Eq a) => Eq (List a) where
    (==) Nil         Nil         = True
    (==) (Cons x xs) (Cons y ys) = x == y && xs == ys
    (==) _           _           = False

递归在xs == ys部分。