data-clist-0.2: Simple functional ring type.

Safe Haskell | Safe-Inferred
Language | Haskell2010

Data.CircularList

Contents

- Data Types
- Functions
  - Creation of CLists
  - Update of CList
  - Converting CLists to Lists
  - Extraction and Accumulation
  - Manipulation of Focus
  - List-like functions
  - Manipulation of Packing
  - Information

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

Synopsis

- 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

data CList a Source #

A functional ring type.

#### Instances

Instances details

Functor CList Source # |
Instance details Defined in Data.CircularList.Internal Methods fmap :: (a -> b) -> CList a -> CList b Source # (<$) :: a -> CList b -> CList a Source #
Foldable CList Source # |

Instance details

Defined in Data.CircularList.Internal

Methods

fold :: Monoid m => CList m -> m Source #

foldMap :: Monoid m => (a -> m) -> CList a -> m Source #

foldMap' :: Monoid m => (a -> m) -> CList a -> m Source #

foldr :: (a -> b -> b) -> b -> CList a -> b Source #

foldr' :: (a -> b -> b) -> b -> CList a -> b Source #

foldl :: (b -> a -> b) -> b -> CList a -> b Source #

foldl' :: (b -> a -> b) -> b -> CList a -> b Source #

foldr1 :: (a -> a -> a) -> CList a -> a Source #

foldl1 :: (a -> a -> a) -> CList a -> a Source #

toList :: CList a -> [a] Source #

null :: CList a -> Bool Source #

length :: CList a -> Int Source #

elem :: Eq a => a -> CList a -> Bool Source #

maximum :: Ord a => CList a -> a Source #

minimum :: Ord a => CList a -> a Source #

sum :: Num a => CList a -> a Source #

product :: Num a => CList a -> a Source #

Traversable CList Source # |
Instance details Defined in Data.CircularList.Internal Methods traverse :: Applicative f => (a -> f b) -> CList a -> f (CList b) Source # sequenceA :: Applicative f => CList (f a) -> f (CList a) Source # mapM :: Monad m => (a -> m b) -> CList a -> m (CList b) Source # sequence :: Monad m => CList (m a) -> m (CList a) Source #
NFData a => NFData (CList a) Source # |
Instance details Defined in Data.CircularList.Internal Methods rnf :: CList a -> () Source #
Read a => Read (CList a) Source # |
Instance details Defined in Data.CircularList.Internal Methods readsPrec :: Int -> ReadS (CList a) Source # readList :: ReadS [CList a] Source # readPrec :: ReadPrec (CList a) Source # readListPrec :: ReadPrec [CList a] Source #
Show a => Show (CList a) Source # |
Instance details Defined in Data.CircularList.Internal Methods showsPrec :: Int -> CList a -> ShowS Source # show :: CList a -> String Source # showList :: [CList a] -> ShowS Source #
Eq a => Eq (CList a) Source # |
Instance details Defined in Data.CircularList.Internal Methods (==) :: CList a -> CList a -> Bool Source # (/=) :: CList a -> CList a -> Bool Source #

# Functions

## Creation of CLists

empty :: CList a Source #

An empty CList.

fromList :: [a] -> CList a Source #

Make a (balanced) CList from a list.

singleton :: a -> CList a Source #

## Update of CList

update :: a -> CList a -> CList a Source #

Replaces the current focus with a new focus.

reverseDirection :: CList a -> CList a Source #

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.

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 a Source #

Return the focus of the CList.

insertL :: a -> CList a -> CList a Source #

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 a Source #

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 a Source #

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

removeR :: CList a -> CList a Source #

Remove the focus from the CList.

## Manipulation of Focus

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

Return all possible rotations of the provided `CList`, where the focus is the provided `CList`.

rotR :: CList a -> CList a Source #

Rotate the focus to the next (right) element.

rotL :: CList a -> CList a Source #

Rotate the focus to the previous (left) element.

rotN :: Int -> CList a -> CList a Source #

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 a Source #

A wrapper around `rotN` that doesn't rotate the CList if `n <= 0`.

rotNL :: Int -> CList a -> CList a Source #

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 a Source #

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 a Source #

As with `filterR`, but rotates to the left if the focus does not satisfy the predicate.

foldrR :: (a -> b -> b) -> b -> CList a -> b Source #

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

foldrL :: (a -> b -> b) -> b -> CList a -> b Source #

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

foldlR :: (a -> b -> a) -> a -> CList b -> a Source #

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

foldlL :: (a -> b -> a) -> a -> CList b -> a Source #

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

## Manipulation of Packing

balance :: CList a -> CList a Source #

Balance the CList. Equivalent to `fromList . toList`

packL :: CList a -> CList a Source #

Move all elements to the left side of the CList.

packR :: CList a -> CList a Source #

Move all elements to the right side of the CList.

## Information

isEmpty :: CList a -> Bool Source #

Returns true if the CList is empty.

size :: CList a -> Int Source #

Return the size of the CList.