Posts Tagged ‘cyclic’

Programming Praxis – Cyclic Equality

April 9, 2013

In today’s Programming Praxis exercise, our goal is to determine if one list is cyclically equal to another. Let’s get started, shall we?

import Data.List

Rather than the provided solution which involves keep track of a bunch of pointers, we use a simple fact of cyclical lists: repeating either list twice produces a list that contains the other one if they are indeed cyclically equal. In order to prevent false positives, we also have to check whether the lengths are equal.

cyclic :: Eq a => [a] -> [a] -> Bool
cyclic xs ys = length xs == length ys && isInfixOf xs (ys ++ ys)

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ cyclic [1,2,3,4,5] [3,4,5,1,2]
          print $ cyclic [1,1,2,2] [2,1,1,2]
          print $ cyclic [1,1,1,1] [1,1,1,1]
          print . not $ cyclic [1,2,3,4] [1,2,3,5]          
          print . not $ cyclic [1,1,1] [1,1,1,1]