Z.Data.Vector.Sort

This module provide three stable sorting algorithms, which are:

• mergeSort, a O(log(n)) general-purpose sorting algorithms for all different size vectors.
• insertSort a O(n^2) sorting algorithms suitable for very small vectors.
• radixSort a O(n) sorting algorithms based on Radix instance, which is prefered on large vectors.

Sorting is always performed in ascending order. To reverse the order, either use XXSortBy or use Down, RadixDown newtypes. In general changing comparing functions can be done by creating auxiliary newtypes and Ord instances (make sure you inline instance's method for performence!). Or Radix instances in radixSort case, for example:

data Foo = Foo { key :: Int16, ... }

instance Radix Foo where
    -- You should add INLINE pragmas to following methods
    bucketSize = bucketSize . key
    passes = passes . key
    radixLSB = radixLSB . key
    radix i = radix i . key
    radixMSB = radixMSB . key

Sort

mergeSort :: forall v a. (Vec v a, Ord a) => v a -> v a

O(n*log(n)) Sort vector based on element's Ord instance with classic mergesort algorithm.

This is a stable sort, During sorting two O(n) worker arrays are needed, one of them will be freezed into the result vector. The merge sort only begin at tile size larger than mergeTileSize, each tile will be sorted with insertSort, then iteratively merged into larger array, until all elements are sorted.

mergeSortBy :: forall v a. Vec v a => (a -> a -> Ordering) -> v a -> v a

mergeTileSize :: Int

The mergesort tile size, mergeTileSize = 8.

insertSort :: (Vec v a, Ord a) => v a -> v a

O(n^2) Sort vector based on element's Ord instance with simple insertion-sort algorithm.

This is a stable sort. O(n) extra space are needed, which will be freezed into result vector.

insertSortBy :: Vec v a => (a -> a -> Ordering) -> v a -> v a

newtype Down a

The Down type allows you to reverse sort order conveniently. A value of type Down a contains a value of type a (represented as Down a). If a has an Ord instance associated with it then comparing two values thus wrapped will give you the opposite of their normal sort order. This is particularly useful when sorting in generalised list comprehensions, as in: then sortWith by Down x

Since: base-4.6.0.0

Constructors

Down

Fields

• getDown :: a

  Since: base-4.14.0.0

Instances

Monad Down

Since: base-4.11.0.0

Defined in Data.Ord

Methods

(>>=) :: Down a -> (a -> Down b) -> Down b

(>>) :: Down a -> Down b -> Down b

return :: a -> Down a

Functor Down

Since: base-4.11.0.0

Defined in Data.Ord

Methods

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

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

Applicative Down

Since: base-4.11.0.0

Defined in Data.Ord

Methods

pure :: a -> Down a

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

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

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

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

Foldable Down

Since: base-4.12.0.0

Defined in Data.Foldable

Methods

fold :: Monoid m => Down m -> m

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

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

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

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

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

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

foldr1 :: (a -> a -> a) -> Down a -> a

foldl1 :: (a -> a -> a) -> Down a -> a

toList :: Down a -> [a]

null :: Down a -> Bool

length :: Down a -> Int

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

maximum :: Ord a => Down a -> a

minimum :: Ord a => Down a -> a

sum :: Num a => Down a -> a

product :: Num a => Down a -> a

Traversable Down

Since: base-4.12.0.0

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> Down a -> f (Down b)

sequenceA :: Applicative f => Down (f a) -> f (Down a)

mapM :: Monad m => (a -> m b) -> Down a -> m (Down b)

sequence :: Monad m => Down (m a) -> m (Down a)

Eq1 Down

Since: base-4.12.0.0

Defined in Data.Functor.Classes

Methods

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

Ord1 Down

Since: base-4.12.0.0

Defined in Data.Functor.Classes

Methods

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

Read1 Down

Since: base-4.12.0.0

Defined in Data.Functor.Classes

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Down a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Down a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Down a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Down a]

Show1 Down

Since: base-4.12.0.0

Defined in Data.Functor.Classes

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Down a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Down a] -> ShowS

NFData1 Down

Since: deepseq-1.4.3.0

Defined in Control.DeepSeq

Methods

liftRnf :: (a -> ()) -> Down a -> ()

Bounded a => Bounded (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

minBound :: Down a

maxBound :: Down a

Enum a => Enum (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

succ :: Down a -> Down a

pred :: Down a -> Down a

toEnum :: Int -> Down a

fromEnum :: Down a -> Int

enumFrom :: Down a -> [Down a]

enumFromThen :: Down a -> Down a -> [Down a]

enumFromTo :: Down a -> Down a -> [Down a]

enumFromThenTo :: Down a -> Down a -> Down a -> [Down a]

Eq a => Eq (Down a)

Since: base-4.6.0.0

Defined in Data.Ord

Methods

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

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

Floating a => Floating (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

pi :: Down a

exp :: Down a -> Down a

log :: Down a -> Down a

sqrt :: Down a -> Down a

(**) :: Down a -> Down a -> Down a

logBase :: Down a -> Down a -> Down a

sin :: Down a -> Down a

cos :: Down a -> Down a

tan :: Down a -> Down a

asin :: Down a -> Down a

acos :: Down a -> Down a

atan :: Down a -> Down a

sinh :: Down a -> Down a

cosh :: Down a -> Down a

tanh :: Down a -> Down a

asinh :: Down a -> Down a

acosh :: Down a -> Down a

atanh :: Down a -> Down a

log1p :: Down a -> Down a

expm1 :: Down a -> Down a

log1pexp :: Down a -> Down a

log1mexp :: Down a -> Down a

Fractional a => Fractional (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

(/) :: Down a -> Down a -> Down a

recip :: Down a -> Down a

fromRational :: Rational -> Down a

Integral a => Integral (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

quot :: Down a -> Down a -> Down a

rem :: Down a -> Down a -> Down a

div :: Down a -> Down a -> Down a

mod :: Down a -> Down a -> Down a

quotRem :: Down a -> Down a -> (Down a, Down a)

divMod :: Down a -> Down a -> (Down a, Down a)

toInteger :: Down a -> Integer

Data a => Data (Down a)

Since: base-4.12.0.0

Defined in Data.Data

Methods

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

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

toConstr :: Down a -> Constr

dataTypeOf :: Down a -> DataType

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

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

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

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

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

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

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

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

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

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

Num a => Num (Down a)

Since: base-4.11.0.0

Defined in Data.Ord

Methods

(+) :: Down a -> Down a -> Down a

(-) :: Down a -> Down a -> Down a

(*) :: Down a -> Down a -> Down a

negate :: Down a -> Down a

abs :: Down a -> Down a

signum :: Down a -> Down a

fromInteger :: Integer -> Down a

Ord a => Ord (Down a)

Since: base-4.6.0.0

Defined in Data.Ord

Methods

compare :: Down a -> Down a -> Ordering

(<) :: Down a -> Down a -> Bool

(<=) :: Down a -> Down a -> Bool

(>) :: Down a -> Down a -> Bool

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

max :: Down a -> Down a -> Down a

min :: Down a -> Down a -> Down a

Read a => Read (Down a)

This instance would be equivalent to the derived instances of the Down newtype if the getDown field were removed

Since: base-4.7.0.0

Defined in Data.Ord

Methods

readsPrec :: Int -> ReadS (Down a)

readList :: ReadS [Down a]

readPrec :: ReadPrec (Down a)

readListPrec :: ReadPrec [Down a]

Real a => Real (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

toRational :: Down a -> Rational

RealFloat a => RealFloat (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

floatRadix :: Down a -> Integer

floatDigits :: Down a -> Int

floatRange :: Down a -> (Int, Int)

decodeFloat :: Down a -> (Integer, Int)

encodeFloat :: Integer -> Int -> Down a

exponent :: Down a -> Int

significand :: Down a -> Down a

scaleFloat :: Int -> Down a -> Down a

isNaN :: Down a -> Bool

isInfinite :: Down a -> Bool

isDenormalized :: Down a -> Bool

isNegativeZero :: Down a -> Bool

isIEEE :: Down a -> Bool

atan2 :: Down a -> Down a -> Down a

RealFrac a => RealFrac (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

properFraction :: Integral b => Down a -> (b, Down a)

truncate :: Integral b => Down a -> b

round :: Integral b => Down a -> b

ceiling :: Integral b => Down a -> b

floor :: Integral b => Down a -> b

Show a => Show (Down a)

This instance would be equivalent to the derived instances of the Down newtype if the getDown field were removed

Since: base-4.7.0.0

Defined in Data.Ord

Methods

showsPrec :: Int -> Down a -> ShowS

show :: Down a -> String

showList :: [Down a] -> ShowS

Ix a => Ix (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

range :: (Down a, Down a) -> [Down a]

index :: (Down a, Down a) -> Down a -> Int

unsafeIndex :: (Down a, Down a) -> Down a -> Int

inRange :: (Down a, Down a) -> Down a -> Bool

rangeSize :: (Down a, Down a) -> Int

unsafeRangeSize :: (Down a, Down a) -> Int

Generic (Down a)

Since: base-4.12.0.0

Defined in GHC.Generics

Associated Types

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

Methods

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

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

Semigroup a => Semigroup (Down a)

Since: base-4.11.0.0

Defined in Data.Ord

Methods

(<>) :: Down a -> Down a -> Down a

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

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

Monoid a => Monoid (Down a)

Since: base-4.11.0.0

Defined in Data.Ord

Methods

mempty :: Down a

mappend :: Down a -> Down a -> Down a

mconcat :: [Down a] -> Down a

Storable a => Storable (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

sizeOf :: Down a -> Int

alignment :: Down a -> Int

peekElemOff :: Ptr (Down a) -> Int -> IO (Down a)

pokeElemOff :: Ptr (Down a) -> Int -> Down a -> IO ()

peekByteOff :: Ptr b -> Int -> IO (Down a)

pokeByteOff :: Ptr b -> Int -> Down a -> IO ()

peek :: Ptr (Down a) -> IO (Down a)

poke :: Ptr (Down a) -> Down a -> IO ()

Bits a => Bits (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

(.&.) :: Down a -> Down a -> Down a

(.|.) :: Down a -> Down a -> Down a

xor :: Down a -> Down a -> Down a

complement :: Down a -> Down a

shift :: Down a -> Int -> Down a

rotate :: Down a -> Int -> Down a

zeroBits :: Down a

bit :: Int -> Down a

setBit :: Down a -> Int -> Down a

clearBit :: Down a -> Int -> Down a

complementBit :: Down a -> Int -> Down a

testBit :: Down a -> Int -> Bool

bitSizeMaybe :: Down a -> Maybe Int

bitSize :: Down a -> Int

isSigned :: Down a -> Bool

shiftL :: Down a -> Int -> Down a

unsafeShiftL :: Down a -> Int -> Down a

shiftR :: Down a -> Int -> Down a

unsafeShiftR :: Down a -> Int -> Down a

rotateL :: Down a -> Int -> Down a

rotateR :: Down a -> Int -> Down a

popCount :: Down a -> Int

FiniteBits a => FiniteBits (Down a)

Since: base-4.14.0.0

Defined in Data.Ord

Methods

finiteBitSize :: Down a -> Int

countLeadingZeros :: Down a -> Int

countTrailingZeros :: Down a -> Int

NFData a => NFData (Down a)

Since: deepseq-1.4.0.0

Defined in Control.DeepSeq

Methods

rnf :: Down a -> ()

Prim a => Prim (Down a)

Defined in Data.Primitive.Types

Methods

sizeOf# :: Down a -> Int#

alignment# :: Down a -> Int#

indexByteArray# :: ByteArray# -> Int# -> Down a

readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Down a #)

writeByteArray# :: MutableByteArray# s -> Int# -> Down a -> State# s -> State# s

setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Down a -> State# s -> State# s

indexOffAddr# :: Addr# -> Int# -> Down a

readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Down a #)

writeOffAddr# :: Addr# -> Int# -> Down a -> State# s -> State# s

setOffAddr# :: Addr# -> Int# -> Int# -> Down a -> State# s -> State# s

Generic1 Down

Since: base-4.12.0.0

Defined in GHC.Generics

Associated Types

type Rep1 Down :: k -> Type

Methods

from1 :: forall (a :: k). Down a -> Rep1 Down a

to1 :: forall (a :: k). Rep1 Down a -> Down a

type Rep (Down a)

Defined in GHC.Generics

type Rep (Down a) = D1 ('MetaData "Down" "Data.Ord" "base" 'True) (C1 ('MetaCons "Down" 'PrefixI 'True) (S1 ('MetaSel ('Just "getDown") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

type Rep1 Down

Defined in GHC.Generics

type Rep1 Down = D1 ('MetaData "Down" "Data.Ord" "base" 'True) (C1 ('MetaCons "Down" 'PrefixI 'True) (S1 ('MetaSel ('Just "getDown") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1))

radixSort :: forall v a. (Vec v a, Radix a) => v a -> v a

O(n) Sort vector based on element's Radix instance with radix-sort, (Least significant digit radix sorts variation).

This is a stable sort, one or two extra O(n) worker array are need depend on how many passes shall be performed, and a bucketSize counting bucket are also needed. This sort algorithms performed extremly well on small byte size types such as Int8 or Word8, while on larger type, constant passes may render this algorithm not suitable for small vectors (turning point around 2^(2*passes)).

class Radix a where

Types contain radixs, which can be inspected with radix during different passes.

The default instances share a same bucketSize 256, which seems to be a good default.

Methods

bucketSize :: a -> Int

The size of an auxiliary array, i.e. the counting bucket

passes :: a -> Int

The number of passes necessary to sort an array of es, it equals to the key's byte number.

radixLSB :: a -> Int

The radix function used in the first pass, works on the least significant bit.

radix :: Int -> a -> Int

The radix function parameterized by the current pass (0 < pass < passes e-1).

radixMSB :: a -> Int

The radix function used in the last pass, works on the most significant bit.

Instances

Radix Int

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Int -> Int

passes :: Int -> Int

radixLSB :: Int -> Int

radix :: Int -> Int -> Int

radixMSB :: Int -> Int

Radix Int8

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Int8 -> Int

passes :: Int8 -> Int

radixLSB :: Int8 -> Int

radix :: Int -> Int8 -> Int

radixMSB :: Int8 -> Int

Radix Int16

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Int16 -> Int

passes :: Int16 -> Int

radixLSB :: Int16 -> Int

radix :: Int -> Int16 -> Int

radixMSB :: Int16 -> Int

Radix Int32

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Int32 -> Int

passes :: Int32 -> Int

radixLSB :: Int32 -> Int

radix :: Int -> Int32 -> Int

radixMSB :: Int32 -> Int

Radix Int64

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Int64 -> Int

passes :: Int64 -> Int

radixLSB :: Int64 -> Int

radix :: Int -> Int64 -> Int

radixMSB :: Int64 -> Int

Radix Word

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Word -> Int

passes :: Word -> Int

radixLSB :: Word -> Int

radix :: Int -> Word -> Int

radixMSB :: Word -> Int

Radix Word8

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Word8 -> Int

passes :: Word8 -> Int

radixLSB :: Word8 -> Int

radix :: Int -> Word8 -> Int

radixMSB :: Word8 -> Int

Radix Word16

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Word16 -> Int

passes :: Word16 -> Int

radixLSB :: Word16 -> Int

radix :: Int -> Word16 -> Int

radixMSB :: Word16 -> Int

Radix Word32

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Word32 -> Int

passes :: Word32 -> Int

radixLSB :: Word32 -> Int

radix :: Int -> Word32 -> Int

radixMSB :: Word32 -> Int

Radix Word64

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: Word64 -> Int

passes :: Word64 -> Int

radixLSB :: Word64 -> Int

radix :: Int -> Word64 -> Int

radixMSB :: Word64 -> Int

Radix a => Radix (RadixDown a)

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: RadixDown a -> Int

passes :: RadixDown a -> Int

radixLSB :: RadixDown a -> Int

radix :: Int -> RadixDown a -> Int

radixMSB :: RadixDown a -> Int

newtype RadixDown a

Similar to Down newtype for Ord, this newtype can inverse the order of a Radix instance when used in radixSort.

Constructors

RadixDown a

Instances

Eq a => Eq (RadixDown a)

Defined in Z.Data.Vector.Sort

Methods

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

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

Show a => Show (RadixDown a)

Defined in Z.Data.Vector.Sort

Methods

showsPrec :: Int -> RadixDown a -> ShowS

show :: RadixDown a -> String

showList :: [RadixDown a] -> ShowS

Prim a => Prim (RadixDown a)

Defined in Z.Data.Vector.Sort

Methods

sizeOf# :: RadixDown a -> Int#

alignment# :: RadixDown a -> Int#

indexByteArray# :: ByteArray# -> Int# -> RadixDown a

readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, RadixDown a #)

writeByteArray# :: MutableByteArray# s -> Int# -> RadixDown a -> State# s -> State# s

setByteArray# :: MutableByteArray# s -> Int# -> Int# -> RadixDown a -> State# s -> State# s

indexOffAddr# :: Addr# -> Int# -> RadixDown a

readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, RadixDown a #)

writeOffAddr# :: Addr# -> Int# -> RadixDown a -> State# s -> State# s

setOffAddr# :: Addr# -> Int# -> Int# -> RadixDown a -> State# s -> State# s

Radix a => Radix (RadixDown a)

Defined in Z.Data.Vector.Sort

Methods

bucketSize :: RadixDown a -> Int

passes :: RadixDown a -> Int

radixLSB :: RadixDown a -> Int

radix :: Int -> RadixDown a -> Int

radixMSB :: RadixDown a -> Int

merge duplicated

mergeDupAdjacent :: (Vec v a, Eq a) => v a -> v a

merge duplicated adjacent element, prefer left element.

Use this function on a sorted vector will have the same effects as nub.

mergeDupAdjacentLeft

Arguments

:: Vec v a

=> (a -> a -> Bool)

equality tester, left right -> eq left right

-> v a

-> v a

Merge duplicated adjacent element, prefer left element.

mergeDupAdjacentRight

Arguments

:: Vec v a

=> (a -> a -> Bool)

equality tester, left right -> eq left right

-> v a

-> v a

Merge duplicated adjacent element, prefer right element.

mergeDupAdjacentBy

Arguments

:: Vec v a

=> (a -> a -> Bool)

equality tester, left right -> eq left right

-> (a -> a -> a)

the merger, left right -> merge left right

-> v a

-> v a

Merge duplicated adjacent element, based on a equality tester and a merger function.