Fcf.Alg.Sort

Fcf.Alg.Sort

Documentation

>>> import qualified Fcf.Data.Nat as N ( type (<) )
>>> import qualified Fcf.Alg.Symbol as S ( type (<) )

data ListCmpFnd :: [Ordering] -> Exp Ordering

Instances

type Eval (ListCmpFnd (a ': as) :: Ordering -> Type)

Defined in Fcf.Alg.Sort

type Eval (ListCmpFnd (a ': as) :: Ordering -> Type) = Eval (If (Eval (TyEq a 'EQ)) (ListCmpFnd as) (Pure a))

type Eval (ListCmpFnd ('[] :: [Ordering]))

Defined in Fcf.Alg.Sort

type Eval (ListCmpFnd ('[] :: [Ordering])) = 'EQ

data ListCmp :: (a -> a -> Exp Ordering) -> [a] -> [a] -> Exp Ordering

Compare lists with the given comparison for the elements.

Instances

type Eval (ListCmp f as bs :: Ordering -> Type)

Defined in Fcf.Alg.Sort

type Eval (ListCmp f as bs :: Ordering -> Type) = Eval (ListCmpFnd =<< ZipWith f as bs)

data ListOrd :: (a -> a -> Exp Ordering) -> [a] -> [a] -> Exp Bool

Give true if the first list is before the second, given the comparison function for the elements.

Instances

type Eval (ListOrd f as bs :: Bool -> Type)

Defined in Fcf.Alg.Sort

type Eval (ListOrd f as bs :: Bool -> Type) = Eval (If (Eval (TyEq 'LT (Eval (ListCmp f as bs)))) (Pure 'True) (Pure 'False))

data NatOrd :: Nat -> Nat -> Exp Ordering

Comparison for the Nats.

TODO: Would this fit to Fcf.Data.Nat on first-class-families?

Instances

type Eval (NatOrd a b :: Ordering -> Type)

Defined in Fcf.Alg.Sort

type Eval (NatOrd a b :: Ordering -> Type) = CmpNat a b

data SymbolListOrd :: [Symbol] -> [Symbol] -> Exp Bool

Comparison for Symbol lists.

Useful when sorting with Qsort.

Instances

type Eval (SymbolListOrd as bs :: Bool -> Type)

Defined in Fcf.Alg.Sort

type Eval (SymbolListOrd as bs :: Bool -> Type) = Eval (ListOrd SymbolOrd as bs)

data NatListOrd :: [Nat] -> [Nat] -> Exp Bool

Comparison for Nat lists.

Useful when sorting with Qsort.

Instances

type Eval (NatListOrd as bs :: Bool -> Type)

Defined in Fcf.Alg.Sort

type Eval (NatListOrd as bs :: Bool -> Type) = Eval (ListOrd NatOrd as bs)

data PartHlp :: (a -> a -> Exp Bool) -> CoAlgebra (BTreeF a) [a]

Instances

type Eval (PartHlp _1 ('[] :: [a]) :: BTreeF a [a] -> Type)

Defined in Fcf.Alg.Sort

type Eval (PartHlp _1 ('[] :: [a]) :: BTreeF a [a] -> Type) = 'BEmptyF :: BTreeF a [a]

type Eval (PartHlp smaller (h ': t) :: BTreeF a [a] -> Type)

Defined in Fcf.Alg.Sort

type Eval (PartHlp smaller (h ': t) :: BTreeF a [a] -> Type) = 'BNodeF h (Eval (Filter (smaller h) t)) (Eval (Filter (Not <=< smaller h) t))

data Inord :: Algebra (BTreeF a) [a]

Instances

type Eval (Inord ('BEmptyF :: BTreeF a [a]) :: [a] -> Type)

Defined in Fcf.Alg.Sort

type Eval (Inord ('BEmptyF :: BTreeF a [a]) :: [a] -> Type) = '[] :: [a]

type Eval (Inord ('BNodeF v l r) :: [a] -> Type)

Defined in Fcf.Alg.Sort

type Eval (Inord ('BNodeF v l r) :: [a] -> Type) = Eval (l ++ Eval ('[v] ++ r))

data Qsort :: (a -> a -> Exp Bool) -> [a] -> Exp [a]

Qsort - give the comparison function a -> a -> Exp Bool comparing your list elements and then Qsort will order the list.

Example

>>> :kind! Eval (Qsort (N.<) '[5,3,1,9,4,6,3])
Eval (Qsort (N.<) '[5,3,1,9,4,6,3]) :: [Nat]
= '[1, 3, 3, 4, 5, 6, 9]

>>> :kind! Eval (Qsort (S.<) '[ "bb", "e", "a", "e", "d" ])
Eval (Qsort (S.<) '[ "bb", "e", "a", "e", "d" ]) :: [Symbol]
= '["a", "bb", "d", "e", "e"]

Instances

type Eval (Qsort cmp lst :: [a] -> Type)

Defined in Fcf.Alg.Sort

type Eval (Qsort cmp lst :: [a] -> Type) = Eval (Hylo (Inord :: BTreeF a [a] -> [a] -> Type) (PartCmp cmp) lst)

data PartCmp :: (a -> a -> Exp Bool) -> CoAlgebra (BTreeF a) [a]

Instances

type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type)

Defined in Fcf.Alg.Sort

type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type) = Eval (PartHlp (Flip cmp) coalg)