{-# language Safe #-}
module Invert
(
function, bijection, injection, surjection,
linearSearchLazy, linearSearchStrict, binarySearch, hashTable,
enumBounded, genum,
Strategy,
strategyAll, strategyOneAndAll,
module Invert.Reexport
) where
import Invert.Reexport
import qualified Map
import Map (Map (Map))
import qualified Vector
import Data.Eq ( Eq, (==) )
import Data.Foldable ( foldl' )
import Data.Function ( (.) )
import Data.List.NonEmpty ( NonEmpty, nonEmpty )
import Data.Maybe ( Maybe (Just, Nothing), fromMaybe, listToMaybe )
import Data.Ord ( Ord )
import Data.Tuple ( uncurry )
import Prelude ( error )
import Prelude ( Enum, enumFromTo )
import Prelude ( Bounded, minBound, maxBound )
import qualified Data.List as List ( lookup, map )
import qualified Data.Maybe as List ( mapMaybe )
import qualified Generics.Deriving as GEnum ( genum )
function ::
Strategy a b
-> [a]
-> (a -> b)
-> (b -> [a])
bijection ::
Strategy a b
-> [a]
-> (a -> b)
-> (b -> a)
injection ::
Strategy a b
-> [a]
-> (a -> b)
-> (b -> Maybe a)
surjection ::
Strategy a b
-> [a]
-> (a -> b)
-> (b -> NonEmpty a)
function :: Strategy a b -> [a] -> (a -> b) -> b -> [a]
function (Strategy [(b, a)] -> b -> Maybe a
_ [(b, a)] -> b -> [a]
s) [a]
as a -> b
f = [(b, a)] -> b -> [a]
s ([a] -> (a -> b) -> [(b, a)]
forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
injection :: Strategy a b -> [a] -> (a -> b) -> b -> Maybe a
injection (Strategy [(b, a)] -> b -> Maybe a
s [(b, a)] -> b -> [a]
_) [a]
as a -> b
f = [(b, a)] -> b -> Maybe a
s ([a] -> (a -> b) -> [(b, a)]
forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
bijection :: Strategy a b -> [a] -> (a -> b) -> b -> a
bijection (Strategy [(b, a)] -> b -> Maybe a
s [(b, a)] -> b -> [a]
_) [a]
as a -> b
f = Maybe a -> a
forall a. Maybe a -> a
finagle (Maybe a -> a) -> (b -> Maybe a) -> b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(b, a)] -> b -> Maybe a
s ([a] -> (a -> b) -> [(b, a)]
forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
where finagle :: Maybe a -> a
finagle = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Not a bijection!")
surjection :: Strategy a b -> [a] -> (a -> b) -> b -> NonEmpty a
surjection (Strategy [(b, a)] -> b -> Maybe a
_ [(b, a)] -> b -> [a]
s) [a]
as a -> b
f = [a] -> NonEmpty a
forall a. [a] -> NonEmpty a
finagle ([a] -> NonEmpty a) -> (b -> [a]) -> b -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(b, a)] -> b -> [a]
s ([a] -> (a -> b) -> [(b, a)]
forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
where finagle :: [a] -> NonEmpty a
finagle = NonEmpty a -> Maybe (NonEmpty a) -> NonEmpty a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> NonEmpty a
forall a. HasCallStack => [Char] -> a
error [Char]
"Not a surjection!") (Maybe (NonEmpty a) -> NonEmpty a)
-> ([a] -> Maybe (NonEmpty a)) -> [a] -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty
data Strategy a b =
Strategy
([(b, a)] -> b -> Maybe a)
([(b, a)] -> b -> [a])
strategyAll ::
([(b, a)] -> b -> [a])
-> Strategy a b
strategyAll :: ([(b, a)] -> b -> [a]) -> Strategy a b
strategyAll [(b, a)] -> b -> [a]
all = ([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
forall b a.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
strategyOneAndAll [(b, a)] -> b -> Maybe a
one [(b, a)] -> b -> [a]
all
where
one :: [(b, a)] -> b -> Maybe a
one [(b, a)]
bas b
b = [a] -> Maybe a
forall a. [a] -> Maybe a
listToMaybe ([(b, a)] -> b -> [a]
all [(b, a)]
bas b
b)
strategyOneAndAll ::
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a])
-> Strategy a b
strategyOneAndAll :: ([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
strategyOneAndAll = ([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
forall a b.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
Strategy
inverseEntries :: [a] -> (a -> b) -> [(b, a)]
inverseEntries :: [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f = (a -> (b, a)) -> [a] -> [(b, a)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a -> (a -> b
f a
a, a
a)) [a]
as
mapStrategy :: Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy :: Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy Map Maybe b a
one Map [] b a
all = ([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
forall a b.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
Strategy (Map Maybe b a -> [(b, a)] -> b -> Maybe a
forall (f :: * -> *) a b. Map f a b -> [(a, b)] -> a -> f b
f Map Maybe b a
one) (Map [] b a -> [(b, a)] -> b -> [a]
forall (f :: * -> *) a b. Map f a b -> [(a, b)] -> a -> f b
f Map [] b a
all)
where
f :: Map f a b -> [(a, b)] -> a -> f b
f Map{ map
empty :: ()
empty :: map
Map.empty, a -> b -> map
singleton :: ()
singleton :: a -> b -> map
Map.singleton, map -> map -> map
union :: ()
union :: map -> map -> map
Map.union, map -> a -> f b
lookup :: ()
lookup :: map -> a -> f b
Map.lookup } =
map -> a -> f b
lookup (map -> a -> f b) -> ([(a, b)] -> map) -> [(a, b)] -> a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (map -> map -> map) -> map -> [map] -> map
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' map -> map -> map
union map
empty ([map] -> map) -> ([(a, b)] -> [map]) -> [(a, b)] -> map
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b) -> map) -> [(a, b)] -> [map]
forall a b. (a -> b) -> [a] -> [b]
List.map ((a -> b -> map) -> (a, b) -> map
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> b -> map
singleton)
linearSearchLazy :: Eq b => Strategy a b
linearSearchLazy :: Strategy a b
linearSearchLazy = ([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
forall a b.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
Strategy [(b, a)] -> b -> Maybe a
forall a b. Eq a => [(a, b)] -> a -> Maybe b
one [(b, a)] -> b -> [a]
forall b b. Eq b => [(b, b)] -> b -> [b]
all
where
one :: [(a, b)] -> a -> Maybe b
one [(a, b)]
bas a
b = a -> [(a, b)] -> Maybe b
forall a b. Eq a => a -> [(a, b)] -> Maybe b
List.lookup a
b [(a, b)]
bas
all :: [(b, b)] -> b -> [b]
all [(b, b)]
bas b
b = ((b, b) -> Maybe b) -> [(b, b)] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
List.mapMaybe (b -> (b, b) -> Maybe b
forall b a. Eq b => b -> (b, a) -> Maybe a
sndIfFstEq b
b) [(b, b)]
bas
linearSearchStrict :: Eq b => Strategy a b
linearSearchStrict :: Strategy a b
linearSearchStrict = ([(b, a)] -> b -> [a]) -> Strategy a b
forall b a. ([(b, a)] -> b -> [a]) -> Strategy a b
strategyAll [(b, a)] -> b -> [a]
forall b b. Eq b => [(b, b)] -> b -> [b]
f
where
f :: [(b, a)] -> b -> [a]
f [(b, a)]
bas b
b = Vector a -> [a]
forall a. Vector a -> [a]
Vector.toList (((b, a) -> Maybe a) -> Vector (b, a) -> Vector a
forall a b. (a -> Maybe b) -> Vector a -> Vector b
Vector.mapMaybe (b -> (b, a) -> Maybe a
forall b a. Eq b => b -> (b, a) -> Maybe a
sndIfFstEq b
b) Vector (b, a)
v)
where
v :: Vector (b, a)
v = [(b, a)] -> Vector (b, a)
forall a. [a] -> Vector a
Vector.fromList [(b, a)]
bas
sndIfFstEq :: Eq b => b -> (b, a) -> Maybe a
sndIfFstEq :: b -> (b, a) -> Maybe a
sndIfFstEq b
x (b
b, a
a) = if b
b b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
x then a -> Maybe a
forall a. a -> Maybe a
Just a
a else Maybe a
forall a. Maybe a
Nothing
binarySearch :: Ord b => Strategy a b
binarySearch :: Strategy a b
binarySearch = Map Maybe b a -> Map [] b a -> Strategy a b
forall b a. Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy Map Maybe b a
forall a b. Ord a => SingleMap a b
Map.ordSingleMap Map [] b a
forall a b. Ord a => MultiMap a b
Map.ordMultiMap
hashTable :: (Eq b, Hashable b) => Strategy a b
hashTable :: Strategy a b
hashTable = Map Maybe b a -> Map [] b a -> Strategy a b
forall b a. Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy Map Maybe b a
forall a b. (Eq a, Hashable a) => SingleMap a b
Map.hashSingleMap Map [] b a
forall a b. (Eq a, Hashable a) => MultiMap a b
Map.hashMultiMap
enumBounded :: (Enum a, Bounded a) => [a]
enumBounded :: [a]
enumBounded = a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo a
forall a. Bounded a => a
minBound a
forall a. Bounded a => a
maxBound
genum :: GEnum a => [a]
genum :: [a]
genum = [a]
forall a. GEnum a => [a]
GEnum.genum