{-# LANGUAGE Safe #-}
module Invert
(
function,
bijection,
injection,
surjection,
linearSearchLazy,
linearSearchStrict,
binarySearch,
hashTable,
enumBounded,
genum,
Strategy,
strategyAll,
strategyOneAndAll,
module Invert.Reexport,
)
where
import Data.Eq (Eq, (==))
import Data.Foldable (foldl')
import Data.Function ((.))
import Data.List qualified as List (lookup, map)
import Data.List.NonEmpty (NonEmpty, nonEmpty)
import Data.Maybe (Maybe (Just, Nothing), fromMaybe, listToMaybe)
import Data.Maybe qualified as List (mapMaybe)
import Data.Ord (Ord)
import Data.Tuple (uncurry)
import Generics.Deriving qualified as GEnum (genum)
import Invert.Reexport
import Map (Map (Map))
import Map qualified
import Vector qualified
import Prelude (Bounded, Enum, enumFromTo, error, maxBound, minBound)
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