Skip to content

Instantly share code, notes, and snippets.

@apellizzn

apellizzn/CycleList.hs

Last active Feb 14, 2017
Embed
What would you like to do?
Check if a list is infinite
module Main where
data List a = Empty | Cons a (List a)
instance Show a => Show (List a) where
show (Cons a next) = show a ++ "-" ++ show next
show Empty = "*"
simpleList :: List Integer
simpleList = Cons 1 . Cons 2 . Cons 3 . Cons 4 $ Empty
closedList :: List Integer
closedList = Cons 1 . Cons 2 . Cons 3 . Cons 4 $ loop
loop :: List Integer
loop = Cons 5 knot
where knot = Cons 6 loop
takeFirst :: Integer -> List Integer -> List Integer
takeFirst 0 _ = Empty
takeFirst n (Cons a rest) = Cons a $ takeFirst (n - 1) rest
isCyclic :: List Integer -> String
isCyclic (Cons a (Cons b rest)) = isCyclic' rest (Cons a . Cons b $ rest)
isCyclic _ = "No"
isCyclic' Empty _ = "No"
isCyclic' (Cons fast (Cons _ fastRest)) (Cons slow slowRest)
| fast == slow = "Yes"
| otherwise = isCyclic' fastRest slowRest
main :: IO ()
main = do
print simpleList
print $ "simpleList is infinite ? " `mappend` isCyclic simpleList
print $ takeFirst 10 loop
print $ "cyclicList is infinite ? " `mappend` isCyclic loop
print $ takeFirst 10 closedList
print $ "closedList is infinite ? " `mappend` isCyclic closedList
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.