Modulestrict-list-1.0.0.1Haskell2010

StrictList

Definitions of strict linked list.

Most basic operations like fmap, filter, <*> are implemented efficiently by producing an intermediate list in reversed order and then reversing it to the original order to avoid stack recursion. 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.

1 type
36 values

Packagestrict-list-1.0.0.1
Exports37
LanguageHaskell2010
LicenceMIT
SourceStrictList.hs

Strict list type

1 declaration

datadata StrictList a

Strict linked list.

Constructors

Cons !a !(StrictList a)
Nil

Instances29Monad, Functor, Applicative, Foldable, Traversable, Alternative, …

Monad StrictListDefined in strict-list-1.0.0.1 · StrictList
Functor StrictListDefined in strict-list-1.0.0.1 · StrictList
Applicative StrictListDefined in strict-list-1.0.0.1 · StrictList
Foldable StrictListDefined in strict-list-1.0.0.1 · StrictList
Traversable StrictListDefined in strict-list-1.0.0.1 · StrictList
Alternative StrictListDefined in strict-list-1.0.0.1 · StrictList
MonadPlus StrictListDefined in strict-list-1.0.0.1 · StrictList
NFData1 StrictListDefined in strict-list-1.0.0.1 · StrictList
Arbitrary1 StrictListDefined in strict-list-1.0.0.1 · StrictList
Alt StrictListDefined in strict-list-1.0.0.1 · StrictList
Apply StrictListDefined in strict-list-1.0.0.1 · StrictList
Bind StrictListDefined in strict-list-1.0.0.1 · StrictList
Plus StrictListDefined in strict-list-1.0.0.1 · StrictList
Generic1 StrictListDefined in strict-list-1.0.0.1 · StrictList
IsList (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Eq a => Eq (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Data a => Data (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Ord a => Ord (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Read a => Read (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Show a => Show (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Generic (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Semigroup (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Monoid (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
NFData a => NFData (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Arbitrary a => Arbitrary (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
Hashable a => Hashable (StrictList a)Defined in strict-list-1.0.0.1 · StrictList
type Rep (StrictList a) = D1 ('MetaData "StrictList" "StrictList" "strict-list-1.0.0.1-JLtLXlC13tlFTB3YmCXrFq" 'False) (C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a) :*: S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (StrictList a))) :+: C1 ('MetaCons "Nil" 'PrefixI 'False) U1)Defined in strict-list-1.0.0.1 · StrictList
type Rep1 StrictList = D1 ('MetaData "StrictList" "StrictList" "strict-list-1.0.0.1-JLtLXlC13tlFTB3YmCXrFq" 'False) (C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1 :*: S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec1 StrictList)) :+: C1 ('MetaCons "Nil" 'PrefixI 'False) U1)Defined in strict-list-1.0.0.1 · StrictList
type Item (StrictList a) = aDefined in strict-list-1.0.0.1 · StrictList

Conversions

4 declarations

valuetoList :: StrictList a -> [a]

Convert to lazy list.

valuetoListReversed :: StrictList a -> [a]

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

valuefromList :: [a] -> StrictList a

Construct from a lazy list.

valuefromListReversed :: [a] -> StrictList a

Construct from a lazy list in reversed order.

Basic transformations

16 declarations

valuereverse :: StrictList a -> StrictList a

Reverse the list.

valuetake :: Int -> StrictList a -> StrictList a

Leave only the specified amount of elements.

valuetakeReversed :: Int -> StrictList a -> StrictList a

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

valuedrop :: Int -> StrictList a -> StrictList a

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

valuefilter :: (a -> Bool) -> StrictList a -> StrictList a

Leave only the elements satisfying the predicate.

valuefilterReversed :: (a -> Bool) -> StrictList a -> StrictList a

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

valuetakeWhile :: (a -> Bool) -> StrictList a -> StrictList a

Leave only the first elements satisfying the predicate.

valuetakeWhileReversed :: (a -> Bool) -> StrictList a -> StrictList a

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

valuedropWhile :: (a -> Bool) -> StrictList a -> StrictList a

Drop the first elements satisfying the predicate.

valuetakeWhileFromEnding :: (a -> Bool) -> StrictList a -> StrictList a

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

Example1 expression

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

valuedropWhileFromEnding :: (a -> Bool) -> StrictList a -> StrictList a

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

Example1 expression

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

valuespan :: (a -> Bool) -> StrictList a -> (StrictList a, StrictList a)

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

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

valuespanReversed :: (a -> Bool) -> StrictList a -> (StrictList a, StrictList a)

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

valuespanFromEnding

:: a -> Bool
-> StrictList a
-> (StrictList a, StrictList a)

Same as (span predicate . reverse).

valuebreak :: (a -> Bool) -> StrictList a -> (StrictList a, StrictList a)

An opposite version of span. I.e.,

break predicate = span (not . predicate)

valuebreakReversed :: (a -> Bool) -> StrictList a -> (StrictList a, StrictList a)

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

Queries

7 declarations

valuematch

:: result
-> element -> StrictList element -> result
-> StrictList element
-> result

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.

valueuncons :: StrictList a -> Maybe (a, StrictList a)

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

valuehead :: StrictList a -> Maybe a

Get the first element, if list is not empty.

valuelast :: StrictList a -> Maybe a

Get the last element, if list is not empty.

valuetail :: StrictList a -> StrictList a

Get all elements of the list but the first one.

valueinit :: StrictList a -> StrictList a

Get all elements but the last one.

valueinitReversed :: StrictList a -> StrictList a

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

Zipping and application

2 declarations

valueapZipping :: StrictList (a -> b) -> StrictList a -> StrictList b

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

valueapZippingReversed :: StrictList (a -> b) -> StrictList a -> StrictList b

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

Reversed-order helpers

7 declarations

valueprependReversed :: StrictList a -> StrictList a -> StrictList a

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

valuemapReversed :: (a -> b) -> StrictList a -> StrictList b

Map producing a list in reversed order.

valueapReversed :: StrictList (a -> b) -> StrictList a -> StrictList b

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

valueexplodeReversed :: (a -> StrictList b) -> StrictList a -> StrictList b

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

valuejoinReversed :: StrictList (StrictList a) -> StrictList a

Join (concat) producing results in reversed order.

valuemapMaybeReversed :: (a -> Maybe b) -> StrictList a -> StrictList b

Map and filter elements producing results in reversed order.

valuecatMaybesReversed :: StrictList (Maybe a) -> StrictList a

Keep only the present values, reversing the order.