Safe Haskell | None |
---|---|
Language | Haskell98 |
Maintaining a list of favorites of some partially ordered type. Only the best elements are kept.
To avoid name clashes, import this module qualified, as in
import Agda.Utils.Favorites (Favorites)
import qualified Agda.Utils.Favorites as Fav
- newtype Favorites a = Favorites {
- toList :: [a]
- data CompareResult a
- = Dominates {
- dominated :: [a]
- notDominated :: [a]
- | IsDominated {
- dominator :: a
- = Dominates {
- compareWithFavorites :: PartialOrd a => a -> Favorites a -> CompareResult a
- compareFavorites :: PartialOrd a => Favorites a -> Favorites a -> (Favorites a, Favorites a)
- unionCompared :: (Favorites a, Favorites a) -> Favorites a
- insertCompared :: a -> Favorites a -> CompareResult a -> Favorites a
- insert :: PartialOrd a => a -> Favorites a -> Favorites a
- union :: PartialOrd a => Favorites a -> Favorites a -> Favorites a
- fromList :: PartialOrd a => [a] -> Favorites a
- property_null_empty :: Bool
- property_not_null_singleton :: forall a. a -> Bool
- prop_compareWithFavorites :: ISet -> Favorites ISet -> Bool
- prop_fromList_after_toList :: Favorites ISet -> Bool
- prop_union_union2 :: Favorites ISet -> Favorites ISet -> Bool
- tests :: IO Bool
Documentation
A list of incomparable favorites.
Foldable Favorites Source | |
Singleton a (Favorites a) Source | |
Ord a => Eq (Favorites a) Source | Equality checking is a bit expensive, since we need to sort!
Maybe use a |
Show a => Show (Favorites a) Source | |
PartialOrd a => Monoid (Favorites a) Source | |
CoArbitrary a => CoArbitrary (Favorites a) Source | |
(PartialOrd a, Arbitrary a) => Arbitrary (Favorites a) Source | |
Null (Favorites a) Source |
data CompareResult a Source
Result of comparing a candidate with the current favorites.
Dominates | Great, you are dominating a possibly (empty list of favorites)
but there is also a rest that is not dominated.
If |
| |
IsDominated | Sorry, but you are dominated by that favorite. |
|
compareWithFavorites :: PartialOrd a => a -> Favorites a -> CompareResult a Source
Gosh, got some pretty a
here, compare with my current favorites!
Discard it if there is already one that is better or equal.
(Skewed conservatively: faithful to the old favorites.)
If there is no match for it, add it, and
dispose of all that are worse than a
.
We require a partial ordering. Less is better! (Maybe paradoxically.)
compareFavorites :: PartialOrd a => Favorites a -> Favorites a -> (Favorites a, Favorites a) Source
Compare a new set of favorites to an old one and discard the new favorites that are dominated by the old ones and vice verse. (Skewed conservatively: faithful to the old favorites.)
compareFavorites new old = (new', old')
unionCompared :: (Favorites a, Favorites a) -> Favorites a Source
insertCompared :: a -> Favorites a -> CompareResult a -> Favorites a Source
After comparing, do the actual insertion.
insert :: PartialOrd a => a -> Favorites a -> Favorites a Source
Compare, then insert accordingly.
insert a l = insertCompared a l (compareWithFavorites a l)
union :: PartialOrd a => Favorites a -> Favorites a -> Favorites a Source
Insert all the favorites from the first list into the second.
fromList :: PartialOrd a => [a] -> Favorites a Source
Construct favorites from elements of a partial order. The result depends on the order of the list if it contains equal elements, since earlier seen elements are favored over later seen equals. The first element of the list is seen first.
Properties
property_not_null_singleton :: forall a. a -> Bool Source
prop_union_union2 :: Favorites ISet -> Favorites ISet -> Bool Source
A second way to compute the union
is to use compareFavorites
.