| 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 | 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 t2 y x t, HCond t2 x y t1) => Proxy Bool t2 -> y -> x -> (t, t1)
- 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 | ps -> b
- class HEqByFn lt => HIsSetBy lt ps b | lt ps -> b
- class HEqByFn le => HAscList le ps
- class HEqByFn le => HAscList0 le ps ps0
- class HEqByFn le => HAscList1 le b 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 | |
| (~) 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
|
| (~) 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. |
analogous to Down
The HEqBy instances for HNeq HLeFn gives <
class HEqByFn le => HIsAscList le xs b | le xs -> b Source
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 Source
quick sort with a special case for sorted lists
Instances
| (SameLength * * a b, HIsAscList k le a ok, HSortBy1 Bool k ok le a b) => HSortBy k le a b |
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)
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 ([] *)) |
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.
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 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 | 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 lt => HIsSetBy lt ps b | lt ps -> b Source
Instances
| (HSortBy k lt ps ps', HIsAscList k lt ps' b) => HIsSetBy k lt ps b |
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