Problem
I find sometimes it is useful to capture the notion of invertible functions.
The idea is that if two functions f :: a -> b and g :: b -> a are the inverse function of each other, and if there is another function h :: b -> b, then h can also work on values of type a.
Moreover, if there f' and g' are another pair of functions that are the inverse function of each other, (f,g) and (f',g') can actually be composed to (f' . f, g . g') and the invertibility still holds.
The following is my attempt to implement this in Haskell, and I’m wondering if an existing library can do the same thing (or even more general thing) for me.
Also advice and comments about my code are appreciated.
Implementation
First I use records to store two functions:
data Invertible a b = Invertible
{ into :: a -> b
, back :: b -> a
}
into means “convert a into b” while back means “convert b back to a”.
And then few helper functions:
selfInv :: (a -> a) -> Invertible a a
selfInv f = Invertible f f
flipInv :: Invertible a b -> Invertible b a
flipInv (Invertible f g) = Invertible g f
borrow :: Invertible a b -> (b -> b) -> a -> a
borrow (Invertible fIn fOut) g = fOut . g . fIn
liftInv :: (Functor f) => Invertible a b -> Invertible (f a) (f b)
liftInv (Invertible a b) = Invertible (fmap a) (fmap b)
In the above code borrow will use the pair of functions to make its last argument g
available to values of type a. And changing borrow f to borrow (flipInv f) will make g available to values of type b. Therefore borrow captures my initial idea of making a function of type b -> b available for values of a if a and b can be converted to each other.
In addition, Invertible forms a monoid-like structure, I use rappend and rempty to suggest a similiarity between it and Monoid:
rempty :: Invertible a a
rempty = selfInv id
rappend :: Invertible a b
-> Invertible b c
-> Invertible a c
(Invertible f1 g1) `rappend` (Invertible f2 g2) =
Invertible (f2 . f1) (g1 . g2)
Examples
Here I have two examples to demonstrate that Invertible might be useful.
Data Encryption
It is natural that Invertible can be used under scenario of symmetric encryption. Invertible (encrypt key) (decrypt key) might be one instance if:
encrypt :: Key -> PlainText -> CipherText
decrypt :: Key -> CipherText -> PlainText
To simplify a little, I make an example of Caesar cipher and assume that plain text contains only uppercase letters:
-- constructor should be invisible from outside
newtype OnlyUpper a = OnlyUpper
{ getOU :: [a]
} deriving (Eq, Ord, Show, Functor)
ouAsList :: Invertible (OnlyUpper a) [a]
ouAsList = Invertible getOU OnlyUpper
onlyUpper :: String -> OnlyUpper Char
onlyUpper = OnlyUpper . filter isAsciiUpper
upperAsOrd :: Invertible Char Int
upperAsOrd = Invertible ord' chr'
where
ord' x = ord x - ord 'A'
chr' x = chr (x + ord 'A')
And Caesar Cipher is basically doing some modular arithmetic:
modShift :: Int -> Int -> Invertible Int Int
modShift base offset = Invertible f g
where
f x = (x + offset) `mod` base
g y = (y + (base - offset)) `mod` base
caesarShift :: Invertible Int Int
caesarShift = modShift 26 4
caesarCipher :: Invertible (OnlyUpper Char) (OnlyUpper Char)
caesarCipher = liftInv (upperAsOrd
-- Char <-> Int
`rappend` caesarShift
-- Int <-> Int
`rappend` flipInv upperAsOrd)
-- Int <-> Char
One way to use Invertible is just using its into and back as encrypt and decrypt, and Invertible also gives you the power of manipulating encrypyed data as if it was plain text:
exampleCaesar :: IO ()
exampleCaesar = do
let encF = into caesarCipher
decF = back caesarCipher
encrypted = encF (onlyUpper "THEQUICKBROWNFOX")
decrypted = decF encrypted
encrypted' = borrow (flipInv caesarCipher
`rappend` ouAsList) (++ "JUMPSOVERTHELAZYDOG") encrypted
decrypted' = decF encrypted'
print encrypted
-- OnlyUpper {getOU = "XLIUYMGOFVSARJSB"}
print decrypted
-- OnlyUpper {getOU = "THEQUICKBROWNFOX"}
print encrypted'
-- OnlyUpper {getOU = "XLIUYMGOFVSARJSBNYQTWSZIVXLIPEDCHSK"}
print decrypted'
-- OnlyUpper {getOU = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG"}
Matrix manipulation
Sometimes it’s convenient to write some code that manipulates matrices using Invertible.
Say there is a list of type [Int] in which 0 stands for an empty cell, and we want every non-zero element move to their leftmost possible position while preserving the order:
compactLeft :: [Int] -> [Int]
compactLeft xs = nonZeros ++ replicate (((-) `on` length) xs nonZeros) 0
where nonZeros = filter (/= 0) xs
Now consider 2D matrices, we want to “gravitize” the matrix so that every non-zero element in it falls to {left,right,up,down}-most possible position while preserving the order.
data Dir = DU | DD | DL | DR deriving (Eq, Ord, Enum, Show, Bounded)
gravitizeMat :: Dir -> [[Int]] -> [[Int]]
gravitizeMat dir = borrow invertible (map compactLeft)
where mirrorI = selfInv (map reverse)
diagonalI = selfInv transpose
invertible = case dir of
DL -> rempty
DR -> mirrorI
DU -> diagonalI
DD -> diagonalI `rappend` mirrorI
here Invertible comes into play by the observation that transpose and map reverse are all invertible (moreover, they are inverse functions of themselves).
So that we can transform matrices and pretend the problem is only “gravitize to the left”.
Here is one example:
print2DMat :: (Show a) => [[a]] -> IO ()
print2DMat mat = do
putStrLn "Matrix: ["
mapM_ print mat
putStrLn "]"
exampleMatGravitize :: IO ()
exampleMatGravitize = do
let mat = [ [1,0,2,0]
, [0,3,4,0]
, [0,0,0,5]
]
print2DMat mat
let showExample d = do
putStrLn $ "Direction: " ++ show d
print2DMat $ gravitizeMat d mat
mapM_ showExample [minBound .. maxBound]
And the result will be:
Matrix: [
[1,0,2,0]
[0,3,4,0]
[0,0,0,5]
]
Direction: DU
Matrix: [
[1,3,2,5]
[0,0,4,0]
[0,0,0,0]
]
Direction: DD
Matrix: [
[0,0,0,0]
[0,0,2,0]
[1,3,4,5]
]
Direction: DL
Matrix: [
[1,2,0,0]
[3,4,0,0]
[5,0,0,0]
]
Direction: DR
Matrix: [
[0,0,1,2]
[0,0,3,4]
[0,0,0,5]
]
Complete code
Since code review’s policy requires complete code (you can also find it from my gist):
{-# LANGUAGE DeriveFunctor #-}
import Data.Char
import Data.Function
import Data.List
data Invertible a b = Invertible
{ into :: a -> b
, back :: b -> a
}
selfInv :: (a -> a) -> Invertible a a
selfInv f = Invertible f f
rempty :: Invertible a a
rempty = selfInv id
rappend :: Invertible a b
-> Invertible b c
-> Invertible a c
(Invertible f1 g1) `rappend` (Invertible f2 g2) =
Invertible (f2 . f1) (g1 . g2)
flipInv :: Invertible a b -> Invertible b a
flipInv (Invertible f g) = Invertible g f
borrow :: Invertible a b -> (b -> b) -> a -> a
borrow (Invertible fIn fOut) g = fOut . g . fIn
liftInv :: (Functor f) => Invertible a b -> Invertible (f a) (f b)
liftInv (Invertible a b) = Invertible (fmap a) (fmap b)
-- examples
-- constructor should be invisible from outside
newtype OnlyUpper a = OnlyUpper
{ getOU :: [a]
} deriving (Eq, Ord, Show, Functor)
ouAsList :: Invertible (OnlyUpper a) [a]
ouAsList = Invertible getOU OnlyUpper
onlyUpper :: String -> OnlyUpper Char
onlyUpper = OnlyUpper . filter isAsciiUpper
upperAsOrd :: Invertible Char Int
upperAsOrd = Invertible ord' chr'
where
ord' x = ord x - ord 'A'
chr' x = chr (x + ord 'A')
modShift :: Int -> Int -> Invertible Int Int
modShift base offset = Invertible f g
where
f x = (x + offset) `mod` base
g y = (y + (base - offset)) `mod` base
caesarShift :: Invertible Int Int
caesarShift = modShift 26 4
caesarCipher :: Invertible (OnlyUpper Char) (OnlyUpper Char)
caesarCipher = liftInv (upperAsOrd
-- Char <-> Int
`rappend` caesarShift
-- Int <-> Int
`rappend` flipInv upperAsOrd)
-- Int <-> Char
exampleCaesar :: IO ()
exampleCaesar = do
let encF = into caesarCipher
decF = back caesarCipher
encrypted = encF (onlyUpper "THEQUICKBROWNFOX")
decrypted = decF encrypted
encrypted' = borrow (flipInv caesarCipher
`rappend` ouAsList) (++ "JUMPSOVERTHELAZYDOG") encrypted
decrypted' = decF encrypted'
print encrypted
-- OnlyUpper {getOU = "XLIUYMGOFVSARJSB"}
print decrypted
-- OnlyUpper {getOU = "THEQUICKBROWNFOX"}
print encrypted'
-- OnlyUpper {getOU = "XLIUYMGOFVSARJSBNYQTWSZIVXLIPEDCHSK"}
print decrypted'
-- OnlyUpper {getOU = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG"}
-- gravitize
compactLeft :: [Int] -> [Int]
compactLeft xs = nonZeros ++ replicate (((-) `on` length) xs nonZeros) 0
where nonZeros = filter (/= 0) xs
data Dir = DU | DD | DL | DR deriving (Eq, Ord, Enum, Show, Bounded)
gravitizeMat :: Dir -> [[Int]] -> [[Int]]
gravitizeMat dir = borrow invertible (map compactLeft)
where mirrorI = selfInv (map reverse)
diagonalI = selfInv transpose
invertible = case dir of
DL -> rempty
DR -> mirrorI
DU -> diagonalI
DD -> diagonalI `rappend` mirrorI
print2DMat :: (Show a) => [[a]] -> IO ()
print2DMat mat = do
putStrLn "Matrix: ["
mapM_ print mat
putStrLn "]"
exampleMatGravitize :: IO ()
exampleMatGravitize = do
let mat = [ [1,0,2,0]
, [0,3,4,0]
, [0,0,0,5]
]
print2DMat mat
let showExample d = do
putStrLn $ "Direction: " ++ show d
print2DMat $ gravitizeMat d mat
mapM_ showExample [minBound .. maxBound]
main :: IO ()
main = do
exampleCaesar
exampleMatGravitize
Solution
Naming:
There are a lot of names I’d change. Some of them matter more than others (local names in a let are not that big a deal even if they’re terrible, but a name for a widely used function should be suggestive, if possible). Some of them I’m more sure of than others.
I’d change borrow to within. The old name isn’t bad, but I think the new one is suggestive in the right way. I’d change Invertible to Transform, since an invertible function is just the one function, and we’re talking about a pair of related functions. Bijection is the mathematical name for it, and it would make a good name too, but it seems (to me at least) to suggest that the domain and range are the entire input and output types, and not every function we’d want to use with this fits that.
I’d change the local invertible to transform to match, so borrow invertible (map compactLeft) becomes within transform (map compactLeft).
I’d change mirrorI -> mirror and diagonalI -> diagonal; the I doesn’t add anything, it just looks as if you’re using roman numerals at first. I’d also change DD, DL, DR, DU -> DOWN, LEFT, RIGHT, UP, as it’s just clearer.
The Inv suffix doesn’t help. Not all of the functions have it, and it isn’t spelled out enough to be suggestive. Also, if we change it from Invertible, it no longer makes sense. So, selfInv -> involution, liftInv -> lift, flipInv -> backwards. An involution is the mathematical name for a function that is its own inverse (and if you didn’t know that, don’t feel bad, I was only guessing there might be a name for it until I googled it). flip is already taken, and I think backwards is more suggestive (reverse would have been nice too, but it’s also taken). lift isn’t taken as far as I know, but it’s the sort of thing that seems like it might be. If so, liftT or liftTr might work (or liftB if we’re using Bijection).
I’d change fIn, fOut -> f, f'. Using f' doesn’t quite say “I’m an inverse”, but it suggests it somewhat if we know how Transform is defined/meant to be used.
I can see why you named rempty and rappend as you did, but the names made me (and would probably make other people) want to try to make it a Monoid instance, and that doesn’t work. I’d change rempty -> idT, rappend -> >>>. >>> matches the Category class, and is nicely intuitive (and doesn’t need backquotes). I’m not really sure about idT, and it could probably be improved, but it still seems a bit nicer than rempty to me.
I’d also change into, back -> fwd, rev, but I don’t have much justification here. It seems a little more suggestive of a thing that can go both ways, instead of a box that you can go into and come out of, but can’t be flipped inside out. The original names here are good.
All Namechanges in One Spot:
DD, DL, DR, DU -> DOWN, LEFT, RIGHT, UP
Invertible -> Transform
invertible -> transform
mirrorI -> mirror
diagonalI -> diagonal
selfInv -> involution
liftInv -> lift
flipInv -> backwards
into, back -> fwd, rev
fIn, fOut -> f, f’
rempty -> idT
rappend -> >>>
Instances that don’t work:
Monad, Applicative, and Functor don’t work because fmap :: (a -> b) -> f a -> f b and that doesn’t fit.
Monoid doesn’t work because mappend :: a -> a -> a, and our composition takes 2 different types and returns yet another different type.
Arrow seems like it should work at first, but arr :: (b -> c) -> a b c. The types match nicely, but we’d need a way that makes sense to take an arbitrary function and find its inverse. Functions and Arrows go one way, but we want to go both ways.
Category fits perfectly, but when I tried to get it to work, the compiler complained about all the uses of . in the program being ambiguous. There may be a way to make it work, but looking at Control.Category, the gains were almost nonexistent, so I abandoned the attempt. The interface (>>> and <<< for forward and backward composition), was nice, though, so I kept it.
Instances that do work:
None?
Non-Naming Changes:
The suggestion in the comments by mjolka is correct, and the resulting code:
modShift base offset = Transform f g
where
f x = (x + offset) `mod` base
g y = (y - offset) `mod` base
looks nicer and is clearer.
This:
compactLeft xs = nonZeros ++ replicate (((-) `on` length) xs nonZeros) 0
where nonZeros = filter (/= 0) xs
is a bit ugly, and can be simplified to this:
compactLeft xs = take (length xs) $ nonZeros ++ repeat 0
where nonZeros = filter (/= 0) xs
I’d introduce a new function that abstracts the pattern in the parentheses in
caesarCipher = liftInv (upperAsOrd
-- Char <-> Int
`rappend` caesarShift
-- Int <-> Int
`rappend` flipInv upperAsOrd)
-- Int <-> Char
making my suggested namechanges, it becomes:
caesarCipher = lift (upperAsOrd >>> caesarShift >>> backwards upperAsOrd)
and the new function I’d suggest is:
nest :: Transform a b -> Transform b b -> Transform a a
nest ab bb = backwards ab <<< bb <<< ab
The reason I’m using <<< is that it composes in the same order as ., and this way, the nest function looks very similar to within (the function formerly known as borrow), which its type signature strongly resembles.
Here they (both) are, with type signatures:
within :: Transform a b -> (b -> b) -> a -> a
within (Transform f f') g = f' . g . f
nest :: Transform a b -> Transform b b -> Transform a a
nest ab bb = backwards ab <<< bb <<< ab
I can’t be sure, based on only one example, that this will end up commonly used, but it would make some sense if it did, based on the fact that it showed up once in a small set of examples and on the type signature resemblance. Also, nest may not be the best possible name, but it seems reasonable to me, and I haven’t been able to think of a better one.
Using nest, we can rewrite caesarCipher to be even shorter:
caesarCipher = lift $ nest upperAsOrd caesarShift
We also used $ to avoid having to wrap parentheses around the nest.
gravitizeMat doesn’t change, except for namechanges, but it is more readable.
Before:
data Dir = DU | DD | DL | DR deriving (Eq, Ord, Enum, Show, Bounded)
gravitizeMat :: Dir -> [[Int]] -> [[Int]]
gravitizeMat dir = borrow invertible (map compactLeft)
where mirrorI = selfInv (map reverse)
diagonalI = selfInv transpose
invertible = case dir of
DL -> rempty
DR -> mirrorI
DU -> diagonalI
DD -> diagonalI `rappend` mirrorI
After:
data Dir = UP | DOWN | LEFT | RIGHT deriving (Eq, Ord, Enum, Show, Bounded)
gravitizeMat :: Dir -> [[Int]] -> [[Int]]
gravitizeMat dir = within transform (map compactLeft)
where mirror = involution (map reverse)
diagonal = involution transpose
transform = case dir of
LEFT -> idT
RIGHT -> mirror
UP -> diagonal
DOWN -> diagonal >>> mirror
exampleCaesar doesn’t change much, but this part looks nicer.
Before:
encrypted' = borrow (flipInv caesarCipher
`rappend` ouAsList) (++ "JUMPSOVERTHELAZYDOG") encrypted
After:
encrypted' = within (backwards caesarCipher >>> ouAsList)
(++ "JUMPSOVERTHELAZYDOG") encrypted
Here I think the suggestion for backwards really shines, since the forward direction of caesarCipher is encryption and the reverse direction is decryption, but here, we’re trying to mess with the plaintext of an encryptedtext, which is using it backwards.
Overall:
It was nice code. There were several names that could be made more suggestive, and a couple of places where complex expressions could be simplified, but overall, it was pleasant to read, and an interesting idea as well.
Complete Modified Code:
{-# LANGUAGE DeriveFunctor #-}
import Data.Char
import Data.Function
import Data.List
data Transform a b = Transform
{ fwd :: a -> b
, rev :: b -> a
}
involution :: (a -> a) -> Transform a a
involution f = Transform f f
idT :: Transform a a
idT = involution id
(>>>) :: Transform a b -> Transform b c -> Transform a c
(Transform f1 g1) >>> (Transform f2 g2) =
Transform (f2 . f1) (g1 . g2)
(<<<) :: Transform b c -> Transform a b -> Transform a c
f <<< g = g >>> f
backwards :: Transform a b -> Transform b a
backwards (Transform f g) = Transform g f
within :: Transform a b -> (b -> b) -> a -> a
within (Transform f f') g = f' . g . f
nest :: Transform a b -> Transform b b -> Transform a a
nest ab bb = backwards ab <<< bb <<< ab
lift :: (Functor f) => Transform a b -> Transform (f a) (f b)
lift (Transform f g) = Transform (fmap f) (fmap g)
-- examples
-- constructor should be invisible from outside
newtype OnlyUpper a = OnlyUpper
{ getOU :: [a]
} deriving (Eq, Ord, Show, Functor)
ouAsList :: Transform (OnlyUpper a) [a]
ouAsList = Transform getOU OnlyUpper
onlyUpper :: String -> OnlyUpper Char
onlyUpper = OnlyUpper . filter isAsciiUpper
upperAsOrd :: Transform Char Int
upperAsOrd = Transform ord' chr'
where
ord' x = ord x - ord 'A'
chr' x = chr (x + ord 'A')
modShift :: Int -> Int -> Transform Int Int
modShift base offset = Transform f g
where
f x = (x + offset) `mod` base
g y = (y - offset) `mod` base
caesarShift :: Transform Int Int
caesarShift = modShift 26 4
caesarCipher :: Transform (OnlyUpper Char) (OnlyUpper Char)
caesarCipher = lift $ nest upperAsOrd caesarShift
exampleCaesar :: IO ()
exampleCaesar = do
let encF = fwd caesarCipher
decF = rev caesarCipher
encrypted = encF (onlyUpper "THEQUICKBROWNFOX")
decrypted = decF encrypted
encrypted' = within (backwards caesarCipher >>> ouAsList)
(++ "JUMPSOVERTHELAZYDOG") encrypted
decrypted' = decF encrypted'
print encrypted
-- OnlyUpper {getOU = "XLIUYMGOFVSARJSB"}
print decrypted
-- OnlyUpper {getOU = "THEQUICKBROWNFOX"}
print encrypted'
-- OnlyUpper {getOU = "XLIUYMGOFVSARJSBNYQTWSZIVXLIPEDCHSK"}
print decrypted'
-- OnlyUpper {getOU = "THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG"}
-- gravitize
compactLeft :: [Int] -> [Int]
compactLeft xs = take (length xs) $ nonZeros ++ repeat 0
where nonZeros = filter (/= 0) xs
data Dir = UP | DOWN | LEFT | RIGHT deriving (Eq, Ord, Enum, Show, Bounded)
gravitizeMat :: Dir -> [[Int]] -> [[Int]]
gravitizeMat dir = within transform (map compactLeft)
where mirror = involution (map reverse)
diagonal = involution transpose
transform = case dir of
LEFT -> idT
RIGHT -> mirror
UP -> diagonal
DOWN -> diagonal >>> mirror
print2DMat :: (Show a) => [[a]] -> IO ()
print2DMat mat = do
putStrLn "Matrix: ["
mapM_ print mat
putStrLn "]"
exampleMatGravitize :: IO ()
exampleMatGravitize = do
let mat = [ [1,0,2,0]
, [0,3,4,0]
, [0,0,0,5]
]
print2DMat mat
let showExample d = do
putStrLn $ "Direction: " ++ show d
print2DMat $ gravitizeMat d mat
mapM_ showExample [minBound .. maxBound]
main :: IO ()
main = do
exampleCaesar
exampleMatGravitize