kleene-list-0.1.0.0: A list type based on the Kleene star and plus.
Copyright(c) Donnacha Oisín Kidney 2020
LicenseApache
Maintainermail@doisinkidney.com
Stabilityexperimental
Portabilityghc
Safe HaskellNone
LanguageHaskell2010

Data.List.Kleene.Star

Description

This module provides a simple list type isomorphic to Haskell's standard [], but which is defined in terms of a non-empty list type. This can make moving between one type and another easier.

Synopsis

The list type

data Star a Source #

A list, based on the Kleene star. This type is isomorphic to Haskell's standard [] type, so it can be used in the same way.

Constructors

Nil 
Cons (Plus a) 

Instances

Instances details
Monad Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

(>>=) :: Star a -> (a -> Star b) -> Star b #

(>>) :: Star a -> Star b -> Star b #

return :: a -> Star a #

Functor Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

fmap :: (a -> b) -> Star a -> Star b #

(<$) :: a -> Star b -> Star a #

MonadFix Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

mfix :: (a -> Star a) -> Star a #

Applicative Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

pure :: a -> Star a #

(<*>) :: Star (a -> b) -> Star a -> Star b #

liftA2 :: (a -> b -> c) -> Star a -> Star b -> Star c #

(*>) :: Star a -> Star b -> Star b #

(<*) :: Star a -> Star b -> Star a #

Foldable Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

fold :: Monoid m => Star m -> m #

foldMap :: Monoid m => (a -> m) -> Star a -> m #

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

foldr :: (a -> b -> b) -> b -> Star a -> b #

foldr' :: (a -> b -> b) -> b -> Star a -> b #

foldl :: (b -> a -> b) -> b -> Star a -> b #

foldl' :: (b -> a -> b) -> b -> Star a -> b #

foldr1 :: (a -> a -> a) -> Star a -> a #

foldl1 :: (a -> a -> a) -> Star a -> a #

toList :: Star a -> [a] #

null :: Star a -> Bool #

length :: Star a -> Int #

elem :: Eq a => a -> Star a -> Bool #

maximum :: Ord a => Star a -> a #

minimum :: Ord a => Star a -> a #

sum :: Num a => Star a -> a #

product :: Num a => Star a -> a #

Traversable Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

traverse :: Applicative f => (a -> f b) -> Star a -> f (Star b) #

sequenceA :: Applicative f => Star (f a) -> f (Star a) #

mapM :: Monad m => (a -> m b) -> Star a -> m (Star b) #

sequence :: Monad m => Star (m a) -> m (Star a) #

Eq1 Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

liftEq :: (a -> b -> Bool) -> Star a -> Star b -> Bool #

Ord1 Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> Star a -> Star b -> Ordering #

Show1 Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Star a -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Star a] -> ShowS #

MonadZip Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

mzip :: Star a -> Star b -> Star (a, b) #

mzipWith :: (a -> b -> c) -> Star a -> Star b -> Star c #

munzip :: Star (a, b) -> (Star a, Star b) #

Alternative Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

empty :: Star a #

(<|>) :: Star a -> Star a -> Star a #

some :: Star a -> Star [a] #

many :: Star a -> Star [a] #

MonadPlus Star Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

mzero :: Star a #

mplus :: Star a -> Star a -> Star a #

IsList (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Associated Types

type Item (Star a) #

Methods

fromList :: [Item (Star a)] -> Star a #

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

toList :: Star a -> [Item (Star a)] #

Eq a => Eq (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

(==) :: Star a -> Star a -> Bool #

(/=) :: Star a -> Star a -> Bool #

Data a => Data (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

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

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

toConstr :: Star a -> Constr #

dataTypeOf :: Star a -> DataType #

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

compare :: Star a -> Star a -> Ordering #

(<) :: Star a -> Star a -> Bool #

(<=) :: Star a -> Star a -> Bool #

(>) :: Star a -> Star a -> Bool #

(>=) :: Star a -> Star a -> Bool #

max :: Star a -> Star a -> Star a #

min :: Star a -> Star a -> Star a #

Show a => Show (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

showsPrec :: Int -> Star a -> ShowS #

show :: Star a -> String #

showList :: [Star a] -> ShowS #

Generic (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Associated Types

type Rep (Star a) :: Type -> Type #

Methods

from :: Star a -> Rep (Star a) x #

to :: Rep (Star a) x -> Star a #

Semigroup (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

(<>) :: Star a -> Star a -> Star a #

sconcat :: NonEmpty (Star a) -> Star a #

stimes :: Integral b => b -> Star a -> Star a #

Monoid (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

mempty :: Star a #

mappend :: Star a -> Star a -> Star a #

mconcat :: [Star a] -> Star a #

NFData a => NFData (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

rnf :: Star a -> () #

type Rep (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

type Rep (Star a) = D1 ('MetaData "Star" "Data.List.Kleene.Internal" "kleene-list-0.1.0.0-inplace" 'False) (C1 ('MetaCons "Nil" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Cons" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Plus a))))
type Item (Star a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

type Item (Star a) = a

pattern (:*) :: a -> Star a -> Star a infixr 5 Source #

A pattern for building up star lists as cons-lists.

>>> 1 :* 2 :* 3 :* Nil
[1,2,3]

data Plus a Source #

A non-empty list type, based on the Kleene plus. This type is isomorphic to NonEmpty type, so it can be used in the same way.

Constructors

(:-) infixr 5 

Fields

Instances

Instances details
Monad Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

(>>=) :: Plus a -> (a -> Plus b) -> Plus b #

(>>) :: Plus a -> Plus b -> Plus b #

return :: a -> Plus a #

Functor Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

fmap :: (a -> b) -> Plus a -> Plus b #

(<$) :: a -> Plus b -> Plus a #

MonadFix Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

mfix :: (a -> Plus a) -> Plus a #

Applicative Plus Source #
>>> (,) <$> (1 :+ 2 :+ One 3) <*> ('a' :+ 'b' :+ One 'c')
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]
>>> liftA2 (,) (1 :+ 2 :+ One 3) ('a' :+ 'b' :+ One 'c')
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]
Instance details

Defined in Data.List.Kleene.Internal

Methods

pure :: a -> Plus a #

(<*>) :: Plus (a -> b) -> Plus a -> Plus b #

liftA2 :: (a -> b -> c) -> Plus a -> Plus b -> Plus c #

(*>) :: Plus a -> Plus b -> Plus b #

(<*) :: Plus a -> Plus b -> Plus a #

Foldable Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

fold :: Monoid m => Plus m -> m #

foldMap :: Monoid m => (a -> m) -> Plus a -> m #

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

foldr :: (a -> b -> b) -> b -> Plus a -> b #

foldr' :: (a -> b -> b) -> b -> Plus a -> b #

foldl :: (b -> a -> b) -> b -> Plus a -> b #

foldl' :: (b -> a -> b) -> b -> Plus a -> b #

foldr1 :: (a -> a -> a) -> Plus a -> a #

foldl1 :: (a -> a -> a) -> Plus a -> a #

toList :: Plus a -> [a] #

null :: Plus a -> Bool #

length :: Plus a -> Int #

elem :: Eq a => a -> Plus a -> Bool #

maximum :: Ord a => Plus a -> a #

minimum :: Ord a => Plus a -> a #

sum :: Num a => Plus a -> a #

product :: Num a => Plus a -> a #

Traversable Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

traverse :: Applicative f => (a -> f b) -> Plus a -> f (Plus b) #

sequenceA :: Applicative f => Plus (f a) -> f (Plus a) #

mapM :: Monad m => (a -> m b) -> Plus a -> m (Plus b) #

sequence :: Monad m => Plus (m a) -> m (Plus a) #

Eq1 Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

liftEq :: (a -> b -> Bool) -> Plus a -> Plus b -> Bool #

Ord1 Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> Plus a -> Plus b -> Ordering #

Show1 Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Plus a -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Plus a] -> ShowS #

MonadZip Plus Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

mzip :: Plus a -> Plus b -> Plus (a, b) #

mzipWith :: (a -> b -> c) -> Plus a -> Plus b -> Plus c #

munzip :: Plus (a, b) -> (Plus a, Plus b) #

IsList (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Associated Types

type Item (Plus a) #

Methods

fromList :: [Item (Plus a)] -> Plus a #

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

toList :: Plus a -> [Item (Plus a)] #

Eq a => Eq (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

(==) :: Plus a -> Plus a -> Bool #

(/=) :: Plus a -> Plus a -> Bool #

Data a => Data (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

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

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

toConstr :: Plus a -> Constr #

dataTypeOf :: Plus a -> DataType #

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

compare :: Plus a -> Plus a -> Ordering #

(<) :: Plus a -> Plus a -> Bool #

(<=) :: Plus a -> Plus a -> Bool #

(>) :: Plus a -> Plus a -> Bool #

(>=) :: Plus a -> Plus a -> Bool #

max :: Plus a -> Plus a -> Plus a #

min :: Plus a -> Plus a -> Plus a #

Show a => Show (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

showsPrec :: Int -> Plus a -> ShowS #

show :: Plus a -> String #

showList :: [Plus a] -> ShowS #

Generic (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Associated Types

type Rep (Plus a) :: Type -> Type #

Methods

from :: Plus a -> Rep (Plus a) x #

to :: Rep (Plus a) x -> Plus a #

Semigroup (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

(<>) :: Plus a -> Plus a -> Plus a #

sconcat :: NonEmpty (Plus a) -> Plus a #

stimes :: Integral b => b -> Plus a -> Plus a #

NFData a => NFData (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

Methods

rnf :: Plus a -> () #

type Rep (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

type Rep (Plus a) = D1 ('MetaData "Plus" "Data.List.Kleene.Internal" "kleene-list-0.1.0.0-inplace" 'False) (C1 ('MetaCons ":-" 'PrefixI 'True) (S1 ('MetaSel ('Just "head") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "tail") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Star a))))
type Item (Plus a) Source # 
Instance details

Defined in Data.List.Kleene.Internal

type Item (Plus a) = a

Utility functions

filter :: Foldable f => (a -> Bool) -> f a -> Star a Source #

Functions the same as filter in Data.List.

>>> filter even ([1..5] :: Star Int)
[2,4]

reverse :: Star a -> Star a Source #

Reverse a list.

>>> reverse [1..5]
[5,4,3,2,1]

uncons :: Star a -> Maybe (Plus a) Source #

Convert to a Plus list.

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

take n xs takes the first n elements from xs.

>>> take 5 [1..]
[1,2,3,4,5]
>>> take 5 [1..3]
[1,2,3]

(!!) :: Star a -> Int -> a Source #

Index into a list.

>>> [0..] !! 3
3
>>> [0..5] !! 6
*** Exception: index: empty list!

Building lists

unfoldr :: (b -> Maybe (a, b)) -> b -> Star a Source #

Unfold a list from a seed.

scans

scanr :: Foldable f => (a -> b -> b) -> b -> f a -> Plus b Source #

Functions the same as scanr in Data.List.

>>> scanr (+) 0 ([1,2,3] :: Star Int)
[6,5,3,0]

scanl :: (b -> a -> b) -> b -> Star a -> Plus b Source #

Functions the same as scanl in Data.List.

>>> scanl (+) 0 [1,2,3]
[0,1,3,6]

prescanl :: (b -> a -> b) -> b -> Star a -> Star b Source #

Like scanl, but without including the initial element in the output.

>>> prescanl (+) 0 [1,2,3]
[1,3,6]

prescanr :: (a -> b -> b) -> b -> Star a -> Star b Source #

Like scanr, but without including the initial element in the output.

>>> prescanr (+) 0 [1,2,3]
[6,5,3]

Sorting

sortBy :: (a -> a -> Ordering) -> Star a -> Star a Source #

Sort given a comparison function. Stable. \(\mathcal{O}(n \log n)\).

>>> sortBy (\x y -> compare (fst x) (fst y)) [(4,1),(3,2),(1,3),(3,4)]
[(1,3),(3,2),(3,4),(4,1)]

sortOn :: Ord b => (a -> b) -> Star a -> Star a Source #

Sort given a selector function. Stable. \(\mathcal{O}(n \log n)\).

>>> sortOn fst [(4,1),(3,2),(1,3),(3,4)]
[(1,3),(3,2),(3,4),(4,1)]

sort :: Ord a => Star a -> Star a Source #

Stable sort. \(\mathcal{O}(n \log n)\).

>>> sort [4,3,1,3]
[1,3,3,4]