Copyright	(c) Ross Paterson 2021
License	BSD-style (see the file LICENSE)
Maintainer	[email protected]
Stability	provisional
Portability	portable
Safe Haskell	None
Language	Haskell2010

Data.YAP.FiniteSet

Contents

Finite sets
Construction
Queries
Finite formal languages

Description

An example instance of the algebraic classes: the semiring of finite sets.

Synopsis

data FiniteSet a
singleton :: a -> FiniteSet a
fromList :: Ord a => [a] -> FiniteSet a
elems :: FiniteSet a -> [a]
type FiniteLanguage a = FiniteSet [a]

Finite sets

data FiniteSet a Source #

The semiring of sets over a monoid, with union as addition and the monoid operation lifted to multiplication. This is equivalent to FiniteMap with a Boolean semiring as codomain.

Instances

Instances details

Show a => Show (FiniteSet a) Source #
Instance details Defined in Data.YAP.FiniteSet Methods showsPrec :: Int -> FiniteSet a -> ShowS # show :: FiniteSet a -> String # showList :: [FiniteSet a] -> ShowS #
Eq a => Eq (FiniteSet a) Source #
Instance details Defined in Data.YAP.FiniteSet Methods (==) :: FiniteSet a -> FiniteSet a -> Bool # (/=) :: FiniteSet a -> FiniteSet a -> Bool #
Ord a => Ord (FiniteSet a) Source #
Instance details Defined in Data.YAP.FiniteSet Methods compare :: FiniteSet a -> FiniteSet a -> Ordering # (<) :: FiniteSet a -> FiniteSet a -> Bool # (<=) :: FiniteSet a -> FiniteSet a -> Bool # (>) :: FiniteSet a -> FiniteSet a -> Bool # (>=) :: FiniteSet a -> FiniteSet a -> Bool # max :: FiniteSet a -> FiniteSet a -> FiniteSet a # min :: FiniteSet a -> FiniteSet a -> FiniteSet a #
Ord a => AdditiveMonoid (FiniteSet a) Source #	`(+)` is union
Instance details Defined in Data.YAP.FiniteSet Methods (+) :: FiniteSet a -> FiniteSet a -> FiniteSet a # zero :: FiniteSet a # atimes :: ToInteger b => b -> FiniteSet a -> FiniteSet a #
(Ord a, Monoid a) => Semiring (FiniteSet a) Source #	`(*)` is elementwise `<>`
Instance details Defined in Data.YAP.FiniteSet Methods (*) :: FiniteSet a -> FiniteSet a -> FiniteSet a # one :: FiniteSet a # fromNatural :: Natural -> FiniteSet a # rescale :: FiniteSet a -> FiniteSet a -> (FiniteSet a, FiniteSet a, FiniteSet a -> FiniteSet a) #

Construction

singleton :: a -> FiniteSet a Source #

A set containing a single element.

fromList :: Ord a => [a] -> FiniteSet a Source #

A set formed from a list by removing duplicates.

Queries

elems :: FiniteSet a -> [a] Source #

The elements of the set.

Finite formal languages

type FiniteLanguage a = FiniteSet [a] Source #

Finite formal languages, with (+) as union and (*) as concatenation.

Examples

Expand

>>> zero :: FiniteSet String
fromList []
>>> one :: FiniteSet String
fromList [""]
>>> (singleton "a" + singleton "ab") * (singleton "c" + singleton "bc")
fromList ["abbc","abc","ac"]
>>> (singleton "a" + singleton "ab")^3
fromList ["aaa","aaab","aaba","aabab","abaa","abaab","ababa","ababab"]