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

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

only in ghc >= 7.7

(HEq Ordering (CmpSymbol x y) GT nb, (~) Bool (HNot nb) b) => HEqBy * Symbol HLeFn x y 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

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

HEqBy * k HLeFn x y b => HEqBy * * HLeFn (Proxy k x) (Proxy k y) b

HEqBy * k HLeFn x y b => HEqBy * * HLeFn (Label k x) (Label k y) b

HEqBy * k HLeFn x y b => HEqBy * * HLeFn (Tagged k x v) (Tagged k y w) b

(HEqBy * HNat HLeFn n m b, (~) * ns ns') => HEqBy * * HLeFn (Lbl n ns desc) (Lbl m ns' desc') b

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

data HDown a

analogous to Down

Instances

HEqBy k1 k f y x b => HEqBy * k (HDown k f) x y b

HEqByFn k a => HEqByFn * (HDown k a)

data HNeq le

The HEqBy instances for HNeq HLeFn gives <

Instances

(HEqBy k1 k le y x b1, (~) Bool (HNot b1) b2) => HEqBy * k (HNeq k le) x y b2

HEqByFn k a => HEqByFn * (HNeq k a)

class HEqByFn le => HIsAscList le xs b | le xs -> b

HIsAscList le xs b is analogous to

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

Instances

HEqByFn k le => HIsAscList k le ([] *) True

(HEqBy k * le x y b1, HIsAscList k le ((:) * y ys) b2, (~) Bool (HAnd b1 b2) b3) => HIsAscList k le ((:) * x ((:) * y ys)) b3

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

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 k le a ok, HSortBy1 Bool k ok le a b) => HSortBy k le a 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

HQSortBy k le a b => HSortBy1 Bool k False le a b

HSortBy1 Bool k True le a a

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 k le => HMSortBy k le ([] *) ([] *)

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

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

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

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

Methods

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

Instances

HSort2 Bool False x y ((:) * y ((:) * x ([] *)))

HSort2 Bool True x y ((:) * 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 k le ([] *) ([] *) ([] *)

HMerge k le ([] *) ((:) * x xs) ((:) * x xs)

HMerge k le ((:) * x xs) ([] *) ((:) * x xs)

(HEqBy k * le x y b, HMerge1 b ((:) * x xs) ((:) * y ys) ((:) * l ls) hhs, HMerge k le ls hhs srt) => HMerge k le ((:) * x xs) ((:) * y ys) ((:) * 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 :: (HCond t2 y x t, HCond t2 x y t1) => Proxy Bool t2 -> y -> x -> (t, t1)

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 k le ([] *) ([] *)

(HPartitionEq k * le a ((:) * b bs) bGeq bLt, HQSortBy k le bLt sortedLt, HQSortBy k le bGeq sortedGeq, (~) [*] (HAppendListR * sortedLt ((:) * a sortedGeq)) sorted, HAppendList sortedLt ((:) * a sortedGeq)) => HQSortBy k le ((:) * a ((:) * b bs)) sorted

HQSortBy k le ((:) * x ([] *)) ((:) * 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

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

class HSetBy (HNeq HLeFn) ps => HSet ps

Instances

HSetBy * (HNeq * HLeFn) ps => HSet ps

class HIsSet ps b | 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

class HEqByFn lt => HIsSetBy lt ps b | lt ps -> b

Instances

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

class HEqByFn le => HAscList le ps

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

Instances

HAscList0 k le ps ps => HAscList k le ps

class HEqByFn le => HAscList0 le ps ps0

Instances

HEqByFn k le => HAscList0 k le ([] *) ps0

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

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

class HEqByFn le => HAscList1 le b ps ps0

Instances

HAscList0 k le ys ys0 => HAscList1 k le True ys ys0

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

>>> import Data.HList.TypeEqO