f :: a -> b类型的值。此外，如果存在g :: b -> a和h :: b -> b是彼此相反的另一对函数，则h和a实际上可以组成f'和可逆仍然成立。以下是我在Haskell中实现此目的的尝试，我想知道现有的图书馆是否可以为我做同样的事情（甚至更一般的事情）。
还要感谢有关我的代码的建议和注释。
实现
首先，我使用记录存储两个函数：
data Invertible a b = Invertible
{ into :: a -> b
, back :: b -> a
}
g'的意思是“将a转换为b”，而(f,g)的意思是“将b转换为a”。然后很少有辅助函数ons：
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)
在上面的代码中，
(f',g')将使用一对函数使其最后一个参数(f' . f, g . g') 可用于类型
into的值。将back更改为borrow将使g可用于类型a的值。因此，如果可以将borrow f和borrow (flipInv f)相互转换，则g捕捉了我最初的想法，即使b类型的函数可用于borrow的值。 b -> b和a暗示了它和a之间的相似之处： 。数据加密
在对称加密的情况下自然可以使用
b。如果满足以下条件，则Invertible可能是一个实例：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)
为了简单起见，我以一个Caesar密码为例，并假设纯文本仅包含大写字母：
encrypt :: Key -> PlainText -> CipherText
decrypt :: Key -> CipherText -> PlainText
Caesar Cipher基本上是在做一些模块化算术：
-- 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')
一种使用
rappend的方法是将rempty和Monoid用作Invertible和Invertible，并且Invertible (encrypt key) (decrypt key)还为您提供了处理加密数据的能力，就像纯文本一样：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
矩阵操作
有时编写一些使用
Invertible操纵矩阵的代码很方便。有一个类型为into的列表，其中back代表一个空单元格，并且我们希望每个非零元素在保留顺序的同时都移到其最左侧可能的位置：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"}
现在考虑2D矩阵，我们想“引力”化矩阵，以使矩阵中的每个非零元素都在{
compactLeft :: [Int] -> [Int]
compactLeft xs = nonZeros ++ replicate (((-) `on` length) xs nonZeros) 0
where nonZeros = filter (/= 0) xs
encrypt在这里起作用，因为观察到decrypt和Invertible都是可逆的（此外，它们本身是逆函数）。 >以便我们可以变换矩阵并假装问题只是“向左重力”。这里是一个示例：结果将是：
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]
#1 楼
命名：我要更改很多名称。它们中的一些比其他更重要（即使很糟糕，let中的本地名称也没什么大不了的，但是，如果可能的话，广泛使用的功能的名称应该是暗示性的）。我有些人比其他人更确定。
我会将
borrow更改为within。旧名称还不错，但是我认为新名称以正确的方式暗示着。我将Invertible更改为Transform，因为可逆函数只是一个函数，而我们正在谈论一对相关的函数。 Bijection是它的数学名称，它也将成为一个好名字，但是（至少在我看来）建议域和范围是整个输入和输出类型，而不是我们想要的每个函数将本地
invertible更改为transform以匹配，因此borrow invertible (map compactLeft)变为within transform (map compactLeft)。我没有添加任何内容，只是看起来好像您刚开始使用罗马数字一样。我还要更改mirrorI，因为它更清楚了。mirror后缀没有帮助。并非所有功能都具有此功能，并且其拼写方式不足以具有暗示性。另外，如果我们从diagonalI对其进行更改，则不再有意义。因此，diagonal-> DD, DL, DR, DU -> DOWN, LEFT, RIGHT, UP，Inv-> Invertible，selfInv-> involution。 liftInv是一个函数的数学名称，该函数本身就是反函数（如果您不知道，就不会感到难过，我只是猜测可能会有一个名称，直到我用谷歌搜索为止）。 lift已经被采用，我认为flipInv更具启发性（backwards也可以，但也已采用）。据我所知，involution尚不完善，但这似乎是一种事情。如果是这样，flip或backwards可能会起作用（如果使用reverse，则可能会起作用）。我将更改
lift，liftT-> liftTr，liftB。使用Bijection并不能完全说“我是个逆子”，但是如果我们知道如何定义/使用fIn，就可以使用它。但是这些名称使我（并且可能会使其他人）想尝试使其成为Monoid实例，但这不起作用。我将更改fOut-> f，f'-> f'。 Transform与rempty类匹配，并且非常直观（并且不需要反引号）。我不太确定rappend，它可能会得到改善，但对我来说似乎仍然比rempty好。这里没有太多理由。似乎可以暗示一种东西可以双向传播，而不是一个盒子可以进出但不能翻转而出的盒子。这里的原始名称很好。一处进行所有名称更改：
DD，DL，DR，DU-> DOWN，LEFT，RIGHT，UP
可逆->变换
可逆->变换
mirrorI->镜子
diagonalI->对角线
selfInv->对合>进入，返回-> fwd，rev
fIn，fOut-> f，f'
idT
rappend-> >>>
不起作用：
，Monad，Applicative和Functor不起作用，因为
idT不合适。Monoid不起作用，因为
rappend，我们的合成有2种不同类型并返回另一种不同的类型。箭头似乎应该首先起作用，但是
>>>。这些类型匹配得很好，但是我们需要一种有意义的方法来采用任意函数并找到其逆函数。函数和箭头是一种方式，但我们希望两者都是。类别非常适合，但是当我尝试使其工作时，编译器抱怨该程序中对
>>>的所有使用都模棱两可。也许有一种方法可以使它起作用，但从Control.Category来看，收益几乎是不存在的，因此我放弃了这一尝试。接口（Category和idT用于向前和向后合成）很好，所以我保留了它。有效的实例：
没有？
非命名更改：
mjolka的注释中的建议是正确的，并且生成的代码：
modShift base offset = Transform f g
where
f x = (x + offset) `mod` base
g y = (y - offset) `mod` base
看起来更好更清晰。 ，可以简化为：
compactLeft xs = nonZeros ++ replicate (((-) `on` length) xs nonZeros) 0
where nonZeros = filter (/= 0) xs
我将引入一个新函数，该函数在
compactLeft xs = take (length xs) $ nonZeros ++ repeat 0
where nonZeros = filter (/= 0) xs
的括号中抽象出图案，从而使我建议的名称更改为： br />
caesarCipher = liftInv (upperAsOrd
-- Char <-> Int
`rappend` caesarShift
-- Int <-> Int
`rappend` flipInv upperAsOrd)
-- Int <-> Char
和我建议的新功能是：
caesarCipher = lift (upperAsOrd >>> caesarShift >>> backwards upperAsOrd)
我使用
rempty的原因是它的构成顺序与into相同，因此back函数看起来与fwd（以前称为rev的函数）非常相似，它的类型签名非常相似。可以肯定，仅基于一个示例例如，le最终将被普遍使用，但是如果这样做的话，这将是有道理的，这是基于事实，即它仅在少量示例中出现一次并且与类型签名相似。另外，fmap :: (a -> b) -> f a -> f b可能不是最好的名字，但对我来说似乎很合理，我一直想不到更好的名称。使用
mappend :: a -> a -> a，我们可以将arr :: (b -> c) -> a b c改写得更短： /> nest :: Transform a b -> Transform b b -> Transform a a
nest ab bb = backwards ab <<< bb <<< ab
我们还使用了
.以避免必须在>>>周围加上括号。<<<不变，除了名称更改外，但它更易读。之前：
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
之后：
caesarCipher = lift $ nest upperAsOrd caesarShift
<<<变化不大，但是这部分看起来更好。之前：
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
之后：
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
在这里，我认为对
.的建议确实很不错，因为nest的正向是加密而反向是解密，但是这里我们正试图弄乱加密文本的纯文本，该纯文本被反向使用。总体：
这是不错的代码。有几个名称可能会更具有启发性，在几个地方可以简化复杂的表达式，但总的来说，它使人读起来很愉快，而且也很有趣。 >
encrypted' = borrow (flipInv caesarCipher
`rappend` ouAsList) (++ "JUMPSOVERTHELAZYDOG") encrypted
评论
我绝不声称它们在理论上适合这里，但是以某种方式，我怀疑通过使用透镜同构，您可能能够抽象出您在此处尝试做的很多事情。为空并从Category实例追加。
hackage.haskell.org/package/TypeCompose-0.6.4/docs/…
要点的第4修订版说明了根据@DannyNavarro的建议使用的镜头同构。我建议将其发布为答案。结合原始代码，两者都显示了使用一对可逆函数的好方法。您的原始代码很不错，因为它是独立的，然后，镜头代码更容易理解。
不足以给出答案，但在modShift中，可以将g简化为g y =（y-offset）`mod` base。