CODEWITHSUNDEEP
algorithmhaskellfunctional-programming
mrLSD
mrLSD

Reputation: 698

Simple linked list loop detection in Haskell

I tried to implement a simple linked list in Haskell...

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

... and a loop detection algorithm for it:

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

However, I got infinite recursion. What is wrong?

Full code here: https://gist.github.com/mrLSD/03381a277c336c1902f9d78b79a131b0

Upvotes: 0

Views: 313

Answers (1)

melpomene
melpomene

Reputation: 85837

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

This line uses == on two unknown lists. To determine whether two lists are equal, == has to walk over their elements. If the lists are infinite, == will only return after finding a difference. If they're equal, == will never stop.

As for why == does this: The compiler-generated Eq instance for your type (as provided by deriving (Eq)) looks like this:

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

The recursion is in the xs == ys part.

Upvotes: 4

Related Questions