{-# 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 :: forall a b. 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 (forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
injection :: forall a b. 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 (forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
bijection :: forall a b. 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 = forall {a}. Maybe a -> a
finagle forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(b, a)] -> b -> Maybe a
s (forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
where finagle :: Maybe a -> a
finagle = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => [Char] -> a
error [Char]
"Not a bijection!")
surjection :: forall a b. 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 = forall {a}. [a] -> NonEmpty a
finagle forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(b, a)] -> b -> [a]
s (forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f)
where finagle :: [a] -> NonEmpty a
finagle = forall a. a -> Maybe a -> a
fromMaybe (forall a. HasCallStack => [Char] -> a
error [Char]
"Not a surjection!") forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 :: forall b a. ([(b, a)] -> b -> [a]) -> Strategy a b
strategyAll [(b, a)] -> b -> [a]
all = 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 = 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 :: forall b a.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
strategyOneAndAll = forall a b.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
Strategy
inverseEntries :: [a] -> (a -> b) -> [(b, a)]
inverseEntries :: forall a b. [a] -> (a -> b) -> [(b, a)]
inverseEntries [a]
as a -> b
f = 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 :: forall b a. Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy Map Maybe b a
one Map [] b a
all = forall a b.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
Strategy (forall {f :: * -> *} {a} {b}. Map f a b -> [(a, b)] -> a -> f b
f Map Maybe b a
one) (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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' map -> map -> map
union map
empty forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
List.map (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> b -> map
singleton)
linearSearchLazy :: Eq b => Strategy a b
linearSearchLazy :: forall b a. Eq b => Strategy a b
linearSearchLazy = forall a b.
([(b, a)] -> b -> Maybe a)
-> ([(b, a)] -> b -> [a]) -> Strategy a b
Strategy forall {a} {b}. Eq a => [(a, b)] -> a -> Maybe b
one forall {b} {b}. Eq b => [(b, b)] -> b -> [b]
all
where
one :: [(a, b)] -> a -> Maybe b
one [(a, b)]
bas a
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 = forall a b. (a -> Maybe b) -> [a] -> [b]
List.mapMaybe (forall b a. Eq b => b -> (b, a) -> Maybe a
sndIfFstEq b
b) [(b, b)]
bas
linearSearchStrict :: Eq b => Strategy a b
linearSearchStrict :: forall b a. Eq b => Strategy a b
linearSearchStrict = forall b a. ([(b, a)] -> b -> [a]) -> Strategy a b
strategyAll forall {b} {b}. Eq b => [(b, b)] -> b -> [b]
f
where
f :: [(b, a)] -> b -> [a]
f [(b, a)]
bas b
b = forall a. Vector a -> [a]
Vector.toList (forall a b. (a -> Maybe b) -> Vector a -> Vector b
Vector.mapMaybe (forall b a. Eq b => b -> (b, a) -> Maybe a
sndIfFstEq b
b) Vector (b, a)
v)
where
v :: Vector (b, a)
v = forall a. [a] -> Vector a
Vector.fromList [(b, a)]
bas
sndIfFstEq :: Eq b => b -> (b, a) -> Maybe a
sndIfFstEq :: forall b a. Eq b => b -> (b, a) -> Maybe a
sndIfFstEq b
x (b
b, a
a) = if b
b forall a. Eq a => a -> a -> Bool
== b
x then forall a. a -> Maybe a
Just a
a else forall a. Maybe a
Nothing
binarySearch :: Ord b => Strategy a b
binarySearch :: forall b a. Ord b => Strategy a b
binarySearch = forall b a. Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy forall a b. Ord a => SingleMap a b
Map.ordSingleMap forall a b. Ord a => MultiMap a b
Map.ordMultiMap
hashTable :: (Eq b, Hashable b) => Strategy a b
hashTable :: forall b a. (Eq b, Hashable b) => Strategy a b
hashTable = forall b a. Map Maybe b a -> Map [] b a -> Strategy a b
mapStrategy forall a b. (Eq a, Hashable a) => SingleMap a b
Map.hashSingleMap forall a b. (Eq a, Hashable a) => MultiMap a b
Map.hashMultiMap
enumBounded :: (Enum a, Bounded a) => [a]
enumBounded :: forall a. (Enum a, Bounded a) => [a]
enumBounded = forall a. Enum a => a -> a -> [a]
enumFromTo forall a. Bounded a => a
minBound forall a. Bounded a => a
maxBound
genum :: GEnum a => [a]
genum :: forall a. GEnum a => [a]
genum = forall a. GEnum a => [a]
GEnum.genum