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.

General data structures

newtype 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.

Constructors

List (Endo [a])

Instances

Monad List

Methods

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

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

return :: a -> List a

fail :: String -> List a

Functor List

Methods

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

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

Applicative List

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

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)

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)

Methods

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

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

Ord a => Ord (List a)

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)

Methods

showsPrec :: Int -> List a -> ShowS

show :: List a -> String

showList :: [List a] -> ShowS

Semigroup (List a)

Methods

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

sconcat :: NonEmpty (List a) -> List a

stimes :: Integral b => b -> List a -> List a

Monoid (List a)

Methods

mempty :: List a

mappend :: List a -> List a -> List a

mconcat :: [List a] -> List a

type Item (List a)

type Item (List a) = a

Data structures for graph traversal

data Focus a

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.

focus :: ToGraph g => (ToVertex g -> Bool) -> g -> Focus (ToVertex g)

Focus on a specified subgraph.

data Context a

The context of a subgraph comprises the input and output vertices outside the subgraph that are connected to the vertices inside the subgraph.

Constructors

Context

Fields

• inputs :: [a]
• outputs :: [a]

context :: ToGraph g => (ToVertex g -> Bool) -> g -> Maybe (Context (ToVertex g))

Extract the context from a graph Focus. Returns Nothing if the focus could not be obtained.