data-clist-0.0.2: Simple functional ring type.

Data.CircularList

Contents

Description

A simple purely functional circular list, or ring, data type.

Lets describe what we mean by ring. A ring is a circular data structure such that if you continue rotating the ring, you'll eventually return to the element you first observed.

All of our analogies involve sitting at a table who's top surface rotates about its center axis (think of those convenient rotating platforms one often finds in an (Americanized) Chinese Restaurant).

Only the closest item on the table is avialable to us. In order to reach other elements on the table, we need to rotate the table to the left or the right.

Our convention for this problem says that rotations to the right are a forward motion while rotations to the left are backward motions.

We'll use the following circular list for our examples:

   8 7 6
  9     5
 A       4
 B       3
  C     2
   D 0 1
     ^

The pointer at the bottom represents our position at the table. The element currently in front of is is referred to as the focus. So, in this case, our focus is 0.

If we were to rotate the table to the right using the rotR operation, we'd have the following table.

   9 8 7
  A     6
 B       5
 C       4
  D     3
   0 1 2
     ^

This yeilds 1 as our new focus. Rotating this table left would return 0 to the focus position.

Synopsis

Data Types

data CList a Source

A functional ring type.

Instances

Functor CList 
Eq a => Eq (CList a) 
Show a => Show (CList a)

The show instance prints a tuple of the balanced CList where the left list's right-most element is the first element to the left. The left most-most element of the right list is the next element to the right.

Arbitrary a => Arbitrary (CList a) 

Functions

Creation of CLists

empty :: CList aSource

An empty CList.

fromList :: [a] -> CList aSource

Make a (balanced) CList from a list.

Converting CLists to Lists

leftElements :: CList a -> [a]Source

Starting with the focus, go left and accumulate all elements of the CList in a list.

rightElements :: CList a -> [a]Source

Starting with the focus, go right and accumulate all elements of the CList in a list.

toList :: CList a -> [a]Source

Make a list from a CList.

toInfList :: CList a -> [a]Source

Make a CList into an infinite list.

Extraction and Accumulation

focus :: CList a -> Maybe aSource

Return the focus of the CList.

insertL :: a -> CList a -> CList aSource

Insert an element into the CList as the new focus. The old focus is now the next element to the left.

insertR :: a -> CList a -> CList aSource

Insert an element into the CList as the new focus. The old focus is now the next element to the right.

removeL :: CList a -> CList aSource

Remove the focus from the CList. The new focus is the next element to the left.

removeR :: CList a -> CList aSource

Remove the focus from the CList.

Manipulation of Focus

rotR :: CList a -> CList aSource

Rotate the focus to the next (right) element.

rotL :: CList a -> CList aSource

Rotate the focus to the previous (left) element.

Manipulation of Packing

balance :: CList a -> CList aSource

Balance the CList. Equivalent to `fromList . toList`

packL :: CList a -> CList aSource

Move all elements to the left side of the CList.

packR :: CList a -> CList aSource

Move all elements to the right side of the CList.

Information

isEmpty :: CList a -> BoolSource

Returns true if the CList is empty.

size :: CList a -> IntSource

Return the size of the CList.