-----------------------------------------------------------------------------
-- |
-- Module     : Algebra.Graph.Internal
-- Copyright  : (c) Andrey Mokhov 2016-2022
-- License    : MIT (see the file LICENSE)
-- Maintainer : andrey.mokhov@gmail.com
-- Stability  : experimental
--
-- __Alga__ is a library for algebraic construction and manipulation of graphs
-- in Haskell. See <https://github.com/snowleopard/alga-paper 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.
-----------------------------------------------------------------------------
module Algebra.Graph.Internal (
    -- * Data structures
    List,

    -- * Graph traversal
    Focus (..), emptyFocus, vertexFocus, overlayFoci, connectFoci, foldr1Safe,
    maybeF,

    -- * Utilities
    cartesianProductWith, coerce00, coerce10, coerce20, coerce01, coerce11,
    coerce21
    ) where

import Data.Coerce
import Data.Foldable
import Data.IntSet (IntSet)
import Data.Semigroup (Endo (..))
import Data.Set (Set)

import qualified Data.IntSet as IntSet
import qualified Data.Set    as Set
import qualified GHC.Exts    as Exts

-- | 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 'Data.Semigroup.<>'). 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@
-- 'Data.Semigroup.<>' '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.
newtype List a = List (Endo [a]) deriving (Semigroup (List a)
List a
Semigroup (List a)
-> List a
-> (List a -> List a -> List a)
-> ([List a] -> List a)
-> Monoid (List a)
[List a] -> List a
List a -> List a -> List a
forall a. Semigroup (List a)
forall a. List a
forall a.
Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall a. [List a] -> List a
forall a. List a -> List a -> List a
mconcat :: [List a] -> List a
$cmconcat :: forall a. [List a] -> List a
mappend :: List a -> List a -> List a
$cmappend :: forall a. List a -> List a -> List a
mempty :: List a
$cmempty :: forall a. List a
$cp1Monoid :: forall a. Semigroup (List a)
Monoid, b -> List a -> List a
NonEmpty (List a) -> List a
List a -> List a -> List a
(List a -> List a -> List a)
-> (NonEmpty (List a) -> List a)
-> (forall b. Integral b => b -> List a -> List a)
-> Semigroup (List a)
forall b. Integral b => b -> List a -> List a
forall a. NonEmpty (List a) -> List a
forall a. List a -> List a -> List a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall a b. Integral b => b -> List a -> List a
stimes :: b -> List a -> List a
$cstimes :: forall a b. Integral b => b -> List a -> List a
sconcat :: NonEmpty (List a) -> List a
$csconcat :: forall a. NonEmpty (List a) -> List a
<> :: List a -> List a -> List a
$c<> :: forall a. List a -> List a -> List a
Semigroup)

instance Show a => Show (List a) where
    show :: List a -> String
show = [a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (List a -> [a]) -> List a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

instance Eq a => Eq (List a) where
    List a
x == :: List a -> List a -> Bool
== List a
y = List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List a
x [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List a
y

instance Ord a => Ord (List a) where
    compare :: List a -> List a -> Ordering
compare List a
x List a
y = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List a
x) (List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List a
y)

-- TODO: Add rewrite rules? fromList . toList == toList . fromList == id
instance Exts.IsList (List a) where
    type Item (List a) = a
    fromList :: [Item (List a)] -> List a
fromList        = Endo [a] -> List a
forall a. Endo [a] -> List a
List (Endo [a] -> List a) -> ([a] -> Endo [a]) -> [a] -> List a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [a]) -> Endo [a]
forall a. (a -> a) -> Endo a
Endo (([a] -> [a]) -> Endo [a])
-> ([a] -> [a] -> [a]) -> [a] -> Endo [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
(<>)
    toList :: List a -> [Item (List a)]
toList (List Endo [a]
x) = Endo [a] -> [a] -> [a]
forall a. Endo a -> a -> a
appEndo Endo [a]
x []

instance Foldable List where
    foldMap :: (a -> m) -> List a -> m
foldMap a -> m
f = (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f ([a] -> m) -> (List a -> [a]) -> List a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List a -> [a]
forall l. IsList l => l -> [Item l]
Exts.toList
    toList :: List a -> [a]
toList    = List a -> [a]
forall l. IsList l => l -> [Item l]
Exts.toList

instance Functor List where
    fmap :: (a -> b) -> List a -> List b
fmap a -> b
f = [b] -> List b
forall l. IsList l => [Item l] -> l
Exts.fromList ([b] -> List b) -> (List a -> [b]) -> List a -> List b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map a -> b
f ([a] -> [b]) -> (List a -> [a]) -> List a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

instance Applicative List where
    pure :: a -> List a
pure    = Endo [a] -> List a
forall a. Endo [a] -> List a
List (Endo [a] -> List a) -> (a -> Endo [a]) -> a -> List a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [a]) -> Endo [a]
forall a. (a -> a) -> Endo a
Endo (([a] -> [a]) -> Endo [a]) -> (a -> [a] -> [a]) -> a -> Endo [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (:)
    List (a -> b)
f <*> :: List (a -> b) -> List a -> List b
<*> List a
x = [Item (List b)] -> List b
forall l. IsList l => [Item l] -> l
Exts.fromList (List (a -> b) -> [a -> b]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List (a -> b)
f [a -> b] -> [a] -> [b]
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List a
x)

instance Monad List where
    return :: a -> List a
return  = a -> List a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    List a
x >>= :: List a -> (a -> List b) -> List b
>>= a -> List b
f = [Item (List b)] -> List b
forall l. IsList l => [Item l] -> l
Exts.fromList (List a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList List a
x [a] -> (a -> [b]) -> [b]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= List b -> [b]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (List b -> [b]) -> (a -> List b) -> a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> List b
f)

-- | 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 'Algebra.Graph.removeEdge' for a use-case example.
data Focus a = Focus
    { Focus a -> Bool
ok :: Bool     -- ^ True if focus on the specified subgraph is obtained.
    , Focus a -> List a
is :: List a   -- ^ Inputs into the focused subgraph.
    , Focus a -> List a
os :: List a   -- ^ Outputs out of the focused subgraph.
    , Focus a -> List a
vs :: List a } -- ^ All vertices (leaves) of the graph expression.

-- | Focus on the empty graph.
emptyFocus :: Focus a
emptyFocus :: Focus a
emptyFocus = Bool -> List a -> List a -> List a -> Focus a
forall a. Bool -> List a -> List a -> List a -> Focus a
Focus Bool
False List a
forall a. Monoid a => a
mempty List a
forall a. Monoid a => a
mempty List a
forall a. Monoid a => a
mempty

-- | Focus on the graph with a single vertex, given a predicate indicating
-- whether the vertex is of interest.
vertexFocus :: (a -> Bool) -> a -> Focus a
vertexFocus :: (a -> Bool) -> a -> Focus a
vertexFocus a -> Bool
f a
x = Bool -> List a -> List a -> List a -> Focus a
forall a. Bool -> List a -> List a -> List a -> Focus a
Focus (a -> Bool
f a
x) List a
forall a. Monoid a => a
mempty List a
forall a. Monoid a => a
mempty (a -> List a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x)

-- | Overlay two foci.
overlayFoci :: Focus a -> Focus a -> Focus a
overlayFoci :: Focus a -> Focus a -> Focus a
overlayFoci Focus a
x Focus a
y = Bool -> List a -> List a -> List a -> Focus a
forall a. Bool -> List a -> List a -> List a -> Focus a
Focus (Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
x Bool -> Bool -> Bool
|| Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
y) (Focus a -> List a
forall a. Focus a -> List a
is Focus a
x List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> Focus a -> List a
forall a. Focus a -> List a
is Focus a
y) (Focus a -> List a
forall a. Focus a -> List a
os Focus a
x List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> Focus a -> List a
forall a. Focus a -> List a
os Focus a
y) (Focus a -> List a
forall a. Focus a -> List a
vs Focus a
x List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> Focus a -> List a
forall a. Focus a -> List a
vs Focus a
y)

-- | Connect two foci.
connectFoci :: Focus a -> Focus a -> Focus a
connectFoci :: Focus a -> Focus a -> Focus a
connectFoci Focus a
x Focus a
y = Bool -> List a -> List a -> List a -> Focus a
forall a. Bool -> List a -> List a -> List a -> Focus a
Focus (Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
x Bool -> Bool -> Bool
|| Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
y) (List a
xs List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> Focus a -> List a
forall a. Focus a -> List a
is Focus a
y) (Focus a -> List a
forall a. Focus a -> List a
os Focus a
x List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> List a
ys) (Focus a -> List a
forall a. Focus a -> List a
vs Focus a
x List a -> List a -> List a
forall a. Semigroup a => a -> a -> a
<> Focus a -> List a
forall a. Focus a -> List a
vs Focus a
y)
  where
    xs :: List a
xs = if Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
y then Focus a -> List a
forall a. Focus a -> List a
vs Focus a
x else Focus a -> List a
forall a. Focus a -> List a
is Focus a
x
    ys :: List a
ys = if Focus a -> Bool
forall a. Focus a -> Bool
ok Focus a
x then Focus a -> List a
forall a. Focus a -> List a
vs Focus a
y else Focus a -> List a
forall a. Focus a -> List a
os Focus a
y

-- | A safe version of 'foldr1'.
foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a
foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a
foldr1Safe a -> a -> a
f = (a -> Maybe a -> Maybe a) -> Maybe a -> [a] -> Maybe a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((a -> a -> a) -> a -> Maybe a -> Maybe a
forall a b. (a -> b -> a) -> a -> Maybe b -> Maybe a
maybeF a -> a -> a
f) Maybe a
forall a. Maybe a
Nothing
{-# INLINE foldr1Safe #-}

-- | 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.
maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a
maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a
maybeF a -> b -> a
f a
x = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> (Maybe b -> a) -> Maybe b -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (b -> a) -> Maybe b -> a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe a
x (a -> b -> a
f a
x)
{-# INLINE maybeF #-}

-- TODO: Can we implement this faster via 'Set.cartesianProduct'?
-- | Compute the Cartesian product of two sets, applying a function to each
-- resulting pair.
cartesianProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c
cartesianProductWith :: (a -> b -> c) -> Set a -> Set b -> Set c
cartesianProductWith a -> b -> c
f Set a
x Set b
y =
    [c] -> Set c
forall a. Ord a => [a] -> Set a
Set.fromList [ a -> b -> c
f a
a b
b | a
a <- Set a -> [a]
forall a. Set a -> [a]
Set.toAscList Set a
x, b
b <- Set b -> [b]
forall a. Set a -> [a]
Set.toAscList Set b
y ]

-- TODO: Get rid of this boilerplate.

-- | Help GHC with type inference when direct use of 'coerce' does not compile.
coerce00 :: Coercible f g => f x -> g x
coerce00 :: f x -> g x
coerce00 = f x -> g x
coerce

-- | 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)
coerce10 :: (a -> f x) -> b -> g x
coerce10 = (a -> f x) -> b -> g x
coerce

-- | 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)
coerce20 :: (a -> c -> f x) -> b -> d -> g x
coerce20 = (a -> c -> f x) -> b -> d -> g x
coerce

-- | 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)
coerce01 :: (f x -> a) -> g x -> b
coerce01 = (f x -> a) -> g x -> b
coerce

-- | 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)
coerce11 :: (a -> f x -> c) -> b -> g x -> d
coerce11 = (a -> f x -> c) -> b -> g x -> d
coerce

-- | 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)
coerce21 :: (a -> c -> f x -> p) -> b -> d -> g x -> q
coerce21 = (a -> c -> f x -> p) -> b -> d -> g x -> q
coerce