| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
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.
- data HLeFn
- data HDown a
- data HNeq le
- class HEqByFn le => HIsAscList le (xs :: [*]) (b :: Bool) | le xs -> b
- class (SameLength a b, HEqByFn le) => HSortBy le (a :: [*]) (b :: [*]) | le a -> b where
- 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
- class HEqByFn le => HMSortBy le (a :: [*]) (b :: [*]) | le a -> b where
- class HSort2 b x y ab | b x y -> ab where
- class HMerge le x y xy | le x y -> xy where
- 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 t x y b, HCond t y x a) => Proxy Bool t -> y -> x -> (a, b)
- class HQSortBy le (a :: [*]) (b :: [*]) | le a -> b where
- class HEqByFn lt => HSetBy lt (ps :: [*])
- class HSetBy (HNeq HLeFn) ps => HSet (ps :: [*])
- class HIsSet (ps :: [*]) (b :: Bool) | ps -> b
- class HEqByFn lt => HIsSetBy lt (ps :: [*]) (b :: Bool) | lt ps -> b
- class HEqByFn le => HAscList le (ps :: [*])
- class HEqByFn le => HAscList0 le (ps :: [*]) (ps0 :: [*])
- class HEqByFn le => HAscList1 le (b :: Bool) (ps :: [*]) (ps0 :: [*])
Documentation
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 Source # | |
| (~) Bool ((<=?) x y) b => HEqBy * Nat HLeFn x y b Source # | only in ghc >= 7.7 |
| (HEq Ordering (CmpSymbol x y) GT nb, (~) Bool (HNot nb) b) => HEqBy * Symbol HLeFn x y b Source # | only in ghc >= 7.7
|
| (~) Bool (HLe x y) b => HEqBy * HNat HLeFn x y b Source # | |
| HEqBy * k HLeFn x y b => HEqBy * * HLeFn (Proxy k x) (Proxy k y) b Source # | |
| HEqBy * k HLeFn x y b => HEqBy * * HLeFn (Label k x) (Label k y) b Source # | |
| HEqBy * k HLeFn x y b => HEqBy * * HLeFn (Tagged k x v) (Tagged k y w) b Source # | |
| (HEqBy * HNat HLeFn n m b, (~) * ns ns') => HEqBy * * HLeFn (Lbl n ns desc) (Lbl m ns' desc') b Source # | Data.HList.Label3 labels can only be compared if they belong to the same namespace. |
analogous to Down
The HEqBy instances for HNeq HLeFn gives <
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)
class (SameLength a b, HEqByFn le) => HSortBy le (a :: [*]) (b :: [*]) | le a -> b where Source #
quick sort with a special case for sorted lists
Minimal complete definition
Instances
| (SameLength * * a b, HIsAscList k le a ok, HSortBy1 Bool k ok le a b, HEqByFn k le) => HSortBy k le a 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 bhSort2 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)
Minimal complete definition
Instances
| HEqByFn k le => HMSortBy k le ([] *) ([] *) Source # | |
| (HSort2 Bool b x y ab, HEqBy k * le x y b) => HMSortBy k le ((:) * x ((:) * y ([] *))) ab Source # | |
| (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 Source # | |
| HEqByFn k le => HMSortBy k le ((:) * x ([] *)) ((:) * x ([] *)) Source # | |
class HMerge le x y xy | le x y -> xy where Source #
Minimal complete definition
Instances
| HMerge k le ([] *) ([] *) ([] *) Source # | |
| HMerge k le ([] *) ((:) * x xs) ((:) * x xs) Source # | |
| HMerge k le ((:) * x xs) ([] *) ((:) * x xs) Source # | |
| (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) 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 #
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 = xson 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.
Minimal complete definition
Instances
| HQSortBy k le ([] *) ([] *) Source # | |
| (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 Source # | |
| HQSortBy k le ((:) * x ([] *)) ((:) * 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
class HIsSet (ps :: [*]) (b :: Bool) | ps -> b Source #
>>>let xx = Proxy :: HIsSet [Label "x", Label "x"] b => Proxy b>>>:t xxxx :: Proxy 'False
>>>let xy = Proxy :: HIsSet [Label "x", Label "y"] b => Proxy b>>>:t xyxy :: Proxy 'True
class HEqByFn le => HAscList le (ps :: [*]) Source #
HAscList le xs confirms that xs is in ascending order,
and reports which element is duplicated otherwise.
>>>import Data.HList.TypeEqO