Data.List.Snoc

Useful for describing zippers and functional queues/buffers more naturally and safely.

We call it an RList because this is really just a vanilla list, but where the semantics are that the last-added thing (internally cons'ed) is understood to be at the "end" of the list.

Documentation

data Tsil a

This datatype defines snoc-lists: lists with O(1) append and O(n) prepend. Underneath the hood, it is just a plain list, but understood as containing its elements in reverse order.

| See? It's "List" in reverse? I dunno, I just think RList is an inelegant name, and word-initial t͜s is one of my favorite phonemes.

Instances

Foldable Tsil

Defined in Data.List.Snoc

Methods

fold :: Monoid m => Tsil m -> m

foldMap :: Monoid m => (a -> m) -> Tsil a -> m

foldMap' :: Monoid m => (a -> m) -> Tsil a -> m

foldr :: (a -> b -> b) -> b -> Tsil a -> b

foldr' :: (a -> b -> b) -> b -> Tsil a -> b

foldl :: (b -> a -> b) -> b -> Tsil a -> b

foldl' :: (b -> a -> b) -> b -> Tsil a -> b

foldr1 :: (a -> a -> a) -> Tsil a -> a

foldl1 :: (a -> a -> a) -> Tsil a -> a

toList :: Tsil a -> [a]

null :: Tsil a -> Bool

length :: Tsil a -> Int

elem :: Eq a => a -> Tsil a -> Bool

maximum :: Ord a => Tsil a -> a

minimum :: Ord a => Tsil a -> a

sum :: Num a => Tsil a -> a

product :: Num a => Tsil a -> a

Alternative Tsil

Defined in Data.List.Snoc

Methods

empty :: Tsil a

(<|>) :: Tsil a -> Tsil a -> Tsil a

some :: Tsil a -> Tsil [a]

many :: Tsil a -> Tsil [a]

Applicative Tsil

Defined in Data.List.Snoc

Methods

pure :: a -> Tsil a

(<*>) :: Tsil (a -> b) -> Tsil a -> Tsil b

liftA2 :: (a -> b -> c) -> Tsil a -> Tsil b -> Tsil c

(*>) :: Tsil a -> Tsil b -> Tsil b

(<*) :: Tsil a -> Tsil b -> Tsil a

Functor Tsil

Defined in Data.List.Snoc

Methods

fmap :: (a -> b) -> Tsil a -> Tsil b

(<$) :: a -> Tsil b -> Tsil a

Monoid (Tsil a)

Defined in Data.List.Snoc

Methods

mempty :: Tsil a

mappend :: Tsil a -> Tsil a -> Tsil a

mconcat :: [Tsil a] -> Tsil a

Semigroup (Tsil a)

Defined in Data.List.Snoc

Methods

(<>) :: Tsil a -> Tsil a -> Tsil a

sconcat :: NonEmpty (Tsil a) -> Tsil a

stimes :: Integral b => b -> Tsil a -> Tsil a

Generic (Tsil a)

Defined in Data.List.Snoc

Associated Types

type Rep (Tsil a) :: Type -> Type

Methods

from :: Tsil a -> Rep (Tsil a) x

to :: Rep (Tsil a) x -> Tsil a

Read a => Read (Tsil a)

Defined in Data.List.Snoc

Methods

readsPrec :: Int -> ReadS (Tsil a)

readList :: ReadS [Tsil a]

readPrec :: ReadPrec (Tsil a)

readListPrec :: ReadPrec [Tsil a]

Show a => Show (Tsil a)

Defined in Data.List.Snoc

Methods

showsPrec :: Int -> Tsil a -> ShowS

show :: Tsil a -> String

showList :: [Tsil a] -> ShowS

NFData a => NFData (Tsil a)

Defined in Data.List.Snoc

Methods

rnf :: Tsil a -> ()

Eq a => Eq (Tsil a)

Defined in Data.List.Snoc

Methods

(==) :: Tsil a -> Tsil a -> Bool

(/=) :: Tsil a -> Tsil a -> Bool

type Rep (Tsil a)

Defined in Data.List.Snoc

type Rep (Tsil a) = D1 ('MetaData "Tsil" "Data.List.Snoc" "reverse-list-0.3.0.0-inplace" 'True) (C1 ('MetaCons "Tsil" 'PrefixI 'True) (S1 ('MetaSel ('Just "unTsil") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [a])))

type RList = Tsil

Deprecated: Preferred spelling is Tsil

I initially went with this boring name for reverse-lists. However, I genuinely would rather write (and pronounce) Tsil.

Introduction and Elimination

nil :: Tsil a

The empty Tsil.

snoc :: Tsil a -> a -> Tsil a

O(1) Append an element.

If you are looking for cons, you should use a plain list, or a finite sequence/queue type.

singleton :: a -> Tsil a

Create a single-element Tsil.

unsnoc :: Tsil a -> Maybe (Tsil a, a)

O(1) Access the last element and initial portion of the list. See also last and init if you only need one component.

If you are looking for uncons, you should use a plain list, or a finite sequence/queue type.

Patterns

pattern Nil :: Tsil a

An empty RList, such as nil.

pattern Snoc :: Tsil a -> a -> Tsil a

The Tsil consisting of initial and last elements, such as created by snoc.

Queries

null :: Tsil a -> Bool

Test if an Tsil is empty.

init :: Tsil a -> Maybe (Tsil a)

O(1) extract the elements of a list other than the last, if they exist. See also unsnoc if you also need last at the same time.

last :: Tsil a -> Maybe a

O(1) extract the last element of a list, if it exists. See also unsnoc if you also need init at the same time.

Traversal

catMaybes :: Tsil (Maybe a) -> Tsil a

Remove all Nothings from an Tsil of Maybes.

Conversion

toList :: Tsil a -> [a]

O(n) Convert to a plain list, maintaining order.

This is here so that you can escape back out to normal cons-list land once you're done building your list.

See reverseOut for when order doesn't matter.

fromList :: [a] -> Tsil a

O(n) Convert from a plain list, maintaining order.

This is added for completion's sake, as I'm not sure you'll often need this adapter.

See toList for the inverse, or reverseIn for when order doesn't matter.

reverseIn :: [a] -> Tsil a

O(0) Reverse a plain cons list, rerutning an Tsil.

See reverseOut for the inverse, and why you might use these.

reverseOut :: Tsil a -> [a]

O(0) Reverse an Tsil, returning a plain cons list.

This is here so that when the output list is fed to an order-agnostic function, you don't have to pay the cost of reversing the representation.

See toList for when order matters.

toArrayN :: (Contiguous arr, Element arr a) => Int -> Tsil a -> arr a

Write the contents of the Tsil into an array, assuming you know the length of the array. This is useful in the common case of buffering an unknown-length stream before allocating contiguous space for the elements.

If you sepcify to small a langth, the initial part of the array will be uninitialized. If you specify to large a length, the initial part of the list will not be written.

If you are unaware of the size of the list, `Arr.fromList . fromList` will do the trick, but will obviously be slower.

toSet :: Ord a => Tsil a -> Set a

Convert to a set without an intermediate conversion to a cons-list.