Copyright	(c) Andrey Mokhov 2016-2020
License	MIT (see the file LICENSE)
Maintainer	andrey.mokhov@gmail.com
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Algebra.Graph.Internal

Contents

Data structures
Graph traversal
Utilities

Description

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module defines various internal utilities and data structures used throughout the library, such as lists with fast concatenation. The API is unstable and unsafe, and is exposed only for documentation.

Synopsis

newtype List a = List (Endo [a])
data Focus a = Focus {
- ok :: Bool
- is :: List a
- os :: List a
- vs :: List a
}
emptyFocus :: Focus a
vertexFocus :: (a -> Bool) -> a -> Focus a
overlayFoci :: Focus a -> Focus a -> Focus a
connectFoci :: Focus a -> Focus a -> Focus a
foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a
maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a
setProduct :: Set a -> Set b -> Set (a, b)
setProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c
forEach :: Applicative f => Set a -> (a -> f b) -> f ()
forEachInt :: Applicative f => IntSet -> (Int -> f a) -> f ()
coerce00 :: Coercible f g => f x -> g x
coerce10 :: (Coercible a b, Coercible f g) => (a -> f x) -> b -> g x
coerce20 :: (Coercible a b, Coercible c d, Coercible f g) => (a -> c -> f x) -> b -> d -> g x
coerce01 :: (Coercible a b, Coercible f g) => (f x -> a) -> g x -> b
coerce11 :: (Coercible a b, Coercible c d, Coercible f g) => (a -> f x -> c) -> b -> g x -> d
coerce21 :: (Coercible a b, Coercible c d, Coercible p q, Coercible f g) => (a -> c -> f x -> p) -> b -> d -> g x -> q

Data structures

newtype List a Source #

An abstract list data type with O(1) time concatenation (the current implementation uses difference lists). Here a is the type of list elements. List a is a Monoid: mempty corresponds to the empty list and two lists can be concatenated with mappend (or operator <>). Singleton lists can be constructed using the function pure from the Applicative instance. List a is also an instance of IsList, therefore you can use list literals, e.g. [1,4] :: List Int is the same as pure 1 <> pure 4; note that this requires the OverloadedLists GHC extension. To extract plain Haskell lists you can use the toList function from the Foldable instance.

Constructors

List (Endo [a])

Instances

Monad List Source #
Instance details Defined in Algebra.Graph.Internal Methods (>>=) :: List a -> (a -> List b) -> List b # (>>) :: List a -> List b -> List b # return :: a -> List a # fail :: String -> List a #
Functor List Source #
Instance details Defined in Algebra.Graph.Internal Methods fmap :: (a -> b) -> List a -> List b # (<$) :: a -> List b -> List a #
Applicative List Source #
Instance details Defined in Algebra.Graph.Internal Methods pure :: a -> List a # (<>) :: List (a -> b) -> List a -> List b # liftA2 :: (a -> b -> c) -> List a -> List b -> List c # (>) :: List a -> List b -> List b # (<*) :: List a -> List b -> List a #
Foldable List Source #
Instance details Defined in Algebra.Graph.Internal Methods fold :: Monoid m => List m -> m # foldMap :: Monoid m => (a -> m) -> List a -> m # foldr :: (a -> b -> b) -> b -> List a -> b # foldr' :: (a -> b -> b) -> b -> List a -> b # foldl :: (b -> a -> b) -> b -> List a -> b # foldl' :: (b -> a -> b) -> b -> List a -> b # foldr1 :: (a -> a -> a) -> List a -> a # foldl1 :: (a -> a -> a) -> List a -> a # toList :: List a -> [a] # null :: List a -> Bool # length :: List a -> Int # elem :: Eq a => a -> List a -> Bool # maximum :: Ord a => List a -> a # minimum :: Ord a => List a -> a # sum :: Num a => List a -> a # product :: Num a => List a -> a #
IsList (List a) Source #
Instance details Defined in Algebra.Graph.Internal Associated Types type Item (List a) :: Type # Methods fromList :: [Item (List a)] -> List a # fromListN :: Int -> [Item (List a)] -> List a # toList :: List a -> [Item (List a)] #
Eq a => Eq (List a) Source #
Instance details Defined in Algebra.Graph.Internal Methods (==) :: List a -> List a -> Bool # (/=) :: List a -> List a -> Bool #
Ord a => Ord (List a) Source #
Instance details Defined in Algebra.Graph.Internal Methods compare :: List a -> List a -> Ordering # (<) :: List a -> List a -> Bool # (<=) :: List a -> List a -> Bool # (>) :: List a -> List a -> Bool # (>=) :: List a -> List a -> Bool # max :: List a -> List a -> List a # min :: List a -> List a -> List a #
Show a => Show (List a) Source #
Instance details Defined in Algebra.Graph.Internal Methods showsPrec :: Int -> List a -> ShowS # show :: List a -> String # showList :: [List a] -> ShowS #
Semigroup (List a) Source #
Instance details Defined in Algebra.Graph.Internal Methods (<>) :: List a -> List a -> List a # sconcat :: NonEmpty (List a) -> List a # stimes :: Integral b => b -> List a -> List a #
Monoid (List a) Source #
Instance details Defined in Algebra.Graph.Internal Methods mempty :: List a # mappend :: List a -> List a -> List a # mconcat :: [List a] -> List a #
type Item (List a) Source #
Instance details Defined in Algebra.Graph.Internal type Item (List a) = a

Graph traversal

data Focus a Source #

The focus of a graph expression is a flattened represenentation of the subgraph under focus, its context, as well as the list of all encountered vertices. See removeEdge for a use-case example.

Constructors

Focus	All vertices (leaves) of the graph expression.
Fields ok :: Bool True if focus on the specified subgraph is obtained. is :: List a Inputs into the focused subgraph. os :: List a Outputs out of the focused subgraph. vs :: List a

emptyFocus :: Focus a Source #

Focus on the empty graph.

vertexFocus :: (a -> Bool) -> a -> Focus a Source #

Focus on the graph with a single vertex, given a predicate indicating whether the vertex is of interest.

overlayFoci :: Focus a -> Focus a -> Focus a Source #

Overlay two foci.

connectFoci :: Focus a -> Focus a -> Focus a Source #

Connect two foci.

foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a Source #

A safe version of foldr1.

maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a Source #

Auxiliary function that try to apply a function to a base case and a Maybe value and return Just the result or Just the base case.

Utilities

setProduct :: Set a -> Set b -> Set (a, b) Source #

Compute the Cartesian product of two sets.

setProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c Source #

Compute the Cartesian product of two sets, applying a function to each resulting pair.

forEach :: Applicative f => Set a -> (a -> f b) -> f () Source #

Perform an applicative action for each member of a Set.

forEachInt :: Applicative f => IntSet -> (Int -> f a) -> f () Source #

Perform an applicative action for each member of an IntSet.

coerce00 :: Coercible f g => f x -> g x Source #