Data.HList.HSort

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.

Documentation

data HLeFn

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

HEqByFn HLeFn

Defined in Data.HList.HSort

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

only in ghc >= 7.7

Defined in Data.HList.HSort

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

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

Defined in Data.HList.HSort

HLe x y ~ b => HEqBy HLeFn (x :: HNat) (y :: HNat) b

Defined in Data.HList.HSort

HEqBy HLeFn x y b => HEqBy HLeFn (Proxy x :: Type) (Proxy y :: Type) b

Defined in Data.HList.HSort

HEqBy HLeFn x y b => HEqBy HLeFn (Label x :: Type) (Label y :: Type) b

Defined in Data.HList.HSort

HEqBy HLeFn x y b => HEqBy HLeFn (Tagged x v :: Type) (Tagged y w :: Type) b

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

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

Defined in Data.HList.HSort

data HDown a

analogous to Down

Instances

HEqBy f y x b => HEqBy (HDown f :: Type) (x :: k2) (y :: k2) b

Defined in Data.HList.HSort

HEqByFn a => HEqByFn (HDown a :: Type)

Defined in Data.HList.HSort

data HNeq le

The HEqBy instances for HNeq HLeFn gives <

Instances

(HEqBy le y x b1, HNot b1 ~ b2) => HEqBy (HNeq le :: Type) (x :: k2) (y :: k2) b2

Defined in Data.HList.HSort

HEqByFn a => HEqByFn (HNeq a :: Type)

Defined in Data.HList.HSort

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

HIsAscList le xs b is analogous to

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

Instances

HEqByFn le => HIsAscList (le :: k) ('[] :: [Type]) 'True

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

Defined in Data.HList.HSort

HEqByFn le => HIsAscList (le :: k) '[x] 'True

Defined in Data.HList.HSort

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

quick sort with a special case for sorted lists

Methods

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

Instances

(SameLength a b, HIsAscList le a ok, HSortBy1 ok le a b, HEqByFn le) => HSortBy (le :: k) a b

Defined in Data.HList.HSort

Methods

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

type HSort x y = HSortBy HLeFn x y

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

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

Methods

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

Instances

HSortBy1 'True (le :: k) a a

Defined in Data.HList.HSort

Methods

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

HQSortBy le a b => HSortBy1 'False (le :: k) a b

Defined in Data.HList.HSort

Methods

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

Merge Sort

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

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

Instances

HEqByFn le => HMSortBy (le :: k) ('[] :: [Type]) ('[] :: [Type])

Defined in Data.HList.HSort

Methods

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

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

Defined in Data.HList.HSort

Methods

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

(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

Defined in Data.HList.HSort

Methods

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

HEqByFn le => HMSortBy (le :: k) '[x] '[x]

Defined in Data.HList.HSort

Methods

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

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

Methods

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

Instances

HSort2 'False x y '[y, x]

Defined in Data.HList.HSort

Methods

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

HSort2 'True x y '[x, y]

Defined in Data.HList.HSort

Methods

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

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

Methods

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

Instances

HMerge (le :: k) ('[] :: [Type]) ('[] :: [Type]) ('[] :: [Type])

Defined in Data.HList.HSort

Methods

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

HMerge (le :: k) ('[] :: [Type]) (x ': xs) (x ': xs)

Defined in Data.HList.HSort

Methods

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

HMerge (le :: k) (x ': xs) ('[] :: [Type]) (x ': xs)

Defined in Data.HList.HSort

Methods

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

(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)

Defined in Data.HList.HSort

Methods

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

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

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

Quick sort

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

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

Instances

HQSortBy (le :: k) ('[] :: [Type]) ('[] :: [Type])

Defined in Data.HList.HSort

Methods

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

(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

Defined in Data.HList.HSort

Methods

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

HQSortBy (le :: k) '[x] '[x]

Defined in Data.HList.HSort

Methods

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

More efficient HRLabelSet / HLabelSet

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

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

(HEqByFn lt, HSortBy lt ps ps', HAscList lt ps') => HSetBy (lt :: k) ps

Defined in Data.HList.HSort

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

Instances

HSetBy (HNeq HLeFn) ps => HSet ps

Defined in Data.HList.HSort

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

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

HIsSetBy (HNeq HLeFn) ps b => HIsSet ps b

Defined in Data.HList.HSort

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

Instances

(HEqByFn lt, HSortBy lt ps ps', HIsAscList lt ps' b) => HIsSetBy (lt :: k) ps b

Defined in Data.HList.HSort

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

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

Instances

(HEqByFn le, HAscList0 le ps ps) => HAscList (le :: k) ps

Defined in Data.HList.HSort

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

Instances

HEqByFn le => HAscList0 (le :: k) ('[] :: [Type]) ps0

Defined in Data.HList.HSort

HEqByFn le => HAscList0 (le :: k) '[x] ps0

Defined in Data.HList.HSort

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

Defined in Data.HList.HSort

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

Instances

HAscList0 le ys ys0 => HAscList1 (le :: k) 'True ys ys0

Defined in Data.HList.HSort

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

Defined in Data.HList.HSort

>>> import Data.HList.TypeEqO