Algebra.Graph.Internal

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.

Data structures

data List a

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.

Instances

Monad List

Defined in Algebra.Graph.Internal

Methods

(>>=) :: List a -> (a -> List b) -> List b

(>>) :: List a -> List b -> List b

return :: a -> List a

Functor List

Defined in Algebra.Graph.Internal

Methods

fmap :: (a -> b) -> List a -> List b

(<$) :: a -> List b -> List a

Applicative List

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

Defined in Algebra.Graph.Internal

Methods

fold :: Monoid m => List m -> m

foldMap :: Monoid m => (a -> m) -> List a -> 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)

Defined in Algebra.Graph.Internal

Associated Types

type Item (List a)

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)

Defined in Algebra.Graph.Internal

Methods

(==) :: List a -> List a -> Bool

(/=) :: List a -> List a -> Bool

Ord a => Ord (List a)

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)

Defined in Algebra.Graph.Internal

Methods

showsPrec :: Int -> List a -> ShowS

show :: List a -> String

showList :: [List a] -> ShowS

Semigroup (List a)

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)

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)

Defined in Algebra.Graph.Internal

type Item (List a) = a

Graph traversal

data Focus a

The focus of a graph expression is a flattened representation 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

Focus on the empty graph.

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

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

Overlay two foci.

connectFoci :: Focus a -> Focus a -> Focus a

Connect two foci.

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

A safe version of foldr1.

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

An auxiliary function that tries to apply a function to a base case and a Maybe value and returns Just the result or Just the base case.

Utilities

cartesianProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c

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

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

Help GHC with type inference when direct use of coerce does not compile.

coerce10 :: (Coercible a b, Coercible f g) => (a -> f x) -> b -> g x

Help GHC with type inference when direct use of coerce does not compile.

coerce20 :: (Coercible a b, Coercible c d, Coercible f g) => (a -> c -> f x) -> b -> d -> g x

Help GHC with type inference when direct use of coerce does not compile.

coerce01 :: (Coercible a b, Coercible f g) => (f x -> a) -> g x -> b

Help GHC with type inference when direct use of coerce does not compile.

coerce11 :: (Coercible a b, Coercible c d, Coercible f g) => (a -> f x -> c) -> b -> g x -> d

Help GHC with type inference when direct use of coerce does not compile.

coerce21 :: (Coercible a b, Coercible c d, Coercible p q, Coercible f g) => (a -> c -> f x -> p) -> b -> d -> g x -> q

Help GHC with type inference when direct use of coerce does not compile.