HList-0.5.2.0: Heterogeneous lists
Safe HaskellNone
LanguageHaskell2010

Data.HList.HSort

Description

Benchmarks for these functions can be found at http://code.haskell.org/~aavogt/HList-nodup/Run.html.

See Data-HList-CommonMain.html#v:hSort for the public interface.

Synopsis

Documentation

data HLeFn Source #

the "standard" <= for types. Reuses HEqBy

Note that ghc-7.6 is missing instances for Symbol and Nat, so that sorting only works HNat (as used by Data.HList.Label3).

Instances

Instances details
HEqByFn HLeFn Source # 
Instance details

Defined in Data.HList.HSort

(x <=? y) ~ b => HEqBy HLeFn (x :: Nat) (y :: Nat) b Source #

only in ghc >= 7.7

Instance details

Defined in Data.HList.HSort

(HEq (CmpSymbol x y) 'GT nb, HNot nb ~ b) => HEqBy HLeFn (x :: Symbol) (y :: Symbol) b Source #

only in ghc >= 7.7

>>> let b1 = Proxy :: HEqBy HLeFn "x" "y" b => Proxy b
>>> :t b1
b1 :: Proxy 'True
>>> let b2 = Proxy :: HEqBy HLeFn "x" "x" b => Proxy b
>>> :t b2
b2 :: Proxy 'True
>>> let b3 = Proxy :: HEqBy HLeFn "y" "x" b => Proxy b
>>> :t b3
b3 :: Proxy 'False
Instance details

Defined in Data.HList.HSort

HLe x y ~ b => HEqBy HLeFn (x :: HNat) (y :: HNat) b Source # 
Instance details

Defined in Data.HList.HSort

HEqBy HLeFn x y b => HEqBy HLeFn (Proxy x :: Type) (Proxy y :: Type) b Source # 
Instance details

Defined in Data.HList.HSort

HEqBy HLeFn x y b => HEqBy HLeFn (Label x :: Type) (Label y :: Type) b Source # 
Instance details

Defined in Data.HList.HSort

HEqBy HLeFn x y b => HEqBy HLeFn (Tagged x v :: Type) (Tagged y w :: Type) b Source # 
Instance details

Defined in Data.HList.HSort

(HEqBy HLeFn n m b, ns ~ ns') => HEqBy HLeFn (Lbl n ns desc :: Type) (Lbl m ns' desc' :: Type) b Source #

Data.HList.Label3 labels can only be compared if they belong to the same namespace.

Instance details

Defined in Data.HList.HSort

data HDown a Source #

analogous to Down

Instances

Instances details
HEqBy f y x b => HEqBy (HDown f :: Type) (x :: k2) (y :: k2) b Source # 
Instance details

Defined in Data.HList.HSort

HEqByFn a => HEqByFn (HDown a :: Type) Source # 
Instance details

Defined in Data.HList.HSort

data HNeq le Source #

The HEqBy instances for HNeq HLeFn gives <

Instances

Instances details
(HEqBy le y x b1, HNot b1 ~ b2) => HEqBy (HNeq le :: Type) (x :: k2) (y :: k2) b2 Source # 
Instance details

Defined in Data.HList.HSort

HEqByFn a => HEqByFn (HNeq a :: Type) Source # 
Instance details

Defined in Data.HList.HSort

class HEqByFn le => HIsAscList le (xs :: [*]) (b :: Bool) | le xs -> b Source #

HIsAscList le xs b is analogous to

b = all (\(x,y) -> x `le` y) (xs `zip` tail xs)

Instances

Instances details
HEqByFn le => HIsAscList (le :: k) ('[] :: [Type]) 'True Source # 
Instance details

Defined in Data.HList.HSort

(HEqBy le x y b1, HIsAscList le (y ': ys) b2, HAnd b1 b2 ~ b3) => HIsAscList (le :: k) (x ': (y ': ys)) b3 Source # 
Instance details

Defined in Data.HList.HSort

HEqByFn le => HIsAscList (le :: k) '[x] 'True Source # 
Instance details

Defined in Data.HList.HSort

class (SameLength a b, HEqByFn le) => HSortBy le (a :: [*]) (b :: [*]) | le a -> b where Source #

quick sort with a special case for sorted lists

Methods

hSortBy :: Proxy le -> HList a -> HList b Source #

Instances

Instances details
(SameLength a b, HIsAscList le a ok, HSortBy1 ok le a b, HEqByFn le) => HSortBy (le :: k) a b Source # 
Instance details

Defined in Data.HList.HSort

Methods

hSortBy :: Proxy le -> HList a -> HList b Source #

type HSort x y = HSortBy HLeFn x y Source #

hSort :: HSort x y => HList x -> HList y Source #

class HSortBy1 ok le (a :: [*]) (b :: [*]) | ok le a -> b where Source #

Methods

hSortBy1 :: Proxy ok -> Proxy le -> HList a -> HList b Source #

Instances

Instances details
HSortBy1 'True (le :: k) a a Source # 
Instance details

Defined in Data.HList.HSort

Methods

hSortBy1 :: Proxy 'True -> Proxy le -> HList a -> HList a Source #

HQSortBy le a b => HSortBy1 'False (le :: k) a b Source # 
Instance details

Defined in Data.HList.HSort

Methods

hSortBy1 :: Proxy 'False -> Proxy le -> HList a -> HList b Source #

Merge Sort

class HEqByFn le => HMSortBy le (a :: [*]) (b :: [*]) | le a -> b where Source #

HMSortBy is roughly a transcription of this merge sort

msort [] = []
msort [x] = [x]
msort [x,y] = hSort2 x y
msort xs = case splitAt (length xs `div` 2) xs of
             (a,b) -> msort a `merge` msort b
hSort2 x y
    | x <= y    = [x,y]
    | otherwise = [y,x]
merge (x : xs) (y : ys)
  | x > y     = y : merge (x : xs) ys
  | otherwise = x : merge xs (y : ys)

Methods

hMSortBy :: Proxy le -> HList a -> HList b Source #

Instances

Instances details
HEqByFn le => HMSortBy (le :: k) ('[] :: [Type]) ('[] :: [Type]) Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMSortBy :: Proxy le -> HList '[] -> HList '[] Source #

(HSort2 b x y ab, HEqBy le x y b, HEqByFn le) => HMSortBy (le :: k) '[x, y] ab Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMSortBy :: Proxy le -> HList '[x, y] -> HList ab Source #

(HMerge le xs' ys' sorted, HMSortBy le ys ys', HMSortBy le xs xs', HLengthEq (a ': (b ': (c ': cs))) n2, HDiv2 n2 ~ n, HSplitAt n (a ': (b ': (c ': cs))) xs ys) => HMSortBy (le :: k) (a ': (b ': (c ': cs))) sorted Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMSortBy :: Proxy le -> HList (a ': (b ': (c ': cs))) -> HList sorted Source #

HEqByFn le => HMSortBy (le :: k) '[x] '[x] Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMSortBy :: Proxy le -> HList '[x] -> HList '[x] Source #

class HSort2 b x y ab | b x y -> ab where Source #

Methods

hSort2 :: Proxy b -> x -> y -> HList ab Source #

Instances

Instances details
HSort2 'False x y '[y, x] Source # 
Instance details

Defined in Data.HList.HSort

Methods

hSort2 :: Proxy 'False -> x -> y -> HList '[y, x] Source #

HSort2 'True x y '[x, y] Source # 
Instance details

Defined in Data.HList.HSort

Methods

hSort2 :: Proxy 'True -> x -> y -> HList '[x, y] Source #

class HMerge le x y xy | le x y -> xy where Source #

Methods

hMerge :: Proxy le -> HList x -> HList y -> HList xy Source #

Instances

Instances details
HMerge (le :: k) ('[] :: [Type]) ('[] :: [Type]) ('[] :: [Type]) Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMerge :: Proxy le -> HList '[] -> HList '[] -> HList '[] Source #

HMerge (le :: k) ('[] :: [Type]) (x ': xs) (x ': xs) Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMerge :: Proxy le -> HList '[] -> HList (x ': xs) -> HList (x ': xs) Source #

HMerge (le :: k) (x ': xs) ('[] :: [Type]) (x ': xs) Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMerge :: Proxy le -> HList (x ': xs) -> HList '[] -> HList (x ': xs) Source #

(HEqBy le x y b, HMerge1 b (x ': xs) (y ': ys) (l ': ls) hhs, HMerge le ls hhs srt) => HMerge (le :: k) (x ': xs) (y ': ys) (l ': srt) Source # 
Instance details

Defined in Data.HList.HSort

Methods

hMerge :: Proxy le -> HList (x ': xs) -> HList (y ': ys) -> HList (l ': srt) Source #

type HMerge1 b x y min max = (HCond b (HList x) (HList y) (HList min), HCond b (HList y) (HList x) (HList max)) Source #

hMerge1 :: forall (t :: Bool) y x a b. (HCond t y x a, HCond t x y b) => Proxy t -> y -> x -> (a, b) Source #

Quick sort

class HQSortBy le (a :: [*]) (b :: [*]) | le a -> b where Source #

HQSortBy is this algorithm

qsort (x : xs @ (_ : _)) = case partition (<= x) xs of
                 (le, gt) -> qsort le ++ x : qsort gt
qsort xs = xs

on random inputs that are not pathological (ie. not already sorted or reverse sorted) this turns out to be faster than HMSortBy, so it is used by default.

Methods

hQSortBy :: Proxy le -> HList a -> HList b Source #

Instances

Instances details
HQSortBy (le :: k) ('[] :: [Type]) ('[] :: [Type]) Source # 
Instance details

Defined in Data.HList.HSort

Methods

hQSortBy :: Proxy le -> HList '[] -> HList '[] Source #

(HPartitionEq le a (b ': bs) bGeq bLt, HQSortBy le bLt sortedLt, HQSortBy le bGeq sortedGeq, HAppendListR sortedLt (a ': sortedGeq) ~ sorted, HAppendList sortedLt (a ': sortedGeq)) => HQSortBy (le :: k) (a ': (b ': bs)) sorted Source # 
Instance details

Defined in Data.HList.HSort

Methods

hQSortBy :: Proxy le -> HList (a ': (b ': bs)) -> HList sorted Source #

HQSortBy (le :: k) '[x] '[x] Source # 
Instance details

Defined in Data.HList.HSort

Methods

hQSortBy :: Proxy le -> HList '[x] -> HList '[x] Source #

More efficient HRLabelSet / HLabelSet

class HEqByFn lt => HSetBy lt (ps :: [*]) Source #

Provided the labels involved have an appropriate instance of HEqByFn, it would be possible to use the following definitions:

type HRLabelSet = HSet
type HLabelSet  = HSet

Instances

Instances details
(HEqByFn lt, HSortBy lt ps ps', HAscList lt ps') => HSetBy (lt :: k) ps Source # 
Instance details

Defined in Data.HList.HSort

class HSetBy (HNeq HLeFn) ps => HSet (ps :: [*]) Source #

Instances

Instances details
HSetBy (HNeq HLeFn) ps => HSet ps Source # 
Instance details

Defined in Data.HList.HSort

class HIsSet (ps :: [*]) (b :: Bool) | ps -> b Source #

>>> let xx = Proxy :: HIsSet [Label "x", Label "x"] b => Proxy b
>>> :t xx
xx :: Proxy 'False
>>> let xy = Proxy :: HIsSet [Label "x", Label "y"] b => Proxy b
>>> :t xy
xy :: Proxy 'True

Instances

Instances details
HIsSetBy (HNeq HLeFn) ps b => HIsSet ps b Source # 
Instance details

Defined in Data.HList.HSort

class HEqByFn lt => HIsSetBy lt (ps :: [*]) (b :: Bool) | lt ps -> b Source #

Instances

Instances details
(HEqByFn lt, HSortBy lt ps ps', HIsAscList lt ps' b) => HIsSetBy (lt :: k) ps b Source # 
Instance details

Defined in Data.HList.HSort

class HEqByFn le => HAscList le (ps :: [*]) Source #

HAscList le xs confirms that xs is in ascending order, and reports which element is duplicated otherwise.

Instances

Instances details
(HEqByFn le, HAscList0 le ps ps) => HAscList (le :: k) ps Source # 
Instance details

Defined in Data.HList.HSort

class HEqByFn le => HAscList0 le (ps :: [*]) (ps0 :: [*]) Source #

Instances

Instances details
HEqByFn le => HAscList0 (le :: k) ('[] :: [Type]) ps0 Source # 
Instance details

Defined in Data.HList.HSort

HEqByFn le => HAscList0 (le :: k) '[x] ps0 Source # 
Instance details

Defined in Data.HList.HSort

(HAscList1 le b (y ': ys) ps0, HEqBy le x y b) => HAscList0 (le :: k) (x ': (y ': ys)) ps0 Source # 
Instance details

Defined in Data.HList.HSort

class HEqByFn le => HAscList1 le (b :: Bool) (ps :: [*]) (ps0 :: [*]) Source #

Instances

Instances details
HAscList0 le ys ys0 => HAscList1 (le :: k) 'True ys ys0 Source # 
Instance details

Defined in Data.HList.HSort

(Fail '("Duplicated element", y, "using le", le, "in", ys0), HEqByFn le) => HAscList1 (le :: k) 'False (y ': ys) ys0 Source # 
Instance details

Defined in Data.HList.HSort

>>> import Data.HList.TypeEqO