-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Sort small lists with sorting network. -- -- Functions that sort small (2~16 elements) lists or homogenous tuples. @package sorting-network @version 0.2.0.0 module Data.SortingNetwork.Types -- | A function that takes as argument number of elements and produces -- zero-based index pairs that we should compare to simulate a sorting -- network sequentially. Should return Nothing if a network of the -- input size is not supported. type MkPairs = Int -> Maybe [(Int, Int)] module Data.SortingNetwork.TH -- | gMkSortBy mkPairs n mkP mkE generates a function that sorts -- elements using sorting network. -- -- mkP :: [Pat] -> Pat and mkE :: [Exp] -> Exp -- deals with unpacking input value and packing final results -- respectively. This generalization allows us to deal with lists, -- tuples, and unboxed-tuples all at once. gMkSortBy :: MkPairs -> Int -> ([Pat] -> Pat) -> ([Exp] -> Exp) -> Q Exp -- | mkUnsafeSortListBy mkPairs n generates an expression of type -- (a -> a -> Ordering) -> [a] -> [a]. -- -- Note that resulting function is partial and requires input list to -- contain exactly n elements. mkUnsafeSortListBy :: MkPairs -> Int -> ExpQ -- | mkSortTupBy mkPairs n generates an expression of type (a -- -> a -> Ordering) -> (a, a, ...) -> (a, a, ...). -- -- Where the input and output tuple (a, a, ...) contains -- n elements. mkSortTupBy :: MkPairs -> Int -> ExpQ mkUnsafeSortListByFns :: MkPairs -> [Int] -> Q [Dec] mkSortTupByFns :: MkPairs -> [Int] -> Q [Dec] -- | Functions that sorts mutable vectors using sorting network. module Data.SortingNetwork.MutableVector -- | Sorts a mutable vector by applying compare-and-swap operations -- generated through MkPairs. -- -- Raises error if vector size cannot be handled by the sorting network. unsafeSortBy :: (PrimMonad m, MVector v e) => MkPairs -> (e -> e -> Ordering) -> v (PrimState m) e -> m () -- | Safe version of unsafeSortBy. -- -- This function either returns input vector reference upon successful -- sorting or Nothing if the vector size cannot be handled. maySortBy :: (PrimMonad m, MVector v e) => MkPairs -> (e -> e -> Ordering) -> v (PrimState m) e -> m (Maybe (v (PrimState m) e)) -- | Functions that generate sorting networks given a input size. module Data.SortingNetwork.Compares -- | Batcher's odd-even mergesort -- -- Adopted from Pseudocode section of -- https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort. oddEvenMerge :: MkPairs -- | Sorting networks that are optimal by size. -- -- Source from -- https://bertdobbelaere.github.io/sorting_networks.html. optimal :: MkPairs module Data.SortingNetwork.OptimalSize unsafeSortList16By :: forall a_aaIG. Ord a_aaIG => (a_aaIG -> a_aaIG -> Ordering) -> [a_aaIG] -> [a_aaIG] unsafeSortList15By :: forall a_aaGo. Ord a_aaGo => (a_aaGo -> a_aaGo -> Ordering) -> [a_aaGo] -> [a_aaGo] unsafeSortList14By :: forall a_aaEf. Ord a_aaEf => (a_aaEf -> a_aaEf -> Ordering) -> [a_aaEf] -> [a_aaEf] unsafeSortList13By :: forall a_aaCh. Ord a_aaCh => (a_aaCh -> a_aaCh -> Ordering) -> [a_aaCh] -> [a_aaCh] unsafeSortList12By :: forall a_aaAw. Ord a_aaAw => (a_aaAw -> a_aaAw -> Ordering) -> [a_aaAw] -> [a_aaAw] unsafeSortList11By :: forall a_aayY. Ord a_aayY => (a_aayY -> a_aayY -> Ordering) -> [a_aayY] -> [a_aayY] unsafeSortList10By :: forall a_aaxz. Ord a_aaxz => (a_aaxz -> a_aaxz -> Ordering) -> [a_aaxz] -> [a_aaxz] unsafeSortList9By :: forall a_aawn. Ord a_aawn => (a_aawn -> a_aawn -> Ordering) -> [a_aawn] -> [a_aawn] unsafeSortList8By :: forall a_aavk. Ord a_aavk => (a_aavk -> a_aavk -> Ordering) -> [a_aavk] -> [a_aavk] unsafeSortList7By :: forall a_aauu. Ord a_aauu => (a_aauu -> a_aauu -> Ordering) -> [a_aauu] -> [a_aauu] unsafeSortList6By :: forall a_aatL. Ord a_aatL => (a_aatL -> a_aatL -> Ordering) -> [a_aatL] -> [a_aatL] unsafeSortList5By :: forall a_aatb. Ord a_aatb => (a_aatb -> a_aatb -> Ordering) -> [a_aatb] -> [a_aatb] unsafeSortList4By :: forall a_aasI. Ord a_aasI => (a_aasI -> a_aasI -> Ordering) -> [a_aasI] -> [a_aasI] unsafeSortList3By :: forall a_aaso. Ord a_aaso => (a_aaso -> a_aaso -> Ordering) -> [a_aaso] -> [a_aaso] unsafeSortList2By :: forall a_aas9. Ord a_aas9 => (a_aas9 -> a_aas9 -> Ordering) -> [a_aas9] -> [a_aas9] sortTup16By :: (a_abd4 -> a_abd4 -> Ordering) -> (a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4) -> (a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4, a_abd4) sortTup15By :: (a_abaM -> a_abaM -> Ordering) -> (a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM) -> (a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM, a_abaM) sortTup14By :: (a_ab8D -> a_ab8D -> Ordering) -> (a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D) -> (a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D, a_ab8D) sortTup13By :: (a_ab6F -> a_ab6F -> Ordering) -> (a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F) -> (a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F, a_ab6F) sortTup12By :: (a_ab4U -> a_ab4U -> Ordering) -> (a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U) -> (a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U, a_ab4U) sortTup11By :: (a_ab3m -> a_ab3m -> Ordering) -> (a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m) -> (a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m, a_ab3m) sortTup10By :: (a_ab1X -> a_ab1X -> Ordering) -> (a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X) -> (a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X, a_ab1X) sortTup9By :: (a_ab0L -> a_ab0L -> Ordering) -> (a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L) -> (a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L, a_ab0L) sortTup8By :: (a_aaZI -> a_aaZI -> Ordering) -> (a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI) -> (a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI, a_aaZI) sortTup7By :: (a_aaYS -> a_aaYS -> Ordering) -> (a_aaYS, a_aaYS, a_aaYS, a_aaYS, a_aaYS, a_aaYS, a_aaYS) -> (a_aaYS, a_aaYS, a_aaYS, a_aaYS, a_aaYS, a_aaYS, a_aaYS) sortTup6By :: (a_aaY9 -> a_aaY9 -> Ordering) -> (a_aaY9, a_aaY9, a_aaY9, a_aaY9, a_aaY9, a_aaY9) -> (a_aaY9, a_aaY9, a_aaY9, a_aaY9, a_aaY9, a_aaY9) sortTup5By :: (a_aaXz -> a_aaXz -> Ordering) -> (a_aaXz, a_aaXz, a_aaXz, a_aaXz, a_aaXz) -> (a_aaXz, a_aaXz, a_aaXz, a_aaXz, a_aaXz) sortTup4By :: (a_aaX6 -> a_aaX6 -> Ordering) -> (a_aaX6, a_aaX6, a_aaX6, a_aaX6) -> (a_aaX6, a_aaX6, a_aaX6, a_aaX6) sortTup3By :: (a_aaWM -> a_aaWM -> Ordering) -> (a_aaWM, a_aaWM, a_aaWM) -> (a_aaWM, a_aaWM, a_aaWM) sortTup2By :: (a_aaWx -> a_aaWx -> Ordering) -> (a_aaWx, a_aaWx) -> (a_aaWx, a_aaWx) module Data.SortingNetwork module Data.SortingNetwork.OddEvenMerge unsafeSortList16By :: forall a_arm8. Ord a_arm8 => (a_arm8 -> a_arm8 -> Ordering) -> [a_arm8] -> [a_arm8] unsafeSortList15By :: forall a_arjK. Ord a_arjK => (a_arjK -> a_arjK -> Ordering) -> [a_arjK] -> [a_arjK] unsafeSortList14By :: forall a_arhv. Ord a_arhv => (a_arhv -> a_arhv -> Ordering) -> [a_arhv] -> [a_arhv] unsafeSortList13By :: forall a_arft. Ord a_arft => (a_arft -> a_arft -> Ordering) -> [a_arft] -> [a_arft] unsafeSortList12By :: forall a_ardC. Ord a_ardC => (a_ardC -> a_ardC -> Ordering) -> [a_ardC] -> [a_ardC] unsafeSortList11By :: forall a_arbY. Ord a_arbY => (a_arbY -> a_arbY -> Ordering) -> [a_arbY] -> [a_arbY] unsafeSortList10By :: forall a_arat. Ord a_arat => (a_arat -> a_arat -> Ordering) -> [a_arat] -> [a_arat] unsafeSortList9By :: forall a_ar9b. Ord a_ar9b => (a_ar9b -> a_ar9b -> Ordering) -> [a_ar9b] -> [a_ar9b] unsafeSortList8By :: forall a_ar82. Ord a_ar82 => (a_ar82 -> a_ar82 -> Ordering) -> [a_ar82] -> [a_ar82] unsafeSortList7By :: forall a_ar7c. Ord a_ar7c => (a_ar7c -> a_ar7c -> Ordering) -> [a_ar7c] -> [a_ar7c] unsafeSortList6By :: forall a_ar6t. Ord a_ar6t => (a_ar6t -> a_ar6t -> Ordering) -> [a_ar6t] -> [a_ar6t] unsafeSortList5By :: forall a_ar5T. Ord a_ar5T => (a_ar5T -> a_ar5T -> Ordering) -> [a_ar5T] -> [a_ar5T] unsafeSortList4By :: forall a_ar5q. Ord a_ar5q => (a_ar5q -> a_ar5q -> Ordering) -> [a_ar5q] -> [a_ar5q] unsafeSortList3By :: forall a_ar56. Ord a_ar56 => (a_ar56 -> a_ar56 -> Ordering) -> [a_ar56] -> [a_ar56] unsafeSortList2By :: forall a_ar4R. Ord a_ar4R => (a_ar4R -> a_ar4R -> Ordering) -> [a_ar4R] -> [a_ar4R] sortTup16By :: (a_arRg -> a_arRg -> Ordering) -> (a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg) -> (a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg, a_arRg) sortTup15By :: (a_arOS -> a_arOS -> Ordering) -> (a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS) -> (a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS, a_arOS) sortTup14By :: (a_arMD -> a_arMD -> Ordering) -> (a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD) -> (a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD, a_arMD) sortTup13By :: (a_arKB -> a_arKB -> Ordering) -> (a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB) -> (a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB, a_arKB) sortTup12By :: (a_arIK -> a_arIK -> Ordering) -> (a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK) -> (a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK, a_arIK) sortTup11By :: (a_arH6 -> a_arH6 -> Ordering) -> (a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6) -> (a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6, a_arH6) sortTup10By :: (a_arFB -> a_arFB -> Ordering) -> (a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB) -> (a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB, a_arFB) sortTup9By :: (a_arEj -> a_arEj -> Ordering) -> (a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj) -> (a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj, a_arEj) sortTup8By :: (a_arDa -> a_arDa -> Ordering) -> (a_arDa, a_arDa, a_arDa, a_arDa, a_arDa, a_arDa, a_arDa, a_arDa) -> (a_arDa, a_arDa, a_arDa, a_arDa, a_arDa, a_arDa, a_arDa, a_arDa) sortTup7By :: (a_arCk -> a_arCk -> Ordering) -> (a_arCk, a_arCk, a_arCk, a_arCk, a_arCk, a_arCk, a_arCk) -> (a_arCk, a_arCk, a_arCk, a_arCk, a_arCk, a_arCk, a_arCk) sortTup6By :: (a_arBB -> a_arBB -> Ordering) -> (a_arBB, a_arBB, a_arBB, a_arBB, a_arBB, a_arBB) -> (a_arBB, a_arBB, a_arBB, a_arBB, a_arBB, a_arBB) sortTup5By :: (a_arB1 -> a_arB1 -> Ordering) -> (a_arB1, a_arB1, a_arB1, a_arB1, a_arB1) -> (a_arB1, a_arB1, a_arB1, a_arB1, a_arB1) sortTup4By :: (a_arAy -> a_arAy -> Ordering) -> (a_arAy, a_arAy, a_arAy, a_arAy) -> (a_arAy, a_arAy, a_arAy, a_arAy) sortTup3By :: (a_arAe -> a_arAe -> Ordering) -> (a_arAe, a_arAe, a_arAe) -> (a_arAe, a_arAe, a_arAe) sortTup2By :: (a_arzZ -> a_arzZ -> Ordering) -> (a_arzZ, a_arzZ) -> (a_arzZ, a_arzZ)