Safe Haskell | Safe-Infered |
---|

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 yields 1 as our new focus. Rotating this table left would return 0 to the focus position.

- data CList a
- empty :: CList a
- fromList :: [a] -> CList a
- singleton :: a -> CList a
- update :: a -> CList a -> CList a
- reverseDirection :: CList a -> CList a
- leftElements :: CList a -> [a]
- rightElements :: CList a -> [a]
- toList :: CList a -> [a]
- toInfList :: CList a -> [a]
- focus :: CList a -> Maybe a
- insertL :: a -> CList a -> CList a
- insertR :: a -> CList a -> CList a
- removeL :: CList a -> CList a
- removeR :: CList a -> CList a
- allRotations :: CList a -> CList (CList a)
- rotR :: CList a -> CList a
- rotL :: CList a -> CList a
- rotN :: Int -> CList a -> CList a
- rotNR :: Int -> CList a -> CList a
- rotNL :: Int -> CList a -> CList a
- rotateTo :: Eq a => a -> CList a -> Maybe (CList a)
- findRotateTo :: (a -> Bool) -> CList a -> Maybe (CList a)
- filterR :: (a -> Bool) -> CList a -> CList a
- filterL :: (a -> Bool) -> CList a -> CList a
- foldrR :: (a -> b -> b) -> b -> CList a -> b
- foldrL :: (a -> b -> b) -> b -> CList a -> b
- foldlR :: (a -> b -> a) -> a -> CList b -> a
- foldlL :: (a -> b -> a) -> a -> CList b -> a
- balance :: CList a -> CList a
- packL :: CList a -> CList a
- packR :: CList a -> CList a
- isEmpty :: CList a -> Bool
- size :: CList a -> Int

# Data Types

A functional ring type.

# Functions

## Creation of CLists

## Update of CList

reverseDirection :: CList a -> CList aSource

Reverse the direction of rotation.

## 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.

## Extraction and Accumulation

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.

## Manipulation of Focus

allRotations :: CList a -> CList (CList a)Source

rotN :: Int -> CList a -> CList aSource

Rotate the focus the specified number of times; if the index is positive then it is rotated to the right; otherwise it is rotated to the left.

rotNR :: Int -> CList a -> CList aSource

A wrapper around `rotN`

that doesn't rotate the CList if `n <= 0`

.

rotNL :: Int -> CList a -> CList aSource

Rotate the focus the specified number of times to the left (but
don't rotate if `n <= 0`

).

rotateTo :: Eq a => a -> CList a -> Maybe (CList a)Source

Rotate the `CList`

such that the specified element (if it exists)
is focused.

findRotateTo :: (a -> Bool) -> CList a -> Maybe (CList a)Source

Attempt to rotate the `CList`

such that focused element matches
the supplied predicate.

## List-like functions

filterR :: (a -> Bool) -> CList a -> CList aSource

Remove those elements that do not satisfy the supplied predicate, rotating to the right if the focus does not satisfy the predicate.

filterL :: (a -> Bool) -> CList a -> CList aSource

As with `filterR`

, but rotates to the *left* if the focus does not
satisfy the predicate.

foldrR :: (a -> b -> b) -> b -> CList a -> bSource

A right-fold, rotating to the right through the CList.

foldrL :: (a -> b -> b) -> b -> CList a -> bSource

A right-fold, rotating to the left through the CList.

foldlR :: (a -> b -> a) -> a -> CList b -> aSource

A (strict) left-fold, rotating to the right through the CList.

foldlL :: (a -> b -> a) -> a -> CList b -> aSource

A (strict) left-fold, rotating to the left through the CList.