Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
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 {}
- emptyFocus :: Focus a
- vertexFocus :: (a -> Bool) -> a -> Focus a
- overlayFoci :: Focus a -> Focus a -> Focus a
- connectFoci :: Focus a -> Focus a -> Focus a
- data Hit
- foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a
General data structures
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 Source # | |
Functor List Source # | |
Applicative List Source # | |
Foldable List Source # | |
Defined in Algebra.Graph.Internal 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 # elem :: Eq a => a -> List a -> Bool # maximum :: Ord a => List a -> a # | |
IsList (List a) Source # | |
Eq a => Eq (List a) Source # | |
Ord a => Ord (List a) Source # | |
Show a => Show (List a) Source # | |
Semigroup (List a) Source # | |
Monoid (List a) Source # | |
type Item (List a) Source # | |
Defined in Algebra.Graph.Internal |
Data structures for graph traversal
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.
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.
An auxiliary data type for hasEdge
: when searching for an edge, we can hit
its Tail
, i.e. the source vertex, the whole Edge
, or Miss
it entirely.
foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a Source #
A safe version of foldr1