Data.List.Kleene.Star

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.

The list type

data Star a

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

Monad Star

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

Defined in Data.List.Kleene.Internal

Methods

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

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

MonadFix Star

Defined in Data.List.Kleene.Internal

Methods

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

Applicative Star

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

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

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

Defined in Data.List.Kleene.Internal

Methods

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

Ord1 Star

Defined in Data.List.Kleene.Internal

Methods

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

Show1 Star

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

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

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

Defined in Data.List.Kleene.Internal

Methods

mzero :: Star a

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

IsList (Star a)

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)

Defined in Data.List.Kleene.Internal

Methods

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

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

Data a => Data (Star a)

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)

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)

Defined in Data.List.Kleene.Internal

Methods

showsPrec :: Int -> Star a -> ShowS

show :: Star a -> String

showList :: [Star a] -> ShowS

Generic (Star a)

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)

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)

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)

Defined in Data.List.Kleene.Internal

Methods

rnf :: Star a -> ()

type Rep (Star a)

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)

Defined in Data.List.Kleene.Internal

type Item (Star a) = a

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

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

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

data Plus a

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

• head :: a
• tail :: Star a

Instances

Monad Plus

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

Defined in Data.List.Kleene.Internal

Methods

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

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

MonadFix Plus

Defined in Data.List.Kleene.Internal

Methods

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

Applicative Plus

>>> (,) <$> (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')]

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

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

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

Defined in Data.List.Kleene.Internal

Methods

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

Ord1 Plus

Defined in Data.List.Kleene.Internal

Methods

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

Show1 Plus

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

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)

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)

Defined in Data.List.Kleene.Internal

Methods

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

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

Data a => Data (Plus a)

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)

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)

Defined in Data.List.Kleene.Internal

Methods

showsPrec :: Int -> Plus a -> ShowS

show :: Plus a -> String

showList :: [Plus a] -> ShowS

Generic (Plus a)

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)

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)

Defined in Data.List.Kleene.Internal

Methods

rnf :: Plus a -> ()

type Rep (Plus a)

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)

Defined in Data.List.Kleene.Internal

type Item (Plus a) = a

Utility functions

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

Functions the same as filter in Data.List.

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

reverse :: Star a -> Star a

Reverse a list.

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

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

Convert to a Plus list.

take :: Int -> Star a -> Star a

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

Index into a list.

>>> [0..] !! 3
3

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

Building lists

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

Unfold a list from a seed.

scans

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

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

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

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

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

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

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

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

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