kleene-list-0.1.0.0: A list type based on the Kleene star and plus.
Copyright (c) Donnacha Oisín Kidney 2020 Apache mail@doisinkidney.com experimental ghc None Haskell2010

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

# 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]