Programming Praxis – Cyclic Equality

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]
About these ads

Tags: , , , , , , , ,

2 Responses to “Programming Praxis – Cyclic Equality”

  1. programmingpraxis Says:

    In Scheme I am not able to append one cyclic list to another, as you did when you wrote (ys ++ ys). Is that because your lists are just normal Haskell lists, not cyclic lists? Maybe I didn’t explain very well, but when I said (1 2 3 4 5) was a cyclic list I meant that it didn’t stop after 5 but instead represented the cycle 1 2 3 4 5 1 2 3 4 5 1 2 3 ….

  2. Remco Niemeijer Says:

    @programmingpraxis: Yes, my lists are plain finite lists. I was under the impression that the ‘unique’ part of the cyclic list (i.e. the part that’s repeated over and over) is known and provided as input to the function. If instead you are given two cyclical lists then this version obviously doesn’t work and things get a lot trickier, since Haskell doesn’t normally expose pointers and as such lacks the option to ‘point to the start of the list’, making it impossible to determine the length of the cycle. In Haskell, cycling a list is simply a matter of infinitely and lazily repeating the elements, which provides no indication that the cycle has been completed.

    Ignoring that little practical problem, the basic idea of the solution can remain the same; you just have to create the two finite lists first. Start at any element, collecting them all until the loop is closed. Then use the solution presented above.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: