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 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))

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

Defined in Fcf.Alg.Sort

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

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

Instances

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 ': ([] :: [a])) ++ r))

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

Defined in Fcf.Alg.Sort

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

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)