strict-list-0.1.7.6: Strict linked list

Safe Haskell | None
Language | Haskell2010

StrictList

Contents

- Reversed intermediate functions used in instances

Description

Definitions of strict linked list.

Most basic operations like `fmap`, `filter`, `<*>` can only be implemented efficiently by producing an intermediate list in reversed order and then reversing it to the original order. These intermediate reversed functions are exposed by the API, because they very well may be useful for efficient implementations of data-structures built on top of list. E.g., the "deque" package exploits them heavily.

One useful rule of thumb would be that whenever you see that a function has a reversed counterpart, that counterpart is faster and hence if you don't care about the order or intend to reverse the list further down the line, you should give preference to that counterpart.

The typical `toList` and `fromList` conversions are provided by means of the `Foldable` and `IsList` instances.

Synopsis

- data List a
  - = Cons !a !(List a)
  - | Nil
- toListReversed :: List a -> [a]
- reverse :: List a -> List a
- take :: Int -> List a -> List a
- takeReversed :: Int -> List a -> List a
- drop :: Int -> List a -> List a
- filter :: (a -> Bool) -> List a -> List a
- filterReversed :: (a -> Bool) -> List a -> List a
- takeWhile :: (a -> Bool) -> List a -> List a
- takeWhileReversed :: (a -> Bool) -> List a -> List a
- dropWhile :: (a -> Bool) -> List a -> List a
- span :: (a -> Bool) -> List a -> (List a, List a)
- spanReversed :: (a -> Bool) -> List a -> (List a, List a)
- break :: (a -> Bool) -> List a -> (List a, List a)
- breakReversed :: (a -> Bool) -> List a -> (List a, List a)
- takeWhileFromEnding :: (a -> Bool) -> List a -> List a
- dropWhileFromEnding :: (a -> Bool) -> List a -> List a
- spanFromEnding :: (a -> Bool) -> List a -> (List a, List a)
- match :: result -> (element -> List element -> result) -> List element -> result
- uncons :: List a -> Maybe (a, List a)
- head :: List a -> Maybe a
- last :: List a -> Maybe a
- tail :: List a -> List a
- init :: List a -> List a
- initReversed :: List a -> List a
- apZipping :: List (a -> b) -> List a -> List b
- apZippingReversed :: List (a -> b) -> List a -> List b
- fromListReversed :: [a] -> List a
- prependReversed :: List a -> List a -> List a
- mapReversed :: (a -> b) -> List a -> List b
- apReversed :: List (a -> b) -> List a -> List b
- explodeReversed :: (a -> List b) -> List a -> List b
- joinReversed :: List (List a) -> List a
- mapMaybeReversed :: (a -> Maybe b) -> List a -> List b
- catMaybesReversed :: List (Maybe a) -> List a

# Documentation

data List a Source #

Strict linked list.

Constructors

Cons !a !(List a) |
Nil |

#### Instances

Instances details

NFData1 List Source # |
Instance details Defined in StrictList Methods liftRnf :: (a -> ()) -> List a -> () Source #
Alternative List Source # |
Instance details Defined in StrictList Methods empty :: List a Source # (<|>) :: List a -> List a -> List a Source # some :: List a -> List [a] Source # many :: List a -> List [a] Source #
Applicative List Source # |
Instance details Defined in StrictList Methods pure :: a -> List a Source # (<*>) :: List (a -> b) -> List a -> List b Source # liftA2 :: (a -> b -> c) -> List a -> List b -> List c Source # (*>) :: List a -> List b -> List b Source # (<*) :: List a -> List b -> List a Source #
Functor List Source # |
Instance details Defined in StrictList Methods fmap :: (a -> b) -> List a -> List b Source # (<$) :: a -> List b -> List a Source #
Monad List Source # |
Instance details Defined in StrictList Methods (>>=) :: List a -> (a -> List b) -> List b Source # (>>) :: List a -> List b -> List b Source # return :: a -> List a Source #
MonadPlus List Source # |
Instance details Defined in StrictList Methods mzero :: List a Source # mplus :: List a -> List a -> List a Source #
Foldable List Source # |

Instance details

Defined in StrictList

Methods

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

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

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

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

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

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

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

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

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

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

null :: List a -> Bool Source #

length :: List a -> Int Source #

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

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

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

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

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

Traversable List Source # |
Instance details Defined in StrictList Methods traverse :: Applicative f => (a -> f b) -> List a -> f (List b) Source # sequenceA :: Applicative f => List (f a) -> f (List a) Source # mapM :: Monad m => (a -> m b) -> List a -> m (List b) Source # sequence :: Monad m => List (m a) -> m (List a) Source #
Alt List Source # |
Instance details Defined in StrictList Methods (<!>) :: List a -> List a -> List a Source # some :: Applicative List => List a -> List [a] Source # many :: Applicative List => List a -> List [a] Source #
Apply List Source # |
Instance details Defined in StrictList Methods (<.>) :: List (a -> b) -> List a -> List b Source # (.>) :: List a -> List b -> List b Source # (<.) :: List a -> List b -> List a Source # liftF2 :: (a -> b -> c) -> List a -> List b -> List c Source #
Bind List Source # |
Instance details Defined in StrictList Methods (>>-) :: List a -> (a -> List b) -> List b Source # join :: List (List a) -> List a Source #
Plus List Source # |
Instance details Defined in StrictList Methods zero :: List a Source #
Generic1 List Source # |

Instance details

Defined in StrictList

Associated Types

type Rep1 List |

Instance details

Defined in StrictList

type Rep1 List = D1 ('MetaData "List" "StrictList" "strict-list-0.1.7.6-1xb7e1yDCgJKphYdlDJ86v" 'False) (C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 List)) :+: C1 ('MetaCons "Nil" 'PrefixI 'False) (U1 :: Type -> Type))

Methods

from1 :: List a -> Rep1 List a Source #

to1 :: Rep1 List a -> List a Source #

NFData a => NFData (List a) Source # |
Instance details Defined in StrictList Methods rnf :: List a -> () Source #
Monoid (List a) Source # |
Instance details Defined in StrictList Methods mempty :: List a Source # mappend :: List a -> List a -> List a Source # mconcat :: [List a] -> List a Source #
Semigroup (List a) Source # |
Instance details Defined in StrictList Methods (<>) :: List a -> List a -> List a Source # sconcat :: NonEmpty (List a) -> List a Source # stimes :: Integral b => b -> List a -> List a Source #
Data a => Data (List a) Source # |

Instance details

Defined in StrictList

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> List a -> c (List a) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (List a) Source #

toConstr :: List a -> Constr Source #

dataTypeOf :: List a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (List a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (List a)) Source #

gmapT :: (forall b. Data b => b -> b) -> List a -> List a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> List a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> List a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> List a -> m (List a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> List a -> m (List a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> List a -> m (List a) Source #

Generic (List a) Source # |

Instance details

Defined in StrictList

Associated Types

type Rep (List a) |

Instance details

Defined in StrictList

type Rep (List a) = D1 ('MetaData "List" "StrictList" "strict-list-0.1.7.6-1xb7e1yDCgJKphYdlDJ86v" 'False) (C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (List a))) :+: C1 ('MetaCons "Nil" 'PrefixI 'False) (U1 :: Type -> Type))

Methods

from :: List a -> Rep (List a) x Source #

to :: Rep (List a) x -> List a Source #

IsList (List a) Source # |

Instance details

Defined in StrictList

Associated Types

type Item (List a) |
Instance details Defined in StrictList type Item (List a) = a

Methods

fromList :: [Item (List a)] -> List a Source #

fromListN :: Int -> [Item (List a)] -> List a Source #

toList :: List a -> [Item (List a)] Source #

Read a => Read (List a) Source # |
Instance details Defined in StrictList Methods readsPrec :: Int -> ReadS (List a) Source # readList :: ReadS [List a] Source # readPrec :: ReadPrec (List a) Source # readListPrec :: ReadPrec [List a] Source #
Show a => Show (List a) Source # |
Instance details Defined in StrictList Methods showsPrec :: Int -> List a -> ShowS Source # show :: List a -> String Source # showList :: [List a] -> ShowS Source #
Eq a => Eq (List a) Source # |
Instance details Defined in StrictList Methods (==) :: List a -> List a -> Bool Source # (/=) :: List a -> List a -> Bool Source #
Ord a => Ord (List a) Source # |
Instance details Defined in StrictList Methods compare :: List a -> List a -> Ordering Source # (<) :: List a -> List a -> Bool Source # (<=) :: List a -> List a -> Bool Source # (>) :: List a -> List a -> Bool Source # (>=) :: List a -> List a -> Bool Source # max :: List a -> List a -> List a Source # min :: List a -> List a -> List a Source #
Hashable a => Hashable (List a) Source # |
Instance details Defined in StrictList Methods hashWithSalt :: Int -> List a -> Int Source # hash :: List a -> Int Source #
type Rep1 List Source # |

Instance details

Defined in StrictList

type Rep1 List = D1 ('MetaData "List" "StrictList" "strict-list-0.1.7.6-1xb7e1yDCgJKphYdlDJ86v" 'False) (C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 List)) :+: C1 ('MetaCons "Nil" 'PrefixI 'False) (U1 :: Type -> Type))

type Rep (List a) Source # |

Instance details

Defined in StrictList

type Rep (List a) = D1 ('MetaData "List" "StrictList" "strict-list-0.1.7.6-1xb7e1yDCgJKphYdlDJ86v" 'False) (C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (List a))) :+: C1 ('MetaCons "Nil" 'PrefixI 'False) (U1 :: Type -> Type))

type Item (List a) Source # |
Instance details Defined in StrictList type Item (List a) = a

toListReversed :: List a -> [a] Source #

Convert to lazy list in normal form (with all elements and spine evaluated).

reverse :: List a -> List a Source #

Reverse the list.

take :: Int -> List a -> List a Source #

Leave only the specified amount of elements.

takeReversed :: Int -> List a -> List a Source #

Leave only the specified amount of elements, in reverse order.

drop :: Int -> List a -> List a Source #

Leave only the elements after the specified amount of first elements.

filter :: (a -> Bool) -> List a -> List a Source #

Leave only the elements satisfying the predicate.

filterReversed :: (a -> Bool) -> List a -> List a Source #

Leave only the elements satisfying the predicate, producing a list in reversed order.

takeWhile :: (a -> Bool) -> List a -> List a Source #

Leave only the first elements satisfying the predicate.

takeWhileReversed :: (a -> Bool) -> List a -> List a Source #

Leave only the first elements satisfying the predicate, producing a list in reversed order.

dropWhile :: (a -> Bool) -> List a -> List a Source #

Drop the first elements satisfying the predicate.

span :: (a -> Bool) -> List a -> (List a, List a) Source #

An optimized version of the same predicate applied to `takeWhile` and `dropWhile`. IOW,

    span predicate list = (takeWhile predicate list, dropWhile predicate list)

spanReversed :: (a -> Bool) -> List a -> (List a, List a) Source #

Same as `span`, only with the first list in reverse order.

break :: (a -> Bool) -> List a -> (List a, List a) Source #

An opposite version of `span`. I.e.,

    break predicate = span (not . predicate)

breakReversed :: (a -> Bool) -> List a -> (List a, List a) Source #

Same as `break`, only with the first list in reverse order.

takeWhileFromEnding :: (a -> Bool) -> List a -> List a Source #

Same as `(`takeWhile` predicate . `reverse`)`. E.g.,

    >>> takeWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])
    fromList [5,4,3]

dropWhileFromEnding :: (a -> Bool) -> List a -> List a Source #

Same as `(`dropWhile` predicate . `reverse`)`. E.g.,

    >>> dropWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])
    fromList [2,4,1]

spanFromEnding :: (a -> Bool) -> List a -> (List a, List a) Source #

Same as `(`span` predicate . `reverse`)`.

match :: result -> (element -> List element -> result) -> List element -> result Source #

Pattern match on list using functions.

Allows to achieve all the same as `uncons` only without intermediate `Maybe`.

Essentially provides the same functionality as `either` for `Either` and `maybe` for `Maybe`.

uncons :: List a -> Maybe (a, List a) Source #

Get the first element and the remainder of the list if it's not empty.

head :: List a -> Maybe a Source #

Get the first element, if list is not empty.

last :: List a -> Maybe a Source #

Get the last element, if list is not empty.

tail :: List a -> List a Source #

Get all elements of the list but the first one.

init :: List a -> List a Source #

Get all elements but the last one.

initReversed :: List a -> List a Source #

Get all elements but the last one, producing the results in reverse order.

apZipping :: List (a -> b) -> List a -> List b Source #

Apply the functions in the left list to elements in the right one.

apZippingReversed :: List (a -> b) -> List a -> List b Source #

Apply the functions in the left list to elements in the right one, producing a list of results in reversed order.

## Reversed intermediate functions used in instances

fromListReversed :: [a] -> List a Source #

Construct from a lazy list in reversed order.

prependReversed :: List a -> List a -> List a Source #

Add elements of the left list in reverse order in the beginning of the right list.

mapReversed :: (a -> b) -> List a -> List b Source #

Map producing a list in reversed order.

apReversed :: List (a -> b) -> List a -> List b Source #

Apply the functions in the left list to every element in the right one, producing a list of results in reversed order.

explodeReversed :: (a -> List b) -> List a -> List b Source #

Use a function to produce a list of lists and then concat them sequentially, producing the results in reversed order.

joinReversed :: List (List a) -> List a Source #

Join (concat) producing results in reversed order.

mapMaybeReversed :: (a -> Maybe b) -> List a -> List b Source #

Map and filter elements producing results in reversed order.

catMaybesReversed :: List (Maybe a) -> List a Source #

Keep only the present values, reversing the order.